U.S. flag   An unofficial archive of your favorite United States government website
Dot gov

Official websites do not use .rip
We are an unofficial archive, replace .rip by .gov in the URL to access the official website. Access our document index here.

Https

We are building a provable archive!
A lock (Dot gov) or https:// don't prove our archive is authentic, only that you securely accessed it. Note that we are working to fix that :)

    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