ElGamal Encryption and Related Zero-Knowledge Proofs

Documentation:

Implementation of ElGamal encryption and related zero-knowledge proofs with pluggable crypto backend.

The following protocols and high-level applications are included:

• Additively homomorphic ElGamal encryption
• Zero-knowledge proofs of zero encryption and Boolean value encryption
• Zero-knowledge range proofs for ElGamal ciphertexts
• Zero-knowledge proof of equivalence between an ElGamal ciphertext and a Pedersen commitment in the same group
• Additively homomorphic m-of-n choice encryption with a zero-knowledge proof of correctness
• Additively homomorphic quadratic voting with a zero-knowledge proof of correctness
• Threshold ElGamal encryption via Feldman's verifiable secret sharing, including verifiable distributed decryption.
• As an alternative method to generate a shared key for threshold encryption, there is Pedersen's distributed key generation with prior key commitments by participants. (Beware that this method can theoretically lead to skewed public key distribution as shown by Gennaro et al.)

⚠ Warnings

While the logic in this crate relies on standard cryptographic assumptions (complexity of decisional Diffie–Hellman, computational Diffie–Hellman and discrete log problems in certain groups), it has not been independently verified for correctness or absence of side-channel attack vectors. Use at your own risk.

ElGamal encryption is not a good choice for general-purpose public-key encryption since it is vulnerable to chosen-ciphertext attacks. For security, decryption operations should be limited on the application level.

Usage

Add this to your Crate.toml:

[dependencies]
elastic-elgamal = "0.3.0"

Single-choice polling

use elastic_elgamal::app::{ChoiceParams, EncryptedChoice};
use elastic_elgamal::{group::Ristretto, DiscreteLogTable, Keypair};
use rand::thread_rng;

let mut rng = thread_rng();
// Generate a keypair for encrypting ballots. In more realistic setup,
// this keypair would be distributed among multiple talliers.
let (pk, sk) = Keypair::<Ristretto>::generate(&mut rng).into_tuple();
let choice_params = ChoiceParams::single(pk, 5);
// ^ single-choice polling with 5 options encrypted for `pk`

let choice = 2; // voter's choice
let enc = EncryptedChoice::single(&choice_params, choice, &mut rng);
let choices = enc.verify(&choice_params).unwrap();
// ^ 5 Boolean value ciphertexts that can be homomorphically added
// across ballots

// Decrypt a separate ballot for demo purposes.
let lookup_table = DiscreteLogTable::new(0..=1);
for (idx, &v) in choices.iter().enumerate() {
    assert_eq!(
        sk.decrypt(v, &lookup_table),
        Some((idx == choice) as u64)
    );
}

Quadratic voting

use elastic_elgamal::app::{QuadraticVotingParams, QuadraticVotingBallot};
use elastic_elgamal::{group::Ristretto, Keypair, DiscreteLogTable};
use rand::thread_rng;

let mut rng = thread_rng();
let (pk, sk) = Keypair::<Ristretto>::generate(&mut rng).into_tuple();
let params = QuadraticVotingParams::new(pk, 5, 20);
// ^ 5 options, 20 credits (= 4 max votes per option)
assert_eq!(params.max_votes(), 4);

let votes = [4, 0, 0, 1, 1]; // voter's votes
let ballot = QuadraticVotingBallot::new(&params, &votes, &mut rng);
let encrypted = ballot.verify(&params).unwrap();
// ^ 5 vote ciphertexts that can be homomorphically added across ballots

// Decrypt a separate ballot for demo purposes.
let lookup = DiscreteLogTable::new(0..=params.max_votes());
let decrypted: Vec<_> = encrypted
    .map(|vote| sk.decrypt(vote, &lookup).unwrap())
    .collect();
assert_eq!(decrypted, votes);

See the crate docs for more examples of usage.

Naming

"Elastic" refers to pluggable backends, encryption with a key shared among a variable number of participants, and the construction of zero-knowledge ring proofs (a proof consists of a variable number of rings, each of which consists of a variable number of admissible values). elastic_elgamal is also one of autogenerated Docker container names.

Alternatives and similar tools

There are several Rust crates implementing ElGamal encryption on elliptic curves, such as elgamal_ristretto (this one features zero-knowledge proofs of correct decryption and knowledge of the secret key).

As mentioned in the Warnings section, ElGamal is not a good choice for general-purpose public-key encryption. RSA or ECIES schemes (such as the box primitive from NaCl / libsodium) can be used instead.

See also

• elasticpoll.app – an open-source web app that uses this library to implement universally verifiable voting. (Like this library, the website is not audited and should not be used for serious votes.)

Contributing

All contributions are welcome! See the contributing guide to help you get involved.

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in elastic-elgamal by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.