elastic_elgamal/
encryption.rs

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

elastic_elgamal/
encryption.rs
