Léo Ducas
YOU?
Author Swipe
View article: Wagner's Algorithm Provably Runs in Subexponential Time for SIS$^\infty$
Wagner's Algorithm Provably Runs in Subexponential Time for SIS$^\infty$ Open
At CRYPTO 2015, Kirchner and Fouque claimed that a carefully tuned variant of the Blum-Kalai-Wasserman (BKW) algorithm (JACM 2003) should solve the Learning with Errors problem (LWE) in slightly subexponential time for modulus $q=\mathrm{p…
View article: Provable lattice reduction of $$\mathbb {Z}^n$$ with blocksize n/2
Provable lattice reduction of $$\mathbb {Z}^n$$ with blocksize n/2 Open
The Lattice Isomorphism Problem (LIP) is the computational task of recovering, assuming it exists, an orthogonal linear transformation sending one lattice to another. For cryptographic purposes, the case of the trivial lattice $$\mathbb Z^…
View article: Smoothing Codes and Lattices: Systematic Study and New Bounds
Smoothing Codes and Lattices: Systematic Study and New Bounds Open
In this article we revisit smoothing bounds in parallel between lattices $and$ codes. Initially introduced by Micciancio and Regev, these bounds were instantiated with Gaussian distributions and were crucial for arguing the security of man…
View article: An Algorithmic Reduction Theory for Binary Codes: LLL and More
An Algorithmic Reduction Theory for Binary Codes: LLL and More Open
In this article, we propose an adaptation of the algorithmic reduction theory of lattices to binary codes. This includes the celebrated LLL algorithm (Lenstra, Lenstra, Lovasz, 1982), as well as adaptations of associated algorithms such as…
View article: Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time
Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time Open
In this article, we study the geometry of units and ideals of cyclotomic rings and derive an algorithm to find a mildly short vector in any given cyclotomic ideal lattice in quantum polynomial time, under some plausible number-theoretic as…
View article: Random Self-reducibility of Ideal-SVP via Arakelov Random Walks
Random Self-reducibility of Ideal-SVP via Arakelov Random Walks Open
Fixing a number field, the space of all ideal lattices, up to isometry, is naturally an Abelian group, called the Arakelov class group. This fact, well known to number theorists, has so far not been explicitly used in the literature on lat…
View article: On the Statistical Leak of the GGH13 Multilinear Map and some Variants
On the Statistical Leak of the GGH13 Multilinear Map and some Variants Open
International audience
View article: CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM
CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM Open
\n Contains fulltext :\n 195423pub.pdf (Publisher’s version ) (Open Access)\n \n Contains fulltext :\n 195423pre.pdf (Author’s version preprint ) (Open Access)\n
View article: CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme
CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme Open
In this paper, we present the lattice-based signature scheme Dilithium, which is a component of the CRYSTALS (Cryptographic Suite for Algebraic Lattices) suite that was submitted to NIST’s call for post-quantum cryptographic standards. The…
View article: CRYSTALS - Kyber: A CCA-secure Module-Lattice-Based KEM
CRYSTALS - Kyber: A CCA-secure Module-Lattice-Based KEM Open
Rapid advances in quantum computing, together with the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digital-signature, encryption, and key-establishment protocols, have created signi…
View article: Frodo
Frodo Open
Lattice-based cryptography offers some of the most attractive primitives believed to be resistant to quantum computers. Following increasing interest from both companies and government agencies in building quantum computers, a number of wo…
View article: Fast Fourier Orthogonalization
Fast Fourier Orthogonalization Open
The classical fast Fourier transform (FFT) allows to compute in quasi-linear time the product of two polynomials, in the {\\em circular convolution ring} R[x]/(x^d−1) --- a task that naively requires quadratic time. Equivalently, it allows…