Falcon

Introduction

Falcon (Fast Fourier Lattice-based Compact Signatures over NTRU) is one of NIST’s four selected post-quantum standards, chosen specifically for producing the smallest signatures of any candidate at a given security level — a decisive advantage for bandwidth-constrained protocols like certificate chains and blockchain transactions. Falcon builds on the same NTRU lattice structure covered earlier, using the GPV hash-and-sign paradigm (Gentry, Peikert, Vaikuntanathan, 2008). But GPV hash-and-sign has a famous cautionary tale behind it: an earlier generation of lattice signatures (GGH and NTRUSign, late 1990s/2000s) used this exact paradigm with a naive trapdoor-inversion step — and were completely broken by an attack that extracted the entire secret key just by watching enough signatures go by. Falcon’s defining engineering achievement is closing that hole with genuinely hard-to-implement randomized Gaussian sampling. This post shows the mechanism, and — deliberately — the vulnerable version of it, so you can see exactly what the fix protects against.

Table of Contents

• Security Levels and Sizes
• Hash-and-Sign: Signing as “Find a Nearby Lattice Point”
• Key Generation
• Signing and Verification
• A Worked Example
• The Nguyen-Regev Attack: Why Babai Rounding Isn’t Enough
• How Falcon Actually Closes the Gap
• Practical Considerations: Implementation Hardness
• FAQ
• References

Security Levels and Sizes

At NIST security level 1, Falcon-512 produces ~666-byte signatures and ~897-byte public keys (in their standard compressed formats); Falcon-1024 (level 5) produces ~1280-byte signatures and ~1792-byte public keys. These remain the smallest among the NIST PQC signature standards, making Falcon highly attractive for heavily bandwidth-constrained applications.

Hash-and-Sign: Signing as “Find a Nearby Lattice Point”

A lattice is an infinite, regularly-spaced grid of points in space. The GPV paradigm turns signing into a closest-vector problem: hash the message to some target point (usually not itself on the lattice), then find a genuine lattice point close to it. Finding any reasonably close lattice point is easy if you know a good, short, near-orthogonal basis for the lattice — but computationally infeasible if all you have is a long, skewed, “bad” basis (even though both bases describe the exact same lattice). The private key is the good basis; the public key is a bad basis for the identical lattice. A valid signature is proof you found a close point — something only someone with the good basis could do efficiently.

Key Generation

1. Generate a short, near-orthogonal private basis B for a lattice — in real Falcon, this comes from solving the NTRU trapdoor equation f·G − g·F = q for small polynomials F, G given a chosen small f, g (a genuinely intricate number-theoretic procedure). This is the same NTRU equation that produces a short dual basis that serves as the trapdoor.
2. Derive a long, “ugly” public basis P for the same lattice — algebraically, P = U·B for some unimodular integer matrix U (determinant ±1, so it doesn’t change the lattice, only how it’s described). Real Falcon’s public key is instead compactly represented as the polynomial h = g·f⁻¹ mod q, from which the ugly basis is implicit.
3. The private key is B; the public key is P (or the compact NTRU-style equivalent).

Signing and Verification

To sign message m:

1. Hash the message to a target point t in the lattice’s ambient space.
2. Using the private basis B, find a lattice point v close to t.
3. The signature is the short difference vector e = t − v.

To verify, given only the public basis P:

1. Recompute t from the message.
2. Compute v = t − e and check that v is actually a lattice point — i.e., that v can be written as an integer combination of P’s rows (equivalently: v·P⁻¹ has all-integer coordinates). While the toy visualizer uses this generic matrix inversion check, real Falcon verifies this much more efficiently using ring arithmetic over the public NTRU polynomial h.
3. Check that e is short enough (below a fixed norm bound) — an attacker who didn’t have the private basis could, at best, find some combination that lands on the lattice, but not one close enough to the original target to also produce a short e.

Interactive Visualizer

The visualizer above implements exactly this — a small 4-dimensional integer lattice with a short private basis and a scrambled public basis (via a random unimodular transform standing in for NTRU’s trapdoor construction, which is too intricate a number-theoretic procedure for a browser demo) — with one deliberate, disclosed simplification described next. By design, this 4-dimensional integer lattice and its random unimodular scramble preserve the core GPV security reduction, but they entirely discard the compactness and efficient trapdoor generation that real NTRU provides.

A Worked Example

1. A short private basis B (built from 8·I plus small perturbations) and a scrambled public basis P = U·B are generated.
2. The message is hashed to a target point t.
3. B⁻¹ converts t into real-valued lattice coordinates; rounding those coordinates to the nearest integers and multiplying back by B gives the closest lattice point v that this rounding method can find.
4. The signature e = t − v is short (for instance, a specific run might yield an error vector like [-1, 2, 0, -1] with a Euclidean norm of ~2.45, as displayed by the visualizer). The verifier reconstructs v = t − e and confirms it’s an integer combination of P’s rows using P⁻¹ — this always succeeds for the real message and (overwhelmingly) fails for a tampered one, since a different hash target generally isn’t exactly a lattice-point-length away from the same e.

The Nguyen-Regev Attack: Why Babai Rounding Isn’t Enough

The visualizer’s rounding step — converting t into B’s coordinate system and rounding to the nearest integer — is called Babai’s rounding algorithm, and it’s a completely deterministic function of t and B. That determinism is exactly the flaw Nguyen and Regev exploited in 2006 against GGH and NTRUSign: because rounding always resolves ties and biases in the same direction relative to B’s specific shape, the error vectors e it produces are subtly not uniformly distributed — their statistical spread traces out the parallelepiped shape of the private basis B itself. Collect enough signatures (a few thousand, in the original attack), average their empirical distribution, and you can recover enough geometric information to reconstruct a short basis — a full, practical break with no lattice problem ever “solved” in the traditional sense. This is why the visualizer above is explicitly a toy: it reproduces this exact vulnerability so it’s visible, not despite it.

How Falcon Actually Closes the Gap

Instead of deterministic rounding, real Falcon samples v from a discrete Gaussian distribution centered at t, using B — specifically via a technique called fast Fourier sampling over the NTRU lattice’s tree structure. Done correctly, the resulting e has a distribution that depends only on the target t and the public lattice, not on which specific short basis B was used to sample it. This statistical indistinguishability provides a zero-knowledge property: no matter how many signatures an attacker collects, the distribution of error vectors reveals no useful information about the specific geometry of the private key B.

Practical Considerations: Implementation Hardness

While Falcon’s compact sizes are ideal for protocols, implementing a correct, constant-time discrete Gaussian sampler is famously difficult. Fast Fourier sampling requires precise floating-point arithmetic (or large fixed-point equivalents) over the NTRU polynomial ring. Several early implementations suffered from subtle floating-point precision bugs that inadvertently leaked timing information.

Due to the high risk of side-channel vulnerabilities in the signing algorithm, many real-world deployments prefer Dilithium despite its larger signature sizes. Dilithium uses simpler, bound-driven rejection sampling that is much easier to implement securely in constant time, reserving Falcon (or hybrid constructions) primarily for environments where bandwidth or storage is the absolute strictest bottleneck.

FAQ

Is the visualizer’s signature scheme actually insecure the way NTRUSign was?

Yes, by design — using deterministic Babai rounding as shown is precisely the flaw that broke GGH and NTRUSign. The visualizer trades that security property for visibility into the shape of hash-and-sign, which real Falcon shares; the part it doesn’t show (correct discrete Gaussian sampling) is the part that makes Falcon actually secure.

Why does Falcon use NTRU lattices specifically, rather than a generic lattice like the visualizer’s?

NTRU lattices admit an efficient, structured trapdoor (the f, g, F, G relation) that keeps keys and signatures compact — a generic lattice trapdoor of comparable security would need a much larger, less efficient basis representation.

Why does Falcon produce smaller signatures than Dilithium?

Falcon’s hash-and-sign paradigm directly outputs a single short vector per signature; Dilithium’s Fiat-Shamir-with-aborts approach needs to include a challenge polynomial and hint bits alongside z, and its bound-driven rejection sampling requires wider safety margins. The net effect is Falcon signatures running roughly half the size of Dilithium’s (e.g., ~666 compressed bytes for Falcon-512 vs approximately 2.4 kB for ML-DSA-44 / Dilithium2) at comparable security levels, at the cost of a substantially harder-to-implement signing algorithm.

Does the visualizer really solve the NTRU trapdoor equation like real Falcon?

No — generating small F, G satisfying f·G − g·F = q is a genuinely advanced procedure (involving field norms and lattice reduction over an auxiliary ring) well beyond toy scope. The visualizer substitutes a simpler but structurally equivalent trapdoor: a short private basis and a random unimodular scrambling to produce the “bad” public basis. As noted, this preserves the essential GPV mechanism (short-basis-finds-close-point, long-basis-can’t) without the NTRU-specific key generation machinery.

References

1. Fouque, P-A., Hoffstein, J., Kirchner, P., et al. “Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU.” NIST PQC submission, 2020.

2. Gentry, C., Peikert, C., Vaikuntanathan, V. “Trapdoors for Hard Lattices and New Cryptographic Constructions.” STOC, 2008.

3. Nguyen, P., Regev, O. “Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures.” EUROCRYPT, 2006.

4. NIST. “Module-Lattice-Based Digital Signature Standard” (FIPS 204) and Falcon standardization track. Available at: https://csrc.nist.gov/projects/post-quantum-cryptography

5. Prest, T., Fouque, P.-A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Ricosset, T., Seiler, G., Stein, W., & Wallet, A. “Falcon: Compact Signatures”. IACR ePrint 2020/1090.