| ▲ | jeremysalwen 2 hours ago | |
To be honest I feel like I have seen much better expositions of zero knowledge proofs. The playing cards example is nice in some ways, but people are often exposed to trickery regarding playing cards. The recipient of the proof needs to verify that the deck of cards is a normal deck of cards, that no cards have been swapped out or altered, etc. These are all precisely the things that magicians are regularly able to fool people about. So really you have to make an additional assumption of "no funny business", which distracts from the mathematical core of what you are trying to demonstrate. Likewise, the example of compositeness is a bit off because even though there is knowledge about the composite number that the proof does not reveal, that knowledge is in fact not known the to person constructing the proof either! The proof is not really zero knowledge either, since it gives the reader knowledge of a specific witness to its compositeness. Even the wikipedia example of going into the cave (which used to be featured more prominently in the article) I think is terrible. Why wouldn't you just walk a loop to prove you know the way through the secret door? Also, it's clearly not zero knowledge, as it reveals some information about how quickly they can pass through the gate. In general I think avoiding physical examples is necessary, since reality is complicated, and in the real world some information always leaks. I think the best example for teaching about ZKPs is the graph isomorphism problem: Given two large graphs, you can prove that you know a isomorphism between two graphs by generating a new randomly labeled graph that is isomorphic to both of them and showing it to the provee, who can then ask you to demonstrate that this new graph is isomorphic to either graph A or graph B. Since you don't know ahead of time which one they will ask for, the only way you could consistently pass this test is if you actually do have a graph that was isomorphic to both A and B simultaneously. But since you only reveal one of the isomorphisms, it really is zero knowledge. | ||
| ▲ | andreareina an hour ago | parent [-] | |
My conclusion from watching a lot of Penn and Teller is that when you're invited to examine the deck it probably is normal and often the trick will involve a force. | ||