In this method we have Peggy (the Prover) and Victor (the Verifier), and where Peggy will prove to Victor that she still knows a secret. In this case, Victor will challenge Peggy to prove her identity by showing that she knows a given secret. This will use probablistic encryption for zero knowledge proof. We will prove that Peggy knows \(x^2 = y \pmod N\), and where \(N=pq\):
Interactive ZKP With Probablistic Methods |
Outline
In this method we have Peggy (the Prover) and Victor (the Verifier), and that Peggy still knows a value of \(y\). Initially Peggy will select two large prime numbers (\(p\) and \(p\)), and then publish their product at \(N\):
\(N=pq\)
Now Peggy has a secret \(y\), and then finds a value of \(y\) which satisfies this:
\(x^2=y \pmod N\)
For example, if \(y= 3\) and \(p=11, q=13\), then \(N=143\). Now we need to find the value of \(x\) for:
\({x}^2 = 3 \pmod{143}\)
The solution for this is \(x=126\):
\({126}^2 = 3 \pmod{143}\)
Now each time Peggy wants to prove that she knows \(y\), she performs the following:
1. Peggy create a random number (\(r\)) and computes:
\(s=r^2 \pmod {N}\)
2. Next Victor either sends Peggy a value of 0 or 1 (\(m \in \{{0,1}\}\)) as a challenge.
3. Peggy now calculates a value of \(z\) on sends it to Victor:
\( z = \begin{cases} r \pmod N, & \text{if } m = 0, \\ xr \pmod N, & \text{if } m = 1. \end{cases} \)
Then Victor calculates \(z^2 \pmod N\) and does a check based on \(m\):
\( z^2 = \begin{cases} s \pmod N, & \text{if } m = 0, \\ ys \pmod N, & \text{if } m = 1. \end{cases} \)
and where \(y\) is the secret that Peggy has registeredCoding
The coding is here:
import sys import random import libnum p=11 q=13 m=0 if (len(sys.argv)>1): m=int(sys.argv[1]) if (len(sys.argv)>2): p=int(sys.argv[2]) if (len(sys.argv)>3): q=int(sys.argv[3]) N=p*q r=random.randint(5,1000) % N s=r**2 % N # Find solution to y^2 = x (mod N) while (True): y=random.randint(5,1000) % N if (libnum.has_sqrtmod(y,{p: 1,q:1})): x=next(libnum.sqrtmod(y,{p: 1,q:1})) break print("x=",x) print("y=",y) print("N=",N) print("\nr=",r) if (m==0): z=r % N else: z=x*r % N res = z**2 % N print("\nz=",z) print("z^2 (mod N)=",res) print("s (mod N)=",s%N) print("ys (mod N)=",y*s%N) if (res == (s%N)): print("\nProof: 0") elif (res==y*s%N): print("\nProof: 1")
A sample run is:
p= 53 q= 59 m= 0 We create a random secret (y) y= 311 x= 1243 N= 3127 r= 367 z= 367 z^2 (mod N)= 228 s (mod N)= 228 ys (mod N)= 2114 Proof: 0
And for a proof for m=1:
p= 53 q= 59 m= 1 We create a random secret (y) y= 626 x= 761 N= 3127 r= 223 z= 845 z^2 (mod N)= 1069 s (mod N)= 2824 ys (mod N)= 1069 Proof: 1