elastic_elgamal

Module 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:

  1. The dealer generates a secret x (a scalar in a group with discrete log assumption). Along with this scalar, the dealer generates t other scalars that are also kept secret. These scalars form a secret polynomial of degree t: P(z) = x + x_1 * z + x_2 * z^2 + ….
  2. The dealer publishes coefficients [x]G, [x_1]G, …, [x_t]G of the public polynomial corresponding to P: Q(z) = [x]G + [z][x_1]G + [z^2][x_2]G + …. Here, [x]G is the shared public key, and values Q(i) at i = 1..=n are public key shares of participants.
  3. The dealer distributes secret key shares s_i = P(i) among participants i = 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§

Enums§

  • Error
    Errors that can occur during the secret sharing protocol.