Schnorr and Fiat-Shamir

ML-DSA descends from a construction that predates lattices entirely. This note builds it in its original setting, where it is easy to follow, before the next note tries to move it.

01.Proving you know something without revealing it

Start with a different problem from signing. Alice wants to convince Bob that she knows a secret, without telling him what it is.

Concretely, in the discrete-logarithm setting from Chapter 2: the public values are a prime $p$, a generator $g$, and $t = g^s \bmod p$. Alice knows $s$ and wants to prove it. Bob knows only $t$.

She cannot simply send $s$, since then Bob knows it too and can impersonate her forever.

02.The Schnorr protocol

Three messages.

Commit. Alice picks a random $y$, computes $w = g^y$, and sends $w$. She keeps $y$.

Challenge. Bob picks a random $c$ and sends it.

Respond. Alice computes $z = y + cs$ and sends $z$.

Check. Bob accepts if

$$g^z \;=\; w \cdot t^c .$$

The check works because

$$g^z \;=\; g^{y + cs} \;=\; g^y \cdot (g^s)^c \;=\; w \cdot t^c .$$

Two properties make this a proof rather than a ritual.

Alice cannot cheat. Suppose she does not know $s$. She commits to $w$ before seeing $c$, so she cannot tailor $w$ to the challenge. If she could answer two different challenges $c$ and $c'$ for the same $w$, then subtracting the two responses gives $z - z' = (c - c')s$, so she could compute $s$ herself. Being able to answer everything therefore means knowing the secret.

Bob learns nothing. The value $z = y + cs$ is $s$ masked by the fresh random $y$. Since $y$ is uniform and independent, $z$ is uniform too, and it reveals nothing about $s$ on its own.

That second property is the one that will break when we move to lattices, and it is worth noticing exactly why it holds here: $y$ is uniform over the whole group, so adding $cs$ to it wraps around and produces something still exactly uniform. Nothing sticks out.

03.Turning a proof into a signature

The protocol above is interactive. Bob has to be present to issue the challenge. A signature has to work with nobody present, since the verifier may read it years later.

The Fiat-Shamir transform removes the interaction with one substitution:

Replace the verifier's random challenge with a hash of the commitment and the message:

$$c \;=\; H(w \,\|\, m).$$

Now Alice generates the challenge herself, and the signature is the pair $(c, z)$, or equivalently $(w, z)$.

The reason this is sound is that $H$ behaves unpredictably. Alice must fix $w$ before she can compute $c$, exactly as she had to commit before seeing Bob's challenge. She cannot choose $w$ to produce a convenient $c$, because changing $w$ changes $c$ unpredictably.

Including $m$ in the hash is what ties the proof to a specific message. Without it, a proof of knowledge on one message would be a valid proof on every message.

This is the origin of a large family of deployed schemes, including Schnorr signatures, DSA, ECDSA and EdDSA. It is also the skeleton of ML-DSA.

04.The pieces to carry forward

Four things transfer directly to the lattice setting, and it is worth naming them now because the next notes use the same words.

The commitment $w$, computed from fresh randomness $y$.

The challenge $c$, a hash of the commitment and the message.

The response $z = y + cs$, which combines the randomness with the secret under the challenge.

The verification equation, which recomputes the commitment from the response and the public key.

What does not transfer is the argument that $z$ leaks nothing. That argument relied on $y$ being uniform over a group where addition wraps cleanly. Lattice secrets are small, lattice randomness is bounded, and there is no wraparound to hide behind.

The next note shows exactly how badly that fails.