Zero-knowledge proofs allow researchers to prove their knowledge without divulging the knowledge itself.
Imagine you had some useful knowledge — maybe a secret recipe, or the key to a cipher. Could you prove to a friend that you had that knowledge, without revealing anything about it? Computer scientists proved over 30 years ago that you could, if you used what’s called a zero-knowledge proof.
For a simple way to understand this idea, let’s suppose you want to show your friend that you know how to get through a maze, without divulging any details about the path. You could simply traverse the maze within a time limit, while your friend was forbidden from watching. (The time limit is necessary because given enough time, anyone can eventually find their way out through trial and error.) Your friend would know you could do it, but they wouldn’t know how.
Zero-knowledge proofs are helpful to cryptographers, who work with secret information, but also to researchers of computational complexity, which deals with classifying the difficulty of different problems. “A lot of modern cryptography relies on complexity assumptions — on the assumption that certain problems are hard to solve, so there has always been some connections between the two worlds,” said Claude Crépeau, a computer scientist at McGill University. “But [these] proofs have created a whole world of connection.”
Zero-knowledge proofs belong to a category known as interactive proofs, so to learn how the former work, it helps to understand the latter. First described in a 1985 paper by the computer scientists Shafi Goldwasser, Silvio Micali and Charles Rackoff, interactive proofs work like an interrogation: Over a series of messages, one party (the prover) tries to convince the other (the verifier) that a given statement is true. An interactive proof must satisfy two properties. First, a true statement will always eventually convince an honest verifier. Second, if the given statement is false, no prover — even one pretending to possess certain knowledge — can convince the verifier, except with negligibly small probability.
Interactive proofs are probabilistic in nature. The prover could answer one or two questions correctly simply by luck, so it takes a large enough number of challenges, all of which the prover must get right, for the verifier to become confident that the prover does in fact know the statement is true.
This idea of interactions came when Micali and Goldwasser — then graduate students at the University of California, Berkeley — puzzled through the logistics of playing poker over a network. How can all players verify that when one of them gets a card from the virtual deck, the result is random? Interactive proofs could lead the way. But then, how can players verify that the entire protocol — the full set of rules — was followed correctly, without revealing every player’s hand along the way?
posted by f.sheikh