ezyang's blog

the arc of software bends towards understanding

Interactive Demo of Zero-Knowledge Proofs

December 17, 2011

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.)

image

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 Comments

  1. Sami Liedes
    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
    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
    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.