Sigma Protocols: Zero-Knowledge Proofs to Digital Signatures

Alice has a secret: a number $x$. She has done one computation with it, raising a fixed group element $g$ to the $x$-th power, and published the result $u=g^x$. The world sees $u$. Only Alice knows $x$.

Now Alice wants to prove to Bob, over a public wire, that she knows $x$, without sending it, and without anyone eavesdropping on an honest run, now or later, with any computation they like, learning anything about $x$ beyond what $u$ already reveals. This sounds impossible. How do you prove you have a secret without giving any of it away?

There is a three-message conversation that does it: the Schnorr identification protocol. What it is, why it works, and what it teaches you about every modern proof system.

The setup#

We work in a cyclic group $G$ of prime order $q$ with a fixed generator $g$: the elements are $g^0,g^1,g^2,\cdots ,g^{q-1}$, and then it wraps around. Multiplying elements adds exponents mod $q$; raising to a power multiplies them. That is the only algebra we need.

The hardness assumption: pick $x$ uniformly at random mod $q$ and compute $u=g^x$. Recovering $x$ from $u$ is the discrete logarithm problem, and in well-chosen groups, elliptic curves in modern practice, the best classical algorithm known takes time exponential in the bit length of $q$. Fifty years of cryptanalysis have not produced a polynomial-time attack.

One caveat: all of this is about classical computation. Shor's algorithm, on a large fault-tolerant quantum computer, recovers discrete logs in polynomial time, so Schnorr, like ECDSA, RSA, and every signature deployed at scale today, is a pre-quantum scheme. Take what follows as the cleanest prototype of how proof systems work, not as the right tool for a multi-decade secret.

Three messages#

Move one: Alice picks a fresh random $r$ mod $q$, keeps it secret, and sends the commitment $R=g^r$. Move two: Bob picks a random challenge $c$ mod $q$ and sends it. Move three: Alice sends the response $s=r+cx$ mod $q$. Bob accepts if and only if

$$g^s=R·u^c.$$

That shape, commit, challenge, respond, is why this family is called sigma protocols. Three properties earn it.

The first, completeness, is one line: if Alice is honest then $g^s=g^{r+cx}=g^r·(g^x{)}^c=R·u^c$, exactly what Bob checks. An honest Alice always convinces Bob.

The extractor#

Now the hard direction. Suppose a cheater with no secret somehow convinces Bob. The central observation: imagine the cheater can answer two different challenges on the same first message $R$. Both transcripts verify, so

$$g^s=R·u^c\text{and}{g}^{s^{\prime }}=R·u^{c^{\prime }}.$$

Divide the equations: $g^{s-s^{\prime }}=u^{c-c^{\prime }}$. Since $u=g^x$, matching exponents gives $s-s^{\prime }=(c-c^{\prime })x$ mod $q$, and because $q$ is prime, $c-c^{\prime }$ has an inverse, so

$$x=\frac{s-s^{\prime }}{c-c^{\prime }}\left(\text{mod}q\right).$$

Two transcripts with the same commitment and different challenges contain the secret. And we can get two such transcripts from any successful cheater by rewinding him: save his state right after he sends $R$, feed him a fresh challenge, and rerun until he succeeds again. If he convinces Bob with non-negligible probability, this takes polynomially many tries.

This algorithm is the extractor: it uses the cheater as a subroutine and outputs his "secret." If some efficient algorithm could convince Bob without knowing $x$, the extractor would compute discrete logs efficiently, and we assume nobody can. So cheating at Schnorr is breaking discrete log. This is knowledge soundness: the prover doesn't just show the statement is true, she shows she knows a witness.

Pause and try: where exactly did the proof use that $q$ is prime?

In the division. From $s-s^{\prime }=(c-c^{\prime })x$ mod $q$ we need to multiply both sides by the inverse of $c-c^{\prime }$. When $q$ is prime, every nonzero residue mod $q$ is invertible, and $c-c^{\prime }$ is nonzero because the challenges differ. With composite $q$, an unlucky $c-c^{\prime }$ could share a factor with $q$ and have no inverse, and the extraction would jam at the last step.

The simulator#

The privacy direction. "Leaks nothing" has a precise meaning: the verifier could have produced the conversation himself. There is a simulator that, given only the public $u$, outputs transcripts with the same distribution as real ones. For Schnorr it is three lines: sample $c$ uniformly, sample $s$ uniformly, set $R=g^s·u^{-c}$, output $(R,c,s)$.

The transcript verifies by construction. And the distribution is identical to a real run: in the real protocol $r$ is uniform and independent of everything else, so $s=r+cx$ is uniform too, and given $c$ and $s$ the commitment is forced to be $R=g^s·u^{-c}$, the same formula the simulator uses. Not computationally indistinguishable, not statistically close: identical. This argument assumes Bob picks $c$ honestly at random, so the property is called honest-verifier zero knowledge, and within that assumption it is perfect.

But wait. The simulator just made an accepting transcript without $x$. Why doesn't that break the protocol? Move order. Real Alice commits to $R$ before seeing the challenge, then must answer the $c$ Bob actually sends. The simulator picks $c$ and $s$ first and computes $R$ last; it writes the question after seeing the answer. Send a simulated transcript to a live Bob and his fresh challenge matches yours with probability $1/q$. Negligible.

So the bits of a real transcript and a fake one are identically distributed, and the difference lives entirely in the live exchange: real Alice answered a challenge she could not predict. That fact is what Bob learns, and combined with special soundness it tells him exactly one thing: Alice knows $x$. Zero knowledge is the promise that he learns nothing else.

A sigma protocol is, by definition, any three-move protocol with these three properties: completeness for utility, special soundness for security, zero knowledge for privacy.

Fiat-Shamir: from protocol to signature#

The protocol is interactive; Bob must be there to flip his coin. That is fine for a live login and hopeless for a signed contract or a public ledger. In 1986 Amos Fiat and Adi Shamir gave a uniform trick for making any sigma protocol non-interactive, in two parts.

Part one removes the interaction: Alice computes the challenge herself by hashing her commitment. A good hash is unpredictable enough to stand in for Bob's coin flips. Part two binds in a message: mix the message $m$ into the same hash, and the whole transcript becomes bound to that message. A proof of knowledge bound to a message is exactly a signature. Concretely,

$$c=H(R,u,m),$$

and the signature on $m$ is the pair $(R,s)$ with $s=r+cx$ mod $q$. Anyone can verify alone: recompute $c$ from $R$, $u$, and $m$, and check $g^s=R·u^c$. Alice cannot cheat by choosing $R$ after the challenge, because the challenge is derived from $R$; the hash plays an honest verifier whose coins she cannot influence. Making that precise is the random oracle model, an idealization that has held up across four decades of Fiat-Shamir practice. Every Schnorr signature you will see, Bitcoin's BIP-340, ed25519 behind ssh and signed git commits, is this skeleton up to engineering details.

The signature inherits both halves of the protocol. Security: by the forking lemma of Pointcheval and Stern, a forger can be rewound at his hash query and fed a second challenge on the same $R$, the special-soundness setup again, so forging implies computing discrete logs (the reduction is loose, so parameters need slack). That is EUF-CMA, the gold standard. Privacy: the simulator carries over by programming the oracle, so anyone who only watches signatures is consuming simulator output, computable from the public key alone. Signatures leak nothing about the key.

The template#

Step back. We took an algebraic relation, $u=g^x$, and built a three-move protocol with completeness, an extractor, and a simulator, then compressed the conversation to one message with Fiat-Shamir. Every modern zero-knowledge proof system has this same skeleton. zk-SNARKs prove that an arithmetic circuit has a satisfying assignment, with an extractor saying you really know one and a simulator saying the proof tells the verifier nothing else. zk-STARKs swap in Reed-Solomon codes and hash functions; Bulletproofs prove range statements from discrete log alone; Monero's ring signatures and Signal's zero-knowledge group credentials are sigma protocols stacked on sigma protocols. The field calls the class arguments of knowledge; Schnorr is the prototype, and its three properties are the coordinates along which every proof system in cryptography is graded.

If you remember three things#

1. The Schnorr protocol is three messages, $R$, $c$, $s$, and one check, $g^s=R·u^c$; the secret $x$ is never sent and never recoverable from anything Bob hears.
2. The extractor and the simulator are the two load-bearing arguments: two transcripts on one commitment yield $x$, so cheating breaks discrete log, while a three-line simulator forges transcripts perfectly, so the conversation teaches Bob only that Alice knows $x$.
3. Fiat-Shamir, $c=H(R,u,m)$, turns the protocol into a signature that inherits security from the extractor and privacy from the simulator, and the same triangle, completeness, soundness, zero knowledge, grades every modern proof system.