Welcome to the resource topic for 2023/582
Title:
New NTRU Records with Improved Lattice Bases
Authors: Elena Kirshanova, Alexander May, Julian Nowakowski
Abstract:The original NTRU cryptosystem from 1998 can be considered the starting point of the great success story of lattice-based cryptography. Modern NTRU versions like NTRU-HPS and NTRU-HRSS are round-3 finalists in NIST’s selection process, and also Crystals-Kyber and especially Falcon are heavily influenced by NTRU.
Coppersmith and Shamir proposed to attack NTRU via lattice basis reduction, and variations of the Coppersmith-Shamir lattice have been successfully applied to solve official NTRU challenges by Security Innovations, Inc. up to dimension n=173.
In our work, we provide the tools to attack modern NTRU versions, both by the design of a proper lattice basis, as well as by tuning the modern BKZ with lattice sieving algorithm from the G6K library to NTRU needs.
Let n be prime, \Phi_n := (X^n-1)/(X-1), and let \mathbb{Z}_q[X]/(\Phi_n) be the cyclotomic ring. As opposed to the common belief, we show that switching from the Coppersmith-Shamir lattice to a basis for the cyclotomic ring provides benefits. To this end, we slightly enhance the LWE with Hints framework by Dachman-Soled, Ducas, Gong, Rossi with the concept of projections against almost-parallel hints.
Using our new lattice bases, we set the first cryptanalysis landmarks for NTRU-HPS with n \in [101,171] and for NTRU-HRSS with n \in [101,211]. As a numerical example, we break our largest HPS-171 instance using the cyclotomic ring basis within 83 core days, whereas the Coppersmith-Shamir basis requires 172 core days.
We also break one more official NTRU challenges by Security Innovation, Inc., originally worth 1000$, in dimension n=181 in 20 core years.
ePrint: https://eprint.iacr.org/2023/582
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .