May 28, 2011

A network zero knowledge proof implementation.

Tonight I’m attempting to clean up some C programming I did using Daniele Raffo’s Feige-Fiat-Shamir zero knowledge proof implementation found herewhich I’ve created a derivative work and posted here.  I contacted Daniele to ask what license he had used on his implementation and heard back from him today that it was GPL’d.  So there’s no problem working on that code now.

A zero knowledge proof is one where one party proves to another that they have knowledge or information without disclosing any of that information.  The classic example involves two people, Bob and Alice, where Bob wants Alice to prove she knows a password.  The password happens to open a locked door in the center of a circular path in the back of a cave.  Bob sends Alice through the entrance, without watching which side (left or right) she goes down.  He then shouts from the entrance for Alice to come out on either the left, or right side.

Alice randomly picks to go down side A or B.

Suppose Alice goes down path A, and Bob asks her to come out on path A.  Then even if Alice doesn’t know the password to open the door in the back center of the cave, Bob will see her come out on the path he asked.  However, if Alice comes out on path B, Bob knows she did not know the password to go through the door in the back to come out on the correct side.  Each time Bob asks Alice to come out on one path or the other, his confidence that Alice knows the password grows.  It’s possible, though increasingly improbable, that Alice will randomly go down every path Bob later asks her to come back out of, and may not in fact know the password.  After a certain point the confidence Bob has in Alice’s knowledge is sufficient for him to believe she knows the password.

The benefit to this authentication scheme is that the password is never exchanged between Bob and Alice.  Even though Alice may not know the password, after Bob asks her to prove her knowledge of the password a sufficient number of times, it is statistically unlikely she does not know the password.  You can read more about ZKP here, on Wikipedia (They use Peggy and Victor).

My implementation needs a bit of work.

 

Network ZKP

Network ZKP (broken)

© Andrew J. Duncan 2016