Léo Ducas — BDGL Sieve, FALCON, g6k, Lattice Algorithms

Léo Ducas (CWI Amsterdam) is one of the most influential researchers in lattice-based cryptography. His work spans lattice reduction, sieving algorithms, signature schemes, fully homomorphic encryption, and security analysis. This article covers his most significant algorithmic contributions and the ideas behind them.

Beginner's Intuition 💡

Think of Léo Ducas as a master architect who didn't just design theoretical, impossible-to-build skyscrapers, but practically bridged the gap between complex mathematical blueprints and real, secure cryptography that we can actually use today.

He helped create some of the fastest ways to break lattice codes (like the BDGL sieve and the g6k tool), which paradoxically helps cryptographers build stronger defenses. He also co-designed FALCON, one of the most compact and efficient "digital wax seals" (digital signatures) in the quantum-resistant world!

BDGL Sieve (2016)

With Becker, Gama, and Laarhoven, Ducas introduced the BDGL sieve — currently the asymptotically fastest classical algorithm for SVP. The key idea is angular locality-sensitive hashing (LSH) to avoid the $O (N^{2})$ pair search that bottlenecks earlier sieves.

Partition the unit sphere $S^{n - 1}$ into $M$ random spherical caps $C_{1}, \dots, C_{M}$ . Hash each vector $v$ to all caps it belongs to. Two vectors $v, w$ are candidate pairs only if they share a cap — i.e., if their angle satisfies $θ (v, w) < 60°$ , which is exactly the condition for $v - w$ to be shorter than both:

∥ v - w ∥^{2} = ∥ v ∥^{2} + ∥ w ∥^{2} - 2 ⟨ v, w ⟩ < ∥ v ∥^{2} ⟺ ⟨ v, w ⟩ > \frac{1}{2} ∥ w ∥^{2}

This reduces the sieve time from $2^{0.415 n}$ (Gauss sieve) to:

T = 2^{0.292 n + o (n)}, M = 2^{0.208 n + o (n)}

Progressive BKZ (2016)

With Ducas, Nguyen, and van Woerden, Ducas developed the progressive BKZ strategy (implemented in FPLLL). Rather than running BKZ- $β$ from scratch, progressive BKZ runs BKZ-2, then BKZ-3, ..., gradually increasing the block size. Each phase uses the output of the previous as input:

BKZ- 2 \to BKZ- 3 \to \dots \to BKZ- β

The Gram–Schmidt profile from smaller block sizes provides a warm start for larger ones, dramatically reducing the total number of SVP oracle calls. In practice this gives a 3–5× speedup over running BKZ- $β$ directly.

g6k (2019)

Co-authored with Albrecht, Herold, Kirshanova, Postlethwaite, and Stevens, g6k (General Sieve Kernel) unified sieving and BKZ into a single programmable framework. See the g6k article for full details. Ducas's specific contribution was the pump abstraction and the progressive sieve database strategy.

FALCON (2017)

FALCON (Fast Fourier Lattice-based Compact Signatures over NTRU) is a NIST-standardized signature scheme (ML-DSA's companion), co-designed by Ducas with Prest, Pornin, and others. It achieves the smallest signature + public key size of any post-quantum scheme.

FALCON is based on the NTRU lattice. Signing requires sampling a short vector from a Gaussian distribution over the lattice coset $Λ + t$ . The key algorithmic challenge is fast Gaussian sampling over an NTRU lattice. Ducas and Prest's solution uses the Fast Fourier Transform on the NTRU ring structure:

sign (m) : sample (s_{1}, s_{2}) \sim D_{Λ + H (m), σ} via FFT sampler

The FFT sampler runs in $O (n lo g n)$ rather than the $O (n^{2})$ of naive Gaussian sampling, making FALCON practical. Signature size for FALCON-512 is 666 bytes — about 3× smaller than Dilithium at the same security level.

NTRU Solves (2021)

Ducas and van Woerden gave the first complete analysis of the security of NTRU against lattice attacks. They characterized precisely which NTRU parameter sets are vulnerable to the "NTRU fatigue" phenomenon — where the structured NTRU lattice is easier to reduce than a random lattice of the same dimension.

Their analysis showed that the security crossover point between structured and random lattice attacks occurs at degree $n \approx 1000$ . Below this threshold, the NTRU structure provides no advantage to an attacker; above it, it does. This directly informed NTRU parameter selection for NIST.

MATZOV and Dual Attacks (2022)

In the MATZOV report (with others from French intelligence), Ducas contributed to a re-analysis of Kyber security using an improved dual lattice attack. The dual attack converts LWE key recovery into an SVP problem in the dual lattice:

A^{T} w \approx 0 (mod q) ⟹ w is a short vector in Λ^{⊥} (A)

Combined with a meet-in-the-middle technique to exploit the small secret distribution, the improved attack reduced Kyber-512 security from the claimed 118 bits to approximately 115 bits — a small margin but sufficient to influence the final parameter choices in ML-KEM.

Role in the NIST Standardization Process

Ducas has been deeply involved in the NIST Post-Quantum Cryptography standardization process (2016–2024) — simultaneously as a submitter, analyst, and de facto referee for lattice-based candidates.

FALCON submission: Ducas co-authored the FALCON submission (2017), which was selected as a NIST standard (FIPS 206, published 2024) alongside Dilithium (ML-DSA). FALCON provides the most compact lattice signatures of any standardized scheme: FALCON-512 produces 666-byte signatures vs. Dilithium2's 2420 bytes at comparable security.

Kyber / ML-KEM security analysis: Ducas contributed to the MATZOV report (2022) re-evaluating Kyber-512 security using improved dual attacks. This analysis fed directly into NIST's final decision to maintain Kyber-512 parameters but tighten the security category bounds. The MATZOV dual attack showed that a hybrid lattice + meet-in-the-middle strategy reduces the effective security of Kyber-512 by approximately 3 bits — from the claimed 118-bit level to roughly 115 bits.

Reviewing other submissions: Ducas publicly analyzed the security of NTRU Prime, CRYSTALS-Kyber, NewHope, and LAC during the NIST rounds, identifying parameter gaps and informing upgrades. His analysis of NTRU fatigue (2021, with van Woerden) was instrumental in NIST's decision to proceed with NTRU parameter sets cautiously.

NewHope and the Road to Kyber

Before Kyber was submitted to NIST, Ducas co-authored NewHope (2016, with Alkim, Pöppelmann, and Schwabe) — a Ring-LWE key exchange that Google deployed experimentally in Chrome in 2016–2017, marking the first large-scale deployment of post-quantum cryptography in a production browser.

NewHope uses a polynomial ring $Z_{q} [x] / (x^{n} + 1)$ with $n = 1024, q = 12289$ . Key encapsulation works by exchanging noisy ring-LWE samples:

Alice sends: (a, b = a s + e), Bob reconciles: u = a r + e^{'}

where $s, r$ are small secret polynomials and $e, e^{'}$ are error terms drawn from a binomial distribution $ψ_{16}$ . The shared secret is derived from the "reconciliation" of $b s - u r$ , which is approximately $(a s + e) s - a (r) s \approx 0$ when errors cancel.

NewHope demonstrated that Ring-LWE-based KEMs could be both provably secure (under the Ring-LWE assumption with a concrete hardness reduction) and fast enough for real-world TLS handshakes. This directly influenced the design philosophy of Kyber, which replaced the reconciliation mechanism with a simpler error-correcting approach and reduced the ring degree to $n = 256$ .

Key Insight Across All Work

A thread runs through Ducas's contributions: the use of algebraic structure to achieve practical speed, combined with careful security analysis that prevents that structure from creating vulnerabilities. FALCON uses NTRU structure for fast sampling but analyzes NTRU security rigorously. g6k uses the lattice's own Gram–Schmidt profile to guide sieving efficiently. Progressive BKZ exploits the continuity of the reduction landscape.

For a developer working with post-quantum cryptography, Ducas's work defines both what you should use (FALCON for compact signatures, ML-KEM for key encapsulation) and what an adversary armed with the best tools can do against them.