Struct elastic_elgamal::SumOfSquaresProof
source · pub struct SumOfSquaresProof<G: Group> { /* private fields */ }
Expand description
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 groupK
is a group element equivalent to the receiver’s public key(R_x, X)
and(R_z, Z)
are ElGamal ciphertexts of valuesx
andx^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:
- Commitment. The prover generates random scalars
e_r
,e_x
ande_z
and commits to them viaE_r = [e_r]G
,E_x = [e_x]G + [e_r]K
,E_rz = [e_x]R_x + [e_z]G
andE_z = [e_x]X + [e_z]K
. - Challenge. The verifier sends to the prover random scalar
c
. - 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
ands_x
are independently defined for each partial ciphertext in the same way as above.- Commitments
E_rz
andE_z
sum over[e_x]R_x
and[e_x]X
for all ciphertexts, respectively. - Response
s_z
similarly substitutesx * 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§
source§impl<G: Group> SumOfSquaresProof<G>
impl<G: Group> SumOfSquaresProof<G>
sourcepub 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
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.
sourcepub 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>
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§
source§impl<G: Clone + Group> Clone for SumOfSquaresProof<G>
impl<G: Clone + Group> Clone for SumOfSquaresProof<G>
source§fn clone(&self) -> SumOfSquaresProof<G>
fn clone(&self) -> SumOfSquaresProof<G>
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read more