Zero-Knowledge Proofs

Proof as a Conversation

Encryption, signature, and key-exchange schemes share a common shape. A secret is used to derive a ciphertext, a signature, or a key, and that derived object is sent across the channel. The recipient learns the derived object, and the security argument is that the derived object leaks nothing useful about the secret.

This page asks a sharper question. Can one party convince another that it knows a secret, or that some assertion is true, while transmitting nothing beyond the single bit that the claim is true, not even an encryption or a function of the secret? The answer, which at first sounds paradoxical, is yes, and the mechanism that achieves it turns the very notion of a proof from a static object into an exchange.

Why Not Just Show the Secret

Consider the humble password. To prove she is authorized, a claimant sends her password to a verifier, who checks it against a stored record. The flaw is structural. The moment the verifier receives the password, he can impersonate the claimant to anyone else. The secret has been spent by being shown.

A first improvement is a challenge-response exchange. Rather than reveal the secret, the claimant answers a fresh, unpredictable question that only a holder of the secret could answer, and answers it in a way that cannot be replayed. This is better, because the secret itself never crosses the wire, but it is not yet enough. Each response may still leak a sliver of information about the secret, and an adversarial verifier, free to choose the questions, might select them precisely to accumulate those slivers until the secret is reconstructed.

What we want is a stronger guarantee: that the claimant can respond to challenges indefinitely, and the verifier, however cleverly he chooses them, ends the exchange knowing nothing he could not have worked out alone before it began. To reach that guarantee we must first change what a proof is.

Interactive Proof Systems

The traditional notion of a mathematical proof is a fixed string of symbols, checkable by anyone, and absolute in that it establishes its conclusion with certainty. We replace it with something looser and, for this purpose, more powerful. An interactive proof is a conversation between a prover, who asserts that some statement is true, and a verifier, who interrogates the prover across several rounds and then decides whether to accept. The prover's messages depend on private randomness, and the verifier's challenges depend on his own. The proof is no longer a document but a protocol, and for this reason it is sometimes called a proof by protocol.

Trading certainty for a probability that can be pushed as near to \(1\) as desired is what buys the new capability. A written proof, being a fixed object, can be copied and shown onward. A conversation conducted with fresh randomness on both sides cannot be replayed to convince a third party, and it is exactly this non-transferability that will make zero knowledge possible.

Interactive proofs used for identification carry a particular reading, in which the prover asserts not merely that some object exists but that it possesses knowledge of one. Proving knowledge of a secret is a stronger claim than proving the secret exists. Demonstrating that one knows the prime factors of a number, for instance, says more than observing that the number is composite. Making that stronger claim precise is the task of the next section.

Completeness and Soundness

Two properties make an interactive proof worth the name. The first says that the protocol works when everyone is honest, and the second says that it cannot be cheated. Together they capture what it means to prove knowledge of a secret, as opposed to merely asserting it.

Completeness is the routine requirement that honest participants succeed. Soundness carries the weight. Its formulation through an extractor is what elevates the protocol from a proof that some object exists to a proof that the prover knows it. Because the secret can be read out of any successful prover, no strategy convinces the verifier without, in effect, encoding the secret.

Hardness Is Not Optional

There is a subtlety that the definitions alone conceal, and it connects this construction to everything the cryptography track has assumed. Completeness and soundness are statements about the protocol, and neither, on its own, says the scheme is secure. A proof of knowledge certifies that whoever passes must possess the secret. If the secret can be computed from the public data by anyone, however, possessing it is no achievement, and the protocol proves nothing of value. The guarantee is meaningful only when the underlying problem the prover's secret solves is computationally hard.

Concretely, the secret is chosen as the solution to an instance of a problem believed intractable. An example is a square root modulo a composite whose factorization is unknown. No efficient method is known to compute such a root. Then computing the secret from public information is infeasible, so the ability to answer the protocol's challenges is genuine evidence of knowledge rather than of public computation.

This dependence is not a defect but the crux. Like every scheme in this track, an interactive proof rests on a conjectured hardness assumption, and its guarantees are exactly as strong as that assumption. On top of the hardness, the protocol adds the next property, which lets knowledge of the secret be demonstrated without surrendering any part of it.

The Zero-Knowledge Property

Completeness and soundness make the protocol a proof of knowledge, but they say nothing about what the verifier learns along the way. A protocol could be a perfect proof of knowledge and still leak the secret outright, because soundness constrains the dishonest prover, not the curious verifier. The property that closes this gap, and gives the construction its name, is a demand on the conversation itself: that it teach the verifier nothing.

Simulation as the Measure of Knowledge

The difficulty is to say precisely what "nothing" means. The verifier plainly ends the protocol knowing one new thing, namely that the assertion is true. How can we certify that he learns only that, and nothing about the secret behind it? The resolution reuses an idea already central to the definition of semantic security on an earlier page. There, a scheme was declared to leak nothing if a simulator, denied the ciphertext, could reproduce whatever an adversary computed from it. A ciphertext that can be dispensed with carries nothing. The same move works here, applied to the entire transcript of the conversation.

The correspondence with the earlier secrecy definition is exact. The secret plays the role the plaintext played, and the transcript the role the ciphertext played. In both, what can be fabricated from public data alone reveals nothing private.

One consequence is worth drawing out, because it explains why the proof must be a live, interactive exchange and cannot be a transferable document. Suppose an observer records a complete protocol run, every message between prover and verifier, and later replays the recording to a third party. The replay convinces that third party of nothing. The simulator establishes why. An indistinguishable recording could have been produced by the verifier alone, with no prover present, so the recording is not evidence that any prover took part. A proof of this kind convinces only the party who is live in the exchange, issuing fresh, unpredictable challenges in real time. This is the non-transferability promised earlier, now seen to be not an incidental feature but the direct expression of the zero-knowledge property.

Two Grades of Indistinguishability

The definition turns on transcripts being "indistinguishable," and we distinguish two grades of this, according to how severely one is permitted to compare the real and simulated distributions.

With completeness, soundness, and zero knowledge in hand, the notion of a zero-knowledge proof is complete. What remains is to exhibit one: a concrete protocol, resting on a concrete hardness assumption, in which all three can be seen at work.

A Concrete Protocol

One of the earliest and most transparent zero-knowledge identification schemes rests on the difficulty of extracting square roots modulo a composite of unknown factorization. It shows the three abstract properties as concrete arithmetic, and its structure recurs in a large family of later protocols: commit, challenge, respond.

Setup and Protocol

A trusted party publishes a modulus \(n = pq\), the product of two distinct odd secret primes, and keeps the factorization private. A prover \(A\) chooses a secret \(s\) coprime to \(n\) and registers the public value \(v = s^2 \bmod n\). Her secret is thus a square root of \(v\). Recovering \(s\) from \(v\) means extracting a square root modulo \(n\), which is as hard as factoring \(n\). An algorithm that extracts square roots modulo \(n\), applied to \(w^2\) for a random \(w\) coprime to \(n\), returns a root other than \(\pm w\) with probability \(1/2\), because it sees only \(w^2\) and \(w\) is equally likely to be any of its four square roots. Such a root reveals a factor of \(n\) by the gcd computation in the soundness argument below.

Each round is a three-message exchange between the prover \(A\) and a verifier \(B\), consisting of a commitment (or witness) from the prover, a one-bit challenge from the verifier, and the prover's response: \[ \begin{align*} A \to B &: \quad x = r^2 \bmod n \\\\ A \leftarrow B &: \quad e \in \{0, 1\} \\\\ A \to B &: \quad y = r\, s^{e} \bmod n \end{align*} \] where \(r\) is a fresh value coprime to \(n\) that the prover draws uniformly at random each round. The verifier accepts the round if \(y \neq 0\) and \[ y^2 \equiv x\, v^{e} \pmod{n}. \] The whole protocol repeats this round \(t\) times, and \(B\) accepts \(A\)'s identity only if all \(t\) rounds succeed.

An honest prover passes the check, because modulo \(n\) we have \[ \begin{align*} y^2 &= r^2 s^{2e} \\\\ &= x\,(s^2)^{e} \\\\ &= x\,v^{e}. \end{align*} \] This is completeness. The two challenge values ask two different questions of the prover. At \(e = 0\) she must produce a square root of the commitment \(x\) itself, namely \(r\). At \(e = 1\) she must instead exhibit a square root of \(x v\), namely \(rs\). Only a prover who knows \(s\) can answer both, and this is the seed of soundness.

Why It Is Sound, and Zero-Knowledge

Soundness appears the moment one asks what it would take to answer both challenges for a single commitment. Suppose a prover, having sent \(x\), could respond correctly to both \(e = 0\) with some \(y_0\) and \(e = 1\) with some \(y_1\). We may assume that \(y_0\) is coprime to \(n\). Otherwise \(\gcd(y_0, n)\) is a nontrivial factor of \(n\), and the prover has broken factoring outright. Then \(y_0^2 \equiv x\) and \(y_1^2 \equiv xv \pmod n\), so \(y_1^2 / y_0^2 \equiv v\), which means \(y_1 / y_0\) is a square root of \(v\). A modulus \(n = pq\) has four square roots of \(v\), so this need not be the prover's original \(s\). Any square root, however, serves as the secret being proved. Should it be one of the two roots other than \(\pm s\), it moreover betrays the factorization of \(n\) to anyone who also holds \(s\), since then \(\gcd(y_1/y_0 - s,\, n)\) is a nontrivial factor. Either way the extractor reads a genuine square root out of such a prover. It obtains the two responses by running the prover up to its commitment and asking \(e = 0\), then resetting the prover to that point and asking \(e = 1\). Showing that a prover who succeeds noticeably more often than \(2^{-t}\) yields such a pair with non-negligible probability requires a probability estimate that is beyond the scope of this page.

A cheat holding no square root can prepare a commitment that answers only one of the two challenges. The cheat either picks \(r\) and sets \(x = r^2\) (ready for \(e = 0\)), or picks \(r\) and sets \(x = r^2 v^{-1}\) (ready for \(e = 1\)). But no single commitment is good for both. Such a cheat therefore survives a single round with probability exactly \(1/2\), by guessing which challenge will come, and survives all \(t\) rounds with probability only \(2^{-t}\), driven as low as desired by taking \(t\) large.

Zero knowledge is the claim that a full transcript teaches the verifier nothing about \(s\), and the argument is the simulator of the previous section made concrete. A verifier who knows in advance which challenge \(e\) he will issue can manufacture a valid transcript with no prover and no secret. He picks the response \(y\) uniformly at random among the residues coprime to \(n\) and defines the commitment backward as \(x = y^2 v^{-e} \bmod n\). By construction this triple satisfies \(y^2 \equiv x v^{e}\), so it passes verification, and the pair \((x, y)\) it produces is distributed exactly as in a real run, because the real protocol also yields a uniform \(y\) and a commitment determined by that \(y\). Since the verifier can generate indistinguishable transcripts alone, the real ones give him nothing he could not already fabricate.

The response \(y = r\) at \(e = 0\) is a random value independent of \(s\), while the response \(y = rs\) at \(e = 1\) is masked by the fresh random \(r\), which \(B\) never learns. No information about \(s\) survives the exchange.

The simulator just described handles a verifier whose challenge does not depend on the commitment, as is the case for the honest verifier, who draws \(e\) uniformly at random. The definition of the zero-knowledge property compared simulated transcripts with runs of the prescribed verifier. Its stronger form asks for a simulator against every efficient verifier strategy, including one that chooses \(e\) after seeing the commitment. Such a verifier is handled by a refinement. The simulator guesses the challenge, produces a transcript for that guess, and, if the verifier's actual challenge differs, resets the verifier and tries again. The simulated commitment is a uniformly random square coprime to \(n\) whichever challenge was guessed, so the verifier's choice is independent of the guess, and each guess is correct with probability \(1/2\). About two attempts per round therefore suffice on average, and the zero-knowledge property holds in this stronger form, not only against a cooperative verifier.

One caution keeps this in step with the rest of the track. The square-root protocol borrows its hardness from factoring, and factoring is exactly the assumption a quantum period-finding algorithm is known to dissolve. The same collapse unseated the classical public-key schemes. A scheme resting on factoring inherits that exposure. What survives is not this particular instance but the framework around it. Completeness, soundness, and the zero-knowledge property are defined for any underlying hard problem, and the commit-challenge-response skeleton re-instantiates on assumptions believed to resist quantum attack. Lattice problems are among these assumptions. Against a quantum adversary, replacing the square root is not the whole task, because the simulator and the extractor both reset the other party, and that resetting must itself be re-justified in the quantum setting.

The distance from a password handed across a wire to a proof that convinces while revealing nothing is the distance this page has traveled. A proof became a conversation. The conversation acquired completeness and soundness, which made it a proof of knowledge. The demand that it be simulatable then made it zero-knowledge, so that conviction and concealment, seemingly opposed, hold at once. The square-root protocol is the smallest complete illustration of how they can.