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.