The NTRU public-key cryptosystem has a lot of interesting properties (being resistant to quantum computer attacks, being standardized by several important bodies), but it also has a pretty unique property:
The decryption algorithm does not always work. Sometimes it just gives wrong answers.
Has this been fixed? Is it really a cryptosystem if having the private key is insufficient to decrypt the encrypted messages?
For instance, from Howgrave-Graham et al. (2003) one reads,
“First, we notice that decryption failures cannot be ignored, as they happen much more frequently than one would have expected. If one strictly follows the recommendations of the EESS standard , decryption failures happen as often as every 212 messages with N = 139, and every 225 messages with N = 251. It turns out that the probability is somewhat lower (around 2−40) with NTRU products, as the key generation implemented in NTRU products surprisingly differs from the one recommended in . In any case, decryption failures happen sufficiently often that one cannot dismiss them, even in NTRU products.”
- Nick Howgrave-Graham, Phong Q. Nguyen, David Pointcheval, John Proos, Joseph H. Silverman, Ari Singer, and William Whyte. "The Impact of Decryption Failures on the Security of NTRU Encryption", Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings, Lecture Notes in Computer Science, 2003, Volume 2729/2003, 226-246, DOI:10.1007/978-3-540-45146-4_14