Executive summary: The "OFFICIAL COMMENT" that I'm replying to is
incorrect regarding every topic of dispute. The errors range from (1)
obvious to (2) more subtle but already discussed in detail on pqc-forum.
The "OFFICIAL COMMENT" also misrepresents its disputed arguments as
undisputed, which is inappropriate.
Details follow, beginning with a review of ciphertext sizes and
continuing with replies to the "OFFICIAL COMMENT".
Regarding 2x ciphertext compression, the numbers speak for themselves:
* 1568-byte ciphertext, including suboptimal encoding and CCA
protection: Kyber-1024. This uses modulus q=3329.
* 2996-byte ciphertext, with optimal encoding, no CCA protection: LPR
with the ring (\Z/3329)[x]/(x^1024+1). An LPR ciphertext has 2 ring
elements, and ceil(2*1024*log(3329)/log(256)) = 2996.
1568 is 52% of 2996. Here's another example:
* 1472-byte ciphertext, with optimal encoding, including CCA
protection: FireSABER. This uses modulus q=8192.
* 3328-byte ciphertext, with optimal encoding, no CCA protection:
LPR with the ring (\Z/8192)[x]/(x^1024+1).
1472 is 44% of 3328. Here's another example:
* 2208 bytes, including suboptimal encoding and CCA protection:
submitted NewHope-1024. This uses modulus q=12289.
* 3478 bytes, with optimal encoding, no CCA protection: LPR
ciphertexts for the ring (\Z/12289)[x]/(x^1024+1).
2208 is 63% of 3478. Here's another example:
* 2048 bytes, including suboptimal encoding, no CCA protection:
original NewHope-1024. This uses modulus q=12289.
* 3478 bytes, with optimal encoding, no CCA protection: LPR
ciphertexts for the ring (\Z/12889)[x]/(x^1024+1).
2048 is 59% of 3478. Original NewHope, in turn, was based on BCNS, which
was based on https://eprint.iacr.org/2014/070
, which highlighted smaller
ciphertexts than LPR as something new---
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
---and correctly stated that an LPR ciphertext has "two R_q elements".
Retroactive efforts at obfuscation do not have the power to stop a
patent court from reaching clarity regarding the ciphertext sizes.
The quoted statement from https://eprint.iacr.org/2014/070
also has an
important error that would be identified in a patent case. The statement
isn't simply a claim to be 2x better than LPR, but rather a claim to be
2x better than the "previous most efficient ring-LWE cryptosystems and
KEMs"---which isn't true. Ding's paper https://eprint.iacr.org/2012/688
was two years earlier, and was already 2x smaller than LPR.
The continued failure of https://eprint.iacr.org/2014/070
appropriate credit to Ding is in violation of basic ethics rules (see,
) and, as a historical matter,
led directly to
* BCNS at first being unaware of Ding's contribution,
* NewHope at first being unaware of Ding's contribution, and
* Google at first being unaware of Ding's contribution.
Google rolled out a big experiment with NewHope in July 2016, saying
that it wanted "to help ensure our users' data will remain secure long
into the future" and that it would end the experiment "within two years,
hopefully by replacing it with something better". Google suddenly ended
the experiment a few _months_ later, after Ding reportedly contacted
Google about his patent. Google then waited _three years_ before trying
a new post-quantum experiment---and didn't select an LPR-type system.
Late-2016 awareness of Ding's patent prompted various efforts to build
LPR-type systems that work around the patent without regressing to the
original LPR ciphertext sizes. The most interesting idea is to build
LPR-type systems without "reconciliation" and thus avoid Ding's patent.
This sounds great if it works. Unfortunately, a careful examination
shows that this dividing line is ill-defined---which is a huge problem
in a patent case, since the procedures used in patent courts force
everything to be defined. See the analysis in my pqc-forum message dated
1 Jan 2021 13:19:26 +0100.
Christopher J Peikert writes:
> Summary of this comment:
> 1. The NTRU Prime FAQ starts with an objectively false factual claim
> about competing submissions Kyber and SABER.
No, the FAQ (https://ntruprime.cr.yp.to/faq.html
) is correct as stated.
> 2. This false claim
Again, the FAQ is correct as stated.
> is central to the FAQ's misleading attempt to
> suggest that these systems infringe on a patent.
The FAQ correctly warns people about patent _threats_. This is an
important public service. Unlike some overconfident commentators, the
FAQ also notes the uncertainties here:
Perhaps the appeal regarding 9094189, and subsequent litigation
regarding both patents, will succeed in eliminating these patents or
limiting their coverage. However, today it is far from clear that
"Product NTRU"/"Ring-LWE"/"LPR" systems will be free to use before
The NISTPQC call for submissions says that it is "critical that this
process leads to cryptographic standards that can be freely implemented
in security technologies and products". NIST's analyses of the patent
threats should have been online years ago for public review.
> 3. Requests to the NTRU Prime team to remove the false claim and
> insinuation were refused.
The FAQ is correct as stated. The recent email messages that Dr. Peikert
characterizes as "requests" were inappropriate and triggered a complaint
from the NTRU Prime team to NIST dated 28 Sep 2021 20:39:53 +0300, also
sent to Dr. Peikert.
> 4. I therefore believe that this is not an honest mistake, but a
> deliberate attempt to smear competing proposals with false disparaging
> claims and FUD.
Once again, the FAQ is correct as stated.
> 5. I request that NIST consider what to do about patterns of behavior
> like this.
> The first answer of the NTRU Prime FAQ, which appears on the official
> project website [link <https://ntruprime.cr.yp.to/faq.html
>] and was
> repeated by Dan Bernstein on the pqc-form on 11 December 2020 [link
> says this (emphasis added):
> "There are known patent threats against ... Kyber, SABER, and NTRU LPRime
> (ntrulpr). *These proposals use ... a 2x ciphertext-compression mechanism* that
> *appears to be covered* by U.S. patent 9246675 expiring 2033."
> (The ellipses replace another claim of threat from a different patent,
That patent, U.S. patent 9094189, is another patent threatening the
LPR-type systems. This is also why NIST tried to buy out the patent.
> which is outside the scope of this message, but was also shown to be
> severely flawed; see, e.g., [link
Nope. See, e.g., my pqc-forum email dated 17 May 2021 12:09:27 +0200.
> *As a matter of objective fact, the "2x" claim is false.*
The 2x claim is correct. See numbers above.
> While Kyber and SABER do perform some mild ciphertext compression,
> they do not, and could not, come close to 2x with the mechanism they
They certainly do come close to 2x. See numbers above. Also, the notion
that the exact magnitude is important was addressed in my pqc-forum
message dated 1 Jan 2021 13:19:26 +0100: "It's normal in patent cases
for defendants to try to avoid a patented efficiency improvement by
interpolating between the prior art and the efficiency improvement, and
it's normal for the patentee to win."
> (I pointed out this false "2x" claim on the pqc-forum on 11 December 2020 [
> and again on 21 May 2021 [link
> and in private correspondence with the NTRU Prime team, with an explicit
> request to correct it, but the team refused.)
> Why does this matter?
> *The false "2x" claim is central to the FAQ's attempt to tie Kyber and
> SABER to the cited patent.*
The 2x claim is correct. See numbers above.
> Specifically, the "appears to be covered" claim
> implicitly conflates the patented mechanism, which does provide (near-)2x
> compression, with
No. Everything is explicit in various pqc-forum messages, notably my
email dated 1 Jan 2021 13:19:26 +0100, which goes through the relevant
systems in detail and certainly doesn't conflate anything.
> the unpatented prior-art method that Kyber/SABER use.
Now _this_ is an example of conflation, where a claimed _analogy_
between Kyber and prior-art systems is being misstated as an _equality_.
That's not how patent cases work.
> Kyber/SABER's compression mechanism is, informally: "drop some low
> bits of certain integers, keeping the several high bits needed for
> correct decryption."
The "mechanism" concept used here is divorced from patent law.
> This method appears in at least four well known works of prior
> art to the cited patent, some of which are cited in every version of the
> Kyber submission. For details, see the last part of my pqc-forum message
> from 21 May 2021 [link
How many of those publications presented compressed LPR? Zero. A lawyer
would have to try to turn this into an _obviousness_ argument, saying
that compressed LPR was _obvious_ from the prior art, but then the
opposing lawyer pulls out a 2014 paper from an expert saying
One of our main technical innovations ... reduces the ciphertext
length of prior (already compact) encryption schemes nearly twofold
... 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
which clearly states that no previous work had compressed the ciphertext
below "two R_q elements". If an expert in 2014 was claiming this as new,
the result of an "innovation", how can it have been obvious in 2012?
> The patent describes a *different* compression mechanism whose main benefit
> is that it can provide near-2x in certain contexts, by keeping just a
> single bit of certain integers. Kyber/SABER do not use this method, and the
> patent does not claim the above prior-art method that they do use. A
> detailed explanation of the prior art and the differences between the
> methods is given in my pqc-forum message from 22 May 2021 [link
See above regarding (1) "mechanism", (2) the notion that exact magnitude
is important here, and (3) the ill-defined claimed dividing line between
Kyber/SABER and what's patented.
> In private correspondence with the NTRU Prime team, based on the above
> reasoning I stated that *the FAQ's "appears to be covered" claim is highly
> misleading*, and requested that it be removed. The team refused.
See above regarding this "request".
> The above summarizes, for the record, the history regarding the facts and
"For the record"? The cited messages are already on the record, except
for the recent "request".
> The rest of this message contains my conclusions about the
> situation, and a discussion of how to proceed from here.
> *I believe that the FAQ entry is a deliberate attempt to smear competing
> proposals with false disparaging claims and FUD.* Of course, the false "2x"
> claim could originally have been an unintentional error---albeit a sloppy
> one, showing unfamiliarity with basic properties of the schemes.
Let's see here:
* On one side, compression of 2996 bytes to 1568 bytes, 52%, is being
described as "some mild ciphertext compression" but nothing "close
* On the other side, compression of 2996 bytes to 1568 bytes, 52%, is
being described as "2x" and "twofold".
I don't think any commentary is needed here for the reader to see which
side is correct. I'll skip commenting on the endless personal attacks.
> However, the team's refusal to fix even this elementary factual error leads
> me to conclude that the claim has been made intentionally to deceive, i.e.,
> to conflate the unpatented prior art with the patent's near-2x method, and
> to misleadingly suggest that Kyber/SABER infringe on the patent. Without
> "2x," there's no link to the patent, and the FAQ entry falls apart (along
> with subsequent entries that are premised on it).
This whole "refusal to fix" narrative, exploration of consequences, and
so on tries to force the reader to imagine that there's something to fix
in the first place. There isn't.
> *What next?*
> I hope the above material sets the record straight.
It doesn't. This "OFFICIAL COMMENT" is wasting everyone's time by
repeating previous errors with marginally different wording.
> But this example raises the broader issue of NIST PQC participants who
> exhibit a pattern of the following behavior:
> 1. Falsely disparage other submissions and/or the process itself.
> 2. Receive corrections showing these claims to be factually false or
> otherwise meritless.
> 3. Make no withdrawal of the false claims. Even worse, give no
> acknowledgment of the corrections. Even worse than that, persist in
> spreading the false claims.
Anyone who looks at the detailed analysis in my message dated 1 Jan 2021
13:19:26 +0100 can see that the above is not a defensible description of
the history. It's disturbing to see this "OFFICIAL COMMENT" trying to
add undeserved weight to its incorrect position by spreading outright
misinformation regarding the status of the discussion.
The loaded word "disparagement" above seems likely to trigger emotional
reactions, so let's take a moment to consider how the Frodo submission
* includes a worst-case-to-average-case reduction in its list of
"reductions supporting the security of FrodoKEM" and
* highlights "several lattice-based proposals that lacked such
reductions, and turned out to be insecure".
This is the obvious source of, e.g., NIST IR 8309 claiming that NTRU
"lacks a formal worst-case-to-average-case reduction" and not saying the
same regarding Frodo. However, the claim that Frodo has an advantage
here---that it has reductions that, e.g., NTRU does not have---is wrong.
* my pqc-forum email dated 21 Apr 2018 22:15:53 -0000,
* my pqc-forum email dated 22 Apr 2018 21:04:33 -0000 (which
described the security-failure mode that we then saw with MQDSS),
* my pqc-forum email dated 23 Apr 2018 15:42:22 -0000, and
* Section 9 of https://cr.yp.to/papers.html#latticeproofs
It's now 3 years later, and the Frodo submission continues to spread
the same claim. Note that the negative effect of the claim upon NTRU
doesn't rely upon the Frodo submission identifying NTRU as an example.
> (Some other examples of this pattern appear at the end of this message.)
> This kind of behavior is outside the bounds of fair play. It sows confusion
> among non-experts who may only be able to see a "controversy," and it badly
> wastes the community's time that could be better spent on more productive
> matters. (Brandolini's law estimates the cost at 10x, but I think that's
> too low in this context.)
The above paragraph nicely captures why this time-wasting "OFFICIAL
COMMENT" should not have been filed in the first place.
> To be absolutely clear: I am not talking about honest mistakes or
> misunderstandings that are acknowledged and corrected. Indeed, this
> describes the vast majority of situations in the NIST PQC process, in which
> submitters and other participants have resolved matters without difficulty.
This claim is hard to evaluate unless "without difficulty" is clarified.
As an example, when Frodo falsely claimed a "Theorem 5.1" assuming
merely OW-CPA rather than IND-CPA, made a synchronized series of changes
in support of this claim, didn't admit the error for a month and a half
after it was pointed out, and then tried to downplay the error as a
"typo", would this qualify as resolution "without difficulty"? See the
discussion that started with my 24 May 2019 08:33:24 -0000 message, and
see Section 6 of https://cr.yp.to/papers.html#latticeproofs
> Procedurally, I think NIST should seriously consider this issue. I can
> think of a few options for how it could respond, such as:
> 1. Take no official action. Let people say whatever they want to, and
> hope that other (unspecified) mechanisms address such behavior. This has
> the big disadvantage that it does not offer any clarity to non-experts and
> the broader community.
> 2. Make an official statement on its findings of the relevant facts, and
> perhaps its analysis of the consequences. This has the advantage of
> offering clarity to the community.
> 3. Do 2, and also penalize submissions/submitters who show a pattern of
> this kind of behavior, perhaps after a warning and a failure to remedy
> matters. This has the additional advantage of providing a disincentive to
> wasting the community's time with FUD and nonsense.
Seems unnecessary to comment on this.
> As mentioned above, here are two more examples fitting the pattern of false
> disparagement, followed by debunking, with no withdrawal or even
> 1. The false accusation that round-3 Kyber "switched from Core-SVP to a
> modified metric," which was conclusively shown [link
> to be based on nothing but the accuser's severe misunderstanding (or worse,
> deliberate mischaracterization) of what Core-SVP means.
The switch of metric is documented in detail in my messages dated 4 Dec
2020 18:06:07 +0100, 17 Dec 2020 16:20:01 +0100, and 2 Jan 2021 18:24:27
+0100. See also the ten questions in my message dated 4 Jan 2021
14:39:45 +0100. I'll again skip commenting on the personal attacks.
> 2. The striking accusation that "NIST started trying, with considerable
> success, to delay and deter public analysis of the patent threats" [link
> A follow-up message [link
> requested evidence to support this accusation---which was never
> provided---and showed prior statements from NIST *encouraging* comments
> about patent issues.
Let's review. This "OFFICIAL COMMENT" is extracting the ending of the
NIST posted the IP statements three years ago. ... However---even
though the call for proposals had described free usability as
"critical"---NIST started trying, with considerable success, to delay
and deter public analysis of the patent threats.
The "OFFICIAL COMMENT" is characterizing this note as "false
disparagement" of the "process". It's then pointing to email dated 21
May 2021 00:35:37 -0400 as "debunking" this "disparagement", where the
"debunking" consists of showing "prior statements from NIST
*encouraging* comments about patent issues."
Now let's compare this to the facts:
* NIST email dated 9 Jan 2018 18:18:08 +0000 says "We would also
appreciate any comments from the community of course." This is
quoted in the email dated 21 May 2021 00:35:37 -0400, which this
"OFFICIAL COMMENT" characterizes as a "debunking" showing "prior
statements from NIST *encouraging* comments about patent issues".
* NIST email four months later, dated 8 May 2018 13:35:17 +0000,
announced that NIST had posted the IP statements. The note quoted
above refers to this posting and then says "NIST started trying,
with considerable success, to delay and deter public analysis of
the patent threats".
Even if we imagine the January 2018 message as requesting public
analysis of the patent threats, how is this supposed to be "debunking"
a note referring to NIST's May 2018 posting of the IP statements and
saying that NIST _started_ trying to delay/deter analysis? Note the word
"started"; words have meanings.
Structurally, the timeline directly disproves the "debunking" narrative.
Of course, the "OFFICIAL COMMENT" omits "posted the IP statements",
hides the timeline from the reader, and indefensibly characterizes this
irrelevant January 2018 reference as "debunking" a note about what
happened later. When this error is stripped away, we're left with
"requested evidence to support this accusation---which was never
provided", which obviously also doesn't qualify as "debunking". The
reader is being fed outright misinformation regarding the status of the
discussion; again, this is not appropriate.
Any reader who looks at the same NIST email dated 8 May 2018 13:35:17
+0000, the one where NIST announced the signed IP statements, sees that
NIST then said "For the 1^ st round, all submissions should be evaluated
and analyzed on their technical merits". That's a delay all the way to
2019---for the only item labeled as "critical" in the call for
---Dan (speaking for myself, except that the ciphertext-size numbers are
speaking for themselves)