Struct SumOfSquaresProof

pub struct SumOfSquaresProof<G: Group> { /* private fields */ }

Zero-knowledge proof that an ElGamal-encrypted value is equal to a sum of squares of one or more other ElGamal-encrypted values.

Construction

Consider the case with a single sum element (i.e., proving that an encrypted value is a square of another encrypted value). The prover wants to prove the knowledge of scalars

r_x, x, r_z:
  R_x = [r_x]G, X = [x]G + [r_x]K;
  R_z = [r_z]G, Z = [x^2]G + [r_z]K,

where

• G is the conventional generator of the considered prime-order group
• K is a group element equivalent to the receiver’s public key
• (R_x, X) and (R_z, Z) are ElGamal ciphertexts of values x and x^2, respectively.

Observe that

r'_z := r_z - x * r_x =>
  R_z = [r'_z]G + [x]R_x; Z = [x]X + [r'_z]K.

and that proving the knowledge of (r_x, x, r'_z) is equivalent to the initial problem. The new problem can be solved using a conventional sigma protocol:

1. Commitment. The prover generates random scalars e_r, e_x and e_z and commits to them via E_r = [e_r]G, E_x = [e_x]G + [e_r]K, E_rz = [e_x]R_x + [e_z]G and E_z = [e_x]X + [e_z]K.
2. Challenge. The verifier sends to the prover random scalar c.
3. Response. The prover computes the following scalars and sends them to the verifier.

s_r = e_r + c * r_x;
s_x = e_x + c * x;
s_z = e_z + c * (r_z - x * r_x);

The verification equations are

[s_r]G ?= E_r + [c]R_x;
[s_x]G + [s_r]K ?= E_x + [c]X;
[s_x]R_x + [s_z]G ?= E_rz + [c]R_z;
[s_x]X + [s_z]K ?= E_z + [c]Z.

The case with multiple squares is a straightforward generalization:

• e_r, E_r, e_x, E_x, s_r and s_x are independently defined for each partial ciphertext in the same way as above.
• Commitments E_rz and E_z sum over [e_x]R_x and [e_x]X for all ciphertexts, respectively.
• Response s_z similarly substitutes x * r_x with the corresponding sum.

A non-interactive version of the proof is obtained by applying Fiat–Shamir transform. As with LogEqualityProof, it is more efficient to represent a proof as the challenge and responses; in this case, the proof size is 2n + 2 scalars, where n is the number of partial ciphertexts.

Implementations

impl<G: Group> SumOfSquaresProof<G>

pub fn new<'a, R: RngCore + CryptoRng>( ciphertexts: impl Iterator<Item = &'a CiphertextWithValue<G>>, sum_of_squares_ciphertext: &CiphertextWithValue<G>, receiver: &PublicKey<G>, transcript: &mut Transcript, rng: &mut R, ) -> Self

Creates a new proof that squares of values encrypted in ciphertexts for receiver sum up to a value encrypted in sum_of_squares_ciphertext.

All provided ciphertexts must be encrypted for receiver; otherwise, the created proof will not verify.

pub fn verify<'a>( &self, ciphertexts: impl Iterator<Item = &'a Ciphertext<G>> + Clone, sum_of_squares_ciphertext: &Ciphertext<G>, receiver: &PublicKey<G>, transcript: &mut Transcript, ) -> Result<(), VerificationError>

Verifies this proof against the provided partial ciphertexts and the ciphertext of the sum of their squares. The order of partial ciphertexts must correspond to their order when creating the proof.

Errors

Returns an error if this proof does not verify.

Trait Implementations

impl<G: Clone + Group> Clone for SumOfSquaresProof<G>

where G::Scalar: Clone,

fn clone(&self) -> SumOfSquaresProof<G>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<G: Debug + Group> Debug for SumOfSquaresProof<G>

where G::Scalar: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de, G: Group> Deserialize<'de> for SumOfSquaresProof<G>

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<G: Group> Serialize for SumOfSquaresProof<G>

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.