use merlin::Transcript;
use rand_core::{CryptoRng, RngCore};
#[cfg(feature = "serde")]
use serde::{de::DeserializeOwned, Deserialize, Serialize};
use zeroize::Zeroizing;
use core::{fmt, iter, ops};
use crate::{
alloc::{vec, Vec},
group::Group,
Ciphertext, CiphertextWithValue, LogEqualityProof, PublicKey, RingProof, RingProofBuilder,
VerificationError,
};
pub trait ProveSum<G: Group>: Clone + crate::sealed::Sealed {
#[cfg(not(feature = "serde"))]
type Proof: Sized;
#[cfg(feature = "serde")]
type Proof: Sized + Serialize + DeserializeOwned;
#[doc(hidden)]
fn prove<R: CryptoRng + RngCore>(
&self,
ciphertext: &CiphertextWithValue<G, u64>,
receiver: &PublicKey<G>,
rng: &mut R,
) -> Self::Proof;
#[doc(hidden)]
fn verify(
&self,
ciphertext: &Ciphertext<G>,
proof: &Self::Proof,
receiver: &PublicKey<G>,
) -> Result<(), ChoiceVerificationError>;
}
#[derive(Debug, Clone, Copy)]
pub struct SingleChoice(());
impl crate::sealed::Sealed for SingleChoice {}
impl<G: Group> ProveSum<G> for SingleChoice {
type Proof = LogEqualityProof<G>;
fn prove<R: CryptoRng + RngCore>(
&self,
ciphertext: &CiphertextWithValue<G, u64>,
receiver: &PublicKey<G>,
rng: &mut R,
) -> Self::Proof {
LogEqualityProof::new(
receiver,
ciphertext.randomness(),
(
ciphertext.inner().random_element,
ciphertext.inner().blinded_element - G::generator(),
),
&mut Transcript::new(b"choice_encryption_sum"),
rng,
)
}
fn verify(
&self,
ciphertext: &Ciphertext<G>,
proof: &Self::Proof,
receiver: &PublicKey<G>,
) -> Result<(), ChoiceVerificationError> {
let powers = (
ciphertext.random_element,
ciphertext.blinded_element - G::generator(),
);
proof
.verify(
receiver,
powers,
&mut Transcript::new(b"choice_encryption_sum"),
)
.map_err(ChoiceVerificationError::Sum)
}
}
#[derive(Debug, Clone, Copy)]
pub struct MultiChoice(());
impl crate::sealed::Sealed for MultiChoice {}
impl<G: Group> ProveSum<G> for MultiChoice {
type Proof = ();
fn prove<R: CryptoRng + RngCore>(
&self,
_ciphertext: &CiphertextWithValue<G, u64>,
_receiver: &PublicKey<G>,
_rng: &mut R,
) -> Self::Proof {
}
fn verify(
&self,
_ciphertext: &Ciphertext<G>,
_proof: &Self::Proof,
_receiver: &PublicKey<G>,
) -> Result<(), ChoiceVerificationError> {
Ok(()) }
}
#[derive(Debug)]
pub struct ChoiceParams<G: Group, S: ProveSum<G>> {
options_count: usize,
sum_prover: S,
receiver: PublicKey<G>,
}
impl<G: Group, S: ProveSum<G>> Clone for ChoiceParams<G, S> {
fn clone(&self) -> Self {
Self {
options_count: self.options_count,
sum_prover: self.sum_prover.clone(),
receiver: self.receiver.clone(),
}
}
}
impl<G: Group, S: ProveSum<G>> ChoiceParams<G, S> {
fn check_options_count(&self, actual_count: usize) -> Result<(), ChoiceVerificationError> {
if self.options_count == actual_count {
Ok(())
} else {
Err(ChoiceVerificationError::OptionsLenMismatch {
expected: self.options_count,
actual: actual_count,
})
}
}
pub fn receiver(&self) -> &PublicKey<G> {
&self.receiver
}
pub fn options_count(&self) -> usize {
self.options_count
}
}
impl<G: Group> ChoiceParams<G, SingleChoice> {
pub fn single(receiver: PublicKey<G>, options_count: usize) -> Self {
assert!(options_count > 0, "Number of options must be positive");
Self {
options_count,
sum_prover: SingleChoice(()),
receiver,
}
}
}
impl<G: Group> ChoiceParams<G, MultiChoice> {
pub fn multi(receiver: PublicKey<G>, options_count: usize) -> Self {
assert!(options_count > 0, "Number of options must be positive");
Self {
options_count,
sum_prover: MultiChoice(()),
receiver,
}
}
}
#[derive(Debug, Clone)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(feature = "serde", serde(bound = ""))]
pub struct EncryptedChoice<G: Group, S: ProveSum<G>> {
choices: Vec<Ciphertext<G>>,
range_proof: RingProof<G>,
sum_proof: S::Proof,
}
impl<G: Group> EncryptedChoice<G, SingleChoice> {
pub fn single<R: CryptoRng + RngCore>(
params: &ChoiceParams<G, SingleChoice>,
choice: usize,
rng: &mut R,
) -> Self {
assert!(
choice < params.options_count,
"invalid choice {}; expected a value in 0..{}",
choice,
params.options_count
);
let choices: Vec<_> = (0..params.options_count).map(|i| choice == i).collect();
Self::new(params, &Zeroizing::new(choices), rng)
}
}
#[allow(clippy::len_without_is_empty)] impl<G: Group, S: ProveSum<G>> EncryptedChoice<G, S> {
pub fn new<R: CryptoRng + RngCore>(
params: &ChoiceParams<G, S>,
choices: &[bool],
rng: &mut R,
) -> Self {
assert!(!choices.is_empty(), "No choices provided");
assert_eq!(
choices.len(),
params.options_count,
"Mismatch between expected and actual number of choices"
);
let admissible_values = [G::identity(), G::generator()];
let mut ring_responses = vec![G::Scalar::default(); 2 * params.options_count];
let mut transcript = Transcript::new(b"encrypted_choice_ranges");
let mut proof_builder = RingProofBuilder::new(
¶ms.receiver,
params.options_count,
&mut ring_responses,
&mut transcript,
rng,
);
let sum = choices.iter().map(|&flag| u64::from(flag)).sum::<u64>();
let choices: Vec<_> = choices
.iter()
.map(|&flag| proof_builder.add_value(&admissible_values, usize::from(flag)))
.collect();
let range_proof = RingProof::new(proof_builder.build(), ring_responses);
let sum_ciphertext = choices.iter().cloned().reduce(ops::Add::add).unwrap();
let sum_ciphertext = sum_ciphertext.with_value(sum);
let sum_proof = params
.sum_prover
.prove(&sum_ciphertext, ¶ms.receiver, rng);
Self {
choices: choices.into_iter().map(|choice| choice.inner).collect(),
range_proof,
sum_proof,
}
}
#[allow(clippy::missing_panics_doc)]
pub fn verify(
&self,
params: &ChoiceParams<G, S>,
) -> Result<&[Ciphertext<G>], ChoiceVerificationError> {
params.check_options_count(self.choices.len())?;
let sum_of_ciphertexts = self.choices.iter().copied().reduce(ops::Add::add);
let sum_of_ciphertexts = sum_of_ciphertexts.unwrap();
params
.sum_prover
.verify(&sum_of_ciphertexts, &self.sum_proof, ¶ms.receiver)?;
let admissible_values = [G::identity(), G::generator()];
self.range_proof
.verify(
¶ms.receiver,
iter::repeat(&admissible_values as &[_]).take(self.choices.len()),
self.choices.iter().copied(),
&mut Transcript::new(b"encrypted_choice_ranges"),
)
.map(|()| self.choices.as_slice())
.map_err(ChoiceVerificationError::Range)
}
pub fn len(&self) -> usize {
self.choices.len()
}
pub fn choices_unchecked(&self) -> &[Ciphertext<G>] {
&self.choices
}
pub fn range_proof(&self) -> &RingProof<G> {
&self.range_proof
}
pub fn sum_proof(&self) -> &S::Proof {
&self.sum_proof
}
}
#[derive(Debug)]
#[non_exhaustive]
pub enum ChoiceVerificationError {
OptionsLenMismatch {
expected: usize,
actual: usize,
},
Sum(VerificationError),
Range(VerificationError),
}
impl fmt::Display for ChoiceVerificationError {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::OptionsLenMismatch { expected, actual } => write!(
formatter,
"number of options in the ballot ({act}) differs from expected ({exp})",
act = actual,
exp = expected
),
Self::Sum(err) => write!(formatter, "cannot verify sum proof: {}", err),
Self::Range(err) => write!(formatter, "cannot verify range proofs: {}", err),
}
}
}
#[cfg(feature = "std")]
impl std::error::Error for ChoiceVerificationError {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match self {
Self::Sum(err) | Self::Range(err) => Some(err),
_ => None,
}
}
}
#[cfg(test)]
mod tests {
use rand::thread_rng;
use super::*;
use crate::{
group::{Generic, Ristretto},
Keypair,
};
fn test_bogus_encrypted_choice_does_not_work<G: Group>() {
let mut rng = thread_rng();
let (receiver, _) = Keypair::<G>::generate(&mut rng).into_tuple();
let params = ChoiceParams::single(receiver.clone(), 5);
let mut choice = EncryptedChoice::single(¶ms, 2, &mut rng);
let (encrypted_one, _) = receiver.encrypt_bool(true, &mut rng);
choice.choices[0] = encrypted_one;
assert!(choice.verify(¶ms).is_err());
let mut choice = EncryptedChoice::single(¶ms, 4, &mut rng);
let (encrypted_zero, _) = receiver.encrypt_bool(false, &mut rng);
choice.choices[4] = encrypted_zero;
assert!(choice.verify(¶ms).is_err());
let mut choice = EncryptedChoice::single(¶ms, 4, &mut rng);
choice.choices[4].blinded_element =
choice.choices[4].blinded_element + G::mul_generator(&G::Scalar::from(10));
choice.choices[3].blinded_element =
choice.choices[3].blinded_element - G::mul_generator(&G::Scalar::from(10));
assert!(choice.verify(¶ms).is_err());
}
#[test]
fn bogus_encrypted_choice_does_not_work_for_edwards() {
test_bogus_encrypted_choice_does_not_work::<Ristretto>();
}
#[test]
fn bogus_encrypted_choice_does_not_work_for_k256() {
test_bogus_encrypted_choice_does_not_work::<Generic<k256::Secp256k1>>();
}
}