Quoting the first entry in https://ntruprime.cr.yp.to/faq.html
There are known patent threats against the
"Product NTRU"/"Ring-LWE"/"LPR" lattice proposals: Kyber, SABER, and
NTRU LPRime (ntrulpr). These proposals use a "noisy DH +
reconciliation" structure that appears to be covered by U.S. patent
9094189 expiring 2032, and a 2x ciphertext-compression mechanism that
appears to be covered by U.S. patent 9246675 expiring 2033. There are
also international patents, sometimes with different wording.
In the rest of this message I'll elaborate on these patent issues. I'm
filing this as an OFFICIAL COMMENT for Kyber since all signals from NIST
appear to be leaning towards Kyber, but for these issues I don't see any
relevant differences among the LPR-based NISTPQC proposals.
Let me start by emphasizing procedures, starting with the role of
patents in NISTPQC. The word "critical" appears exactly once in the
NISTPQC call for proposals:
NIST believes it is critical that this process leads to cryptographic
standards that can be freely implemented in security technologies and
This is in Section 2.D, "Intellectual Property Statements / Agreements /
Disclosures". NIST appears to have tried to collect statements from
submitters regarding their own patents on their own submissions; this is
helpful, and seems authoritative, but it doesn't make clear that a
submission "can be freely implemented". Sometimes submissions are
covered by patents from other people.
Patents are also included in the call for proposals under evaluation
criterion 4.C.3, "Adoption", which broadly considers all factors "that
might hinder or promote widespread adoption of an algorithm or
implementation", and names "intellectual property" as an example. Again
the statements from submitters regarding their own patents on their own
submissions are not sufficient for evaluating this.
NISTPQC has already established a track record of mistakes even within
the technical areas of expertise of the submitters and evaluators. It's
not reasonable to imagine that evaluations of patent threats will have a
zero error rate. It's important to have procedures in place to recognize
and correct errors in evaluations of patent threats, starting with a
rule of detailed public analyses.
As an analogy, NISTPQC efficiency claims are subjected to detailed
public reviews, even when it's clear that the specific claims matter for
only a narrow (and shrinking) corner of the user base. When two patents
have been identified that can each singlehandedly destroy >99% of the
potential usage of Kyber et al. between now and the early 2030s, we
should be putting a correspondingly careful, publicly reviewed effort
into establishing the magnitude and boundaries of the threat.
NIST IR 8309 says that if "intellectual property issues threaten the
future of KYBER and SABER" then "NTRU would be seen as a more appealing
finalist"---but hides its _reasons_ for saying this. Readers are misled
into thinking this is a purely hypothetical issue. Readers who already
know better aren't being given the opportunity to see and comment on the
NIST handling of patent issues. Given the (obviously intentional) lack
of transparency regarding such an important issue, I've filed a FOIA
request for metadata regarding NIST's secret patent discussions, after
careful consideration of the potential consequences of such a request.
Patent problems, like efficiency problems, are sometimes solved. There
are occasional rumors of efforts to solve NISTPQC patent problems. This
is _not_ an argument against public evaluations of the problems that
currently exist. We should publicly evaluate the dangers to users _and_
publicly evaluate the chance of the dangers going away. If they go away,
great; if they don't, we know how bad they are; either way, we're
putting due diligence into understanding the issues.
I was disappointed to see a recent non-NIST message M on this list where
the ending of M
(1) is the patent equivalent of a map stating "there are no landmines
(2) sounds like it's relying on discussions that, like NIST's patent
discussions, were never even _trying_ to meet the minimum
requirement of being published.
#1 isn't a problem per se but #2 is a problem. The rest of this message
is organized as a reply to the patent comments in M, in the same order
as M. (There are also non-patent topics in M, which I'll address in the
This message includes what might be the first detailed public chart
matching up the LPR cryptosystem to patent 9094189, which was filed 18
February 2010 and wasn't known to the community until eight years later.
In theory, patents are published; in reality, millions of hard-to-read
patents operate as a denial-of-service attack against the general public.
The patent-statement requirement deserves credit for bringing this
submarine patent to the attention of the community---but it did so only
because the patent holders happened to be on other submissions, and it's
completely missing the public analyses needed to establish which
submissions can be "freely implemented".
> What you wrote was not even close to correct,
What I wrote was correct exactly as stated: "it's not hard to imagine
users skipping the rounding since the idea of saving bandwidth in this
way was first published and patented by Ding, two years before Peikert
announced it as new".
> but it's neat to see you try to backtrack like this.
There's no backtracking.
> "In this way" referred specifically to Round-3 Kyber rounding away low
> bits (of Z_q elements)
No. "The rounding" is referring specifically to Kyber's rounding, but
"in this way" is generalizing to what Ding published and patented. See,
e.g., claims 4 and 5 of U.S. patent 9246675.
It's particularly important in patent discussions to be clear about
levels of generality. When a patent has a claim with limitations X+Y+Z,
meaning that it's claiming anything simultaneously doing X and Y and Z,
you can pretty much always find X and Y and Z separately in the prior
art, so someone doing X+Y+Z is doing a special case of the X prior art
and a special case of the Y prior art and a special case of the Z prior
art---but this doesn't invalidate the patent. Even having X+Y and X+Z
and Y+Z as prior art doesn't invalidate the patent. Meanwhile doing
X+Y+Z+A+B+C doesn't escape the patent, since it includes doing X+Y+Z.
> which -- again -- is described in detail in the 2009 paper that
> predates that patent application by more than two years.
No. Readers who follow references to a compression idea "first published
and patented by Ding, two years before Peikert announced it as new" will
see that these are 2012 Ding and 2014 Peikert respectively, and will
find the following statement in 2014 Peikert:
As compared with the previous most efficient ring-LWE cryptosystems
and KEMs, the new reconciliation mechanism reduces the ciphertext
length by nearly a factor of two, because it replaces one of the
ciphertext's two R_q elements with an R_2 element.
This reduction in ciphertext size is such an important part of the paper
that it's also summarized as the culmination of the abstract, as a
consequence of a claimed "innovation" in the paper:
One of our main technical innovations (which may be of independent
interest) is a simple, low-bandwidth _reconciliation_ technique that
allows two parties who ``approximately agree'' on a secret value to
reach _exact_ agreement, a setting common to essentially all
lattice-based encryption schemes. Our technique reduces the
ciphertext length of prior (already compact) encryption schemes
nearly twofold, at essentially no cost.
The basic difficulty here is that Ding had already published and
(unfortunately) patented essentially the same cryptosystem in 2012,
using essentially the same technique. Courts don't care about minor
differences: the "doctrine of equivalents" asks whether the accused
device performs "substantially" the same function in "substantially" the
same way to obtain the same result. (This is the wording in U.S. courts,
but similar principles apply internationally.)
Readers seeing this claim from 2014 Peikert can't logically rule out the
possibility of essentially the same cryptosystem already appearing in
2009 Peikert, but anyone checking 2009 Peikert will see that there's
nothing in that paper anywhere near this level of efficiency. The fact
that one can point to various features of the cryptosystem that already
appeared in the 2009 paper---rounding, noisy multiples, etc.---doesn't
kill the patent.
Here's a summary of how a court will evaluate and reject the argument
that this 2009 Peikert cryptosystem invalidates claim 4 of U.S. patent
* As a preliminary step, the lawyers argue about what exactly the
words in the patent mean. Definitions are settled in enough detail
to evaluate the prior art (and the claimed infringement).
* The defendant's lawyers argue that the 2009 cryptosystem meets all
the limitations of claim 4 of the patent, so the claimed invention
In response, the plaintiff's lawyers have experts testify that the
2009 cryptosystem doesn't have the "ring R_q=F_q[x]/f(x) with
f(x)=x^n+1" from claim 4.
To eliminate equivalence arguments, the plaintiff's experts also
testify that the level of efficiency reached by claim 4 of the
patent (and mentioned in the patent) is just one R_q element for
keys and slightly larger for ciphertexts, far better than the level
of efficiency reached by the 2009 cryptosystem (and mentioned in
the 2009 paper). This is a winning argument; patent courts
understand the concept of efficiency.
* The defendant's laywers argue that the claimed invention is
obvious: specifically, that something covered by claim 4 of the
patent was, at the time of filing of the patent, obvious to someone
of ordinary skill in the art, given the 2009 cryptosystem and other
publications available before the patent was filed.
In response, the plaintiff's lawyers have a slam dunk: if the
cryptosystems covered by claim 4 were obvious to someone of
ordinary skill in the art in 2012, how could they not have been
obvious to the world-renowned author of a 2014 paper claiming that
nothing before 2014 had achieved this level of efficiency? (Not to
mention the reviewers of the paper.)
The defendant's lawyers will try to escape this, maybe even paying
the author to testify that the 2014 paper actually meant something
else, and that really everything in the patent was obvious in 2009
or 2010 or 2011. The plaintiff's lawyers will spend money on other
experts saying the opposite. Patent courts are facing this sort of
battle all the time, and---to make a long story short---basically
always rule against obviousness _unless_ there's a slam-dunk
argument _for_ obviousness, which is the opposite of the situation
There are various sources of randomness in this process, but, given what
2014 Peikert says, the defendant's lawyers will expect to lose the
obviousness argument, and will be desperate to find a pre-2012 lattice
cryptosystem that's as small as Ding's cryptosystem. The 2009
cryptosystem clearly doesn't do the job here.
> No, Kyber's "compactness" -- obtained from its use of a (degree-256)
> polynomial ring -- is entirely orthogonal to its use of rounding
1. The word "No" here falsely claims a contradiction between the
orthogonality statement and the correct statement it was responding to.
2. Regarding the orthogonality statement: Courts understand the idea of
interchangeable parts, but they're also faced with a constant stream of
defendants claiming that _clearly_ the components inside the patent are
interchangeable, while being unable to point to prior art _saying_ that
the components are interchangeable. The winning words for the plaintiff
have been repeated thousands of times: the most important advances often
come from people simply having the cleverness to put together two things
that hadn't been combined before, it's easy to claim in hindsight that
this was obvious but much harder to see it the first time, etc.
> (There are plenty of constructions in the literature with every combination of
> "uses polynomial ring" or not, and "uses rounding" or not.)
Claim 4 of Ding's patent has one party sending one element of R_q =
F_q[x]/(x^n+1)---let's call this the "key"---and the other party sending
one element of R_q plus slightly more information---let's call this the
I'm not aware of any prior lattice systems that are so small. Are you?
Original LPR was one R_q element for the key but two for the ciphertext.
As far as I can tell, compressed LPR was Ding's idea. Pointing to
compressed versions of _larger_ cryptosystems isn't a scientifically
valid argument to refuse to credit him, and, more to the point, won't
work in court.
> > Ding's patent isn't the only problem for Kyber (and SABER): there's the
> > much earlier, February 2010, Gaborit--Aguilar Melchor patent that as far
> > as I can tell covers the entire idea of compact noisy-DH encryption with
> > reconciliation.
> If you really believe this, then you should lay out your reasoning,
> instead of making unjustified assertions.
Many readers will interpret the word "unjustified" here as saying that
there was a request for justification. There had, however, been no such
request before the above statement.
Anyway, now that there's a request for justification (however poorly
worded the request might be), let's go through the details.
There are a few choices of details at this point, since there are some
differences in the members of the patent family. For definiteness let's
take European Patent 2537284; my reason to pick Europe instead of the
U.S. here is that the European patent has already survived one round of
litigation, whereas I haven't heard about any litigation yet regarding
the U.S. patent. (I don't expect the U.S. patent to be invalidated, but,
all else being equal, it's reasonable to estimate the ultimate
invalidation chance as being even lower for a patent that some people
have tried and so far failed to invalidate.)
Within this patent, let's look at Claim 19, and go through the exercise
of matching up the limitations of the claim to the LPR cryptosystem:
* "Cryptographic method": yes;
* "according to any one of Claims 1 to 18": let's pick Claim 1;
* "in which the ring R is the ring F_q[x]/(X^n-1)"---LPR emphasizes
different rings, but the patent description says that one can take
other rings and gives various examples, so LPR will be covered by
(European versions of) the doctrine of equivalents;
* "in other words the set of polynomials with coefficients in the
body F_q with q elements for which the remainder by division with
the polynomial (X^n - 1) is considered"---sure, this is what we
assumed they meant anyway by F_q[x]/(X^n-1).
The remaining task is to match up the limitations of Claim 1 to the LPR
* "Cryptographic method": yes;
* "for communicating a confidential piece of information m"---yes; at
this point m could be either the key or a subsequent user message;
* "between a first electronic entity (A)"---let's assume that in the
LPR example this will be the key generator;
* "and a second electronic entity (B)"---the sender;
* "comprising a distribution step and a reconciliation step"---we'll
check details below;
* "the distribution step comprising several steps consisting in
that"---we'll check details below;
* "on the one hand, the first entity (A): calculates a first syndrome
S_A = X_A + f(Y_A)"---to match this to LPR, let's take Y_A as the
LPR secret, f() as multiplying by some public random ring element,
and X_A as the LPR error;
* "based on a first secret piece of information composed of two
primary elements X_A and Y_A"---yes, the LPR secret Y_A and the LPR
error X_A are both secrets;
* "belonging to a ring R"---yes;
* "and having a norm that is substantially small relative to an
element f(X_A) or f(Y_A)"---yes, the LPR secret Y_A and the LPR
error X_A are both practically guaranteed to be small compared to
the big multiples f(X_A) and f(Y_A);
* "the ring R having addition and multiplication"---yes;
* "f being an internal composition law associating with any element
X_I of the ring R, another element f(X_I) of the ring R"---yes,
multiplying by a public ring element does this;
* "and having the property that, for any pair of elements X_I and Y_I
of R, such that X_I and Y_I have a norm that is small relative to
the elements f(X_I) and f(Y_I), then X_I.f(Y_I) - Y_I.f(X_I) has a
small norm"---sounds like zero, which is definitely small;
* "and generates a first message composed from this first syndrome
S_A"---yes, the LPR public key is sent as part of a message;
* "such that the said first syndrome S_A is accessible by the second
entity (B)"---yes, the LPR sender sees the public key;
* "on the other hand, the second entity (B): calculates a second
syndrome S_B = X_B + f(Y_B)"---yes, the LPR sender has another
secret Y_B multiplied by the same public ring element, and another
* "based on a second secret piece of information composed of two
secondary elements X_B and Y_B"---yes, the LPR sender secret Y_B
and the LPR sender error X_B are both secrets;
* "belonging to the ring R"---yes;
* "and having a norm that is substantially small relative to an
element f(X_B) or f(Y_B)"---yes, same situation as the other side;
* "transmits to the first entity (A) a second message"---yes, this is
the LPR ciphertext;
* "composed from the second syndrome S_B"---yes, the ciphertext
includes the sender's noisy multiple S_B;
* "such that the said second syndrome S_B is accessible by the first
entity (A)"---yes, the LPR receiver sees the ciphertext;
* "characterized in that, during this first distribution step, the
first entity (A) and the second entity (B) respectively calculate a
first intermediate value P_A and a second intermediate value P_B,
such that: P_A = Y_A.S_B = Y_A.X_B + Y_A.f(Y_B)"---yes, the LPR
receiver multiplies the secret Y_A by the ciphertext component S_B,
and the second equation is just the definition of S_B;
* "and P_B = Y_B.S_A = Y_B.X_A + Y_B.f(Y_A)"---yes, the LPR sender
multiplies the sender secret Y_B by the LPR public key S_A;
* "such that, during the reconciliation step, the first entity (A) is
capable of recovering the confidential information"---yes, the LPR
receiver recovers a confidential message in the end;
* "by an operation for decrypting a noisy message"---yes, the LPR
receiver obtains and decrypts a noisy message;
* "composed by the second entity (B)"---yes, the noisy message comes
from the LPR sender;
* "from, among others, the second intermediate value P_B"---yes, the
LPR sender uses P_B in building the noisy message.
I think "LPR" remains the proper name for the cryptosystem, since
scientifically the first publication wins, and as far as I know the
first publication of the cryptosystem was in an April 2010 LPR talk.
However, under patent law, an April 2010 publication doesn't invalidate
a February 2010 patent filing.
> Despite multiple attempts by different experts, I have never seen a
> demonstration of how Kyber/SABER could fall under that patent's claims
Within the above list, what's Kyber doing differently? The noisy message
is shorter (see above re compressed LPR and the 2012 patent), but this
isn't even a literal deviation from the claims of the 2010 patent. More
to the point, the doctrine of equivalents says that one has to be doing
something "substantially" different.
Maybe I should note that it's common for a patent on X+Y (e.g., the
general LPR idea) to be followed by a patent on X+Y+Z (e.g., compressed
LPR). Someone doing X+Y+Z is violating both. But a patent on X+Y is
invalid if there's a _previous_ patent on X+Y+Z, since X+Y+Z is prior
art for X+Y. Again, one has to be clear about levels of generality.
> -- every attempt failed to meet at least three central requirements.
I'll say this with all due respect: My best guess is that whoever did
that analysis was unaware of the doctrine of equivalents and excitedly
reported the minus sign in X^n-1; and that "three" is exaggeration for
rhetorical effect. I would love to see a convincing analysis concluding
that Kyber and other LPR-type systems avoid the patent, but so far this
sounds to me like a combination of ignorance and wishful thinking.
> So, I don't think anyone should credit the belief that the patent
> "covers the entire idea of compact noise-DH encryption with
> reconciliation," without a proper demonstration.
Patents are public, and the rules for interpreting patents are public.
Going through claim 19 and particularly claim 1 is tedious but hardly
rocket science. One _almost_ doesn't even need to know the rules, except
that people who don't know the rules will incorrectly think that the
patent applies only to X^n-1 and not X^n+1.
Again, there are various sources of randomness in court cases, so it's
hard to _guarantee_ that a user deploying an LPR-type cryptosystem will
lose in court, but my assessment is that the risks are close to 100%.
> (Since this issue is quite far afield from the ostensible topic of
> this thread,
Patents arose briefly in the original message as a natural part of a
careful analysis of the main topic of that message:
* The original message gave "two examples of differences between
Core-SVP and Kyber3-Modified-Core-SVP". The second example started
as follows: "Core-SVP for RLWE/MLWE-based systems is defined by 2n
full samples (public multiples plus errors), whether or not the
systems actually apply further rounding to those samples. See,
e.g., the round-2 Kyber submission."
* Within the second example, there was a paragraph discussing two
types of previous NISTPQC commentary consistent with preferring
this Core-SVP definition over Kyber3-Modified-Core-SVP. The second
half of the paragraph was as follows: "Also, certain people have
been claiming that it's a problem if cryptosystem parameters
provide less security in other cryptosystems; it's not hard to
imagine users skipping the rounding since the idea of saving
bandwidth in this way was first published and patented by Ding, two
years before Peikert announced it as new."
Followups led to more detailed patent discussion, and I'm happy to split
patents off into this separate thread, although it seems that NIST needs
the "ROUND 3 OFFICIAL COMMENT: CRYSTALS-KYBER" subject line for all
official comments about Kyber no matter what the specific topic is.
> I'll omit the technical details here, but am happy to
> share with whoever is interested.)
Now that this is a separate thread, please elaborate! It would be great
to have some way to kill or avoid these patents without abandoning the
whole LPR idea. Please tell me that potential LPR users haven't pinned
their hopes of patent avoidance to the choice of sign in X^n+-1. Please
tell me that they haven't pinned their hopes to an unpublished analysis
by an unnamed "expert" unaware of the doctrine of equivalents.