How Falcon Would Break: NTRU Lattices and the Structure Nobody Fully Trusts

1. The One Standardized Signature Nobody Fully Trusts#

Falcon is the smallest signature NIST chose for the post-quantum era. A Falcon-512 signature is 666 bytes and its public key is 897 bytes -- roughly the classical security of RSA-2048 ^[1]. It is also the only one of NIST's lattice signatures still stuck in draft. ML-DSA and SLH-DSA were finalized as FIPS 204 and FIPS 205 in 2024, while FN-DSA -- Falcon's standardized name -- remains a draft as of mid-2026 ^{[2] [3]}. And it is the only standardized signature whose core hardness assumption has a published regime where it simply collapses ^[4].

Here is the detail that should make you lean in. Pierre-Alain Fouque co-designed Falcon ^[1]. He is also a co-author of the attack that maps where NTRU's collapse begins ^[5]. The person who helped build the trapdoor also helped chart its fault line. That is not a scandal. It is the tell.

So this article asks the diagnostic question of the How It Would Break series: when Falcon eventually cracks, where does the crack start? The answer, argued before any math, is that the likeliest structural break is NTRU-specific -- a sharper exploitation of the ratio $h = g/f$, or a downward push of a documented failure boundary toward Falcon's own parameters.

Among all the ways Falcon's own mathematics could fail, the most likely structural break is NTRU-specific. It ranks above a generic lattice-reduction advance (which threatens every lattice scheme equally, so is not Falcon's alone) and above the transcript leakage that broke Falcon's ancestor (which Falcon provably closes). This is a ranked judgment, not a documented break -- and earning that ranking is the whole point of the article.

Three hypotheses will compete for the title of "Falcon's likeliest crack." Hypothesis A is the NTRU-specific advance -- the thesis. Hypothesis B is a generic improvement to lattice reduction that would hit Dilithium and Kyber too. Hypothesis C is the transcript leak that felled NTRUSign. By the end you will see why A wins the structural, Falcon-specific question, why B is the larger but non-specific existential risk, and why C is already closed.

flowchart LR
A["NTRU 1996: public key is the ratio g/f"] --> B["NTRUSign 2003: deterministic good-basis signing"]
B --> C["Nguyen-Regev 2006: the transcript reveals the key"]
C --> D["GPV 2008: provable Gaussian sampling"]
D --> E["Falcon 2017: GPV over NTRU, fast-Fourier sampled"]
E --> F["Overstretched NTRU 2016-2021: a documented cliff"]
F --> G["Draft FIPS 206: where does the crack start?"]

One fence, stated once: this is a structural analysis. Side channels, Falcon's floating-point sampler, fault and power attacks, RNG failures, and protocol misuse attack the code, not the mathematics. They belong to this article's empirical sibling, How the NIST Finalists Broke: Rainbow in a Weekend, SIKE in an Afternoon, and the Graveyard of Post-Quantum Candidates, and appear here only to mark the boundary. This is Part 7 of the series.

To see why the crack starts in the NTRU structure, you first have to see what Falcon actually is -- and why its smallness is not free.

2. What Falcon Actually Is: GPV Hash-and-Sign over an NTRU Lattice#

Every signature scheme is a way to prove you know a secret without revealing it. Falcon's way is to be the only person on earth who can find a short vector in one particular lattice.

Start with the public key. It is a single element of a polynomial ring, $h = g/f$, where $f$ and $g$ are two short secret polynomials and the division happens modulo a prime $q = 12289$ ^{[1] [6]}. That element $h$ pins down a lattice -- the NTRU lattice -- in which the secret pair $(f, g)$ is an unusually short vector. The private key is a short basis of that lattice, built from $(f, g)$ and a completing pair. Anyone with the short basis can solve a hard-looking geometry problem cheaply; anyone without it cannot.

To sign a message, Falcon hashes it (with a random salt) to a target point $c$ in the lattice's ambient space, then samples a short preimage $(s_1, s_2)$ satisfying $s_1 + s_2 h = c$, with both parts small. That sampling step is the heart of the scheme. Falcon draws the preimage from a discrete Gaussian using a fast-Fourier tree walk over the ring's recursive structure -- the operation the designers call ffSampling, which runs in $O(n \log n)$ time ^{[8] [1]}. ※ The FFT tree mirrors the tower of subfields inside the cyclotomic ring: descend it once, sampling one Gaussian coordinate per node, and you have drawn a short preimage without ever forming a full basis matrix.

To verify, anyone recomputes $s_1 = c - s_2 h$ from the public $h$ and checks that $\|(s_1, s_2)\|$ falls below a fixed norm bound. The compact half of the signature, $s_2$, plus the salt, is all that travels.

sequenceDiagram
participant M as Message
participant S as Signer (secret short basis)
participant T as ffSampling tree
participant V as Verifier (public h only)
M->>S: hash message plus salt to a coset point c
S->>T: request a short preimage of c
T-->>S: discrete-Gaussian preimage s1, s2
Note over S,T: output is short and provably basis-independent
S->>V: send signature, the salt and compact s2
V->>V: recompute s1 from c and h, check the norm is small

The numbers are the reason Falcon exists. At Falcon-512 the public key is 897 bytes and the signature 666 bytes; at Falcon-1024 they are 1793 and 1280 bytes ^[1]. Its nearest standardized rival at the low end of the security range, ML-DSA-44, needs a 1312-byte key and a 2420-byte signature ^[9]. Falcon wins on size by a wide margin, and the win comes from NTRU.

That contrast runs through the rest of the article. ML-DSA rests on Module-LWE; Falcon rests on NTRU. They live over the same kind of polynomial ring, yet one is routinely called the conservative choice and the other the aggressive one. Everything rests on a single asymmetry: with the short trapdoor you can sample these tiny preimages; without it, finding a short vector that maps to $c$ is the NTRU lattice problem, believed hard. FALCON is a backronym: FAst-Fourier Lattice-based COmpact signatures over NTRU ^[1]. Because the trapdoor lives in the NTRU lattice specifically, it is NTRU -- not "a lattice" in the abstract -- that stands trial here.

There is one more guarantee to bank. With a genuine discrete Gaussian, Falcon's key stays statistically hidden even after roughly $2^{64}$ signatures from a single key -- a leakage bound it inherits directly from the underlying proof, discussed in Section 5 ^[1]. That $2^{64}$ figure is a structural, information-theoretic bound on transcript leakage for a true Gaussian. Whether a floating-point implementation emits a true Gaussian is a separate, out-of-scope question, flagged at the boundary in Section 6.

That compact public key $h = g/f$ is a ratio -- and a ratio is a very particular thing to hand an attacker. To see the handle it creates, we have to go back to 1996.

3. Where the Handle Comes From: NTRU and the Quotient#

In 1996, three Brown University mathematicians -- Jeffrey Hoffstein, Jill Pipher, and Joseph Silverman -- circulated a public-key system built not on factoring or discrete logs but on arithmetic in a polynomial ring. They wanted something far faster than RSA, and they got it. NTRU was published at the Third Algorithmic Number Theory Symposium in 1998 ^[10]. Hoffstein would, two decades later, be a co-author of Falcon ^[1]. The line from that ring to the smallest post-quantum signature is short and direct.

Here is the move that matters for everything after. NTRU works in a polynomial ring and makes its public key a ratio of two secret elements: $h = g/f$, computed as $g \cdot f^{-1}$ modulo a prime $q$ ^[10]. Both $f$ and $g$ are short -- their coefficients are tiny. Their quotient $h$ is not short; it looks like a uniform random element of the ring. To recover the secret is to recover the short $(f, g)$ from the innocuous-looking $h$. That is the NTRU problem. The original 1998 NTRU used the convolution ring $\mathbb{Z}[x]/(x^N - 1)$ with $N$ prime ^[10]. Falcon keeps the same $g/f$ quotient idea but instantiates it over the power-of-two cyclotomic ring $\mathbb{Z}_q[x]/(x^n + 1)$, with $n = 512$ or $1024$ and $q = 12289$ ^[6]. The dense-sublattice argument is identical for both rings, so the difference is historical precision, not a change in the mechanism.

Publishing a ratio is not the same as publishing two independent random-looking numbers. The quotient ties $g$ to $f$ through $h$, and that tie is geometric: it plants inside the NTRU lattice a dense sublattice, a region unusually rich in short vectors, spanned by ring-shifts of the secret $(f, g)$. This is the object the entire thesis turns on. Module-LWE -- the assumption under Dilithium and Kyber -- builds its public data differently and does not expose this same handle. Two schemes, the same ring, but only one hands the attacker a ratio.

You can watch the quotient hide its secret. The toy below works in a tiny eight-dimensional ring with Falcon's real modulus. It picks two short secrets, forms the public ratio, and confirms the relation $f \cdot h \equiv g$ -- yet the published $h$ is smeared across the whole range $[0, q)$.

// NTRU public key in the ring R = Z_q[x]/(x^n + 1).
// The secret is a SHORT pair (f, g); the public key is the ratio h = g/f.
// h looks like uniform noise mod q, yet it hides the short (f, g).
// Recovering (f, g) from h is the NTRU lattice problem: trivial at n = 8,
// believed hard at Falcon's n = 512.
const q = 12289;   // Falcon's modulus (prime, 12*1024 + 1)
const n = 8;       // a tiny ring, so every coefficient is printable

const mod = (a, m) => ((a % m) + m) % m;
const invMod = (a, m) => {           // scalar inverse via extended Euclid
let [o, r] = [mod(a, m), m], [os, s] = [1, 0];
while (r !== 0) { const k = Math.floor(o / r);
  [o, r] = [r, o - k * r]; [os, s] = [s, os - k * s]; }
return mod(os, m);
};
const polyMul = (a, b) => {          // negacyclic convolution: x^n = -1
const o = new Array(n).fill(0);
for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) {
  const k = i + j, c = a[i] * b[j];
  if (k < n) o[k] = mod(o[k] + c, q); else o[k - n] = mod(o[k - n] - c, q);
} return o;
};
const deg = p => { let d = p.length - 1; while (d > 0 && p[d] === 0) d--; return d; };
const trim = p => { const c = p.slice(); while (c.length > 1 && c[c.length-1] === 0) c.pop(); return c; };
const divmod = (a, b) => {           // polynomial division over Z_q
const rem = a.slice(), db = deg(b), lead = invMod(b[db], q);
const quo = new Array(Math.max(1, rem.length)).fill(0);
for (let i = rem.length - 1; i >= db; i--) { if (rem[i] === 0) continue;
  const fct = mod(rem[i] * lead, q); quo[i - db] = fct;
  for (let j = 0; j <= db; j++) rem[i - db + j] = mod(rem[i - db + j] - fct * b[j], q);
} return [trim(quo), trim(rem)];
};
const polyInv = f => {               // inverse in Z_q[x]/(x^n + 1)
let r0 = new Array(n + 1).fill(0); r0[0] = 1; r0[n] = 1;
let r1 = trim(f.slice()), t0 = [0], t1 = [1];
while (deg(r1) > 0 || r1[0] !== 0) {
  const [quo, rem] = divmod(r0, r1);
  const qt = new Array(quo.length + t1.length).fill(0);
  for (let i = 0; i < quo.length; i++) for (let j = 0; j < t1.length; j++)
    qt[i + j] = mod(qt[i + j] + quo[i] * t1[j], q);
  const tn = new Array(Math.max(t0.length, qt.length)).fill(0);
  for (let i = 0; i < tn.length; i++) tn[i] = mod((t0[i] || 0) - (qt[i] || 0), q);
  [r0, r1] = [r1, rem]; [t0, t1] = [t1, trim(tn)];
}
if (deg(r0) !== 0) return null;    // f not invertible; try another f
const sc = invMod(r0[0], q), o = new Array(n).fill(0);
for (let i = 0; i < t0.length; i++) o[i] = mod(t0[i] * sc, q);
return o;
};

const f = [1, 1, -1, 0, 1, -1, 0, -1];   // short secret (ternary)
const g = [-1, 0, 1, 1, 0, -1, 1, 0];    // short secret (ternary)

const h = polyMul(g, polyInv(f));          // public key: the ratio g/f
console.log("secret f (short) :", f.join(", "));
console.log("secret g (short) :", g.join(", "));
console.log("public h = g/f   :", h.join(", "));
console.log("-> h is spread across [0, " + q + "): it looks uniform, but (f, g) are tiny.");
const ctr = x => x > q/2 ? x - q : x;  // center into (-q/2, q/2]
const gCheck = polyMul(f, h).map(ctr);     // recompute g = f * h to prove the relation
console.log("verify f*h == g  :", gCheck.join(", "), "(equals g)");

In one dimension a ratio modulo $q$ is easy to invert -- rational reconstruction reads off small numerator and denominator in moments. NTRU's hardness comes from doing this with $n$ coefficients at once, where the short $(f, g)$ is buried in a $2n$-dimensional lattice and only the best reduction algorithms have any chance of digging it out. Falcon's modulus is $q = 12289 = 12 \cdot 1024 + 1$, chosen so the number-theoretic transform (a fast ring multiplication) has the roots of unity it needs. The value comes from the specification and standard parameter descriptions ^[6].

flowchart TD
A["Secret: two short polynomials f and g"] --> B["Publish h, the ratio of g over f, mod q"]
B --> C["h defines the NTRU lattice of dimension 2n"]
C --> D["The pair f, g is an unusually short vector in it"]
C --> E["The quotient plants a dense sublattice"]
E --> F["A structural handle Module-LWE does not expose"]

A ratio you publish is a door you cannot fully close. The first people to walk through it were not attacking NTRU encryption at all. They were attacking NTRU's signature -- and they walked away with the key.

4. NTRUSign and the Break That Defines the Design#

The first NTRU signature verified perfectly, ran fast, and fit in a handful of bytes. It was also fatally, provably insecure -- and the reason has nothing to do with a bug.

The idea came from a 1997 template by Goldreich, Goldwasser, and Halevi (GGH): a lattice has many bases, some useful and some useless, and that gap is a trapdoor ^[11].

NTRUSign, in 2003, made this compact by using the NTRU lattice, whose basis is a few ring elements rather than a full matrix ^[12]. To sign, it hashed the message to a target point and used the secret good basis to round to the nearest lattice vector; the short difference was the signature. Fast, tiny, and correct. And deterministic -- the same message always rounded the same way. That determinism was the wound.

Think about what each signature reveals. Rounding a target with the secret basis lands you inside the basis's fundamental parallelepiped -- the tilted box you get by taking the basis vectors as edges. Every signature is one point drawn from that box. Collect a few thousand and their shape emerges; collect enough and the box's edges are simply visible, and the edges are the secret basis vectors.

In 2006 Phong Nguyen and Oded Regev made this precise and devastating. They cast key recovery as finding the directions in which the signature cloud is flattest -- a fourth-moment (kurtosis) minimization solved by a gradient descent, the same shape of computation as independent-component analysis. From roughly 90,000 signatures they recovered the NTRUSign secret key outright ^[13]. The ~90,000-signature figure is the original NTRUSign-251 experiment; later analysis cut the sample count and went on to defeat the countermeasures ^{[13] [14]}. This was not brute force and not a quantum computer. It was statistics applied to a leak that was baked into the design.

Correctness is not security -- a hash-and-sign lattice signature can bleed its key through its own transcript.

NTRUSign's authors tried to save it. They added perturbations to blur the parallelepiped into a more complicated shape, a zonotope (the Minkowski sum of several segments), hoping to hide the edges. In 2012 Leo Ducas and Nguyen extended the moment method with a covariance-gradient refinement and learned the zonotope too ^[14]. The patch bought a little sample complexity and nothing else.

This was not the first NTRU-signature dead end, either: the earlier NSS design of 2001 leaked its key almost immediately ^[15], and GGH's own encryption had already fallen to Nguyen in 1999 ^[16]. GGH-style objects bleed structure; that was becoming a pattern.

The lesson was total, and it reshaped the field. You cannot obfuscate your way out of an information-theoretic leak. A hash-and-sign lattice signature must leak nothing about which basis produced it, and "nothing" has to be a theorem, not a hope. This is the first of our three hypotheses for how Falcon breaks -- Hypothesis C, transcript leakage -- raised here so the next section can show how Falcon shuts it. Everything that made NTRUSign attractive survives in Falcon: the NTRU lattice, the compact keys, the hash-and-sign shape. Only the fatal part was cut out.

And two years before NTRUSign's perturbation patch even fell, someone had already shown exactly how to prove a signature leaks nothing.

5. The Fix Was a Theorem: GPV and Provable Gaussian Sampling#

The answer to NTRUSign was not a cleverer patch. It was a proof.

In 2008 Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan published a general framework for trapdoors on hard lattices, and with it the repair for the entire NTRUSign class ^[7]. The change is one word: stop rounding, start sampling. Instead of deterministically snapping a target to the nearest lattice point, draw a preimage from a discrete Gaussian centered on the target, using the secret basis only as a sampling aid.

The magic is in the width. If the Gaussian is wider than the basis's longest Gram-Schmidt vector, the distribution of the output depends only on the lattice and the target -- and not on which basis did the sampling. GPV's sampler is a randomized nearest-plane walk, the Klein sampler: descend the Gram-Schmidt-orthogonalized basis and draw one discrete-Gaussian coordinate per step. The width must exceed the basis's longest Gram-Schmidt vector for the independence proof to hold ^[7]. A good basis and a bad basis, fed the same target, produce statistically identical signatures. So the transcript that gave away NTRUSign now gives away nothing.

This is also where lattice signatures earn a word they wear with pride. GPV's security reduces to SIS, and SIS in the relevant settings enjoys something NTRU does not.

Keep that definition in your pocket. It is the hinge of the whole thesis, and it will swing in Section 7.

flowchart LR
subgraph D["Design chain, each fix answers the last break"]
G1["GGH and NTRUSign, deterministic rounding"] --> G2["GPV 2008, provable Gaussian sampling"]
G2 --> G3["Falcon, GPV over NTRU"]
end
subgraph K["Attack chain, where each break lands"]
A1["Transcript geometry, parallelepiped and zonotope"]
A2["NTRU structure, overstretched dense sublattice"]
end
A1 -. closed by .-> G2
A2 -. still open, aimed at .-> G3

There is a catch, and it is the reason GPV alone is not a product. Sampling over a general lattice needs the full Gram-Schmidt basis in memory and costs on the order of $n^2$ time and space, with signatures and keys to match ^[7]. GPV is not a broken scheme; it is the correct scheme, too heavy to deploy as written. It was outgrown, not defeated -- a distinction worth holding onto, because it is the opposite of what happened to NTRUSign.

So the state of play by 2008 was strange and specific. Cryptographers had a signature that provably leaked nothing, backed by a reduction to SIS, and it was too slow and too large to use. They had, separately, a lattice with tiny keys and a fast ring structure -- NTRU -- carrying an assumption nobody could prove. GPV told you what to sample. It did not tell you how to do it small and fast. The lattice that answered that question was the one with the handle.

6. Falcon: GPV, NTRU Compactness, and a Tree You Can Walk in n log n#

Take the theorem that fixes the leak. Instantiate it over the lattice with the smallest keys in the business. Sample its Gaussian by walking a tree in $O(n \log n)$. That is Falcon -- and its genius is also its single uninsured bet.

The missing engine arrived in 2014, when Ducas, Lyubashevsky, and Prest built a discrete-Gaussian sampler that exploits the recursive tower of the cyclotomic ring ^[8]. Instead of storing and walking a full Gram-Schmidt basis, it descends a binary "Falcon tree," sampling one Gaussian coordinate per node. The generic GPV sampler's $n^2$ cost collapses to $n \log n$, and the full-matrix key shrinks to a few ring elements. Bolt this sampler onto GPV, run it over the NTRU lattice, and you have Falcon, submitted to NIST in 2017 ^[1].

Key generation shows how tightly the pieces fit. Falcon samples short secrets $f$ and $g$, then solves the NTRU equation $fG - gF = q$ for a completing pair $(F, G)$; the secret basis is built from all four, and the public key is the familiar single element $h = g/f$ ^[1]. Signing draws a short preimage with ffSampling; verification checks a norm. The result is the smallest footprint of any standardized lattice signature ^[1].

Now count what Falcon has actually insured. Deterministic leakage: closed, because ffSampling emits a true discrete Gaussian, and GPV's theorem then makes the transcript independent of the trapdoor, with key leakage negligible past $2^{64}$ signatures from one key ^{[1] [7]}. Large keys and slow signing: closed, by NTRU compactness and the FFT tree. Falcon is the scheme that fixed every wound its ancestors died of.

Except one.

Falcon's smallness is not free. GPV's proof closes the transcript leak, and NTRU's ring structure closes the size and speed problems -- but the very choice of NTRU reintroduces the one bet the entire lineage could never insure: an assumption with a dense-sublattice handle and no worst-case-to-average-case reduction at Falcon's parameters. Every other risk got insured. This one got concentrated.

That is the shift worth pausing on. It is tempting to read Falcon as simply a well-engineered, compressed signature -- smaller is better, end of story. But by closing the transcript branch and shrinking the generic exposure, the compression funnels nearly all of Falcon's remaining structural risk onto a single assumption. Its safety is not spread across three independent bets. It rides on one.

Before we press on that assumption, one honest boundary marker.

There is a temptation to treat the draft status as the story -- "Falcon is late, so Falcon is shaky." That gets it backwards. The lateness is an implementation problem about a sampler. The structural question is entirely separate, and it is more interesting: Falcon could ship tomorrow with a flawless constant-time sampler and still rest on the least-insured assumption in the standardized lattice family.

It could not prove that the lattice it stands on is hard. To see why that gap is unique to Falcon -- why the same is not said of Dilithium, which lives over the same kind of ring -- compare the bet Falcon made to the bet Dilithium made.

7. The Least Conservative Bet: NTRU Versus Module-LWE#

Both Falcon and Dilithium live over the same kind of polynomial ring. So why do cryptographers call one of them the conservative choice and the other the aggressive one?

The lazy answer is "NTRU has more algebraic structure." That answer is wrong, and getting it right is the center of this article. NTRU and Module-LWE are built over the same class of rings; neither has "more ring" than the other. The difference that matters is precise, and it has exactly two parts.

First difference: the public key is a quotient. Module-LWE publishes noisy products; NTRU publishes the ratio $h = g/f$. As Section 3 showed, that ratio plants a dense sublattice -- an extra geometric handle that the overstretched attacks will grab. Module-LWE's public data does not expose that same handle ^[17].

Second difference: the reduction gap. Module-LWE has a worst-case-to-average-case reduction in its parameter regime; NTRU at Falcon's parameters has none ^{[17] [19]}. This is the structural insurance policy from Section 5, and Dilithium holds it while Falcon does not. That policy is worth reading precisely, though, because it is weaker than the slogan "Dilithium is proven" suggests.

Line the standardized signatures up and the trade becomes visible.

The sizes come from the Falcon specification, FIPS 204, and FIPS 205; the reduction column from the survey literature and the standards; the handle and status columns summarize Sections 3 and 6 ^{[1] [9] [24] [17] [2]}. Read across the Falcon column and the shape of the bet is stark: it is the only entry that is smallest on size and alone in carrying both a dense-sublattice handle and no worst-case reduction. SLH-DSA sits at the opposite corner, resting on nothing but hash functions and paying for it in multi-kilobyte signatures ^[2].

Among the standardized lattice signatures, Falcon rests on the only assumption with a dense-sublattice handle and no worst-case reduction at $q = 12289$. That is what "least conservative" means -- stated precisely, not rhetorically.

Now for the honest complication, because the thesis has to survive it.

So the "least conservative" verdict is not a slur on Falcon. It is a factual placement on a map that Stehle-Steinfeld themselves drew: the reduction sits over there, at big parameters; Falcon sits over here, at small ones, in the open country between the proof and the best-known attacks. Its security in that country is a well-tested assumption, not a theorem.

An assumption with no proof beneath it is only as safe as the attacks that have failed to reach it so far. That would be a comfortable enough position -- most of cryptography lives there -- if not for one specific, documented fact about NTRU. For some parameters, the attacks do not fail. They succeed completely. The only question is how far those parameters sit from Falcon's.

8. The Documented Failure Regime: Overstretched NTRU#

There is a number that decides whether NTRU is safe or doomed, and it is not the dimension. It is the modulus $q$ -- and NTRU has a cliff.

To see the cliff you need the yardstick every lattice scheme is measured against: generic lattice reduction.

The generic curve is the same for every lattice scheme, Falcon and Dilithium and Kyber alike: pick the blocksize that breaks you, read off $2^{0.292\beta}$. You can run the mapping yourself. The blocksizes below are the ones the standard estimator assigns to Falcon-512, which we return to in Section 9.

// R3: Core-SVP cost. A lattice attack must run BKZ with block size beta;
// the best heuristic sieve costs about 2^(0.292*beta) classically (BDGL 2016).
// Falcon-512's cheapest structural attack (in this conservative model) is
// forgery at beta = 415; key recovery needs beta = 481.
const classicalBits = beta => 0.292 * beta;   // BDGL sieving exponent
const quantumBits   = beta => 0.265 * beta;   // model-dependent quantum sieve
for (const [label, beta] of [["forgery (SIS)", 415], ["key recovery (NTRU)", 481]]) {
const c = classicalBits(beta), qb = quantumBits(beta);
console.log(label + ": beta = " + beta +
  "  ->  classical 2^" + c.toFixed(1) + ",  quantum 2^" + qb.toFixed(1));
}
console.log("Doubling the attack's reach means moving beta -- an exponential wall.");

Those two numbers -- forgery near $2^{121}$, key recovery near $2^{140}$ -- are Falcon-512's generic security floor in the conservative model, computed with the standard lattice estimator, and they are shared-shape risk: an advance in sieving lowers that exponent for everyone ^{[27] [26]}.

It is worth knowing what fixes that blocksize, because it sets the entire floor. After BKZ reduces a basis, the lengths of its Gram-Schmidt vectors fall along a predictable downward profile, and an attack succeeds at the smallest $\beta$ whose profile first lets the target vector poke through -- the projected-target picture behind the standard estimate ^{[28] [29]}. Two things lower the $\beta$ you need: a shorter or more uniquely planted target, and a flatter, lower profile.

That is why Falcon-512's two costs differ. Forgery needs only some vector under a relatively loose norm bound and clears its profile at $\beta \approx 415$; key recovery must expose the specific, very short secret module and only clears at $\beta \approx 481$ -- which is why the one $0.292$ constant reads out $2^{121}$ for the first and $2^{140}$ for the second ^[27]. Those constants come from the model, not from a derivation here: this is the intuition for what sets the floor, kept on the near side of the scope fence.

Now watch what NTRU does that Module-LWE does not.

In 2016, Martin Albrecht, Shi Bai, and Leo Ducas showed that when $q$ is large relative to $n$, you can project NTRU into a subfield of the ring, shrink the dimension, and expose the secret far below the generic cost ^[30].

A year later, Paul Kirchner and Pierre-Alain Fouque removed the subfield crutch: plain BKZ, run on the NTRU lattice directly, finds the dense sublattice on its own once $q$ is large enough ^[5]. The $g/f$ quotient's planted structure becomes so short that reduction stumbles onto it early. This is a structural collapse, not a generic speedup -- the cost falls because of what NTRU is, not because sieving got faster.

Why does the planted sublattice go short exactly when $q$ is large? The mechanism is a one-line volume argument, and it turns on two lengths inside the NTRU lattice that move with $q$ in opposite directions.

Begin with the ambient lattice. The NTRU lattice has dimension $2n$ and volume $q^n$ -- one factor of $q$ for each of the $n$ coset constraints $v \equiv u \cdot h$ ^[31]. The Gaussian heuristic estimates the shortest vector of a structureless lattice of dimension $d$ and volume $V$ at about $\sqrt{d / 2\pi e} \cdot V^{1/d}$ ^[28]. Substitute $d = 2n$ and $V = q^n$:

So the generic shortest vector -- what plain reduction finds in a lattice of this shape with no planted structure -- grows like $\sqrt{q}$. Now take the planted sublattice. The secret $(f, g)$ and its $n$ ring-shifts $x^i \cdot (f, g)$ span a rank-$n$ sublattice inside the NTRU lattice. Multiplication by $x$ in the ring is only a signed coordinate rotation, so every one of those generators has the same norm as $(f, g)$ itself -- a length set by how short the secret is, and completely independent of $q$.

Put the two lengths together and the whole overstretched phenomenon falls out. As $q$ climbs, the ambient generic length rises like $\sqrt{q}$ while the planted sublattice stays pinned at $\|(f, g)\|$. The secret module grows steadily more anomalous against its own surroundings. The security-relevant quantity is their ratio, proportional to $\|(f, g)\| / \sqrt{q}$, and it shrinks as $q$ grows. That is the entire content of the warning that a bigger modulus is backwards: enlarging $q$ inflates the haystack's generic vectors while leaving the secret needle exactly as long, so the needle protrudes further, not less.

Past a threshold, that protrusion changes what reduction finds first. Instead of isolating the single shortest secret, BKZ surfaces the whole planted block. Ducas and van Woerden separate the two outcomes experimentally: a Dense-Sublattice-Discovery event, in which reduction reveals vectors of the planted module, versus a Secret-Key-Recovery event, in which it pins down the one shortest secret ^[31]. Overstretched NTRU is precisely the regime where the Dense-Sublattice-Discovery event fires first, at a blocksize far below the cost of ordinary key recovery. That early discovery is the structural short-cut, and it is the engine of Hypothesis A.

How large is large? In 2021 Ducas and van Woerden answered it with an extensive experimental campaign, pinning the exact crossover.

That formula is the whole game, so read it carefully. It says the cliff scales like $n^{2.484}$: as the dimension grows, you can afford a much larger modulus before falling off. It is also, in two specific ways, softer than a theorem -- it is an experimental average-case crossover rather than a proven bound, and it was fit to ternary secrets, whereas Falcon samples discrete-Gaussian secrets. Both caveats matter enormously, and Section 9 makes them do work. Pierre-Alain Fouque co-designed Falcon and co-authored the Kirchner-Fouque overstretched attack. The designer and the cryptanalyst of the failure regime are the same person -- the strongest signal available that this is the live fault line, not a hypothetical one ^{[1] [5]}.

The same expertise that built Falcon's trapdoor also mapped its one uninsured failure regime.

So the cliff is real, it has a mechanism -- the dense sublattice going short -- and it has a formula, fit from real computation. Falcon's whole claim to safety is that it sits on the near side of that cliff. The only question left is arithmetic. Plug in Falcon's numbers. How much margin is there?

9. The Margin: Why Falcon Stays Clear, For Now#

Falcon-512 uses $q = 12289$. The fatigue formula says the cliff at $n = 512$ sits near $q \approx 21{,}500$. That is a safety factor of about 1.75. Sit with that number for a moment.

Here is the calculation, laid out so you can move the dimension yourself and watch the margin change.

// R2: NTRU "fatigue" margin. Ducas-van Woerden (2021) measured the modulus q
// at which the overstretched (dense-sublattice) attack overtakes ordinary key
// recovery: q ~= 0.004 * n^2.484, for TERNARY secrets. Falcon uses q = 12289.
const fatigueQ = n => 0.004 * Math.pow(n, 2.484);
const FALCON_Q = 12289;
for (const n of [512, 1024]) {
const fq = fatigueQ(n);
console.log("n = " + n + ":  fatigue-q ~= " + Math.round(fq) +
  "   Falcon q = " + FALCON_Q +
  "   margin ~= " + (fq / FALCON_Q).toFixed(2) + "x");
}
console.log("Caveat: this fit is experimental and for ternary secrets;");
console.log("Falcon uses discrete-Gaussian secrets, so the margin is an extrapolation.");

The two rows are the whole story of Falcon's structural safety today.

At $n = 1024$ the margin is roughly 9.8x -- comfortable by any standard. At $n = 512$ it is about 1.75x, and Falcon-512 is likely to be the more widely deployed of the two, because it is the small, fast one ^{[4] [1]}. With FN-DSA still in draft and nothing yet in production, that is a prediction rather than a measured fact -- but if it holds, the thinnest margin in the standardized lattice family sits under the Falcon most deployments will reach for.

Take those caveats seriously in both directions. They do not prove Falcon is in danger; nobody has broken $q = 12289$, and the extrapolation could just as easily place the true cliff higher for Gaussian secrets as lower. But they do mean the number guarding Falcon-512 is not a proven wall. It is a measured, extrapolated fence, and its exact location for Falcon's own secret distribution has never been pinned.

A 1.75x margin below an unproven, extrapolated cliff is not a reason to panic. Falcon is not broken, and this section has not shown a break -- it has shown a boundary and measured a distance to it. But it is a reason to ask the real question, the one the whole article has been building toward. When Falcon eventually breaks, is this where it starts -- the NTRU cliff creeping toward $q = 12289$ -- or does it start somewhere else entirely, in a generic advance or a quantum machine? To answer that, we have to rank.

10. Weighing the Hypotheses: Where Does Falcon's Crack Start?#

Now we can rank. There are exactly three ways Falcon's own mathematics could fail, and only one of them is both open and Falcon's alone.

Hypothesis A -- an NTRU-specific advance. Someone finds a sharper way to exploit the $g/f$ dense sublattice at Falcon's small $q$, or pushes the fatigue boundary $q \approx 0.004 \cdot n^{2.484}$ downward -- or extends it rigorously to discrete-Gaussian secrets and it lands lower than the ternary fit suggested. Any of these would break Falcon while leaving Module-LWE schemes untouched. It is open, it is aimed squarely at NTRU, and it is the one hypothesis with an already-documented failure regime one factor of 1.75 away ^{[5] [4]}.

Hypothesis B -- a generic reduction advance. Someone improves BKZ or sieving and lowers the exponent below the classical $2^{0.292\beta}$ (or the model-dependent quantum $2^{0.265\beta}$), where $\beta$ is the attack blocksize, for all lattices ^[26]. This is the larger threat in absolute terms: it would weaken Dilithium, Kyber, and Falcon in a single stroke. But that universality is exactly why it is the wrong answer to our question. It moves the whole floor, not Falcon's floor.

Hypothesis C -- transcript leakage. The break that felled NTRUSign. Closed, structurally, by GPV's provable Gaussian sampling, as Section 5 showed. A true-Gaussian transcript is independent of the secret basis, so there is nothing to learn ^{[7] [13]}.

flowchart TD
Q["How could Falcon's mathematics fail?"] --> A["A. NTRU-specific advance, sharper g/f or the cliff moves down"]
Q --> B["B. Generic reduction or sieving advance"]
Q --> C["C. Transcript leakage"]
A --> AV["Open and Falcon-specific, with a documented regime, ranked first"]
B --> BV["Open but hits every lattice scheme, largest yet non-specific"]
C --> CV["Closed by GPV Gaussian sampling, dismissed"]

Set them side by side on the properties that matter.

The table is the argument in miniature. Column C is greyed out by a theorem. Column B is real and frightening, but it is a threat to lattice cryptography as a category, not a Falcon story -- if it lands, the headline is "lattices weakened," and Falcon is one name in a long list. Column A is the only one where the headline reads "Falcon" and no one else.

Say the honest part out loud, because the thesis lives or dies on it. "Most likely" here is a ranked judgment, not a documented fact. No one has broken Falcon's actual parameters; the overstretched attacks break other, large-$q$ NTRU, and the 1.75x margin is an extrapolation across secret distributions.

If you want a claim of the form "here is Falcon, broken," this article cannot give it to you, and neither can anyone else today. What it can give you is a disciplined ordering: given that Falcon will eventually face sharper mathematics, the break that is simultaneously open, Falcon-specific, and already partway documented is the one to bet on first.

The assumption Falcon cannot insure -- the NTRU quotient plus the missing worst-case reduction -- is exactly where the crack is likeliest to begin.

Notice what carries the ranking. It is not that the NTRU attack is close to working -- it is a comfortable distance away. It is that the NTRU attack is the only one of the three that is both live and specific. Hypothesis C had specificity but is dead; Hypothesis B is alive but generic. Only Hypothesis A has both at once -- and in a "how would this scheme break" question, both are what you rank on.

The whole ranking, though, rests on two load-bearing assumptions of its own: that Shor's algorithm really cannot touch Falcon, so the quantum future does not simply erase the question, and that the fatigue cliff really is unproven, so the margin is a research frontier rather than a settled bound. Both deserve a hard look, and the second is more fragile than the first.

11. Theoretical Limits and the Quantum Question#

The most important fact about Falcon's quantum security is a non-result: the algorithm that broke RSA does nothing here.

That deserves to be stated carefully, because it is the reason the whole field exists. Shor's algorithm is not a general code-breaker. It solves one abstract problem exceptionally well, and factoring and discrete logarithm happen to be instances of it.

Lattices sit outside the abelian-HSP family, so Shor has no purchase on Falcon. The closest anyone has come to a quantum handle is a 2004 result of Oded Regev connecting a lattice problem (unique-SVP) to the dihedral hidden-subgroup problem -- but the reduction runs one way only, and no one knows how to prepare the quantum states it would need to run usefully in reverse ^[33]. Two decades of effort have not reversed it.

flowchart TD
Q["Is the hard problem an abelian hidden-subgroup problem?"] -->|Yes, such as RSA and ECC| S["Shor solves it, the scheme is broken"]
Q -->|No, as with lattices| L["Shor does not apply"]
L --> R["The only quantum lever is a faster sieve"]
R --> E["The classical 0.292 beta exponent drops toward 0.265 beta"]
E --> N["A constant-factor gain in the exponent, not a structural collapse"]

So what does a quantum computer buy an attacker against Falcon? One thing, and it is modest in shape if not in size: a faster sieve. Quantum near-neighbor search lowers the sieving exponent from the classical $2^{0.292\beta}$ toward roughly $2^{0.265\beta}$ in the sieve blocksize $\beta$ -- a model-dependent figure associated with the Core-SVP quantum line ^{[26] [28]}. That is a genuine improvement, but look at what kind it is: it lowers the exponent's constant. It makes Hypothesis B a little cheaper. It does not convert the problem into one Shor can solve, and it does not touch the NTRU-specific structure at all. Regev's one-directional reduction lands lattices on the dihedral hidden-subgroup problem ^[33] -- the same problem Kuperberg's sub-exponential algorithm attacks ^[34]. But no one knows how to prepare the coset states that algorithm needs from a lattice instance, which is why it drives attacks on isogeny schemes such as CSIDH ^[35] rather than on lattices. It is a frequent source of confusion in exactly this discussion. Grover's algorithm speeds up unstructured brute-force search ^[36], but Falcon's security rests on the hardness of a lattice problem, not on guessing a symmetric key, so Grover has no structural target here. It is named once and set aside as a generic search speedup, not a break.

Now stack the two things the theory leaves unproven, because together they are the real picture.

Falcon's safety lives in two unproven gaps at once. The reduction gap: at $q = 12289$ there is no worst-case-to-average-case reduction, so no theorem sits beneath the assumption. The fatigue gap: only about 1.75x separates Falcon-512 from an experimental, ternary-secret cliff. Shor cannot touch either gap, and a faster sieve only nudges the generic floor. The real exposure is the NTRU-specific space between those two gaps -- which is exactly why the likeliest structural crack is Hypothesis A, not a quantum collapse and not a generic advance.

This is the understanding that flips the usual intuition. Most people carry a mental model in which "NIST standardized it, so it is proven, and the only danger is a future quantum computer running Shor." Every clause of that is off. Shor cannot touch Falcon. A quantum computer buys only a constant-factor sieving gain against a floor that is already high. And "standardized" does not mean "proven": Falcon's exact parameters have no reduction beneath them, and the boundary that keeps them safe is an experimental fit to a different secret distribution.

There is a positive impossibility in the mix too, and it belongs on the ledger in Falcon's favor. For a true discrete Gaussian, GPV's theorem makes transcript-based key recovery information-theoretically impossible -- not hard, impossible ^[7]. Falcon's quantum-and-theory scorecard is therefore lopsided in a very specific way: strong where people fear weakness (Shor, transcripts), and quietly exposed where people assume strength (the reduction and fatigue gaps).

So the theory leaves Falcon standing on an assumption with no proof beneath it and a cliff whose exact location for its own secrets nobody has pinned. That is not a flaw to hide. It is a research frontier to map -- and the people best placed to map it are already at work. Here is where that frontier actually is.

12. Open Problems and the NTRU-Free Frontier#

The people best positioned to know where Falcon breaks are already building the scheme that would replace it. That is the most honest signal in this whole story.

The research frontier around Falcon is not vague hand-wringing; it is five specific questions, and each one is a lever on the thesis.

Can the fatigue analysis be made a proof? Ducas and van Woerden measured the crossover; no one has proven that NTRU is hard for every $q$ below it, and no one has redone the measurement for Falcon's discrete-Gaussian secrets rather than ternary ones ^[4]. A proof would settle Falcon-512's safety; a sharper measurement could move the cliff either way. This is the single most decisive open problem for the thesis.

Is there an unexploited handle at Falcon's dimension? Both overstretched routes -- subfield and subfield-free -- need a large $q$. Whether some other structural attack on $h = g/f$ beats generic reduction at Falcon's small $q$ is open; the consolidated survey of refinements records steady progress but no sub-generic attack there yet ^{[37] [5]}. Such an attack would be Hypothesis A made real.

Does quantum help lattices beyond sieving? Reversing Regev's one-directional reduction, or finding any quantum lever past the sieving speedup, would reshape the entire field ^[33]. Widely believed impossible, entirely unproven.

Can NTRU's reduction be narrowed to Falcon's parameters? This is the one open problem whose success would strengthen Falcon. OP4 is the escape hatch: narrow the Stehle-Steinfeld reduction toward $q = 12289$ and Falcon's assumption would finally gain the theorem it currently lacks, softening the "least conservative" verdict at the center of this article ^[25]. No one has managed it; the reduction still lives only at large parameters ^[25].

Is Module-LWE's reduction worth the bytes? The practitioner's version of the thesis: quantify how much the worst-case reduction is worth against Falcon's roughly 1.5x to 3.6x size advantage. NIST's answer so far is an institutional hedge -- standardize both, ML-DSA as the default and Falcon for the compact niche -- rather than a resolved ranking ^{[2] [9]}.

And then there is the tell.

That HAWK exists, and that its designers overlap with NTRU's own cliff-mappers, is the strongest available evidence that Falcon's NTRU assumption is a chosen trade-off rather than a free lunch. No standardized scheme occupies the ideal corner -- compact, integer-only, reduction-backed, and quotient-free all at once. Falcon has the compactness and pays with the assumption; ML-DSA has the reduction and pays with bytes; HAWK reaches for the quotient-free corner and pays with youth. The design space has no free lunch, only priced trades.

None of this is a reason to avoid Falcon. It is a reason to deploy it with your eyes open -- which, for a defender planning a real migration, is a concrete and answerable question. What do you actually do on Monday?

13. What a Defender Does on Monday#

You are a defender planning a post-quantum migration. You have read the argument. What do you actually do?

Start by matching the signature to the constraint, not to the hype.

Then decide what you watch, because the thesis tells you exactly what an early warning looks like. Watch the fatigue margin: any result pushing $q \approx 0.004 \cdot n^{2.484}$ downward, or extending it rigorously to discrete-Gaussian secrets and landing lower, is a signal aimed straight at Falcon-512 ^[4]. Watch for a new $g/f$ sublattice technique that bites at Falcon's small $q$ ^[5]. What you do not need to watch for is a sudden Shor-style collapse -- the mathematics rules that out. An NTRU break announces itself as a shrinking margin, not a thunderclap.

Return, finally, to the paradox we opened with. Pierre-Alain Fouque helped build Falcon's trapdoor, and he helped map the overstretched regime that is its likeliest structural fault line. That is not a scandal and not a warning to run from Falcon. It is how good cryptography is supposed to work: the same experts who build a scheme are the ones who probe hardest at where it could give way, in public, with formulas and CPU-years, long before an adversary gets there.

When Falcon eventually cracks, the crack most likely starts in the NTRU structure -- not in Shor, not in a generic sieve, but in the one assumption Falcon's compactness could never insure.

That is the whole argument, assembled from the evidence: transcript leakage is closed by a theorem, a generic advance is real but hits everyone alike, and the NTRU-specific break is the only failure that is open, aimed at Falcon in particular, and already one measured factor of 1.75 away. The ranking is a judgment, not a proof -- but it is the judgment the evidence supports. Deploy Falcon where its smallness earns its place, watch the fatigue margin like a hawk, and keep ML-DSA one configuration change away.

Part 8 of How It Would Break turns to a different assumption entirely -- but the question stays the same: when it breaks, where does the crack start?