With the Damgard-Fujisaki method, Peggy proves to Victor that she knows still knows a secret value, by showing that she can produce its square:
Zero-knowledge proof (Damgard-Fujisaki method) for square |
Method
In this case we will use the Damgard-Fujisaki method defined [here], and where Peggy has to prove to Victor that she still knows a value of \(x\). In this case Peggy will prove that she can determine the square of \(x\) to the power of \(g\). First Victor and Peggy agree on two bases for their calculations (\(g\) and \(h\)) and a prime number (\(n\)). Victor then sends Peggy using a random number (\(r\)) as a challenge. Next Peggy creates her own random number (\(r_1\)) and then calculates the following:
\(c_1 = g^x h^{r_1} \pmod n\)
\(r_2=r - x r_1\)
and then computes:
\(c_2 = {c_1}^x h^{r_2} \pmod n\)
She sends \(c_2\) to Victor, and Victor checks that it equals:
\(g^{x^2} h^r \pmod n\)
If they match, Peggy has proven that she knows \(x\).
This work because:
\(c_2 = {c_1}^x h^{r_2} \pmod n = {(g^x h^{r_1})}^x h^{r - x r_1} \pmod n = g^{x^2} h^{r_1 x + r - x r_1} = g^{x^2} h^{r}\)
In this case, if the value of \(r_2\) is negative, we will have to perform a modular divide operation with the negative value of \(r_2\). Peggy also sends \(c_1\) and \(r_1\) and Victor proves this too.
Coding
The following is some simple coding to prove the method. In this case we will use a prime number of \(2^{19}-1\), \(g=3\), and \(h=5\):
import libnum import random import sys x=42 if (len(sys.argv)>1): x=int(sys.argv[1]) g=3 n=pow(2,19)-1 h=5 # Victor sends r to Peggy r=random.randint(0,n) print ("Victor sends (r): :",r) # Peggy generates a random number r1 # And computes r2 = r-r1 x r1=random.randint(0,n) r2=(r-r1*x) print ("\nPeggy generates (r1): :",r1) print ("And calculates (r2): :",r2) small=(pow(g,x,n)*pow(h,r1,n)) % n if (r2>0): c_peggy=(pow(small,x,n)*pow(h,r2,n)) % n else: val=pow(h,-r2,n) c_peggy=(pow(small,x,n)*libnum.invmod(val,n)) % n print ("\nCommit from Peggy:",c_peggy) c_victor = (pow(g,x*x,n)*pow(h,r)) %n print ("Commit from Victor:",c_victor) if (c_victor==c_peggy): print ("\nPeggy has proven she knows: ",x)