Fighting patents

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

- at a conference open to the public (even if there are registration fees)
- without confidentiality restrictions

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.