Paper 2021/999

NTRU Fatigue: How Stretched is Overstretched?

Léo Ducas and Wessel van Woerden

Abstract

Until recently lattice reduction attacks on NTRU lattices were thought to behave similar as on (ring-)LWE lattices with the same parameters. However several works (Albrecht-Bai-Ducas 2016, Kirchner-Fouque 2017) showed a significant gap for large moduli $q$, the so-called overstretched regime of NTRU. With the NTRU scheme being a finalist to the NIST PQC competition it is important to understand ---both asymptotically and concretely--- where the fatigue point lies exactly, i.e. at which $q$ the overstretched regime begins. Unfortunately the analysis by Kirchner and Fouque is based on an impossibility argument, which only results in an asymptotic upper bound on the fatigue point. It also does not really explain how lattice reduction actually recovers secret-key information. We propose a new analysis that asymptotically improves on that of Kirchner and Fouque, narrowing down the fatigue point for ternary NTRU from $q \leq n^{2.783+o(1)}$ to $q=n^{2.484+o(1)}$, and finally explaining the mechanism behind this phenomenon. We push this analysis further to a concrete one, settling the fatigue point at $q \approx 0.004 \cdot n^{2.484}$, and allowing precise hardness predictions in the overstretched regime. These predictions are backed by extensive experiments.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2021
Keywords
NTRUcryptanalysislattice techniques
Contact author(s)
wvw @ cwi nl
History
2021-09-08: revised
2021-07-28: received
See all versions
Short URL
https://ia.cr/2021/999
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/999,
      author = {Léo Ducas and Wessel van Woerden},
      title = {{NTRU} Fatigue: How Stretched is Overstretched?},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/999},
      year = {2021},
      url = {https://eprint.iacr.org/2021/999}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.