IACR News item: 10 December 2019
Paul Kirchner, Thomas Espitau, Pierre-Alain Fouque
ePrint Report
We introduce a framework generalizing lattice reduction algorithms to module
lattices in order to practically and efficiently solve the $\gamma$-Hermite Module-SVP
problem over arbitrary cyclotomic fields. The core idea is to exploit the
structure of the subfields for designing a doubly-recursive strategy of
reduction: both recursive in the rank of the module and in the field we are
working in. Besides, we demonstrate how to leverage the inherent symplectic
geometry existing in the tower of fields to provide a significant speed-up of the
reduction for rank two modules. The recursive strategy over the rank can also
be applied to the reduction of Euclidean lattices, and we can
perform a reduction in asymptotically almost the same time as matrix
multiplication. As a byproduct of the design of these fast reductions, we
also generalize to all cyclotomic fields and provide speedups for many
previous number theoretical algorithms.
Quantitatively, we show that a module of rank 2 over a cyclotomic field of degree $n$ can be heuristically reduced within approximation factor $2^{\tilde{O}(n)}$ in time $\tilde{O}(n^2B)$, where $B$ is the bitlength of the entries. For $B$ large enough, this complexity shrinks to $\tilde{O}(n^{\log_2 3}B)$. This last result is particularly striking as it goes below the estimate of $n^2B$ swaps given by the classical analysis of the LLL algorithm using the so-called potential.
Finally, all this framework is fully parallelizable, and we provide a full implementation. We apply it to break multilinear cryptographic candidates on concrete proposed parameters. We were able to reduce matrices of dimension 4096 with 6675-bit integers in 4 days, which is more than a million times faster than previous state-of-the-art implementations. Eventually, we demonstrate a quasicubic time for the Gentry-Szydlo algorithm which finds a generator given the relative norm and a basis of an ideal. This algorithm is important in cryptanalysis and requires efficient ideal multiplications and lattice reductions; as such we can practically use it in dimension 1024.
Quantitatively, we show that a module of rank 2 over a cyclotomic field of degree $n$ can be heuristically reduced within approximation factor $2^{\tilde{O}(n)}$ in time $\tilde{O}(n^2B)$, where $B$ is the bitlength of the entries. For $B$ large enough, this complexity shrinks to $\tilde{O}(n^{\log_2 3}B)$. This last result is particularly striking as it goes below the estimate of $n^2B$ swaps given by the classical analysis of the LLL algorithm using the so-called potential.
Finally, all this framework is fully parallelizable, and we provide a full implementation. We apply it to break multilinear cryptographic candidates on concrete proposed parameters. We were able to reduce matrices of dimension 4096 with 6675-bit integers in 4 days, which is more than a million times faster than previous state-of-the-art implementations. Eventually, we demonstrate a quasicubic time for the Gentry-Szydlo algorithm which finds a generator given the relative norm and a basis of an ideal. This algorithm is important in cryptanalysis and requires efficient ideal multiplications and lattice reductions; as such we can practically use it in dimension 1024.
Additional news items may be found on the IACR news page.