With the Damgard-Fujisaki method, Peggy can provde to Victor that she can commit proofs that she has a value between \(a\) and \(b\), without revealing the value:
Zero-knowledge proof (Damgard-Fujisaki method) for a range proof |
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. 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\)
Now to prove the range, we take (x-a) and (b-x) and which should be positive values. Next we compute a commitment of:
\(c_1=g^{(b-x)}.h^{-r} \pmod n\)
and:
\(c_2=g^{(x-a)}.h^{r} \pmod n\)
To prove the commitments we take:
\(p_1=\frac{g^b}{c_1} \pmod n\)
and:
\(p_2=c_2.{g^a} \pmod n\)
and they 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 import libnum n=pow(2,19)-1 a=5 b=22 x=10 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) def positiveProof(x,r,n): if x<0: print("Cannot prove") sys.exit(0) x0,x1,x2,x3=lipmaa(x) r0=random.randint(0,n) r1=random.randint(0,n) r2=random.randint(0,n) r3=random.randint(0,n) r0=(r-r1-r2-r3) c0=(pow(g,x0*x0,n) * pow(h,r0,n)) % n c1=(pow(g,x1*x1,n) * pow(h,r1,n)) % n c2=(pow(g,x2*x2,n) * pow(h,r2,n)) % n c3=(pow(g,x3*x3,n) * pow(h,r3,n)) % n return(c0,c1,c2,c3) if (len(sys.argv)>1): x=int(sys.argv[1]) if (len(sys.argv)>2): a=int(sys.argv[2]) if (len(sys.argv)>3): b=int(sys.argv[3]) g=3 h=4 r=random.randint(0,n) print ("x=",x) print ("a=",a) print ("b=",b) print ("r=",r) c1_0,c1_1,c1_2,c1_3=positiveProof(b-x,-r,n) print ("\nb-x=",b-x) commit1=(c1_0*c1_1*c1_2*c1_3)%n c2_0,c2_1,c2_2,c2_3=positiveProof(x-a,r,n) print ("\nx-a=",x-a) commit2=(c2_0*c2_1*c2_2*c2_3)%n print ("\nCommit 1: ",c1_0,c1_1,c1_2,c1_3) print ("Commit 2: ",c2_0,c2_1,c2_2,c2_3) prover1 =(pow(g,b,n) * pow(commit1,-1,n)) % n prover2 =(commit2 * pow(g,a,n)) % n print ("Prover 1: ",prover1) print ("Prover 2: ",prover2) prover3 =(pow(g,x,n) * pow(h,r,n)) % n print ("Prover 3: ",prover3) if (prover1==prover2): print(" Peggy has proven that her value is between: ",a," and ",b) else: print(" Peggy has NOT proven that her value is between: ",a," and ",b) a=x+1 b=x+5 prover1 =(pow(g,b,n) * pow(commit1,-1,n)) % n prover2 =(commit2 * pow(g,a,n)) % n print ("Prover 1: ",prover1) print ("Prover 2: ",prover2) prover3 =(pow(g,x,n) * pow(h,r,n)) % n print ("Prover 3: ",prover3) if (prover1==prover2): print(" Peggy has proven that her value is between: ",a," and ",b) else: print(" Peggy has NOT proven that her value is between: ",a," and ",b)
A sample run shows:
x= 70 a= 20 b= 100 r= 302939 b-x= 30 x-a= 50 Commit 1: 8192 1536 5184 341773 Commit 2: 16384 1 262145 170605 Prover 1: 441705 Prover 2: 441705 Prover 3: 441705 Peggy has proven that her value is between: 20 and 100 Prover 1: 347636 Prover 2: 342720 Prover 3: 441705 Peggy has NOT proven that her value is between: 71 and 75