Roughly: Claims generating and using NTRU parameters "causing no decryption error", using the condition "2·p·d+2df−1<q/2" where df is "the number of coefficients in a private key polynomial f whose coefficient values equal to 1".
This might be stretched to cover similar formulas to eliminate decryption failures in other variants of NTRU, so it's a potential problem for the 2005 NTRU parameter sets, Streamlined NTRU Prime, the HRSS NTRU KEM, etc. The priority date of the patent is 24 April 2003, and my understanding of USPTO data is that the patent runs for an extra 1561 days in the US on top of the usual 20 years.
Prior art 1: Hoffstein, Pipher, and Silverman handed out a preprint "NTRU: a new high speed public key cryptosystem" in 1996, in particular at Crypto 1996. Section 4.3 of this draft (page 18) says "NTRU with 0% decoding failure. It is possible to eliminate gap failure entirely by choosing the parameter q sufficiently large. ... a trivial analysis shows that the coefficient range is less than d^2+2dp for binary NTRU and less than r^5 d^2+r^2 dp for symmetric NTRU. So if we choose q larger than this bound, gap failure disappears."
The patent holder will object that this draft wasn't put online until 20 years later. However, handing out documents
should count as prior art under patent law. In MIT v. AB Fortia, 774 F.2d 1104 (Fed. Cir. 1985), the U.S. Court of Appeals for the Federal Circuit (the main court deciding rules for patentability in the U.S.) treated conference handouts as prior art, writing the following:
We agree with the ITC's conclusion that the Birmingham paper is prior art. As the Commission noted, between 50 and 500 persons interested and of ordinary skill in the subject matter were actually told of the existence of the paper and informed of its contents by the oral presentation, and the document itself was actually disseminated without restriction to at least six persons.
In In re Klopfenstein, 380 F.3d 1345 (Fed. Cir. 2004), the same court treated a three-day conference-poster display as prior art. The court said that it was "considering and balancing" the following factors:
the length of time the display was exhibited, the expertise of the target audience, the existence (or lack thereof) of reasonable expectations that the material displayed would not be copied, and the simplicity or ease with which the material displayed could have been copied.
My impression is that similar factors are considered by courts outside the U.S.
Prior art 2: Jaulmes and Joux published a paper in 2000 that includes the following statement about NTRU: "How Decryption Works. ... For appropriate parameter choices, we can ensure that all coefficients of the polynomial ... lie between −q/2 and q/2. So the intermediate value ... is in fact the true (non modular) value of this polynomial. This means that when we compute a and reduce its coefficients into this interval, we recover exactly the polynomial ... Hence ... retrieves the message m."
The patent holder will object that Jaulmes and Joux didn't bother going through the trivial exercise of writing down a safe size for q; they merely said that this can be done. Courts will ask whether doing this is obvious to someone of ordinary skill in the art. I say it is. The patent description seems to say it isn't ("while the existing technique presents conditions for generating NTRU parameters that do not cause any decryption errors, such conditions are not formulated, which makes it difficult to generate NTRU parameters that do not cause any decryption errors"), although Jaulmes and Joux weren't cited.