ezyang’s blog

the arc of software bends towards understanding

Interactive Demo of Zero-Knowledge Proofs

For the final project in our theoretical computer science and philosophy class taught by Scott Aaronson, Karen Sittig and I decided to create an interactive demonstration of zero-knowledge proofs. (Sorry, the picture below is not clickable.)

/img/interactive-zk.png

For the actually interactive demonstration, click here: http://web.mit.edu/~ezyang/Public/graph/svg.html (you will need a recent version of Firefox or Chrome, since we did our rendering with SVG.)

3 Responses to “Interactive Demo of Zero-Knowledge Proofs”

  1. Sami Liedes says:
    December 17, 2011 at 6:00 pm

    I don’t understand. Since the prover is allowed to mix up the colorings between choices, how does this prove anything? What would prevent the prover from cheating by just revealing two random different colors every time?

  2. Edward Z. Yang says:
    December 17, 2011 at 6:19 pm

    Right. So the key assumption is that in a real instance of the protocol, the prover has to *commit* to some color before the user makes any choice. The usual metaphor is that the prover puts all of his colors in locked boxes which he gives to the user, the user picks two, and then he sends the keys for just those two boxes, which the user can then use to check.

  3. Anonymous says:
    December 25, 2011 at 9:50 pm

    Are you sure in the question you correctly gave the equation for confidence?
    It seems that the program is using 1-((E-1)/E)^n, but you put 1-(1/E)^n there.

Leave a Comment