How Do You Prove a Secret?

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?

To achieve this goal, Micali and Goldwasser added a third property to the two needed for an interactive proof: The proof should reveal nothing about the knowledge itself, only the truthfulness of the statement. “There is a notion of going through a protocol, at the end of which you believe that [the poker players] don’t know anything more than what they’re supposed to know,” said Goldwasser.

Let’s consider the classic example. Alice wants to prove to Bob that a certain graph G — a unique collection of vertices (dots) connected by edges (lines) — has a “Hamiltonian cycle.” This means the graph has a path that visits every dot exactly once and ends at the same dot it started from. Alice could do this by simply showing Bob the path that does this, but of course then he’d know the path too.

Here’s how Alice can convince Bob that she knows such a path exists, without showing it to him. First she draws a new graph, H, that doesn’t look like G but is similar in a crucial way: It has the same number of vertices, connected in the same ways. (If G really has a Hamiltonian cycle, this similarity means H will too.) Then, after covering every edge in H with masking tape, she locks H in a box and gives the box to Bob. This prevents him from seeing it directly but also prevents her from altering it. Then Bob makes a choice: Either he can ask Alice to show that H really is similar to G, or he can ask her to show him the Hamiltonian cycle in H. Both requests should be easy for Alice, assuming that H really is similar enough to G, and that she really does know the path.

Of course, even if Alice doesn’t know the Hamiltonian cycle in G, she can try to fool Bob, either by drawing graphs that aren’t similar to G, or by submitting graphs she doesn’t know the path for. But after they’ve played multiple rounds, the chance of Alice deceiving Bob every time becomes vanishingly small. If she gets everything right, eventually Bob will be convinced that Alice knows a Hamiltonian cycle in graph G, without Bob ever having seen it.

After the initial paper that first described such proofs, Micali and two mathematicians — Oded Goldreich and Avi Wigderson — discovered an unexpected consequence with far-reaching effects. It has to do with a major category of problems of roughly equal difficulty, known as NP. These problems are hard to solve, but their solutions are easy to verify. The three researchers found that, if truly secure encryption is possible, then the solution to every problem in NP can also be proved with a zero-knowledge proof. This study helped researchers conceive of variants of zero-knowledge proofs that don’t even require secure encryption in the first place; these are known as multi-prover interactive proofs.

And in 1988, Micali and others showed that if a prover and a verifier share a short string of random bits, no interaction is necessary. This theoretically meant that zero-knowledge proofs don’t have to be interactive, which would imply that constant communication between two parties isn’t necessary. This would make them much more useful to researchers, but it wasn’t until after the turn of the 21st century that such proofs took off.

“In the late 2000s, we started to see the evolution of efficient techniques for building zero-knowledge proofs,” said Matthew D. Green, a cryptographer at John Hopkins University. “We got to the point where we realized, ‘Wait a second, there might actually be a way to use this in practice.’”

Now a prover could send a single message to a verifier without both of them having to be online, and researchers could create a very short proof that could be quickly verified, even for very complicated problems. This has led to several practical uses, such as the ability to quickly verify the blockchain after a cryptocurrency transaction while hiding the details of the transaction. And in 2016, a group of physicists showed how zero-knowledge proofs can help with nuclear disarmament: Without revealing any secret about the design of its nuclear warhead, a country could now prove to nuclear inspectors whether the warhead is active or inactive.

More recently, advances in quantum computing have compelled Crépeau to stress-test past research to make sure zero-knowledge protocols are still viable. In 2021, he helped demonstrate that multi-prover interactive proofs do retain their secrecy even when quantum computers are involved, but achieving the same level of security makes the protocol much slower. The finding was good news, he said, but new concerns will arise as technology advances.

“Every type of computation we may do in the future will involve quantum computers,” said Crépeau. “So as good paranoid cryptographers, whenever we assess the security of a system, we want to make sure that our system is safe.”

Editor’s note: Shafi Goldwasser has received funding from the Simons Foundation, which also funds this editorially independent publication. Simons Foundation funding decisions have no influence on our coverage.