elgamal/
lib.rs

1//! # Elgamal Public Key Encryption
2//!
3//! This document represents an executable specification of the Elgamal Public Key Encryption scheme.
4//!
5//! At the basis of the encryption scheme is a prime order group $`\mathbb{G}`$ with the same interface as defined in [draft-oprf].
6#![warn(missing_docs)]
7
8use hacspec_lib::Randomness;
9use p256::{p256_point_mul, p256_point_mul_base, point_add, random_scalar, P256Point, P256Scalar};
10
11use std::ops::Neg;
12
13/// Domain separator for scalar sampling during key generation.
14const DST_KEYGEN: &[u8] = b"ElGamal-KeyGeneration";
15/// Domain separator for scalar sampling during encryption.
16const DST_ENCRYPT: &[u8] = b"ElGamal-Encryption";
17/// Domain separator for scalar sampling during ciphertext rerandomization.
18const DST_RERANDOMIZE: &[u8] = b"ElGamal-Rerandomize";
19
20/// An Elgamal encryption of a message `M` under public key `PK` is a pair of group elements `(c0, c1)` where
21/// * `c0` is the group generator multiplied by a randomizer `r`
22/// * `c1` is the result of multiplying the  target public encryption key the same randomizer `r` and adding the result to the message `M` that is to be encrypted.
23pub type Ciphertext = (P256Point, P256Point);
24
25/// An Elgamal plaintext is a member of the base group.
26pub type Plaintext = P256Point;
27
28#[derive(Debug)]
29/// Any of the given algorithms may fail if the given arguments result in invalid group operations.
30pub enum Error {
31    /// Wrapper around Errors given by the underlying group implementation.
32    CurveError,
33    /// Wrapper around rejection sampling Errors
34    SamplingError,
35}
36
37impl From<p256::Error> for Error {
38    fn from(_value: p256::Error) -> Self {
39        Self::CurveError
40    }
41}
42
43/// An Elgamal private decryption key is a scalar $`dk`$ of base group $`\mathcal{G}`$.
44pub type DecryptionKey = P256Scalar;
45/// An Elgamal encryption key is a group element in $`\mathcal{G}$.
46pub type EncryptionKey = P256Point;
47
48/// To generate a pair of encryption and decryption keys, first the decryption key is drawn uniformly at random from the set of scalars.
49/// Then the corresponding encryption key is generated by scalar multiplication of the group generator with the decryption key.
50pub fn generate_keys(randomness: &mut Randomness) -> Result<(DecryptionKey, EncryptionKey), Error> {
51    let dec_key = random_scalar(randomness, DST_KEYGEN)?;
52    let enc_key = p256_point_mul_base(dec_key)?;
53
54    Ok((dec_key, enc_key))
55}
56
57/// To encrypt a `message` (a group element) under encryption key `ek`, the encryption key randomized by scalar muliplication with `randomizer`. The result is used as a blinding element by adding it to the message using the group operation.
58/// To allow for decryption, the ciphertext also includes as an auxillary component the result of scalar multiplication of the generator by the `randomizer` that was used in the blinding.
59///
60
61pub fn encrypt(
62    enc_key: P256Point,
63    message: Plaintext,
64    randomness: &mut Randomness,
65) -> Result<Ciphertext, Error> {
66    let randomizer = random_scalar(randomness, DST_ENCRYPT)?;
67
68    let blinded_message = p256::point_add(message, p256::p256_point_mul(randomizer, enc_key)?)?;
69    let auxillary = p256::p256_point_mul_base(randomizer)?;
70    Ok((auxillary, blinded_message))
71}
72
73/// To decrypt an Elgamal ciphertext, the holder of the decryption key can multiply the auxillary component of the ciphertext by the decryption key, thus reproducing the blinding element that was calculated during encryption. Adding the negation of this blinding to the blinded message component of the ciphertext recovers the encrypted message.
74pub fn decrypt(dec_key: P256Scalar, ctx: Ciphertext) -> Result<Plaintext, Error> {
75    let blinding: P256Point = p256::p256_point_mul(dec_key, ctx.0)?;
76
77    p256::point_add(ctx.1, blinding.neg()).map_err(|e| e.into())
78}
79
80/// Given the correct public encryption key, it is possible to rerandomize Elgamal ciphertexts without changing the message that is encrypted.
81/// To do so, the encryption is multiplied by the fresh randomizer and the result is added to the blinded message component of the ciphertext.
82///
83/// The auxillary element of the ciphertext is similarly updated by adding the result of multiplying the generator by the fresh randomizer.
84pub fn rerandomize(
85    enc_key: P256Point,
86    ctx: Ciphertext,
87    randomness: &mut Randomness,
88) -> Result<Ciphertext, Error> {
89    let randomizer = random_scalar(randomness, DST_RERANDOMIZE)?;
90    let updated_blinding = p256_point_mul(randomizer, enc_key)?;
91    let updated_blinded_message = point_add(updated_blinding, ctx.1)?;
92
93    let updated_auxillary = point_add(p256_point_mul_base(randomizer)?, ctx.0)?;
94    Ok((updated_auxillary, updated_blinded_message))
95}
96
97/// Elgamal ciphertexts under the same encryption key enjoy an additive homomorphism,
98///  i.e. if `c1 = Enc(ek, m1)` and `c2 = Enc(pk, m2)`, then we can define an addition operation `+` such that
99/// `Dec(dk, c1 + c2) = m1 + m2`.
100///
101/// The addition is defined as componentwise application of the group operation on the pairs of group elements that make up ciphertexts.
102pub fn add_ciphertexts(lhs: Ciphertext, rhs: Ciphertext) -> Result<Ciphertext, Error> {
103    let sum_blinded_messages = p256::point_add(lhs.0, rhs.0)?;
104    let sum_auxillaries = p256::point_add(lhs.1, rhs.1)?;
105
106    Ok((sum_blinded_messages, sum_auxillaries))
107}
108
109/// Since addition as described above is defined via component-wise application of the group operation, repeated addition of a ciphertext with itself
110/// can be expressed via componentwise scalar multiplication of the ciphertext.
111pub fn scalar_mul_ciphertext(scalar: P256Scalar, ctx: Ciphertext) -> Result<Ciphertext, Error> {
112    let multiple_blinded_message = p256_point_mul(scalar, ctx.0)?;
113    let multiple_auxillary = p256_point_mul(scalar, ctx.1)?;
114
115    Ok((multiple_blinded_message, multiple_auxillary))
116}
117
118#[cfg(test)]
119mod test {
120    use super::*;
121    use p256::random_scalar;
122    use rand::RngCore;
123
124    #[test]
125    fn test_correctness() {
126        let msg = random_element().unwrap();
127        let mut uniform_bytes = vec![0u8; 32];
128        rand::thread_rng().fill_bytes(&mut uniform_bytes);
129        let mut uniform_bytes = Randomness::new(uniform_bytes);
130        let (dk, ek) = generate_keys(&mut uniform_bytes).unwrap();
131
132        let ctx = encrypt(ek, msg, &mut Randomness::new(vec![0xab; 32])).unwrap();
133        let decryption = decrypt(dk, ctx).unwrap();
134
135        debug_assert_eq!(msg, decryption);
136    }
137
138    #[test]
139    fn test_rerandomize() {
140        let msg = random_element().unwrap();
141
142        let mut uniform_bytes = vec![0u8; 32];
143        rand::thread_rng().fill_bytes(&mut uniform_bytes);
144        let mut uniform_bytes = Randomness::new(uniform_bytes);
145        let (dk, ek) = generate_keys(&mut uniform_bytes).unwrap();
146
147        let ctx = encrypt(ek, msg, &mut Randomness::new(vec![0xab; 32])).unwrap();
148        let rctx = rerandomize(ek, ctx, &mut Randomness::new(vec![0xab; 32])).unwrap();
149        let decryption = decrypt(dk, rctx).unwrap();
150
151        debug_assert_eq!(msg, decryption);
152        assert_ne!(ctx, rctx);
153    }
154
155    fn random_element() -> Result<P256Point, Error> {
156        let rand = random_scalar(&mut Randomness::new(vec![0xab; 32]), b"ElGamal-Test").unwrap();
157        let res = p256_point_mul_base(rand)?;
158
159        Ok(res)
160    }
161}
elgamal/lib.rs

elgamal/
lib.rs
