elastic_elgamal/
encryption.rs

1//! `Ciphertext` and closely related types.
2
3use rand_core::{CryptoRng, RngCore};
4#[cfg(feature = "serde")]
5use serde::{Deserialize, Serialize};
6use zeroize::{Zeroize, Zeroizing};
7
8use core::{fmt, marker::PhantomData, ops};
9
10#[cfg(feature = "serde")]
11use crate::serde::ElementHelper;
12use crate::{
13    alloc::{vec, HashMap, Vec},
14    group::{Group, ScalarOps},
15    PublicKey, SecretKey,
16};
17
18/// Ciphertext for ElGamal encryption.
19///
20/// A ciphertext consists of 2 group elements: the random element `R` and a blinded encrypted
21/// value `B`. If the ciphertext encrypts integer value `v`, it holds that
22///
23/// ```text
24/// R = [r]G;
25/// B = [v]G + [r]K = [v]G + [k]R;
26/// ```
27///
28/// where:
29///
30/// - `G` is the conventional group generator
31/// - `r` is a random scalar selected by the encrypting party
32/// - `K` and `k` are the recipient's public and private keys, respectively.
33///
34/// Ciphertexts are partially homomorphic: they can be added together or multiplied by a scalar
35/// value.
36///
37/// # Examples
38///
39/// Basic usage and arithmetic for ciphertexts:
40///
41/// ```
42/// # use elastic_elgamal::{group::Ristretto, DiscreteLogTable, Ciphertext, Keypair};
43/// # use rand::thread_rng;
44/// // Generate a keypair for the ciphertext receiver.
45/// let mut rng = thread_rng();
46/// let receiver = Keypair::<Ristretto>::generate(&mut rng);
47/// // Create a couple of ciphertexts.
48/// let mut enc = receiver.public().encrypt(2_u64, &mut rng);
49/// enc += receiver.public().encrypt(3_u64, &mut rng) * 4;
50/// // Check that the ciphertext decrypts to 2 + 3 * 4 = 14.
51/// let lookup_table = DiscreteLogTable::new(0..20);
52/// let decrypted = receiver.secret().decrypt(enc, &lookup_table);
53/// assert_eq!(decrypted, Some(14));
54/// ```
55///
56/// Creating a ciphertext of a boolean value together with a proof:
57///
58/// ```
59/// # use elastic_elgamal::{group::Ristretto, Ciphertext, Keypair};
60/// # use rand::thread_rng;
61/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
62/// // Generate a keypair for the ciphertext receiver.
63/// let mut rng = thread_rng();
64/// let receiver = Keypair::<Ristretto>::generate(&mut rng);
65/// // Create and verify a boolean encryption.
66/// let (enc, proof) =
67///     receiver.public().encrypt_bool(false, &mut rng);
68/// receiver.public().verify_bool(enc, &proof)?;
69/// # Ok(())
70/// # }
71/// ```
72///
73/// Creating a ciphertext of an integer value together with a range proof:
74///
75/// ```
76/// # use elastic_elgamal::{group::Ristretto, Keypair, RangeDecomposition};
77/// # use rand::thread_rng;
78/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
79/// // Generate the ciphertext receiver.
80/// let mut rng = thread_rng();
81/// let receiver = Keypair::<Ristretto>::generate(&mut rng);
82/// // Find the optimal range decomposition for our range
83/// // and specialize it for the Ristretto group.
84/// let range = RangeDecomposition::optimal(100).into();
85///
86/// let (ciphertext, proof) = receiver
87///     .public()
88///     .encrypt_range(&range, 42, &mut rng);
89///
90/// // Check that the the proof verifies.
91/// receiver.public().verify_range(&range, ciphertext, &proof)?;
92/// # Ok(())
93/// # }
94/// ```
95#[derive(Clone, Copy)]
96#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
97pub struct Ciphertext<G: Group> {
98    #[cfg_attr(feature = "serde", serde(with = "ElementHelper::<G>"))]
99    pub(crate) random_element: G::Element,
100    #[cfg_attr(feature = "serde", serde(with = "ElementHelper::<G>"))]
101    pub(crate) blinded_element: G::Element,
102}
103
104impl<G: Group> fmt::Debug for Ciphertext<G> {
105    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
106        formatter
107            .debug_struct("Ciphertext")
108            .field("random_element", &self.random_element)
109            .field("blinded_element", &self.blinded_element)
110            .finish()
111    }
112}
113
114impl<G: Group> Ciphertext<G> {
115    /// Represents encryption of zero value without the blinding factor.
116    pub fn zero() -> Self {
117        Self {
118            random_element: G::identity(),
119            blinded_element: G::identity(),
120        }
121    }
122
123    /// Creates a non-blinded encryption of the specified scalar `value`, i.e., `(O, [value]G)`
124    /// where `O` is identity and `G` is the conventional group generator.
125    pub fn non_blinded<T>(value: T) -> Self
126    where
127        G::Scalar: From<T>,
128    {
129        let scalar = Zeroizing::new(G::Scalar::from(value));
130        Self {
131            random_element: G::identity(),
132            blinded_element: G::mul_generator(&scalar),
133        }
134    }
135
136    /// Returns a reference to the random element.
137    pub fn random_element(&self) -> &G::Element {
138        &self.random_element
139    }
140
141    /// Returns a reference to the blinded element.
142    pub fn blinded_element(&self) -> &G::Element {
143        &self.blinded_element
144    }
145
146    /// Serializes this ciphertext as two group elements (the random element,
147    /// then the blinded value).
148    pub fn to_bytes(self) -> Vec<u8> {
149        let mut bytes = vec![0_u8; 2 * G::ELEMENT_SIZE];
150        G::serialize_element(&self.random_element, &mut bytes[..G::ELEMENT_SIZE]);
151        G::serialize_element(&self.blinded_element, &mut bytes[G::ELEMENT_SIZE..]);
152        bytes
153    }
154}
155
156impl<G: Group> ops::Add for Ciphertext<G> {
157    type Output = Self;
158
159    fn add(self, rhs: Self) -> Self {
160        Self {
161            random_element: self.random_element + rhs.random_element,
162            blinded_element: self.blinded_element + rhs.blinded_element,
163        }
164    }
165}
166
167impl<G: Group> ops::AddAssign for Ciphertext<G> {
168    fn add_assign(&mut self, rhs: Self) {
169        *self = *self + rhs;
170    }
171}
172
173impl<G: Group> ops::Sub for Ciphertext<G> {
174    type Output = Self;
175
176    fn sub(self, rhs: Self) -> Self {
177        Self {
178            random_element: self.random_element - rhs.random_element,
179            blinded_element: self.blinded_element - rhs.blinded_element,
180        }
181    }
182}
183
184impl<G: Group> ops::SubAssign for Ciphertext<G> {
185    fn sub_assign(&mut self, rhs: Self) {
186        *self = *self - rhs;
187    }
188}
189
190impl<G: Group> ops::Mul<&G::Scalar> for Ciphertext<G> {
191    type Output = Self;
192
193    fn mul(self, rhs: &G::Scalar) -> Self {
194        Self {
195            random_element: self.random_element * rhs,
196            blinded_element: self.blinded_element * rhs,
197        }
198    }
199}
200
201impl<G: Group> ops::Mul<u64> for Ciphertext<G> {
202    type Output = Self;
203
204    fn mul(self, rhs: u64) -> Self {
205        let scalar = G::Scalar::from(rhs);
206        self * &scalar
207    }
208}
209
210impl<G: Group> ops::Neg for Ciphertext<G> {
211    type Output = Self;
212
213    fn neg(self) -> Self::Output {
214        Self {
215            random_element: -self.random_element,
216            blinded_element: -self.blinded_element,
217        }
218    }
219}
220
221/// Lookup table for discrete logarithms.
222///
223/// For [`Ciphertext`]s to be partially homomorphic, the encrypted values must be
224/// group scalars linearly mapped to group elements: `x -> [x]G`, where `G` is the group
225/// generator. After decryption it is necessary to map the decrypted group element back to a scalar
226/// (i.e., get its discrete logarithm with base `G`). Because of discrete logarithm assumption,
227/// this task is computationally infeasible in the general case; however, if the possible range
228/// of encrypted values is small, it is possible to "cheat" by precomputing mapping `[x]G -> x`
229/// for all allowed `x` ahead of time. This is exactly what `DiscreteLogTable` does.
230///
231/// # Examples
232///
233/// ```
234/// # use elastic_elgamal::{group::Ristretto, DiscreteLogTable, Ciphertext, Keypair};
235/// # use rand::thread_rng;
236/// let mut rng = thread_rng();
237/// let receiver = Keypair::<Ristretto>::generate(&mut rng);
238/// let ciphertexts = (0_u64..16)
239///     .map(|i| receiver.public().encrypt(i, &mut rng));
240/// // Assume that we know that the plaintext is in range 0..16,
241/// // e.g., via a zero-knowledge proof.
242/// let lookup_table = DiscreteLogTable::new(0..16);
243/// // Then, we can use the lookup table to decrypt values.
244/// // A single table may be shared for multiple decryption operations
245/// // (i.e., it may be constructed ahead of time).
246/// for (i, enc) in ciphertexts.enumerate() {
247///     assert_eq!(
248///         receiver.secret().decrypt(enc, &lookup_table),
249///         Some(i as u64)
250///     );
251/// }
252/// ```
253#[derive(Debug, Clone)]
254pub struct DiscreteLogTable<G: Group> {
255    inner: HashMap<Vec<u8>, u64>,
256    _t: PhantomData<G>,
257}
258
259impl<G: Group> DiscreteLogTable<G> {
260    /// Creates a lookup table for the specified `values`.
261    pub fn new(values: impl IntoIterator<Item = u64>) -> Self {
262        let lookup_table = values
263            .into_iter()
264            .filter(|&value| value != 0)
265            .map(|i| {
266                let element = G::vartime_mul_generator(&G::Scalar::from(i));
267                let mut bytes = vec![0_u8; G::ELEMENT_SIZE];
268                G::serialize_element(&element, &mut bytes);
269                (bytes, i)
270            })
271            .collect();
272
273        Self {
274            inner: lookup_table,
275            _t: PhantomData,
276        }
277    }
278
279    /// Gets the discrete log of `decrypted_element`, or `None` if it is not present among `values`
280    /// stored in this table.
281    pub fn get(&self, decrypted_element: &G::Element) -> Option<u64> {
282        if G::is_identity(decrypted_element) {
283            // The identity element may have a special serialization (e.g., in SEC standard
284            // for elliptic curves), so we check it separately.
285            Some(0)
286        } else {
287            let mut bytes = vec![0_u8; G::ELEMENT_SIZE];
288            G::serialize_element(decrypted_element, &mut bytes);
289            self.inner.get(&bytes).copied()
290        }
291    }
292}
293
294/// [`Ciphertext`] together with the random scalar used to create it.
295#[derive(Debug, Clone)]
296#[doc(hidden)] // only public for benchmarking
297pub struct ExtendedCiphertext<G: Group> {
298    pub(crate) inner: Ciphertext<G>,
299    pub(crate) random_scalar: SecretKey<G>,
300}
301
302impl<G: Group> ExtendedCiphertext<G> {
303    /// Creates a ciphertext of `value` for the specified `receiver`.
304    pub(crate) fn new<R: CryptoRng + RngCore>(
305        value: G::Element,
306        receiver: &PublicKey<G>,
307        rng: &mut R,
308    ) -> Self {
309        let random_scalar = SecretKey::<G>::generate(rng);
310        let random_element = G::mul_generator(random_scalar.expose_scalar());
311        let dh_element = receiver.as_element() * random_scalar.expose_scalar();
312        let blinded_element = value + dh_element;
313
314        Self {
315            inner: Ciphertext {
316                random_element,
317                blinded_element,
318            },
319            random_scalar,
320        }
321    }
322
323    pub(crate) fn zero() -> Self {
324        Self {
325            inner: Ciphertext::zero(),
326            random_scalar: SecretKey::new(G::Scalar::from(0_u64)),
327        }
328    }
329
330    pub(crate) fn with_value<V>(self, value: V) -> CiphertextWithValue<G, V>
331    where
332        V: Zeroize,
333        G::Scalar: From<V>,
334    {
335        CiphertextWithValue {
336            inner: self,
337            value: Zeroizing::new(value),
338        }
339    }
340}
341
342impl<G: Group> ops::Add for ExtendedCiphertext<G> {
343    type Output = Self;
344
345    fn add(self, rhs: Self) -> Self::Output {
346        Self {
347            inner: self.inner + rhs.inner,
348            random_scalar: self.random_scalar + rhs.random_scalar,
349        }
350    }
351}
352
353impl<G: Group> ops::AddAssign for ExtendedCiphertext<G> {
354    fn add_assign(&mut self, rhs: Self) {
355        self.inner += rhs.inner;
356        self.random_scalar += rhs.random_scalar;
357    }
358}
359
360impl<G: Group> ops::Sub for ExtendedCiphertext<G> {
361    type Output = Self;
362
363    fn sub(self, rhs: Self) -> Self::Output {
364        Self {
365            inner: self.inner - rhs.inner,
366            random_scalar: self.random_scalar - rhs.random_scalar,
367        }
368    }
369}
370
371/// ElGamal [`Ciphertext`] together with fully retained information about the encrypted value and
372/// randomness used to create the ciphertext.
373///
374/// This type can be used to produce certain kinds of proofs, such as
375/// [`SumOfSquaresProof`](crate::SumOfSquaresProof).
376#[derive(Debug)]
377pub struct CiphertextWithValue<G: Group, V: Zeroize = <G as ScalarOps>::Scalar> {
378    inner: ExtendedCiphertext<G>,
379    value: Zeroizing<V>,
380}
381
382impl<G: Group, V: Zeroize> From<CiphertextWithValue<G, V>> for Ciphertext<G> {
383    fn from(ciphertext: CiphertextWithValue<G, V>) -> Self {
384        ciphertext.inner.inner
385    }
386}
387
388impl<G: Group, V> CiphertextWithValue<G, V>
389where
390    V: Copy + Zeroize,
391    G::Scalar: From<V>,
392{
393    /// Encrypts a value for the specified receiver.
394    ///
395    /// This is a lower-level operation compared to [`PublicKey::encrypt()`] and should be used
396    /// if the resulting ciphertext is necessary to produce proofs.
397    pub fn new<R: CryptoRng + RngCore>(value: V, receiver: &PublicKey<G>, rng: &mut R) -> Self {
398        let scalar = Zeroizing::new(G::Scalar::from(value));
399        let element = G::mul_generator(&scalar);
400        ExtendedCiphertext::new(element, receiver, rng).with_value(value)
401    }
402
403    /// Converts the enclosed value into a scalar.
404    pub fn generalize(self) -> CiphertextWithValue<G> {
405        CiphertextWithValue {
406            inner: self.inner,
407            value: Zeroizing::new(G::Scalar::from(*self.value)),
408        }
409    }
410}
411
412impl<G: Group, V> CiphertextWithValue<G, V>
413where
414    V: Zeroize,
415    G::Scalar: From<V>,
416{
417    /// Returns a reference to the contained [`Ciphertext`].
418    pub fn inner(&self) -> &Ciphertext<G> {
419        &self.inner.inner
420    }
421
422    pub(crate) fn extended_ciphertext(&self) -> &ExtendedCiphertext<G> {
423        &self.inner
424    }
425
426    pub(crate) fn randomness(&self) -> &SecretKey<G> {
427        &self.inner.random_scalar
428    }
429
430    pub(crate) fn value(&self) -> &V {
431        &self.value
432    }
433}
434
435#[cfg(test)]
436mod tests {
437    use rand::{thread_rng, Rng};
438
439    use super::*;
440    use crate::{curve25519::scalar::Scalar as Curve25519Scalar, group::Ristretto, Keypair};
441
442    #[test]
443    fn ciphertext_addition() {
444        let mut rng = thread_rng();
445        let numbers: Vec<_> = (0..10).map(|_| u64::from(rng.gen::<u32>())).collect();
446        let sum = numbers.iter().copied().sum::<u64>();
447
448        let (pk, sk) = Keypair::<Ristretto>::generate(&mut rng).into_tuple();
449        let ciphertexts = numbers.into_iter().map(|x| pk.encrypt(x, &mut rng));
450        let sum_ciphertext = ciphertexts.reduce(ops::Add::add).unwrap();
451        let decrypted = sk.decrypt_to_element(sum_ciphertext);
452
453        assert_eq!(decrypted, Ristretto::vartime_mul_generator(&sum.into()));
454    }
455
456    #[test]
457    fn ciphertext_mul_by_u64() {
458        let mut rng = thread_rng();
459        let (pk, sk) = Keypair::<Ristretto>::generate(&mut rng).into_tuple();
460        for _ in 0..100 {
461            let x = rng.gen::<u64>();
462            let multiplier = rng.gen::<u64>();
463            let ciphertext = pk.encrypt(x, &mut rng);
464            let decrypted = sk.decrypt_to_element(ciphertext * multiplier);
465
466            let expected_decryption =
467                Curve25519Scalar::from(x) * Curve25519Scalar::from(multiplier);
468            assert_eq!(
469                decrypted,
470                Ristretto::vartime_mul_generator(&expected_decryption)
471            );
472        }
473    }
474
475    #[test]
476    fn ciphertext_negation() {
477        let mut rng = thread_rng();
478        let (pk, sk) = Keypair::<Ristretto>::generate(&mut rng).into_tuple();
479        for _ in 0..100 {
480            let x = rng.gen::<u64>();
481            let ciphertext = pk.encrypt(x, &mut rng);
482            let neg_ciphertext = -ciphertext;
483            let decrypted = sk.decrypt_to_element(neg_ciphertext);
484
485            assert_eq!(
486                decrypted,
487                Ristretto::vartime_mul_generator(&-Curve25519Scalar::from(x))
488            );
489        }
490    }
491
492    #[test]
493    fn non_blinded_ciphertext() {
494        let mut rng = thread_rng();
495        let (_, sk) = Keypair::<Ristretto>::generate(&mut rng).into_tuple();
496        for _ in 0..100 {
497            let x = rng.gen::<u64>();
498            let ciphertext = Ciphertext::non_blinded(x);
499            let decrypted = sk.decrypt_to_element(ciphertext);
500
501            assert_eq!(
502                decrypted,
503                Ristretto::vartime_mul_generator(&Curve25519Scalar::from(x))
504            );
505        }
506    }
507}
elastic_elgamal/encryption.rs

elastic_elgamal/
encryption.rs
