With the Damgard-Fujisaki method, Peggy proves to Victor that she has a postive integer value:
Zero-knowledge proof (Damgard-Fujisaki method) for a positive value |
Method
In this case we will use the Damgard-Fujisaki method defined [here], and where Peggy has to prove to Victor that she has a postive value. 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. As defined by Jacobi's four-square theorem, every positive value can be represented in the form:
\(x = x_0^2 + x_1^2 + x_2^2 + x_3^2\)
For example:
\(51 = 1^2 + 3^2 + 4^2 + 5^2\)
\(1451 = 1^2 +9^2 +12^2 +35^2\)
\(99999 = 1^2 +2^2 +313^2 +45^2\)
Peggy now creates four commitments from these four values, and takes four random numbers (\(r_0\), \(r_1\), \(r_2\) and \(r_3\)).
\(c_0=g^{x_0^2} h^{r_0} \pmod n\)
\(c_1=g^{x_1^2} h^{r_1} \pmod n\)
\(c_2=g^{x_2^2} h^{r_2} \pmod n\)
\(c_3=g^{x_3^2} h^{r_3} \pmod n\)
And:
\(r = r_0 + r_1 + r_2 + r_3\)
Victor then checks:
\(c = c_1 \times c_2 \times c_3 \times c_4\)
And this should be equal to:
\(g^x h^r \pmod n\)
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 random import sys n=pow(2,19)-1 def lipmaa(val): for i in range(0,100000): for j in range(0,1000): for k in range(0,100): for l in range(0,10): if (((i*i) + (j*j) + (k*k) + (l*l)) == val): return (i,j,k,l) return(0) x=999909 if (len(sys.argv)>1): x=int(sys.argv[1]) if (x<0): print("Not possible to find a commitment, as negative") sys.exit(1) x0,x1,x2,x3=lipmaa(x) print ("x=",x) print (" x0,x1,x2,x3=",x0,x1, x2,x3) g=3 h=4 r0=random.randint(0,n) r1=random.randint(0,n) r2=random.randint(0,n) r3=random.randint(0,n) r=(r0+r1+r2+r3) c0=(pow(g,x0*x0,n) * pow(h,r0,n)) % n print (" \nc0=",c0) c1=(pow(g,x1*x1,n) * pow(h,r1,n)) % n print (" c1=",c1) c2=(pow(g,x2*x2,n) * pow(h,r2,n)) % n print (" c2=",c2) c3=(pow(g,x3*x3,n) * pow(h,r3,n)) % n print (" c3=",c3) commit1 = (c0*c1*c2*c3) % n print (" \nCheck1=",commit1) commit2 = (pow(g,x,n) * pow(h,r,n)) % n print (" Check2=",commit2) if (commit1==commit2): print(" Peggy has proven that her value is positive")