Table of contents
Open Table of contents
What it is
The Chaum-Pedersen Protocol allows one to prove the equality of a secret value given a set of two equations that hide the value but can be publicly shared.
It’s an interactive Zero-Knowledge Proof protocol where a prover wants to convince a verifier that the aforementioned condition of equality holds true.
How it works
In this example let’s assume that Alice, the prover wants to convince Bob, the verifier. Furthermore we’ll be using an Elliptic Curve we call of order .
There are two points on this curve, and , what will be used throughout the protocol.
The first thing Alice does is to sample a random value .
Next up she computes the two values and via and the curve points and : and . Those two values are shared with Bob.
Once done Alice samples a random value called a “nonce”:
It’s important that this value is random and never reused. She then multiplies by the two curve points and to get the values and :
Note that these two operations are “the same” as the computation done to derive and .
The values and are now shared with Bob.
Bob samples a random value called the “commitment” and sends it to Alice. This value should be random and not guessable by Alice.
Alice computes and sends to Bob.
Bob can now calculate the following equations to see if the same secret value was used by Alice:
Why it works
Given that Alice samples the value randomly and adds it to the challenge multiplied by the secret value , there’s no leakage of information regarding to Bob, because Bob can’t distinguish the value of from randomness.
Therefore the nonce masks the value .
Similarity to the Schnorr Identification Protocol
The Chaum-Pedersen Protocol is similar in function to the Schnorr Identification Protocol. The main difference between the two protocols being that in Chaum-Pedersen we not only want to convince the verifier that we know the secret value (as it’s the case in the Schnorr Identification Protocol). We also want to prove that the discrete logarithm between the two values is the same: