Fiat-Shamir Transform
The Fiat-Shamir transform is the technique that turns a back-and-forth identification conversation into a one-shot digital signature. In an interactive identification scheme a prover convinces a verifier they hold a secret by answering a random challenge the verifier picks, and the exchange proves knowledge without revealing the secret. Fiat and Shamir noticed that if you replace the verifier’s random challenge with a hash of the message plus the prover’s opening move, the prover can generate the challenge themselves, answer it, and hand over the whole transcript as a signature that anyone can check. No live verifier is needed, and the hash binds the signature to the specific message. This one idea underpins a large share of modern signatures, and its lattice adaptation, Fiat-Shamir with aborts, is the construction behind ML-DSA.
Source: Amos Fiat & Adi Shamir, “How to Prove Yourself: Practical Solutions to Identification and Signature Problems,” CRYPTO 1986, per Wikipedia, “Fiat-Shamir heuristic”.
The short version:
- It converts an interactive proof into a signature by having the prover hash the message to generate the challenge that a live verifier would otherwise send, so the whole exchange becomes non-interactive.
- Fiat and Shamir introduced it in 1986 at CRYPTO, in a paper on practical identification and signature schemes.
- Its security lives in the random oracle model. Treating the hash as an ideal random function, Pointcheval and Stern later proved Fiat-Shamir signatures secure against chosen-message attacks. The guarantee depends on that idealization.
- The lattice version is “Fiat-Shamir with aborts.” Lyubashevsky adapted it so that the signer sometimes restarts, using rejection sampling, to keep the published signature from leaking the secret key.
- ML-DSA is a Fiat-Shamir-with-aborts signature, which is why understanding this transform explains the shape of the primary post-quantum signature standard.
Picture proving you know a password without saying it. A live challenger flips a coin, asks you a question that only someone with the password could answer that particular way, and repeats until they are convinced. The trouble is you need the challenger present and flipping coins. Fiat-Shamir removes them. You make your opening move, then feed that move and the message you want to sign into a hash function, and you treat the hash output as if it were the challenger’s coin flips. Because the hash is unpredictable and depends on your opening move, you cannot rig the challenge in your favor, and because it depends on the message, the finished transcript is glued to that exact message. You answer your own self-generated challenge, bundle the transcript, and that bundle is a signature anyone can verify by recomputing the same hash.
What is the Fiat-Shamir transform?
The Fiat-Shamir transform is a general method for making an interactive proof of knowledge non-interactive by deriving the verifier’s challenge from a hash function instead of from the verifier. The interactive schemes it starts from are a specific shape called a three-move or sigma protocol: the prover sends a commitment, the verifier replies with a random challenge, and the prover sends a response that convinces the verifier only if it holds the secret. The transform’s move is to compute the challenge as a hash of the commitment together with whatever the signature must be bound to, which for a signature is the message. The prover now needs no counterpart, and the commitment, challenge, and response together form the signature.
Source: Amos Fiat & Adi Shamir, “How to Prove Yourself: Practical Solutions to Identification and Signature Problems,” CRYPTO 1986, per Wikipedia, “Fiat-Shamir heuristic”.
The reason including the message in the hash matters is that it is what makes the result a signature rather than a mere proof of identity. Two different messages produce two different challenges and therefore two different valid transcripts, so a signature on one message cannot be reused as a signature on another. That binding of the transcript to the message is the whole reason the transform produces something worth calling a signature, and it is why the hash function is not an optional detail but the load-bearing component of the construction.
How does the transform build a signature step by step?
The transform runs the interactive protocol with the prover playing both roles, and the hash function standing in for the honest verifier. Concretely:
- Commitment. The signer runs the first move of the identification scheme, producing a commitment from fresh randomness. This is the same opening move a prover would send to a live verifier.
- Challenge by hash. Instead of waiting for a verifier’s random challenge, the signer computes the challenge as a hash of the commitment and the message being signed. Because the hash is deterministic and unpredictable, the signer cannot choose a challenge that would let them cheat.
- Response. The signer computes the response the identification scheme requires for that commitment and challenge, using the secret key.
- Signature. The commitment, challenge, and response together are the signature. A verifier recomputes the hash of the commitment and message, checks it matches the challenge, and confirms the response is valid, all without any interaction.
Source: Amos Fiat & Adi Shamir, CRYPTO 1986, per Wikipedia, “Fiat-Shamir heuristic”.
The verifier’s job is symmetric to the signer’s. It recomputes the same hash the signer used, so it arrives at the same challenge, then it runs the identification scheme’s verification check on the commitment, challenge, and response. If the check passes, the verifier is convinced the signer held the secret and signed this exact message. The elegance is that the entire security of the interactive identification scheme carries over, provided the hash behaves like a genuinely random function.
Why does the security rest on the random oracle model?
The transform’s security is proven under the random oracle model, an analysis where the hash function is treated as an idealized black box that returns a fresh uniformly random output for every new input. Fiat and Shamir’s original paper introduced the technique without a formal proof, and it was Pointcheval and Stern who later proved that the resulting signatures are secure against adaptive chosen-message attacks, the standard strong notion for signatures, when the hash is modeled as a random oracle. Under that idealization the challenge is genuinely unpredictable, which is what forces a forger to actually solve the underlying hard problem rather than manipulate the hash.
Source: Pointcheval-Stern security proof in the random oracle model, per Wikipedia, “Fiat-Shamir heuristic”.
The honest caveat is that real hash functions are not random oracles, and there exist constructed counterexamples where the transform is insecure once the hash is instantiated with any concrete function. In practice, with well-designed standard hashes, Fiat-Shamir signatures have proven robust across decades of deployment, and the random-oracle proof is treated as strong heuristic evidence rather than an ironclad guarantee. Post-quantum use adds a wrinkle worth noting: a quantum attacker can query a hash in superposition, so the analysis for schemes like ML-DSA uses the quantum random oracle model, a stronger version of the same idealization that accounts for that capability.
What is Fiat-Shamir with aborts, and why does ML-DSA use it?
Fiat-Shamir with aborts is the lattice-specific adaptation of the transform, and the “aborts” are the reason lattice signatures are safe. When you build a Fiat-Shamir signature directly on a lattice identification scheme, the naive response leaks information about the secret key, because the response is a combination of the secret and the fresh randomness, and its distribution shifts depending on the secret. Lyubashevsky’s insight was to add a step where the signer checks whether the response falls in a safe region and, if it does not, throws it away and restarts with fresh randomness. This is rejection sampling, and it forces the distribution of published signatures to be independent of the secret key, so no number of signatures reveals it.
Source: Vadim Lyubashevsky, “Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures,” ASIACRYPT 2009, DBLP record; refined in “Lattice Signatures without Trapdoors,” Eurocrypt 2012, ePrint 2011/537.
ML-DSA is built directly on this construction. Its signing algorithm runs the Fiat-Shamir move over the lattice identification scheme, hashing the commitment and message to produce the challenge, and it applies rejection sampling so the signature does not leak the Module-LWE secret. The unforgeability of the finished signature reduces to the hardness of Module-SIS. So ML-DSA is three ideas stacked: Fiat-Shamir to remove interaction, aborts (rejection sampling) to stop leakage, and the lattice problems Module-LWE and Module-SIS to make forgery and key-recovery hard. Understanding the transform is understanding the skeleton of the primary post-quantum signature standard.
Source: NIST, “Module-Lattice-Based Digital Signature Standard,” FIPS 204, August 13, 2024.
Common misconceptions
- “Fiat-Shamir is a signature scheme.” It is a transform, a recipe that turns an interactive identification scheme into a signature. The security and the math come from the underlying scheme; Fiat-Shamir is what removes the need for a live verifier.
- “The hash is just a formatting step.” The hash is the load-bearing component. It generates the challenge and binds the signature to the message, and the whole security proof treats it as a random oracle. A weak or misused hash breaks the construction.
- “Fiat-Shamir signatures are proven secure with no assumptions.” They are proven secure in the random oracle model, an idealization of the hash. That is strong heuristic evidence and has held up in practice, but real hashes are not perfect random oracles, which is the honest limit of the guarantee.
- “The aborts in ML-DSA are an efficiency hack.” They are a security necessity. Rejection sampling is what makes the signature distribution independent of the secret key, so it is what stops signatures from leaking the key over time.
- “ML-DSA and classical signatures like ECDSA share no design ideas.” ML-DSA is a Fiat-Shamir-style signature, and so are several classical schemes such as Schnorr. The shared skeleton is the transform; what differs is the hard problem underneath, lattice problems for ML-DSA versus the discrete logarithm for the classical ones.
Questions people ask
What is the Fiat-Shamir transform in simple terms? It is a way to turn a live challenge-and-response identity check into a signature you can send in one shot. Instead of a verifier picking a random challenge, the signer hashes the message to generate the challenge themselves, answers it, and bundles the transcript as a signature anyone can recompute and verify.
Who invented it and when? Amos Fiat and Adi Shamir introduced it in 1986 at the CRYPTO conference, in a paper on practical identification and signature schemes. Pointcheval and Stern later supplied the formal security proof in the random oracle model.
Why does Fiat-Shamir need a hash function? The hash does two jobs. It replaces the verifier’s random challenge with something unpredictable the signer cannot rig, and it binds the signature to the specific message so it cannot be reused on a different one. The security proof treats the hash as an ideal random function.
What is Fiat-Shamir with aborts? It is the lattice adaptation where the signer sometimes discards a response and restarts, using rejection sampling, so that the published signatures reveal nothing about the secret key. Vadim Lyubashevsky introduced it, and it is the construction ML-DSA is built on.
Does ML-DSA really use the same idea as classical signatures? Yes, at the level of the transform. ML-DSA is a Fiat-Shamir-with-aborts signature, sharing the non-interactive-proof skeleton with classical Schnorr-style signatures, while resting on lattice problems (Module-SIS and Module-LWE) instead of the discrete logarithm, which is what makes it quantum-resistant.
Is Fiat-Shamir safe against quantum computers? The transform itself is not the vulnerable part; what matters is the hard problem underneath and the hash analysis. ML-DSA’s security is analyzed in the quantum random oracle model, which accounts for a quantum attacker querying the hash in superposition, and it rests on lattice problems that Shor’s algorithm does not solve.
Everything here is the map, given freely. When your team needs its signature stack understood and sequenced onto the post-quantum standards, that’s what an alignment briefing is for.
Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.