Categories

Pedersen-ElGamal equality proof

You are here:
< All Topics

This is a zero-knowledge proof that an ElGamal ciphertext encrypts the same value as a Pedersen commitment. It is used for asset tracers. This is implemented in the Zei cryptographic library using a variation of a classical cryptographic technique known as the Chaum-Pedersen proof.

 

As an optimization, the randomization value r in the ElGamal ciphertext for the asset tracer E = (rG, mG + rPK) may be the same as the blinding factor for the Pedersen commitment C = mG + rH. The proof for the equality of the message m inside E and C is then:

 

  1. Prover generates:
    1. Two new random values r1, r2
    2. The Pedersen commitment C1 = r1G + r2H
    3. ElGamal ciphertext E1 = (r2G, r1G + r2PK)
    4. The “challenge” c = SHA256(C, E, C1, E1)
    5. Integer values mod p: z1 = c m + r1 and z2 = c r + r2
  2. The proof sent to the verifier contains C1, E1, z1, and z2. The verifier checks:
    1. C1 + c * C = z1 G + z2H
    2. E1 + c * E = [z2 G, z1 G + z2 PK]

 

Generating the proof requires 4 scalar multiplications on the elliptic curve (about 60 µs) and verifying this proof requires 7 scalar multiplications (about 105 µs). The size of the proof is three curve points and two scalars, or approximately 160 bytes.

 

Associated functions:

  • pedersen_elgamal_equality_prove([uint64_t] m, [curve_point] E1, [curve_point] E2, [uint256_t] r1, [curve_point] C, [uint256_t] r2) – returns the proof

 

  • pedersen_eglamal_equality_verify([string] proof, [curve_point] E1, [curve_point] E2, [curve_point] C) – outputs 1 for a valid proof and 0 for an invalid proof
Previous Pedersen commitment equality proof
Next Circuit proof
Table of Contents