Paper 2003/002

Imperfect Decryption and an Attack on the NTRU Encryption Scheme

John Proos

Abstract

A property of the NTRU public-key cryptosystem is that it does not provide perfect decryption. That is, given an instance of the cryptosystem, there exist ciphertexts which can be validly created using the public key but which can't be decrypted using the private key. The valid ciphertexts which an NTRU secret key will not correctly decipher determine, up to a cyclic shift, the secret key. In this paper we present attacks based on this property against the NTRU primitive and many of the suggested NTRU padding schemes. These attacks use an oracle for determining if valid ciphertexts can be correctly deciphered, and recover the user's secret key. The attacks are quite practical. For example, the attack against the NTRU-REACT padding scheme proposed at CRYPTO 2002 with the $N=503$ parameter set requires on average fewer than 30,000 oracle calls and can be performed on a PC in a few minutes. As the traditional definition of a public-key encryption scheme requires perfect decryption, we also define a new type of encryption scheme which encompasses both NTRU and an attack model for the attacks presented against it.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
cryptanalysisNTRU
Contact author(s)
japroos @ math uwaterloo ca
History
2003-01-08: received
Short URL
https://ia.cr/2003/002
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/002,
      author = {John Proos},
      title = {Imperfect Decryption and an Attack on the NTRU Encryption Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2003/002},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/002}},
      url = {https://eprint.iacr.org/2003/002}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.