Improved Provable Reduction of NTRU and Hypercubic Lattices

Henry Bambury; Phong Q. Nguyen

Paper 2024/601

Improved Provable Reduction of NTRU and Hypercubic Lattices

Henry Bambury, DIENS, Ecole normale supérieure, PSL University, CNRS, Inria, Paris, France, DGA, Paris, France

Phong Q. Nguyen, DIENS, Ecole normale supérieure, PSL University, CNRS, Inria, Paris, France

Abstract

Lattice-based cryptography typically uses lattices with special properties to improve efficiency. We show how blockwise reduction can exploit lattices with special geometric properties, effectively reducing the required blocksize to solve the shortest vector problem to half of the lattice's rank, and in the case of the hypercubic lattice $Z^{n}$ , further relaxing the approximation factor of blocks to $\sqrt{2}$ . We study both provable algorithms and the heuristic well-known primal attack, in the case where the lattice has a first minimum that is almost as short as that of the hypercubic lattice . Remarkably, these near-hypercubic lattices cover Falcon and most concrete instances of the NTRU cryptosystem: this is the first provable result showing that breaking NTRU lattices can be reduced to finding shortest lattice vectors in halved dimension, thereby providing a positive response to a conjecture of Gama, Howgrave-Graham and Nguyen at Eurocrypt 2006. Yet, the best primal attack on NTRU heuristically decreases the provable dimension reduction factor to .

Note: V2: fixed minor typos and extended the heuristic analysis in the case of NTRU.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published elsewhere. Minor revision. PQCrypto 2024
DOI: 10.1007/978-3-031-62743-9_12
Keywords: Lattices Cryptanalysis NTRU LIP
Contact author(s): henry bambury @ m4x org
phong nguyen @ inria fr
History: 2025-01-28: revised; 2024-04-18: received; See all versions
Short URL: https://ia.cr/2024/601
License: CC BY

BibTeX

@misc{cryptoeprint:2024/601,
      author = {Henry Bambury and Phong Q. Nguyen},
      title = {Improved Provable Reduction of {NTRU} and Hypercubic Lattices},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/601},
      year = {2024},
      doi = {10.1007/978-3-031-62743-9_12},
      url = {https://eprint.iacr.org/2024/601}
}