Module elastic_elgamal::sharing
source · Expand description
Feldman’s verifiable secret sharing (VSS) for ElGamal encryption.
Feldman’s VSS is an extension of Shamir’s secret sharing that provides a degree
of verifiability for the scheme participants and the public. As with other VSS schemes,
the goal is to securely distribute a secret among n
participants so that the secret can
be recombined by any t
(but not less) of these participants. Unlike distributed key
generation (DKG), VSS assumes a central authority (a dealer) generating the secret
and distributing its shares among participants.
§Construction
Inputs:
- Total number of participants
n
- Minimum number of participants necessary to restore secret
t
- Prime-order group with discrete log assumption with generator
G
Assumptions:
- There is a secure broadcast among participants, which acts as a single source of truth (e.g., a blockchain). The broadcast is synchronous w.r.t. the protocol steps (in practice, this means that protocol steps take sufficiently long amount of time).
- Secure synchronous P2P channels can be established between the dealer and participants.
- The adversary is static (corrupts parties before protocol instantiation) and can corrupt less than a half of participants (including the dealer).
Feldman’s VSS proceeds as follows:
- The dealer generates a secret
x
(a scalar in a group with discrete log assumption). Along with this scalar, the dealer generatest
other scalars that are also kept secret. These scalars form a secret polynomial of degreet
:P(z) = x + x_1 * z + x_2 * z^2 + …
. - The dealer publishes coefficients
[x]G
,[x_1]G
, …,[x_t]G
of the public polynomial corresponding toP
:Q(z) = [x]G + [z][x_1]G + [z^2][x_2]G + …
. Here,[x]G
is the shared public key, and valuesQ(i)
ati = 1..=n
are public key shares of participants. - The dealer distributes secret key shares
s_i = P(i)
among participantsi = 1..=n
via secure P2P channels. Each participant can verify share validity by calculating[s_i]G ?= Q(i)
.
If a participant receives an incorrect secret share, the participant broadcasts a complaint against the dealer. The dealer responds by broadcasting the participant’s share. Either the share is correct (in which case the complaining participant is at fault), or it is not (in which case the dealer is at fault).
To improve auditability, the implemented version of VSS provides zero-knowledge proofs of possession both for the dealer and participants. The dealer must broadcast the public polynomial together with the proof; participants should broadcast proof of knowledge of a secret share once they receive the share from the dealer.
§Distributed key generation
Distributed key generation (DKG) differs from the approach implemented in this module
in that there is no centralized dealer trusted by all participants. Instead, the participants
essentially run parallel secret sharing protocol instances where each participant
is a dealer in one of the instances. This approach is implemented
in the dkg
module of this crate. Beware that it may not protect
from participants biasing the distribution of the shared public key, e.g. by aborting
the protocol; see Gennaro et al. for more details.
§Examples
Threshold encryption scheme requiring 2 of 3 participants.
let mut rng = thread_rng();
let params = Params::new(3, 2);
// Initialize the dealer.
let dealer = Dealer::<Ristretto>::new(params, &mut rng);
let (public_poly, poly_proof) = dealer.public_info();
let key_set = PublicKeySet::new(params, public_poly, poly_proof)?;
// Initialize participants based on secret shares provided by the dealer.
let participants = (0..3)
.map(|i| ActiveParticipant::new(
key_set.clone(),
i,
dealer.secret_share_for_participant(i),
))
.collect::<Result<Vec<_>, _>>()?;
// At last, participants can decrypt messages!
let encrypted_value = 5_u64;
let enc = key_set.shared_key().encrypt(encrypted_value, &mut rng);
let shares_with_proofs = participants
.iter()
.map(|p| p.decrypt_share(enc, &mut rng))
.take(2); // emulate the 3rd participant dropping off
// Emulate share transfer via untrusted network.
let dec_shares = shares_with_proofs
.enumerate()
.map(|(i, (share, proof))| {
let share = CandidateDecryption::from_bytes(&share.to_bytes()).unwrap();
key_set.verify_share(share, enc, i, &proof).unwrap()
});
// Combine decryption shares.
let combined = params.combine_shares(dec_shares.enumerate()).unwrap();
// Use a lookup table to decrypt back to scalar.
let lookup_table = DiscreteLogTable::<Ristretto>::new(0..10);
let dec = combined.decrypt(enc, &lookup_table);
assert_eq!(dec, Some(encrypted_value));
Structs§
- Personalized state of a participant of a threshold ElGamal encryption scheme once the participant receives the secret share from the
Dealer
. At this point, the participant can produceVerifiableDecryption
s. - Dealer in a Feldman verifiable secret sharing scheme.
- Parameters of a threshold ElGamal encryption scheme.
- Full public information about the participants of a threshold ElGamal encryption scheme after all participants’ commitments are collected.
Enums§
- Errors that can occur during the secret sharing protocol.