When Peggy Met Victor

When Peggy Met Victor

Zero Knowledge Proof (ZKP) with probabilistic encryption

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. Initially Peggy will select two large prime numbers (p and q), 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²=y (mod 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²=3 (mod 143)

The solution for this is x=126:

126²=3 (mod 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² (mod N)

2. Next Victor either sends Peggy a value of 0 or 1 (m∈{0,1}) as a challenge.

3. Peggy now calculates a value of z on sends it to Victor:

z=r (mod N), if m=0

z=xr (mod N), if m=1.

Then Victor calculates z² (mod N ) and does a check based on m:

z²=s (mod N), if m=0,

z²=ys (mod N), if m=1.

and where y is the secret that Peggy has registered.

The coding is here [sample]:

In this case we find the solution to the square root modulus with:

# Find solution to x^2 = y (mod N)
while (True):
	y=random.randint(5,1000) % N
        if (libnum.has_sqrtmod(y,{p: 1,q:1})):
		x=libnum.sqrtmod(y,{p: 1,q:1}).next()
		break

A sample run for m=0 [sample]:

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 [sample]:

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

In this case, Victor can prompt Peggy a number of times, and each time she proves she knows the secret, the more trust Victor will have in her. For n challenges, the chances of Peggy not being Peggy is 1 over 2^n. With three challenges, if Peggy produces the right proof, there is a 1 in 8 chance that she has guessed them by random.