Chaum Pedersen ZKP Protocol
The Chaum-Pedersen Zero-Knowledge Proof (ZKP) Protocol is a cryptographic method for proving the equality of discrete logarithms without revealing the secret exponent. It ensures that for given group elements (g, h, A, B), there exists a secret x such that A = g^x and B = h^x.
Core Protocol Workflow
Setup
- Public parameters: Cyclic group G with prime order q, generators g, h \in G.
- Prover's secret: x \in \Bbb{Z}_q
- Public values: A = g^x , B=h^x
Commitment (Prover):
- Choose random: w \in \Bbb{Z}_q
- Compute commitments t_1 = g^w, t_2 = h ^w
- Send (t_1, t_2) to the verifier
Challenge (Verifier):
- Generate random challenge c \in \Bbb{Z}_q
- Send c to the Prover.
Response (Prover):
- Compute s = w + c * x \mod q
- Send s to the verifier
Verification:
- Check g^s \overset{?}{=} t_1 * A^c
- Check h^s \overset{?}{=} t_2 * B^c
- Accept if both hold; reject otherwise
Proof
\begin{align*} g^{s} &= g^{w + c * x \mod q} = g^w g^{cx} \mod q \newline t_1 * A^c &= g^w * (g^x)^c = g^w g^{cx} \mod q \newline & \implies g^s = t_1 * A^c \end{align*} Similarly, can prove that h^s = t_2 * B^c