ZKPs with Decisional Diffie–Hellman (DDH) assumption (Chaum-Pedersen)Within DDH we have a tuple of \(\langle g, g^a, g^b, g^{ab} \rangle\) and where \(a\) and \(b\) are secrets. The values of \(g^a\) and \(g^b\) are exchanged between two parties, and after this they should each be able to generate \(g^{ab}\) [1]. If we have Peggy as a prover and Victor as a verifier, then Peggy needs to show that she knows a secret value \(a\). With the Chaum-Pedersen ZKP [2], Victor generates a commitment for Peggy to produce a ZKP in protecting a secret. For this, she will send Victor the value of \(g^a \pmod p\). When Victor needs to prove that she still knows the value of \(a\), he will send a challenge value (\(s\)). Alice then generates a random value (\(r\)) and sends back \(y_1 = g^r\) and \(y_2 = B^r\). Victor then checks the equality of \(g^z = A^s y_1 \pmod p\) and \(B^z = C^s y_2 \pmod p\). |
Theory
A typical thing we must prove is that we still hold a secret (private) key. So, how can we bind Victor and Peggy into a proof infastructure that Peggy can prove to Victor that she still holds a private key. For this, we will bind Victor and Peggy through a Diffie-Hellman key exchange. Within DDH we have a tuple of \(\langle g,A,B,C \rangle = \langle g, g^a, g^b, g^{ab} \rangle\) and where a and b are secrets. The values of \(g^a\) and \(g^b\) are exchanged between two parties, and after this they should each be able to generate \(g^{ab}\):
Within DDH we have a tuple of \(\langle g, g^a, g^b, g^{ab} \rangle\) and where \(a\) and \(b\) are secrets. The values of \(g^a\) and \(g^b\) are exchanged between two parties, and after this they should each be able to generate \(g^{ab}\). If we have Peggy as a prover and Victor as a verifier, then Peggy needs to show that she knows a secret value \(a\). With the Chaum-Pedersen ZKP, Victor generates a commitment for Peggy to produce a ZKP in protecting a secret. For this, she will send Victor the value of \(g^a \pmod p\). When Victor needs to prove that she still knows the value of \(a\), he will send a challenge value (\(s\)). Alice then generates a random value (\(r\)) and sends back \(y_1 = g^r\) and \(y_2 = B^r\). Victor then checks the equality of \(g^z = A^s y_1 \pmod p\) and \(B^z = C^s y_2 \pmod p\).
After Victor and Peggy exchange their secrets, Victor will hold \(g^a \pmod p\) and Peggy will hold \(g^b \pmod p\). For the zero knowledge proof we thus start with:
\(\langle g,A,B,C \rangle = \langle g, g^a, g^b, g^{ab} \rangle\)
Peggy has a secret value of \(a\) and generates \(A=g^a\).
Victor has a secret value of \(b\) and generates \(B=g^b\).
They exchange \(A\) and \(B\) and then use the Diffie Hellman method to generate \(C\).
Victor sends a commitment (\(s\)) to Peggy:
\(s\leftarrow\mathbb{Z}_p\)
Peggy then generates a random value (\(r\)):
\(r\leftarrow\mathbb{Z}_p\)
And send Victor:
\(y_1 = g^r \pmod p\)
and:
\(y_2 = B^r \pmod p\)
She also sends:
\(z = r + a.s \pmod p\)
Victor then checks:
\(g^z = A^s.y_1 \pmod p\)
and:
\(B^z = C^s.y_2 \pmod p\)
If these equalities are true, Peggy has proven that she knows the secret value of \(a\). This works because:
\(A^s.y_1 = {(g^a)}^s.g^r = g^{as}.g^{r} = g^{as+r} = g^z\pmod p\)
\(C^s.y_2 = {(g^{ab})}^s.B^r = g^{abs}.g^{br} = g^{abs+br} = {(g^b)}^{as+r} = B^z \pmod p\)
Coding
The coding is:
import random import libnum import sys bitsize=128 if (len(sys.argv)>1): bitsize=int(sys.argv[1]) p=libnum.generate_prime(bitsize) s=random.getrandbits(bitsize) g=2 a=random.getrandbits(bitsize) b=random.getrandbits(bitsize) c=random.getrandbits(bitsize) r=random.getrandbits(bitsize) A=pow(g,a,p) B=pow(g,b,p) C=pow(g,a*b,p) y1=pow(g,r,p) y2=pow(B,r,p) z=(r+a*s) % (p-1) print("== Chaum-Pederson ZKP with DDH ==") print("p=",p) print("a=",a) print("A=g^a (mod p)=",A) print("b=",b) print("B=g^a (mod p)=",B) print("ab=",a*b) print("C=g^{ab} (mod p)=",C) print("\nProof: g^z = A^s y1") val1= pow(g,z,p) val2=(pow(A,s,p)*y1) % p print("Val1=",val1) print("Val2=",val2) if (val1==val2): print("- Proof verified") print("\nProof: B^z = C^s y2") val3= pow(B,z,p) val4=(pow(C,s,p)*y2) % p print("Val3=",val3) print("Val4=",val4) if (val3==val4): print("- Proof verified")
A sample run for \(g=2\) and for a random 256-bit random prime:
== Chaum-Pederson ZKP with DDH == Prime size: 256 bits p= 64342474638298969136920816577185745650081474423926632680138038631504026705239 g= 2 a= 31864519802410778334681424781326545168680167550776193607092092327124058840820 A=g^a (mod p)= 14921943714585517002109157322490340485006606337510286196275496583071146027243 b= 55089868459129667483672595326694484161171568366406169153125003143095721082707 B=g^a (mod p)= 4208448948380412620360491046026560117269932927136867013874938661774350264349 ab= 1755412204428142241642620958939176622171801704312324934896023427496837907106870209705010197038353530621223374314754603687065819562889758833011665767699740 C=g^{ab} (mod p)= 13320781547672426359604236155856559404106006113802567061325485263752483621081 Proof: g^z = A^s y1 Val1= 11259347840992948849211406369708794953438909880550806223387808255331785448398 Val2= 11259347840992948849211406369708794953438909880550806223387808255331785448398 - Proof verified Proof: B^z = C^s y2 Val3= 41734342317164983823786777388073116576641928544245832594014666565074989115342 Val4= 41734342317164983823786777388073116576641928544245832594014666565074989115342 - Proof verified
Reference
[1] Diffie, W., & Hellman, M. E. (1976). New directions in cryptography. In IEEE Transactions on Information Theory, Volume: 22, Issue: 6, November 1976.
[2] Chaum, D., & Pedersen, T. P. (1992, August). Wallet databases with observers. In Annual international cryptology conference (pp. 89–105). Springer, Berlin, Heidelberg.