Paper 2023/582

New NTRU Records with Improved Lattice Bases

Elena Kirshanova, Technology Innovation Institute, I.Kant Baltic Federal University
Alexander May, Ruhr University Bochum
Julian Nowakowski, Ruhr University Bochum
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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published elsewhere. PQCrypto 2023
Keywords
NTRUCryptanalysisBKZSieving
Contact author(s)
elenakirshanova @ gmail com
alex may @ rub de
julian nowakowski @ rub de
History
2023-06-23: revised
2023-04-24: received
See all versions
Short URL
https://ia.cr/2023/582
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/582,
      author = {Elena Kirshanova and Alexander May and Julian Nowakowski},
      title = {New NTRU Records with Improved Lattice Bases},
      howpublished = {Cryptology ePrint Archive, Paper 2023/582},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/582}},
      url = {https://eprint.iacr.org/2023/582}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.