elastic_elgamal/app/
choice.rs

1//! Encrypted choice.
2
3use core::{fmt, iter, ops};
4
5use elliptic_curve::{
6    rand_core::{CryptoRng, RngCore},
7    zeroize::Zeroizing,
8};
9use merlin::Transcript;
10#[cfg(feature = "serde")]
11use serde::{Deserialize, Serialize, de::DeserializeOwned};
12
13use crate::{
14    Ciphertext, CiphertextWithValue, LogEqualityProof, PublicKey, RingProof, RingProofBuilder,
15    VerificationError,
16    alloc::{Vec, vec},
17    group::Group,
18};
19
20/// Encapsulation of functionality for proving and verifying correctness of the sum of option
21/// ciphertexts in an [`EncryptedChoice`].
22///
23/// This trait is not meant to be implemented for external types.
24pub trait ProveSum<G: Group>: Clone + crate::sealed::Sealed {
25    /// Produced / verified proofs.
26    #[cfg(not(feature = "serde"))]
27    type Proof: Sized;
28    /// Produced / verified proofs.
29    #[cfg(feature = "serde")]
30    type Proof: Sized + Serialize + DeserializeOwned;
31
32    #[doc(hidden)]
33    fn prove<R: CryptoRng + RngCore>(
34        &self,
35        ciphertext: &CiphertextWithValue<G, u64>,
36        receiver: &PublicKey<G>,
37        rng: &mut R,
38    ) -> Self::Proof;
39
40    #[doc(hidden)]
41    fn verify(
42        &self,
43        ciphertext: &Ciphertext<G>,
44        proof: &Self::Proof,
45        receiver: &PublicKey<G>,
46    ) -> Result<(), ChoiceVerificationError>;
47}
48
49/// Single-choice setup for [`EncryptedChoice`], in which it can contain a single selected option.
50///
51/// # Examples
52///
53/// See [`EncryptedChoice`] docs for an example of usage.
54#[derive(Debug, Clone, Copy)]
55pub struct SingleChoice(());
56
57impl crate::sealed::Sealed for SingleChoice {}
58
59impl<G: Group> ProveSum<G> for SingleChoice {
60    type Proof = LogEqualityProof<G>;
61
62    fn prove<R: CryptoRng + RngCore>(
63        &self,
64        ciphertext: &CiphertextWithValue<G, u64>,
65        receiver: &PublicKey<G>,
66        rng: &mut R,
67    ) -> Self::Proof {
68        LogEqualityProof::new(
69            receiver,
70            ciphertext.randomness(),
71            (
72                ciphertext.inner().random_element,
73                ciphertext.inner().blinded_element - G::generator(),
74            ),
75            &mut Transcript::new(b"choice_encryption_sum"),
76            rng,
77        )
78    }
79
80    fn verify(
81        &self,
82        ciphertext: &Ciphertext<G>,
83        proof: &Self::Proof,
84        receiver: &PublicKey<G>,
85    ) -> Result<(), ChoiceVerificationError> {
86        let powers = (
87            ciphertext.random_element,
88            ciphertext.blinded_element - G::generator(),
89        );
90        proof
91            .verify(
92                receiver,
93                powers,
94                &mut Transcript::new(b"choice_encryption_sum"),
95            )
96            .map_err(ChoiceVerificationError::Sum)
97    }
98}
99
100/// Multi-choice setup for [`EncryptedChoice`], in which it can contain any possible number
101/// of selected options (`0..=n`, where `n` is the number of options).
102///
103/// # Examples
104///
105/// See [`EncryptedChoice`] docs for an example of usage.
106#[derive(Debug, Clone, Copy)]
107pub struct MultiChoice(());
108
109impl crate::sealed::Sealed for MultiChoice {}
110
111impl<G: Group> ProveSum<G> for MultiChoice {
112    type Proof = ();
113
114    fn prove<R: CryptoRng + RngCore>(
115        &self,
116        _ciphertext: &CiphertextWithValue<G, u64>,
117        _receiver: &PublicKey<G>,
118        _rng: &mut R,
119    ) -> Self::Proof {
120        // Do nothing.
121    }
122
123    fn verify(
124        &self,
125        _ciphertext: &Ciphertext<G>,
126        _proof: &Self::Proof,
127        _receiver: &PublicKey<G>,
128    ) -> Result<(), ChoiceVerificationError> {
129        Ok(()) // no failure conditions
130    }
131}
132
133/// Parameters of an [`EncryptedChoice`] polling.
134#[derive(Debug)]
135pub struct ChoiceParams<G: Group, S: ProveSum<G>> {
136    options_count: usize,
137    sum_prover: S,
138    receiver: PublicKey<G>,
139}
140
141impl<G: Group, S: ProveSum<G>> Clone for ChoiceParams<G, S> {
142    fn clone(&self) -> Self {
143        Self {
144            options_count: self.options_count,
145            sum_prover: self.sum_prover.clone(),
146            receiver: self.receiver.clone(),
147        }
148    }
149}
150
151impl<G: Group, S: ProveSum<G>> ChoiceParams<G, S> {
152    fn check_options_count(&self, actual_count: usize) -> Result<(), ChoiceVerificationError> {
153        if self.options_count == actual_count {
154            Ok(())
155        } else {
156            Err(ChoiceVerificationError::OptionsLenMismatch {
157                expected: self.options_count,
158                actual: actual_count,
159            })
160        }
161    }
162
163    /// Returns the public key for which the [`EncryptedChoice`] are encrypted.
164    pub fn receiver(&self) -> &PublicKey<G> {
165        &self.receiver
166    }
167
168    /// Returns the number of options in these parameters.
169    pub fn options_count(&self) -> usize {
170        self.options_count
171    }
172}
173
174impl<G: Group> ChoiceParams<G, SingleChoice> {
175    /// Creates parameters for a single-choice polling.
176    ///
177    /// # Panics
178    ///
179    /// Panics if provided `options_count` is zero.
180    pub fn single(receiver: PublicKey<G>, options_count: usize) -> Self {
181        assert!(options_count > 0, "Number of options must be positive");
182        Self {
183            options_count,
184            sum_prover: SingleChoice(()),
185            receiver,
186        }
187    }
188}
189
190impl<G: Group> ChoiceParams<G, MultiChoice> {
191    /// Creates parameters for a multi-choice polling.
192    ///
193    /// # Panics
194    ///
195    /// Panics if provided `options_count` is zero.
196    pub fn multi(receiver: PublicKey<G>, options_count: usize) -> Self {
197        assert!(options_count > 0, "Number of options must be positive");
198        Self {
199            options_count,
200            sum_prover: MultiChoice(()),
201            receiver,
202        }
203    }
204}
205
206/// Zero or more encrypted choices from `n` options (`n >= 1`) together with zero-knowledge
207/// proofs of correctness.
208///
209/// # Construction
210///
211/// The choice is represented as a vector of `n` *choice ciphertexts* of Boolean values (0 or 1),
212/// where the ciphertexts for the chosen options encrypt 1 and the other ciphertexts encrypt 0.
213/// This ensures that multiple [`EncryptedChoice`]s can be added (e.g., within a voting protocol).
214///
215/// Zero-knowledge proofs are:
216///
217/// - A [`RingProof`] attesting that all `n` ciphertexts encrypt 0 or 1.
218///   This proof can be obtained via [`Self::range_proof()`].
219/// - A [`LogEqualityProof`] attesting that the encrypted values sum up to 1. Combined with
220///   the range proof, this means that exactly one of encrypted values is 1, and all others are 0.
221///   This proof can be obtained via [`Self::sum_proof()`]. This proof is absent for
222///   a [`MultiChoice`] setup (`sum_proof()` just returns `()`).
223///
224/// # Examples
225///
226/// ## Single-choice setup
227///
228/// ```
229/// # use elastic_elgamal::{
230/// #     app::{ChoiceParams, EncryptedChoice}, group::Ristretto, DiscreteLogTable, Keypair,
231/// # };
232/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
233/// let mut rng = rand::rng();
234/// let (pk, sk) = Keypair::<Ristretto>::generate(&mut rng).into_tuple();
235/// let choice_params = ChoiceParams::single(pk, 5);
236///
237/// let choice = 2;
238/// let enc = EncryptedChoice::single(&choice_params, choice, &mut rng);
239/// let choices = enc.verify(&choice_params)?;
240///
241/// // `choices` is a slice of 5 Boolean value ciphertexts
242/// assert_eq!(choices.len(), 5);
243/// let lookup_table = DiscreteLogTable::new(0..=1);
244/// for (idx, &v) in choices.iter().enumerate() {
245///     assert_eq!(
246///         sk.decrypt(v, &lookup_table),
247///         Some((idx == choice) as u64)
248///     );
249/// }
250/// # Ok(())
251/// # }
252/// ```
253///
254/// ## Multi-choice setup
255///
256/// ```
257/// # use elastic_elgamal::{
258/// #     app::{ChoiceParams, EncryptedChoice}, group::Ristretto, DiscreteLogTable, Keypair,
259/// # };
260/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
261/// let mut rng = rand::rng();
262/// let (pk, sk) = Keypair::<Ristretto>::generate(&mut rng).into_tuple();
263/// let choice_params = ChoiceParams::multi(pk, 5);
264///
265/// let choices = [true, false, true, true, false];
266/// let enc = EncryptedChoice::new(&choice_params, &choices, &mut rng);
267/// let recovered_choices = enc.verify(&choice_params)?;
268///
269/// let lookup_table = DiscreteLogTable::new(0..=1);
270/// for (idx, &v) in recovered_choices.iter().enumerate() {
271///     assert_eq!(sk.decrypt(v, &lookup_table), Some(choices[idx] as u64));
272/// }
273/// # Ok(())
274/// # }
275/// ```
276#[derive(Debug, Clone)]
277#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
278#[cfg_attr(feature = "serde", serde(bound = ""))]
279pub struct EncryptedChoice<G: Group, S: ProveSum<G>> {
280    choices: Vec<Ciphertext<G>>,
281    range_proof: RingProof<G>,
282    sum_proof: S::Proof,
283}
284
285impl<G: Group> EncryptedChoice<G, SingleChoice> {
286    /// Creates a new encrypted choice.
287    ///
288    /// # Panics
289    ///
290    /// Panics if `choice` exceeds the maximum index allowed by `params`.
291    pub fn single<R: CryptoRng + RngCore>(
292        params: &ChoiceParams<G, SingleChoice>,
293        choice: usize,
294        rng: &mut R,
295    ) -> Self {
296        assert!(
297            choice < params.options_count,
298            "invalid choice {choice}; expected a value in 0..{}",
299            params.options_count
300        );
301        let choices: Vec<_> = (0..params.options_count).map(|i| choice == i).collect();
302        Self::new(params, &Zeroizing::new(choices), rng)
303    }
304}
305
306#[allow(clippy::len_without_is_empty)] // `is_empty()` would always be false
307impl<G: Group, S: ProveSum<G>> EncryptedChoice<G, S> {
308    /// Creates an encrypted multi-choice.
309    ///
310    /// For a [`SingleChoice`] polling, it is caller's responsibility to ensure that `choices`
311    /// contains exactly one `true` value; otherwise, the produced proof will not verify.
312    ///
313    /// # Panics
314    ///
315    /// Panics if the length of `choices` differs from the number of options specified in `params`.
316    pub fn new<R: CryptoRng + RngCore>(
317        params: &ChoiceParams<G, S>,
318        choices: &[bool],
319        rng: &mut R,
320    ) -> Self {
321        assert!(!choices.is_empty(), "No choices provided");
322        assert_eq!(
323            choices.len(),
324            params.options_count,
325            "Mismatch between expected and actual number of choices"
326        );
327
328        let admissible_values = [G::identity(), G::generator()];
329        let mut ring_responses = vec![G::Scalar::default(); 2 * params.options_count];
330        let mut transcript = Transcript::new(b"encrypted_choice_ranges");
331        let mut proof_builder = RingProofBuilder::new(
332            &params.receiver,
333            params.options_count,
334            &mut ring_responses,
335            &mut transcript,
336            rng,
337        );
338
339        let sum = choices.iter().map(|&flag| u64::from(flag)).sum::<u64>();
340        let choices: Vec<_> = choices
341            .iter()
342            .map(|&flag| proof_builder.add_value(&admissible_values, usize::from(flag)))
343            .collect();
344        let range_proof = RingProof::new(proof_builder.build(), ring_responses);
345
346        let sum_ciphertext = choices.iter().cloned().reduce(ops::Add::add).unwrap();
347        let sum_ciphertext = sum_ciphertext.with_value(sum);
348        let sum_proof = params
349            .sum_prover
350            .prove(&sum_ciphertext, &params.receiver, rng);
351        Self {
352            choices: choices.into_iter().map(|choice| choice.inner).collect(),
353            range_proof,
354            sum_proof,
355        }
356    }
357
358    /// Verifies the zero-knowledge proofs in this choice and returns Boolean ciphertexts
359    /// for all options.
360    ///
361    /// # Errors
362    ///
363    /// Returns an error if the `choice` is malformed or its proofs fail verification.
364    #[allow(clippy::missing_panics_doc)]
365    pub fn verify(
366        &self,
367        params: &ChoiceParams<G, S>,
368    ) -> Result<&[Ciphertext<G>], ChoiceVerificationError> {
369        params.check_options_count(self.choices.len())?;
370        let sum_of_ciphertexts = self.choices.iter().copied().reduce(ops::Add::add);
371        let sum_of_ciphertexts = sum_of_ciphertexts.unwrap();
372        // ^ `unwrap()` is safe; `params` cannot have 0 options by construction
373        params
374            .sum_prover
375            .verify(&sum_of_ciphertexts, &self.sum_proof, &params.receiver)?;
376
377        let admissible_values = [G::identity(), G::generator()];
378        self.range_proof
379            .verify(
380                &params.receiver,
381                iter::repeat_n(&admissible_values as &[_], self.choices.len()),
382                self.choices.iter().copied(),
383                &mut Transcript::new(b"encrypted_choice_ranges"),
384            )
385            .map(|()| self.choices.as_slice())
386            .map_err(ChoiceVerificationError::Range)
387    }
388
389    /// Returns the number of encrypted choices. This value is equal to
390    /// [`ChoiceParams::options_count()`] with which the encryption was created.
391    pub fn len(&self) -> usize {
392        self.choices.len()
393    }
394
395    /// Returns ciphertexts for all options **without** checking the validity of this choice.
396    pub fn choices_unchecked(&self) -> &[Ciphertext<G>] {
397        &self.choices
398    }
399
400    /// Returns the range proof for the choice ciphertexts.
401    pub fn range_proof(&self) -> &RingProof<G> {
402        &self.range_proof
403    }
404
405    /// Returns the sum proof for the choice ciphertexts.
406    pub fn sum_proof(&self) -> &S::Proof {
407        &self.sum_proof
408    }
409}
410
411/// Error verifying an [`EncryptedChoice`].
412#[derive(Debug)]
413#[non_exhaustive]
414pub enum ChoiceVerificationError {
415    /// Mismatch between expected and actual number of options in the `EncryptedChoice`.
416    OptionsLenMismatch {
417        /// Expected number of options.
418        expected: usize,
419        /// Actual number of options.
420        actual: usize,
421    },
422    /// Error verifying [`EncryptedChoice::sum_proof()`].
423    Sum(VerificationError),
424    /// Error verifying [`EncryptedChoice::range_proof()`].
425    Range(VerificationError),
426}
427
428impl fmt::Display for ChoiceVerificationError {
429    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
430        match self {
431            Self::OptionsLenMismatch { expected, actual } => write!(
432                formatter,
433                "number of options in the ballot ({actual}) differs from expected ({expected})",
434            ),
435            Self::Sum(err) => write!(formatter, "cannot verify sum proof: {err}"),
436            Self::Range(err) => write!(formatter, "cannot verify range proofs: {err}"),
437        }
438    }
439}
440
441#[cfg(feature = "std")]
442impl std::error::Error for ChoiceVerificationError {
443    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
444        match self {
445            Self::Sum(err) | Self::Range(err) => Some(err),
446            _ => None,
447        }
448    }
449}
450
451#[cfg(test)]
452mod tests {
453    use super::*;
454    use crate::{
455        Keypair,
456        group::{Generic, Ristretto},
457    };
458
459    fn test_bogus_encrypted_choice_does_not_work<G: Group>() {
460        let mut rng = rand::rng();
461        let (receiver, _) = Keypair::<G>::generate(&mut rng).into_tuple();
462        let params = ChoiceParams::single(receiver.clone(), 5);
463
464        let mut choice = EncryptedChoice::single(&params, 2, &mut rng);
465        let (encrypted_one, _) = receiver.encrypt_bool(true, &mut rng);
466        choice.choices[0] = encrypted_one;
467        assert!(choice.verify(&params).is_err());
468
469        let mut choice = EncryptedChoice::single(&params, 4, &mut rng);
470        let (encrypted_zero, _) = receiver.encrypt_bool(false, &mut rng);
471        choice.choices[4] = encrypted_zero;
472        assert!(choice.verify(&params).is_err());
473
474        let mut choice = EncryptedChoice::single(&params, 4, &mut rng);
475        choice.choices[4].blinded_element =
476            choice.choices[4].blinded_element + G::mul_generator(&G::Scalar::from(10));
477        choice.choices[3].blinded_element =
478            choice.choices[3].blinded_element - G::mul_generator(&G::Scalar::from(10));
479        // These modifications leave `choice.sum_proof` correct, but the range proofs
480        // for the last 2 choices should no longer verify.
481        assert!(choice.verify(&params).is_err());
482    }
483
484    #[test]
485    fn bogus_encrypted_choice_does_not_work_for_edwards() {
486        test_bogus_encrypted_choice_does_not_work::<Ristretto>();
487    }
488
489    #[test]
490    fn bogus_encrypted_choice_does_not_work_for_k256() {
491        test_bogus_encrypted_choice_does_not_work::<Generic<k256::Secp256k1>>();
492    }
493}
elastic_elgamal/app/choice.rs

elastic_elgamal/app/
choice.rs
