Ongoing Independent Scrutiny of NTRU Technology

It is important to note that every cryptography system receives attacks from time to time (even those which are 20 years old). We are pleased to see our technology receive this kind of close, independent scrutiny.

This page reviews some recent developments in the independent scrutiny of NTRU technology, as well as recent significant contributions by the NTRU research team. For a more detailed overview, download our NTRU Technology Peer Review Summary, in html or pdf form.

NTRU Lattice and Lattice Reduction Techniques

2005

Howgrave-Graham, Hoffstein, Pipher and Whyte posted the paper On Estimating the Lattice Security of NTRU, analyzing the claims of Ludwig and Buchmann and determining that they were unsupported by the evidence. The paper also analyses the impact of the Random Sampling Reduction due to Schnorr on the NTRU lattice and finds that it is not necessary to adjust the estimated security levels of existing NTRU parameter sets.

Ludwig and Buchmann posted the paper Practical Lattice Basis Sampling Reduction, describing a lattice reduction technique which they claimed reduced the security of a particular NTRU parameter set from 80 bits to 74 bits.

NTRUEncrypt

2005

Hoffstein, Howgrave-Graham, Pipher, Silverman, and Whyte presented thepaper "Choosing Parameter Sets for NTRUEncrypt with NAEP and SVES-3" at CT-RSA 2005.

2003

Howgrave-Graham, Silverman, Singer, and Whyte posted the paper "NAEP: Provable security in the presence of decryption failures". This paper gives a new padding scheme for NTRUEncrypt, and the proof that the security of the padding scheme reduces to an associated lattice problem if decryption failures are negligibly infrequent in the average case.

Hoffstein, Silverman and Whyte posted a revised version of NTRU Technical Report #12, "Estimated Breaking Times for NTRU Lattices", demonstrating that for N=251 it is possible to choose parameter sets that greatly reduce decryption failures without compromising lattice security.

Howgrave-Graham, Silverman and Whyte posted a revised version of NTRU Technical Report #4, "A Meet-In-The-Middle Attack on an NTRU Private Key", refining the formulas for calculating strength against meet-in-the-middle attacks and demonstrating that for recommended parameter sets with N=251 the strength against these attacks is at least 2⁸⁰.

Silverman and Whyte posted NTRU Technical Report 18, "Estimating Decryption Failure Probabilities for NTRUEncrypt", showing that the recommended parameter sets and decryption method for N=251 give a decryption failure probability considerably below 2^-80.

Papers were posted by Howgrave-Graham, Nguyen, Pointcheval, Singer and Whyte, by Proos, and by Meskanen and Renvall, analyzing the effects of decryption failures on the security of NTRUEncrypt. For greatest security, parameters should be chosen so that the chance of a decryption failure is negligible. The paper by Meskanen and Renvall was presented at WCC 2003; a merged paper by Howgrave-Graham, Nguyen, Pointcheval, Proos, Silverman, Singer and Whyte was presented at CRYPTO 2003.

Hong et al presented the paper "Key Recovery Attacks on NTRU without Ciphertext Validation Routine" at ACISP 2003. This paper emphasized the importance of choosing a correct padding method when performing encryption with NTRUEncrypt.

Naslund, Shparlinski and Whyte presented the paper "On the Bit Security of NTRUEncrypt" at PKC 2003. The paper shows that in certain natural computational models every bit of a message encrypted with NTRUEncrypt is as secure as the whole message.

2002

Nguyen and Pointcheval presented the paper "Analysis and Improvements of NTRU Encryption Paddings" at CRYPTO 2002. This paper demonstrated that with the padding scheme SVES-1, the provable security of NTRUEncrypt against chosen plaintext attacks fell short of the desired level. The paper did not give an attack that exploited this observation. Dai later posted an attack that was effective in very specialized circumstances, allowing an attacker to tell which of two specially-constructed messages had been encrypted with slightly better than 50% probability.

Hong et al posted the paper "Chosen-Ciphertext Attacks on Optimized NTRU" on the IACR ePrint server, http://eprint.iacr.org. This paper illustrated an attack that was effective against NTRUEncrypt if no padding scheme was used.

2001

Gentry presented the paper "Key Recovery and Message Attacks on NTRU-Composite," at EUROCRYPT 2001. In it, Gentry presented a clever attack that would work against NTRU if NTRU were ever deployed with the security parameter N not a prime number. His research does not impact NTRU's security in practice, because, from its introduction, NTRU has strongly recommended that N always be prime. Indeed, all commercial implementations conform to NTRU's recommendations, and are immune to this attack. So, while Gentry's research is interesting, it has no practical effect on NTRU's security.

2000

Jaulmes and Joux presented the paper "A Chosen-Ciphertext Attack against NTRU" at CRYPTO 2000. Chosen-ciphertext attacks exist for all public key cryptosystems, including RSA, ECC and NTRU. Such attacks rely on sending specially constructed fake messages and watching to see what happens. The Jaulmes-Joux paper presented interesting new material in this direction and further highlights the need to use industry-standard enveloping techniques with provable security properties in order to protect against chosen-ciphertext and other reaction-type attacks.

These papers exemplify the quality of the ongoing independent scrutiny and analysis of NTRU, which consistently reaffirms its security.

NTRUSign

NTRUSign was first presented at the rump session of Asiacrypt 2001, and officially published in the proceedings of CT-RSA 2003. The current draft of the paper is available here.

2004

Min, Yamamoto and Kim published the paper "Weak property of malleability in NTRUSign", demonstrating that an attacker can find multiple valid NTRUSign signatures on a message if they are given a single valid signature to start from. However, the attacker cannot find signatures on any messages for which they do not already know a valid signature.

2003

The NTRUSign paper was presented at CT-RSA 2003. Szydlo presented the paper "Hypercubic Lattice Reduction and Analysis of GGH and NTRU Signatures" at Eurocrypt 2003, analyzing the difficulty of a problem known as the Gram Matrix Problem. Published estimates of NTRUSign security already assume the Gram Matrix Problem is easy, so the results in this paper, while interesting, do not affect NTRUSign parameter sets.

2002

At Eurocrypt 2002, in their paper about attacks on the NSS algorithm, Mike Szydlo and Craig Gentry presented methods of attack against the preliminary version of NTRUSign. These are discussed in the current draft of the paper.

For more details on NTRUSign, see our Introduction to NTRUSign page.

NSS

Mike Szydlo from RSA Laboratories and Craig Gentry from NTTDoCoMo USA Group's DoCoMo Communications Laboratories presented new research on NSS at the rump session of CRYPTO 2001; this research was formally presented at Eurocrypt 2002. Earlier results of this research, carried out by Jacques Stern of the Ecole Normale Superieure and Jakob Jonsson of RSA Labs, Sweden in conjunction with the two researchers just named, were presented as a reviewed paper at AsiaCrypt in December 2001.

These results make it clear that NSS should not be recommended for use. NTRU instead recommends the NTRUSign algorithm, presented at the AsiaCrypt rump session. For more details on NTRUSign, see our Introduction to NTRUSign page.