Welcome to the resource topic for 2024/601
Title:
Improved Provable Reduction of NTRU and Hypercubic Lattices
Authors: Henry Bambury, Phong Q. Nguyen
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 \mathbb{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 \mathbb{Z}^n.
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.
ePrint: https://eprint.iacr.org/2024/601
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 .