4.5 Ducas

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.

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 $\mathcal{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 — a cheap filter for pairs whose angle satisfies $\theta(v,w) < 60°$, which is the condition for $v - w$ to be shorter than both:

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

Progressive BKZ (2016)

Progressive BKZ is due to Aono, Wang, Hayashi and Takagi (2016), not Ducas, but it is the reduction strategy his sieving tools plug into. Rather than running BKZ-$\beta$ 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:

The Gram–Schmidt profile from smaller block sizes provides a warm start for larger ones, reducing the total number of expensive SVP oracle calls. In practice this is substantially faster than running BKZ-$\beta$ 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. g6k is joint work of all six authors; its pump builds on Ducas’s 2018 “dimensions for free” sieving technique.

FALCON (2017)

FALCON (Fast Fourier Lattice-based Compact Signatures over NTRU) was selected by NIST as ML-DSA’s companion and is being standardized as FN-DSA (draft FIPS 206). Ducas is not one of the FALCON submitters, but the scheme builds directly on his work: the Ducas–Lyubashevsky–Prest (2014) NTRU hash-and-sign framework and the Ducas–Prest (2016) fast Fourier sampler. It has the smallest combined signature and public key of the NIST-selected signatures.

FALCON is based on the NTRU lattice. Signing requires sampling a short vector from a Gaussian distribution over the lattice coset $\Lambda + 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:

The FFT sampler runs in $\mathcal{O}(n \log n)$ rather than the $\mathcal{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 Fatigue (2021)

Ducas and van Woerden studied overstretched NTRU — parameters where the modulus $q$ is large relative to the dimension $n$ — and asked when the NTRU structure makes the lattice easier to reduce than a random lattice of the same dimension.

They located the “fatigue point” concretely: once $q$ grows beyond roughly $n^{2.484}$ (for ternary secrets), BKZ finds a dense sublattice and the attack becomes much cheaper than the usual key-recovery estimate. Standard NTRU encryption and FALCON parameters sit well below this point; the result matters mainly for schemes with very large $q$, such as some FHE and NTRU-based constructions.

MATZOV and Dual Attacks (2022)

The MATZOV report (2022, from the Israeli Defence Forces’ cryptology unit — not Ducas’s work) re-analyzed Kyber security using an improved dual lattice attack. Ducas’s connection is on the analysis side: with Pulles (2023) he showed that the independence heuristics behind such dual attacks can fail. The dual attack converts LWE key recovery into an SVP problem in the dual lattice:

Combined with techniques that exploit the small secret distribution, the improved attack lowered the cost estimates for Kyber-512 somewhat. NIST kept the parameters unchanged.

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: Ducas was not a FALCON submitter, but FALCON is built on his hash-and-sign and fast-sampling work. NIST selected it in 2022 alongside Dilithium (ML-DSA), and it is being standardized as FN-DSA (draft FIPS 206). FALCON provides the most compact lattice signatures of any NIST-selected scheme: FALCON-512 produces 666-byte signatures vs. Dilithium2’s 2420 bytes at comparable security.

Kyber and Dilithium: Ducas is a co-author of CRYSTALS-Kyber and CRYSTALS-Dilithium, standardized as ML-KEM (FIPS 203) and ML-DSA (FIPS 204). When the MATZOV report (2022) proposed cheaper dual attacks on Kyber-512, his later work with Pulles (2023) questioned the heuristics those estimates relied on. NIST kept the Kyber-512 parameters.

Reviewing other submissions: Ducas took an active part in the public cryptanalysis of lattice-based candidates during the NIST rounds.

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 (the CECPQ1 experiment), marking the first large-scale deployment of post-quantum cryptography in a production browser.

NewHope uses a polynomial ring $\mathbb{Z}_q[x]/(x^n+1)$ with $n = 1024, q = 12289$. The key exchange works by exchanging noisy ring-LWE samples:

where $s, r$ are small secret polynomials and $e, e'$ are error terms drawn from a binomial distribution $\psi_{16}$. Bob computes $v = br + e'' \approx asr$ and Alice computes $v' = us \approx ars$. Their difference $v - v' = er + e'' - e's$ is small, and a “reconciliation” step (Bob sends a few hint bits) lets both sides extract the same key.

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 encryption-based 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 strategies, in BKZ and in g6k’s pump, exploit the fact that the cost changes smoothly from one block size to the next.

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.