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 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§

source§

impl<G: Group> SumOfSquaresProof<G>

source

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.

source

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>
where G::Scalar: Clone,

source§

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

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

impl<G: Debug + Group> Debug for SumOfSquaresProof<G>
where G::Scalar: Debug,

source§

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

Formats the value using the given formatter. Read more
source§

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

source§

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>
where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer. Read more
source§

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

source§

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

Serialize this value into the given Serde serializer. Read more

Auto Trait Implementations§

§

impl<G> Freeze for SumOfSquaresProof<G>
where <G as ScalarOps>::Scalar: Freeze,

§

impl<G> RefUnwindSafe for SumOfSquaresProof<G>

§

impl<G> Send for SumOfSquaresProof<G>
where <G as ScalarOps>::Scalar: Send,

§

impl<G> Sync for SumOfSquaresProof<G>
where <G as ScalarOps>::Scalar: Sync,

§

impl<G> Unpin for SumOfSquaresProof<G>
where <G as ScalarOps>::Scalar: Unpin,

§

impl<G> UnwindSafe for SumOfSquaresProof<G>
where <G as ScalarOps>::Scalar: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> Same for T

§

type Output = T

Should always be Self
source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

§

fn vzip(self) -> V

source§

impl<T> DeserializeOwned for T
where T: for<'de> Deserialize<'de>,