Lattice Trapdoors and Hash-and-Sign
A lattice trapdoor is a secret piece of information that lets its holder solve a lattice problem that is hard for everyone else. The public description of the lattice is a bad, tangled basis that reveals no easy structure, and the trapdoor is a matching short, well-behaved basis that unlocks the same lattice. Whoever holds the good basis can find short vectors quickly; whoever holds only the public bad basis faces the full hard problem. The GPV framework, named for Gentry, Peikert, and Vaikuntanathan, took that idea and built the first sound hash-and-sign lattice signatures on it. The message is hashed to a target point, the trapdoor samples a short vector near that target, and the short vector is the signature. That paradigm is the one behind Falcon, a different route to a signature than the Fiat-Shamir approach ML-DSA takes.
Source: Craig Gentry, Chris Peikert, Vinod Vaikuntanathan, “Trapdoors for Hard Lattices and New Cryptographic Constructions,” STOC 2008, ePrint 2007/432.
The short version:
- A lattice trapdoor is a secret good basis for a lattice whose public description is a bad basis. The good basis lets its holder find short vectors and invert an otherwise one-way lattice function; the public basis does not.
- The GPV framework (2008) built the first secure hash-and-sign lattice signatures on trapdoors, by defining a preimage-sampleable function: a one-way function anyone can compute forward and only the trapdoor holder can invert to a short preimage.
- Hash-and-sign, in one line. Hash the message to a target, use the trapdoor to sample a short vector that maps to that target, and publish the short vector as the signature. A verifier checks the vector is short and maps correctly.
- The sampling must leak nothing. GPV’s insight is that the trapdoor holder samples from a discrete Gaussian distribution over the lattice so that the released signature reveals essentially nothing about the secret good basis, which is what earlier lattice signature attempts got wrong.
- This is the paradigm behind FN-DSA, distinct from the Fiat-Shamir-with-aborts paradigm of ML-DSA. The unforgeability rests on SIS.
Picture a vast city laid out on a perfectly regular grid of intersections, and the grid is the lattice. The public map is drawn with a warped, skewed coordinate system that makes it genuinely hard to tell which intersections are close to any given spot. The trapdoor is a second, clean coordinate system for the exact same city, the one the surveyor kept, and with it you can instantly point to the nearest intersection to wherever you stand. Signing a message works by hashing it into a random location; the surveyor uses the clean coordinates to walk to a nearby intersection and reports it, and anyone can verify the report really is close to the hashed location. Only the surveyor could have found it quickly, and the way she chooses among the several near intersections is done so carefully that watching her answers never reveals her clean coordinates.
What is a lattice trapdoor?
A lattice trapdoor is a secret short basis for a lattice that is published only in a hard-to-use form. A lattice is a regular grid of points in high-dimensional space, and it can be described by many different bases, some clean and some tangled, all generating the same grid. A short, nearly-orthogonal basis makes the lattice easy to work with: given any target point in space, its holder can quickly find a lattice point close to the target, which is the closest-vector task that anchors lattice cryptography. A long, skewed basis generates the identical lattice while making that same task hard. The trapdoor construction publishes a public key equivalent to the bad basis and keeps the good basis secret, so the world sees a lattice it cannot navigate and the key holder holds the map that navigates it.
Source: Gentry, Peikert, Vaikuntanathan, “Trapdoors for Hard Lattices and New Cryptographic Constructions,” STOC 2008, ePrint 2007/432.
The reason a trapdoor is cryptographically useful is that the underlying lattice problems are believed hard without it and easy with it, and that gap is the same gap that makes LWE and SIS secure. Trapdoors sit on top of those problems. Where plain LWE and SIS give you a hard problem, a trapdoor gives you a hard problem plus a private shortcut, which is exactly the shape every public-key primitive needs: a function easy to run in one direction for everyone and easy to reverse only for the holder of a secret. GPV made that shape rigorous for lattices, and in the same work used it to build both hash-and-sign signatures and identity-based encryption.
What did the GPV framework prove?
The GPV framework introduced the notion of a preimage-sampleable function and showed how to build one from a lattice trapdoor, which is what made secure lattice hash-and-sign possible. A preimage-sampleable function is a one-way function that anyone can evaluate in the forward direction, that is hard to invert without the trapdoor, and that the trapdoor holder can invert in a special way: not by finding any preimage, but by sampling a preimage from a prescribed distribution, so that the outputs the holder produces look the same as if they had been drawn from that distribution directly. The forward function is the SIS-style map that sends a short vector to its modular image, and inverting it means finding a short vector that lands on a given target.
Source: Gentry, Peikert, Vaikuntanathan, STOC 2008, ePrint 2007/432 (preimage-sampleable functions; hash-and-sign signatures and identity-based encryption from lattice trapdoors).
The technical heart of the framework is the sampling algorithm. GPV gave a way to sample a lattice point from a discrete Gaussian distribution around any target, using the secret good basis, in a manner that is oblivious to the specific geometry of that basis. That obliviousness is the whole security argument. Earlier lattice signature schemes, such as GGH and the original NTRUSign, let each signature leak a little information about the secret basis, and enough collected signatures let attackers reconstruct the key. GPV’s Gaussian sampler is engineered so that the distribution of signatures is independent of which good basis produced them, so an attacker who collects a mountain of signatures learns nothing about the trapdoor. That is the difference between a heuristic that gets broken and a construction with a proof.
How does hash-and-sign work in a lattice signature?
Hash-and-sign turns the trapdoor into a signature in three moves, and every lattice hash-and-sign scheme, Falcon included, follows this shape.
- Hash the message to a target. The message is hashed to a point in the same space the lattice lives in, so different messages map to effectively random, independent targets. This is the “hash” half, and it binds the signature to the exact message.
- Sample a short vector near the target. The signer uses the secret trapdoor to sample a lattice vector close to the hashed target, drawn from the discrete Gaussian distribution so it reveals nothing about the trapdoor. That short vector, tying the message-target to the lattice, is the signature. This is the “sign” half, and only the trapdoor holder can do it.
- Verify shortness and correctness. Anyone with the public key checks two things: that the signature vector really is short, and that it maps to the target the message hashes to. Both must hold. The shortness check is what makes forgery hard, because dropping it would let any large vector satisfy the equation.
Source: Gentry, Peikert, Vaikuntanathan, STOC 2008, ePrint 2007/432; Falcon’s realization of this paradigm per the Falcon specification.
The reason forgery is hard is the reason SIS is hard. An attacker who wants to forge a signature on a message of their choosing has to produce a short vector mapping to that message’s hashed target, without the trapdoor, and that is exactly a SIS instance: find a short vector that a fixed modular map sends to a fixed value. The trapdoor holder solves it with the good basis; the attacker faces the full hard problem. So a lattice hash-and-sign signature is a digital signature whose unforgeability is the hardness of SIS and whose signing capability is the possession of a lattice trapdoor.
How is this different from the Fiat-Shamir approach in ML-DSA?
Lattice signatures come in two paradigms, and the split maps cleanly onto the two lattice signature standards. Hash-and-sign, the GPV route, hashes the message to a target and uses a trapdoor to sample a short vector near it. The Fiat-Shamir route, which ML-DSA takes, instead turns an interactive identification protocol into a signature by using the message hash to generate the verifier’s challenge, and it needs rejection sampling (Fiat-Shamir “with aborts”) to keep each signature from leaking the secret. Both end up with a short vector that a verifier checks, and they arrive there by different machinery.
| Hash-and-sign (GPV) | Fiat-Shamir with aborts | |
|---|---|---|
| Standard using it | Falcon | ML-DSA |
| Core operation | Trapdoor samples a short vector near a hashed target | Message hash forms the challenge in a transformed identification protocol |
| Leakage control | Discrete Gaussian sampling independent of the basis | Rejection sampling discards signatures that would leak |
| Lattice type in the standard | NTRU lattices | Module lattices |
| Notable cost | High-precision, side-channel-sensitive Gaussian sampler | Larger signatures than Falcon |
Source: paradigm split per Gentry-Peikert-Vaikuntanathan, ePrint 2007/432, and the Falcon specification; ML-DSA’s Fiat-Shamir-with-aborts construction per NIST FIPS 204.
The consequence of the split is the practical profile of each standard. Hash-and-sign over NTRU lattices produces Falcon’s very small signatures, which is its whole reason to exist, and it pays for that with a delicate floating-point Gaussian sampler that is hard to implement in constant time. Fiat-Shamir with aborts produces ML-DSA’s larger but more implementation-robust signatures, which is why NIST named ML-DSA the general-purpose default and positioned Falcon for the roles where signature size is the binding constraint. Two paradigms, two standards, one underlying lattice foundation.
Where does hash-and-sign show up in the standards?
The GPV hash-and-sign paradigm is the design basis of FN-DSA, the standardization-track name for the scheme known during the NIST competition as Falcon. Falcon builds hash-and-sign over NTRU lattices and uses a fast-Fourier trapdoor sampler to draw its short vectors from a discrete Gaussian, which is what yields its compact signatures. As of mid-2026 FIPS 206 is selected and in development while ML-DSA and SLH-DSA are finalized, so hash-and-sign’s standardized appearance is a target on the near horizon rather than a published standard today.
Source: Falcon uses the hash-and-sign paradigm with a fast-Fourier trapdoor sampler over NTRU lattices, per the Falcon specification; FN-DSA / FIPS 206 status per the NIST Post-Quantum Cryptography project. [OPERATOR VERIFY: confirm current FIPS 206 status at csrc.nist.gov before publishing a date.]
For a leadership decision, the meaning is that hash-and-sign is the reason Falcon exists as a distinct third signature option and the reason it is the trickiest to implement safely. The trapdoor sampler that gives Falcon its small signatures is the same component whose constant-time implementation is difficult, so the paradigm is directly responsible for both the reward and the hazard. Understanding it tells a decision-maker why the signature portfolio holds three algorithms of different shapes, and why the compact one carries an implementation-maturity caveat the others do not.
Common misconceptions
- “A trapdoor is a backdoor that weakens the scheme.” A cryptographic trapdoor is the legitimate private key, held only by the owner, and it is the thing that makes public-key cryptography work at all. It is the private shortcut every signature and decryption uses, and possessing it is what defines the legitimate signer rather than a hidden flaw.
- “Hash-and-sign is the same as Fiat-Shamir.” They are two different ways to build a lattice signature. Hash-and-sign hashes the message to a target and samples a short vector near it with a trapdoor; Fiat-Shamir turns an identification protocol into a signature using the message hash as the challenge. Falcon uses the first, ML-DSA uses the second.
- “Older lattice signatures failed, so the whole approach is fragile.” The early schemes like GGH and NTRUSign leaked the secret basis through their signatures and were broken. The GPV framework’s contribution was a Gaussian sampler whose output is independent of the basis, which closed exactly that leak and is what makes Falcon’s hash-and-sign sound.
- “The security comes from the hashing.” The hashing binds the signature to the message, and the unforgeability comes from SIS: forging means finding a short vector that maps to the hashed target without the trapdoor. The shortness check at verification is what makes that a hard SIS instance rather than trivial linear algebra.
- “If I use ML-DSA I am using hash-and-sign.” ML-DSA uses Fiat-Shamir with aborts over module lattices. Hash-and-sign is the paradigm of Falcon / FN-DSA, so you encounter it only when you deploy that scheme, which as of mid-2026 is still on the standardization track.
Questions people ask
What is a lattice trapdoor in simple terms? It is a secret good basis for a lattice whose public form is a tangled bad basis. Both describe the same grid of points, and the good basis lets its holder quickly find lattice points near any target, which is hard for anyone holding only the public bad basis. That gap between easy-with-the-secret and hard-without-it is what makes the trapdoor a usable private key.
What did the GPV framework contribute? Gentry, Peikert, and Vaikuntanathan showed in 2008 how to build a preimage-sampleable function from a lattice trapdoor and use it for secure hash-and-sign signatures and identity-based encryption. The key advance was a way to sample signatures from a discrete Gaussian distribution that reveals nothing about the secret basis, which fixed the leakage that had broken earlier lattice signatures.
How does hash-and-sign actually sign a message? The message is hashed to a target point, the signer uses the trapdoor to sample a short lattice vector close to that target, and that short vector is the signature. A verifier checks the vector is genuinely short and maps to the message’s target. Only the trapdoor holder can find such a short vector quickly, and forging one without the trapdoor is a SIS instance.
How is this different from how ML-DSA signs? ML-DSA uses the Fiat-Shamir-with-aborts paradigm over module lattices, turning an identification protocol into a signature and using rejection sampling to prevent leakage. Hash-and-sign over NTRU lattices is Falcon’s paradigm. The two produce different size and implementation profiles, which is why NIST standardized both.
Why does Falcon use hash-and-sign instead of Fiat-Shamir? Because hash-and-sign over NTRU lattices, with a fast-Fourier trapdoor sampler, produces very small signatures, and compactness is Falcon’s whole reason to exist. The cost is a high-precision Gaussian sampler whose constant-time implementation is difficult, which is the source of Falcon’s implementation caution.
Do I need to understand trapdoors to deploy the signature standards? No. The signing and verification live inside the libraries you integrate, and the migration work is inventory, sizing, and testing. Understanding lattice trapdoors and hash-and-sign explains why the signature portfolio has three differently shaped algorithms and why the compact one, FN-DSA, carries an implementation-maturity caveat the others do not.
Everything here is the map, given freely. When your team needs its signature estate inventoried 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.