NTRU | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

NTRU is an open-source public-key cryptosystem that uses lattice-based cryptography to encrypt and decrypt data. It consists of two algorithms: NTRUEncrypt, which is used for encryption, and NTRUSign, which is used for digital signatures. Unlike other popular public-key cryptosystems, it is resistant to attacks using Shor's algorithm. NTRUEncrypt was patented, but it was placed in the public domain in 2017. NTRUSign is patented, but it can be used by software under the GPL. The first version of the system, which was called NTRU, was developed in 1996 by mathematicians Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. That same year, the developers of NTRU joined with Daniel Lieman and founded the company NTRU Cryptosystems, Inc., and were given a patent on the cryptosystem. The name "NTRU", chosen for the company and soon applied to the system as well, was originally derived from the pun Number Theorists 'R' Us or, alternatively, stood for Number Theory Research Unit. In 2009, the company was acquired by Security Innovation, a software security corporation. In 2013, Damien Stehle and Ron Steinfeld created a provably secure version of NTRU, which is being studied by a post-quantum crypto group chartered by the European Commission. In May 2016, Daniel Bernstein, Chitchanok Chuengsatiansup, Tanja Lange and Christine van Vredendaal released NTRU Prime, which adds defenses against potential attack to NTRU by eliminating algebraic structure they considered worrisome. However, after more than 20 years of scrutiny, no concrete approach to attack the original NTRU exploiting its algebraic structure has been found so far. NTRU became a finalist in the 3rd round of the Post-Quantum Cryptography Standardization project, whereas NTRU Prime became an alternate candidate. At equivalent cryptographic strength, NTRU performs costly private-key operations much faster than RSA does. The time of performing an RSA private operation increases as the cube of the key size, whereas that of an NTRU operation increases quadratically.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (2)

In this paper we view the possibilities to lance a multiple (iterative) birthday attack on NTRU. Recently Wagner's algorithm for the generalized birthday problem [9] allowed to speed-up several combinatorial attacks. However, in the case of NTRU we can not hope to to apply Wagner's algorithm directly, as the search space does not behave nicely. In this paper we show that we can nevertheless draw profit from a multiple birthday approach. Our approach allows us to attack ees251ep6 parameter set on a computer with only 2(52) Bits of memory and about 2(9) times faster as with Odlyzko's combinatorial attack - this is an improvement factor about 2(43) in space complexity. We thus contradict the common believe, that in comparison to computational requirements, the "storage requirement is by far the larger obstacle" [3] to attack NTRU by combinatorial attacks. Further, our attack is about 2(7) times faster than the space-reduced variant from [3] employing the same amount of memory.

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2009

A multiple birthday attack on NTRU

In this paper we view the possibilities to lance a multiple (iterative) birthday attack on NTRU. Recently Wagner's algorithm for the generalized birthday problem (Wagner, 2002) allowed to speed-up several combinatorial attacks. However, in the case of NTRU we can not hope to to apply Wagner's algorithm directly, as the search space does not behave nicely. In this paper we show that we can nevertheless draw profit from a multiple birthday approach. Our approach allows us to attack ees251ep6 parameter set on a computer with only 252 Bits of memory and about 29 times faster as with Odlyzko's combinatorial attack - this is an improvement factor about 243 in space complexity. We thus contradict the common believe, that in comparison to computational requirements, the "storage requirement is by far the larger obstacle" (Howgrave-Graham, 2007) to attack NTRU by combinatorial attacks. Further, our attack is about 27 times faster than the space-reduced variant from (Howgrave-Graham, 2007) employing the same amount of memory.

Insticc-Inst Syst Technologies Information Control & Communication, Avenida D Manuel L, 27A 2 Esquerdo, Setubal, 2910-595, Portugal2008