Pedersen-ElGamal equality proof
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:
- Prover generates:
- Two new random values r1, r2
- The Pedersen commitment C1 = r1G + r2H
- ElGamal ciphertext E1 = (r2G, r1G + r2PK)
- The “challenge” c = SHA256(C, E, C1, E1)
- Integer values mod p: z1 = c m + r1 and z2 = c r + r2
- The proof sent to the verifier contains C1, E1, z1, and z2. The verifier checks:
- C1 + c * C = z1 G + z2H
- 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.
- 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