The Chaum-Pedersen Zero Knowledge Proof can be used to show that Peggy (the Prover) knows a secret to Victor (the Verifier):
Chaum-Pedersen Zero Knowledge Proof |
Theory
In the Chaum-Pederson method, we initially define the values of \( \langle g,A,B,C \rangle \) = \(\langle g,g^a,g^b,g^{ab}\rangle\). The basic method is:
Peggy (the prover) defines a secret value of \(r\).
Peggy sends Vector (the Verifier) the commitments of \(y_1=g^r\) and \(y_2=B^r\).
Victor generate a random value (\(c\)) and sends it to Peggy.
Peggy computes \( z= r + as \pmod{q}\) and sends it to Victor.
Victor checks that \( g^z = A^s y_1 \pmod{q}\) and:
Victor checks that \( B^z = C^s y_2 \pmod{q}\)
Code
An outline of the code is:
import random import sys q=10009 s=random.randint(1,1000) r=random.randint(1,1000) if (len(sys.argv)>1): r=int(sys.argv[1]) g=3 a=10 b=13 A=pow(g,a,q) B=pow(g,b, q) C=pow(g,(a*b),q) y1=pow(g,r,q) y2=pow(B,r,q) z=(r+a*s) % q print("Victor and Peggy agree of (g,g^a, g^b and g^ab) =(",g,A,B,C,")") print("\nPeggy generates random number (r)",r) print("Peggy sends y1 (g^r, B^r)=(",y1,y2,")") print() print("Victor sends a challenge (s)=",s) print("Peggy computes z=r+as (mod q)=",z) print("\nVictor now checks these are the same") print("Victor checks g^z=",pow(g,z,q)) print("Victor checks A^s y1=",(A**s * y1) % q) print("\nVictor now checks these are the same") print("Victor checks B^z=", pow(B,z,q)) print("Victor checks C^s y2=",(C**s * y2) % q)