Feige-Fiat-Shamir and Zero Knowledge Proof

Why do we still pass our passwords over a network? Why do we still hash passwords? Why can’t we come up with our own random value, and then prove to everyone that we know the secret?

Well, the Feige-Fiat-Shamir method provides a zero-knowledge proof — created by Uriel Feige, Amos Fiat, and Adi Shamir in 1988 [paper] — and where Bob can prove something to Alice, without revealing the information that he has.

First Peggy (the prover) and Victor (the verifier) agree on two prime numbers (say 101 and 23), and calculate a value of N (101𝗑23), to give N=2,323.

Peggy has three secret numbers of s1=5; s2=7; and s3=3. Note that these numbers need to be co-prime to N, so that they do not share a factor with n. If we choose N as the multiplication of two prime numbers, we only need to avoid these numbers.

Now Victor generates three random numbers which are either 0 or a 1, such as a1=1; a2=0; and a3=1, and sends these to Peggy.

Next Peggy generates a random number (such as r=13). She then calculates a value of x which is:

x = (r^2) % n

which gives x = 169. Peggy sends this to Victor.

Peggy calculates:

y1 = (r * ((s1^a1) * (s2^a2) * (s3^a3)) ) % n