Introduction

It’s 2 AM and you’re locked out of your email account. The system asks you to prove your identity by entering your password. You type it in, hit enter, and hope the server isn’t compromised. Even if the connection is encrypted, even if the password is hashed, you’ve just revealed your secret to another computer. If that server gets hacked tomorrow, or if a malicious employee decides to peek at the database, your credential is exposed. For decades, this seemed like an unavoidable tradeoff: to prove you know something, you must reveal it.

In 1985, three researchers - Shafi Goldwasser, Silvio Micali, and Charles Rackoff - published a paper that would fundamentally challenge this assumption. Their work introduced the concept of zero-knowledge proofs (ZKPs): protocols that allow you to convince someone that a statement is true without revealing anything about why it’s true or how you know it. The idea was so counterintuitive that the paper kept being rejected by multiple major conferences for 3 years. It would later earn them the first ever Gödel Prize.

Imagine logging into that email account without ever transmitting your password, not even in encrypted form. You simply convince the server that you possess the correct password, and the server becomes certain you’re legitimate, yet learns nothing about the password itself. This isn’t science fiction. This is what zero-knowledge proofs make possible.

What is a proof, anyway?

Before we can understand zero-knowledge proofs, we need to step back and ask a more fundamental question: what is a proof?

Throughout our education, we’ve written countless proofs—on exams, in problem sets, in essays. Informally, a proof is something uttered by someone (the “prover”) aiming to convince someone else (the “verifier”) of the veracity of some statement. To formalize this, we can imagine there’s some set $L \subseteq \{0,1\}^*$ (called a language in complexity theory), collecting all objects satisfying some relevant property. The prover’s goal is to convince the verifier that some string $x$ belongs to $L$.

You’ve probably encountered the complexity class NP before. Intuitively, NP captures languages that admit short, deterministic, non-interactive, and efficiently-checkable proofs. Think of a Sudoku puzzle: verifying a solution takes seconds, but finding it might take hours. The solution itself serves as a witness that the puzzle is solvable.

But what happens if we relax these assumptions? What if we allow the prover and verifier to interact back and forth, exchange multiple messages, and use randomness (and a small probability of error) on the verifier’s side? This leads us to the notion of interactive proofs.

Interactive proofs

Fix a language $L$ and some string $x \in \{0,1\}^*$. In an interactive proof system, a computationally-unbounded prover $\mathcal{P}(x)$ and a Probabilistic Polynomial Time (PPT) verifier $\mathcal{V}(x)$ exchange messages back and forth. The prover’s goal is to convince $\mathcal{V}$ that $x \in L$. At the end of the interaction, $\mathcal{V}$ outputs a bit $b$: output $b = 1$ means $\mathcal{V}$ believes $x \in L$, while $b = 0$ means $\mathcal{V}$ remains unconvinced.

Of course, for this interaction to be interesting we need some basic properties:

Completeness: If $x$ truly belongs to $L$, then an honest prover should be able to convince the verifier. Formally, for any $x \in L$, we require $\Pr[\text{output}_\mathcal{V}(\mathcal{P}(x),\mathcal{V}(x))=1]=1$.

Soundness: If $x$ does not belong to $L$, then no prover—even a computationally unbounded cheating prover $\mathcal{P}^*$—should be able to convince the verifier, except with small probability. Formally, for any $x \notin L$ and any prover $\mathcal{P}^*$, we require $\Pr[\text{output}_\mathcal{V}(\mathcal{P}^*(x),\mathcal{V}(x))=1] \leq 1/2$.

Why bound the soundness error by 1/2? Because we can always reduce this error exponentially by repeating the protocol multiple times with fresh randomness. After $k$ repetitions, a cheating prover succeeds with probability at most $2^{-k}$.

We denote by IP the class of languages that admit complete and sound interactive proofs. It turns out that IP is surprisingly powerful. In fact, IP = PSPACE, meaning interactive proofs can verify any computation that uses polynomial space, even if it takes exponential time.

The zero-knowledge property

We still haven’t defined what it means for a protocol to be “zero-knowledge.” Intuitively, a protocol should be zero-knowledge if the verifier learns nothing beyond the validity of the statement itself. More precisely, when the statement is true, the interaction gives $\mathcal{V}$ nothing that they couldn’t have computed on their own without ever talking to $\mathcal{P}$.

To formalize this, we use a simulation paradigm. The idea is elegant: if the verifier could have simulated the entire interaction by themselves, then the interaction couldn’t have taught them anything new. Consider the complete record of all messages exchanged during the protocol, we call this the transcript. We capture the simulation paradigm by requiring the existence of an efficient simulator $S$ that, given only the input $x$, can produce a transcript that is computationally indistinguishable from a real interaction between $\mathcal{P}$ and $\mathcal{V}$.

Crucially, the simulator doesn’t know any witness proving that $x \in L$. For NP languages, for instance, the simulator has no access to a certificate or solution, it only knows the statement $x$ itself. This means a zero-knowledge proof reveals no information about why $x \in L$, only that $x \in L$.

There’s one more subtlety: a dishonest verifier might deviate from the protocol in an attempt to extract some information. Imagine that someone, instead of following the prescribed steps, asks unexpected questions or responds in unusual ways, hoping to trick the prover into revealing the secret witness. Our definition must account for this possibility.

Let $\text{view}_{\mathcal{V}}(\mathcal{P}(x),\mathcal{V}(x))$ denote the verifier’s view in an interactive protocol, that is, everything the verifier observes during the execution, including all messages received and all random coins flipped.

We define an interactive protocol between a prover $\mathcal{P}$ and a PPT verifier $\mathcal{V}$ for a language $L$ to be perfectly zero-knowledge if for any PPT verifier $\mathcal{V}^*$ (even a malicious one deviating from the protocol), there exists a PPT simulator $S$ such that for any $x \in L$, the random variables $S(x)$ and $\text{view}_{\mathcal{V}^*}(\mathcal{P}(x),\mathcal{V}^*(x))$ are identically distributed.

This definition captures our intuition: no matter how the verifier behaves, they learn nothing they couldn’t simulate themselves.

The power of zero-knowledge

It’s easy to see that every language in P (the class of problems solvable in polynomial time) has a trivial zero-knowledge proof: the prover and verifier can both just compute the answer themselves, and no interaction is needed.

But what about NP? Do all NP languages have zero-knowledge proofs? This seems much harder. After all, for an NP language, the verifier cannot efficiently determine membership on their own, they need a witness. How could we possibly prove membership without revealing information about that witness?

Remarkably, the answer is yes (assuming one-way functions exist). In a seminal result, Goldreich, Micali, and Wigderson proved that every language in NP has a zero-knowledge interactive proof. This was a stunning discovery: problems that seem to fundamentally require revealing a solution can actually be proven without revealing anything at all.

There is one catch: we must relax our notion of zero-knowledge slightly. Perfect zero-knowledge (where the simulated and real distributions are identical) is too strong. In fact, if all NP languages have perfect zero-knowledge proofs, then the polynomial hierarchy collapses, a consequence considered highly unlikely by most complexity theorists. Instead, the GMW protocol achieves computational zero-knowledge, where the simulated and real distributions are indistinguishable to any efficient algorithm.

An example: Graph Isomorphism

Let’s see zero-knowledge in action with a concrete example: the graph isomorphism problem. Two graphs $G_0$ and $G_1$ on $n$ vertices are isomorphic if there exists a permutation $\pi : [n] \to [n]$ such that applying $\pi$ to the vertices of $G_0$ produces exactly $G_1$. The graph isomorphism problem asks: given $G_0$ and $G_1$, are they isomorphic?

Here’s a zero-knowledge protocol for proving that two graphs are isomorphic. Let $\pi^1 : [n] \to [n]$ be the isomorphism satisfying $G_0 = \pi^1(G_1)$, and let $\pi^0$ denote the identity permutation.

1. The prover $\mathcal{P}$ samples a uniformly random permutation $\pi^* : [n] \to [n]$ and sends $G = \pi^*(G_0)$ to the verifier $\mathcal{V}$.
2. The verifier $\mathcal{V}$ samples a random bit $b \in \{0, 1\}$ and sends $b$ to $\mathcal{P}$.
3. The prover $\mathcal{P}$ responds with $\sigma = \pi^* \circ \pi^b$ (the composition of $\pi^*$ and $\pi^b$).
4. The verifier $\mathcal{V}$ accepts (outputs 1) if and only if $\sigma(G_b) = G$.

In words: the prover sends a random permutation of $G_0$ to the verifier. The verifier then randomly challenges the prover to either (a) show how to get from $G_0$ to $G$ (if $b=0$), or (b) show how to get from $G_1$ to $G$ (if $b=1$). If the graphs are truly isomorphic, the prover can answer either challenge. If they’re not isomorphic, the prover can answer at most one of the two challenges.

You might wonder: why does the verifier need to make this random choice? Why not always send $b = 1$ (asking for a permutation from $G_1$ to $G$)? The reason is soundness against dishonest provers. If $\mathcal{V}$ always sent $b = 1$, a cheating prover could simply send a random permutation of $G_1$ as $G$ in step 1, and they’d always pass the test even if $G_0$ and $G_1$ aren’t isomorphic. The randomness prevents this attack.

The Nikhef Protocol

Zero-knowledge proofs have revolutionized modern cryptography, enabling private authentication, anonymous credentials, and verifiable computation. But perhaps their most valuable application remains tragically theoretical: proving to your friends you’re actually being productive in the MoL room without revealing the number of trips to Nikhef it took to get there.

The protocol would work as follows: you convince your friends you’re being productive (completeness), while revealing nothing about your coffee consumption (zero-knowledge). Your friends are entirely satisfied with your work ethic, yet learn nothing about your Nikhef visit count. Unfortunately, the protocol breaks down when they ask about your progress and your response time is polynomial in the number of espressos required to process the question.

There’s also a soundness problem: if you haven’t actually been to Nikhef, no amount of cryptographic cleverness can simulate genuine productivity. A dishonest prover attempting this protocol will be caught with probability approaching 1 as the day progresses. The simulator, of course, can generate transcripts of perfect productivity without any coffee at all, but the simulator has the ability to rewind time, which would be far more useful for getting extra sleep than for faking work.

In conclusion: zero-knowledge proofs can hide what you know, but they can’t create knowledge you don’t have. And they definitely can’t replace coffee. For that, you’ll still need to make the trip to Nikhef :)