Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.


Boosting the Hybrid Attack on NTRU: Torus LSH, Permuted HNF and Boxed Sphere

June 9, 2021


Phong Nguyen - Inria Paris


We revisit collision attacks on NTRU, namely Odlyzko's meet-in-the-middle attack and Howgrave-Graham's hybrid attack. We show how to simplify and improve these attacks with respect to efficiency, analysis and ease of implementation. Our main ingredients are randomization and geometry: we randomize the attacks by introducing
torus variants of locality sensitive hashing (LSH) and new HNF-like bases of the NTRU lattice; and we establish a connection between the success probability of the hybrid attack and the intersection of an n-dimensional sphere with a random box. We provide mathematical and algorithmic bounds for such intersections, which is of independent interest. Our new analyses remain partially heuristic, but are arguably much more sound than previous analyses, and are backed by experiments. Our results show that the security estimates of the NTRU finalist in NIST's post-quantum 
standardization need to be revised.

Event Details



Related Topics

Security and Privacy: post-quantum cryptography

Created June 09, 2021, Updated June 10, 2021