Cryptographic hardness of module lattices – CHARM

With quantum computing coming closer to fruition, the security of currently deployed public-key cryptography standards may near its end. It is hence pressing to investigate mathematical and complexity-theoretic foundations that are resistant to quantum computers. Led by the National Institute of Standards and Technology (NIST) post-quantum standardization effort, there has been significant progress towards making quantum-safe cryptography ready for wide-spread practical deployment. Among the finalist candidates in the NIST standardization project, five out of seven have their security that relies on the presumed computational intractability of problems involving algebraic number theory Euclidean lattices. These lattices correspond to small-rank modules over the rings of integers of high-degree number fields. This proposed NSF-ANR collaborative project aims at studying the algorithmic and computational complexity aspects of lattice problems when they are restricted to modules over the rings of integers of number fields.

At present, no better algorithm is known, which takes advantage of the extra algebraic structure, to solve these structured lattice problems faster than generic lattice algorithms, for typical cryptographic parameters. However, there exist a few attacks taking advantage of the algebraic structure of specific module lattices (in rank 1 or in rank 2 with an unexpectedly short vector), but they are limited to parameter regimes of limited cryptographic interest. Assessing to which extent these attacks extend to the standard Ring Learning With Errors problem is completely open. In fact, the algorithmic study of module lattices,
such as those derived from Ring-LWE, is still in its infancy: it is only just over a year ago that was proposed the first lattice reduction algorithm designed to exploit the module structure. From a complexity-theoretic perspective, the situation is similarly puzzling, with unestablished relationships between central problems such as Ring-LWE, the Shortest Vector problem for ideal and module lattices, and the NTRU problem.

The primary focus of this collaborative proposal is to provide a clearer understanding of the intractability of module lattice problems of cryptographic interest, via improved reductions between them and improved dedicated algorithms. The research initiatives include: (i) Investigate algorithms for Ideal-SVP which have a better approximation factor below the current barrier without requiring pre-processing; study dedicated algorithms for specific number fields such as cyclotomics and multiquadratics. (ii) Understand the precise complexity of the NTRU assumption and its relation with other average-case module lattice problems; investigate better algorithms for attacking the NTRU assumption; understand the precise relation (or lack thereof) between the subfield structure of the underlying field and the security of NTRU. (iii) Understand the hardness “transition” between rank-1 and rank-2 module lattice problems; investigate whether rank-1 algorithms can be extended to rank-2 modules. (iv) Contribute to efficient and robust open-source software for lattice algorithms and algebraic number theory. The research outcomes will benefit the cryptography community and developers of lattice-based cryptosystems, and help informing the current cryptographic standard process by NIST.

This collaborative CISE-ANR project brings together a group of experts from four institutions, with complementary skills and research experiences on algorithms for generic lattices and algebraic lattices, hardness proofs for lattice problems, heuristic algorithms and efficient implementations for lattice problems.