Does NTRU decrypt correctly now? 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 [3], 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 [3]. 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
The likelihood of a decryption failure can be made arbitrarily small. IEEE P1363.1 says in appendix A.4.10:

For ternary polynomials with $d$ $+1$s and the same number of $-1$s, the chance of a decryption failure is given by [B30]:
$$\operatorname{Prob}_{(q, d, N)}(\text{Decryption fails}) = P_{(d, N)} \left( \frac{q - 2}{6} \right)$$
where
$$P_{(d, N)}(c) = N \times \operatorname{erfc} \left( \frac{c}{\sigma\sqrt{2N}} \right)$$
and
$$ \sigma(d, N) = \sqrt{\frac{8d}{3N}}$$

where $\operatorname{erfc}(x)$ is the Gauss error function.
As a practical example, for the EES1087EP2 parameter set where $N=1087$, $q=2048$, and $d=120$, the failure probability is $5.62·10^{-78}$, which is a bit less than $2^{-256}$. Those parameters have been chosen for a $256$-bit security level in general, and the failure probability is also smaller than $2^{-256}$. So exploiting a decryption failure requires just as much work as breaking other parts of the system.
Ps. The [B30] reference is to the paper &quot;Hybrid
Lattice reduction and Meet in the Middle Resistant Parameter Selection for NTRUEncrypt&quot; by P. Hirschhorn, J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman and W. Whyte.