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.

    Presentations 2021
Presentation

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

June 9, 2021

Presenters

Phong Nguyen - Inria Paris

Description

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

Location

    
                        

                


                

        
 Related Topics


            

                Security and Privacy:
                    post-quantum cryptography            

    


        

        






    


            Created June 09, 2021, Updated June 10, 2021