ROUND 3 OFFICIAL COMMENT: NTRU Prime

986 views
Skip to first unread message

Christopher J Peikert

unread,
Sep 30, 2021, 10:30:30 AMSep 30
to pqc-forum
Summary of this comment:
  1. The NTRU Prime FAQ starts with an objectively false factual claim about competing submissions Kyber and SABER.
  2. This false claim is central to the FAQ's misleading attempt to suggest that these systems infringe on a patent.
  3. Requests to the NTRU Prime team to remove the false claim and insinuation were refused.
  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.
  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] 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, which is outside the scope of this message, but was also shown to be severely flawed; see, e.g., [link, link].)

As a matter of objective fact, the "2x" claim is false. While Kyber and SABER do perform some mild ciphertext compression, they do not, and could not, come close to 2x with the mechanism they use.

(I pointed out this false "2x" claim on the pqc-forum on 11 December 2020 [link], 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. Specifically, the "appears to be covered" claim implicitly conflates the patented mechanism, which does provide (near-)2x compression, with the unpatented prior-art method that Kyber/SABER use.

Kyber/SABER's compression mechanism is, informally: "drop some low bits of certain integers, keeping the several high bits needed for correct decryption." 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].

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].

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.

The above summarizes, for the record, the history regarding the facts and analysis. 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.

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).

What next?

I hope the above material sets the record straight. 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.
(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.)

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.

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.
As mentioned above, here are two more examples fitting the pattern of false disparagement, followed by debunking, with no withdrawal or even acknowledgment:
  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.
  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.
Sincerely yours in cryptography,
Chris

D. J. Bernstein

unread,
Oct 7, 2021, 6:20:08 AM (12 days ago) Oct 7
to pqc-co...@nist.gov, pqc-...@list.nist.gov
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 to give
appropriate credit to Ding is in violation of basic ethics rules (see,
e.g., https://ori.hhs.gov/plagiarism-ideas) 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
2033.

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.

See below.

> 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
> <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/NSe0wAzKJtA/m/DSIMaEOcCAAJ>],
> 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
> <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/NSe0wAzKJtA/m/SDaWm_qtCAAJ>,
> link
> <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/NSe0wAzKJtA/m/DxGrdfWHAgAJ>
> ].)

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
> use.

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 [
> link
> <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/NSe0wAzKJtA/m/MMJdZOq1CAAJ>],
> and again on 21 May 2021 [link
> <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/nbIZhtICKWU/m/SOk7xQBsBQAJ>],
> 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
> <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/nbIZhtICKWU/m/SqvzrtVOBQAJ>
> ].

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
> <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/NSe0wAzKJtA/m/uYJ3W-_RBQAJ>
> ].

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
> analysis.

"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
to 2x".

* 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.
See, e.g.,

* 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.)

See below.

> 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
> acknowledgment:
> 1. The false accusation that round-3 Kyber "switched from Core-SVP to a
> modified metric," which was conclusively shown [link
> <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/NSe0wAzKJtA/m/JmAHc1GqCAAJ>]
> 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
> <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/nbIZhtICKWU/m/ML7aYY71AgAJ>].
> A follow-up message [link
> <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/nbIZhtICKWU/m/SqvzrtVOBQAJ>]
> 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
following note:

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
submissions!

---Dan (speaking for myself, except that the ciphertext-size numbers are
speaking for themselves)
signature.asc

Vadim Lyubashevsky

unread,
Oct 7, 2021, 7:58:10 AM (12 days ago) Oct 7
to pqc-forum, pqc-comments
Dear all,

Dan wrote:

> 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.

Why is Kyber with compression being compared to a *different* scheme
without compression? Without *any* compression, Kyber-1024 would have
256*12*5/8 =1920 bytes in the ciphertext. With the compression
directly from [page 17 of
https://web.eecs.umich.edu/~cpeikert/pubs/svpcrypto.pdf] where the
entire ciphertext is rounded to the same precision, we can drop 2 bits
from each coefficient of the ciphertext and end up with
256*10*5/8=1600 bytes. This precedes any patents. So the only
question now is whether dropping a different number of bits from
different parts of the ciphertext is something covered by Ding's
patent or not. I already weighed in on this many times, so I won't
repeat my argument again -- but just so it's clear to everyone, the
argument pertaining the ciphertext size of Kyber-1024 and Ding's
patent is an argument about 32 bytes (so 2% and not a factor of 2).

Best,
Vadim
> --
> You received this message because you are subscribed to the Google Groups "pqc-forum" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
> To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20211007101934.682050.qmail%40cr.yp.to.

Christopher J Peikert

unread,
Oct 7, 2021, 11:16:33 AM (12 days ago) Oct 7
to Vadim Lyubashevsky, pqc-forum, pqc-comments
On Thu, Oct 7, 2021 at 7:58 AM Vadim Lyubashevsky <vadim....@gmail.com> wrote:
Dear all,

Dan wrote:

> 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.

Why is Kyber with compression being compared to a *different* scheme
without compression? Without *any* compression, Kyber-1024 would have
256*12*5/8 =1920 bytes in the ciphertext. 

Vadim is of course correct. The actual difference between compressed and uncompressed Kyber-1024 is about 1.22x. The numbers do indeed speak for themselves: this is not even close to 2x (it's less than a third of the way there).

That this is the first (and best?) attempted public justification ever offered for the FAQ's "2x" claim is extremely telling. But the claim is factually false, so it's going to have a hard time.

More broadly, all of the offered comparisons between Kyber/SABER and LPR are nonsensical, because of the significant difference in size between Module-LWE/LWR-style (like Kyber/SABER) and Ring-LWE-style (like LPR) ciphertexts. The comparisons misleadingly suggest that this difference is due to the cited patent instead of to its actual source, the use of Module-LWE/LWR.

(For the record, the patent says nothing about Module-LWE-style constructions, and Module-LWE was first defined in prior art from 2011, under the name "General LWE": https://eprint.iacr.org/2011/277 .)

The easy calculation: ignoring the (small, generic) CCA overhead,
  1. An uncompressed "LPR-1024" ciphertext is two elements of a 1024-dimensional ring mod q. This uses one full ring element to "carry" the encapsulated key.
  2. An uncompressed Kyber-1024 ciphertext is five elements of a 256-dimensional ring mod q. This is due to Kyber's use of Module-LWE over a 256-dimensional ring, with only one smaller ring element needed to carry the key.
Of course, 5*256 = 1280 is less than 2*1024=2048, by an 8/5 = 1.6x factor. This is much more than the 1.22x factor obtained from the drop-some-low-bits compression. (Similar comments apply to SABER as well.)

With the "2x" claim now conclusively refuted, I stand by my original comments.

Moody, Dustin (Fed)

unread,
Oct 7, 2021, 11:51:59 AM (12 days ago) Oct 7
to Christopher J Peikert, pqc-forum
Chris Peikert asked about what NIST can do about behavior that is "outside the bounds of fair play," and offered some suggestions.  We appreciate that.  We will do our best to set a standard of good behavior by example.  The goal of creating secure post-quantum standards for the future should remain the primary focus of the pqc-forum.  We have always encouraged interested parties to ask questions, make comments on the submissions, share their relevant work, etc. in a civil and constructive way.  

NIST appreciates the dialogue fostered on this forum, and understands that disagreements are a natural part of the process. However, unethical behavior can undermine the integrity of the PQC process.  Politely and professionally addressing misleading or inaccurate statements is an appropriate part of maintaining high academic and ethical standards.

NIST's four core values are perseverance, integrity, inclusivity, and excellence.  Towards these values, NIST strongly discourages dishonesty, misrepresentations of science, personal attacks, and any form of hostility. The IEEE Code of Ethics https://www.ieee.org/about/corporate/governance/p7-8.html encapsulates the ethical standard we expect from ourselves and the community as we continue the PQC Standardization process.  

NIST realizes there are limits to the time and energy that the community can realistically spend on "calling out" questionable behavior.  There is also only so much that NIST can do.  We respect people's right to share their work and opinions in a scientific way.  When somebody is acting in a negative or malicious manner, it doesn't strengthen their argument, and we think most of the community will discount what they are saying (and we tend to do the same). 

In that spirit, the NIST PQC team disagrees with some of the statements in the NTRUprime FAQ.  For example, as Chris noted, we have not been discouraging public discussion on patent issues that may be relevant to the PQC standardization process.  Also, we disagree that we have been inconsistent in handling security categories, or any suggestion that we are favoring one submission more than another.  Ultimately, NIST will need to select the most promising algorithms for standardization, but we try to treat each submission in the same fashion.  (These are just 2 examples - this doesn't mean we agree or disagree with everything else in the FAQ.)  

Dustin Moody
NIST

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Christopher J Peikert <cpei...@alum.mit.edu>
Sent: Thursday, October 7, 2021 11:16 AM
To: Vadim Lyubashevsky <vadim....@gmail.com>
Cc: pqc-forum <pqc-...@list.nist.gov>; pqc-comments <pqc-co...@nist.gov>
Subject: Re: [pqc-forum] ROUND 3 OFFICIAL COMMENT: NTRU Prime
 
--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

D. J. Bernstein

unread,
Oct 8, 2021, 8:17:58 AM (11 days ago) Oct 8
to pqc-...@list.nist.gov
'Moody, Dustin (Fed)' via pqc-forum writes:
> For example, as Chris noted, we have not been discouraging
> public discussion on patent issues that may be relevant to the PQC
> standardization process.

Moody, Dustin (Fed) writes:
> Subject: IP statements
> From: "Moody, Dustin (Fed)" <dustin...@nist.gov>
> Date: Mon, 7 Dec 2020 15:24:16 +0000
> To: "D. J. Bernstein" <d...@cr.yp.to>
> Message-ID: <BLAPR09MB60814E534E...@BLAPR09MB6081.namprd09.prod.outlook.com>
>
> Dan,
>
> Regarding some of your comments on the forum regarding patents:
>
> We note that your submitted primitive NTRU-LPRime is a structured lattice
> scheme that uses rounding and truncation during the encryption process in a
> similar way to Kyber and Saber. We further note that the owners of your
> submission, NTRUprime, which incorporates NTRU-LPRime, are listed as the same
> as the submitters, and your latest signed IPR statement does not list any
> patents covering your submission. Does any of this need to be revised based on
> the statements you are making on the forum?
>
> We are working to clear up the IP situation, but it is a slow process. We hope
> everyone will focus on the technical issues, rather than on the patents right
> now.
>
> Dustin
signature.asc

D. J. Bernstein

unread,
Oct 9, 2021, 12:55:12 AM (10 days ago) Oct 9
to pqc-...@list.nist.gov
I must admit to being surprised that, after I sent the message below,
the whole business day at NIST went by without NIST issuing apologies
for the evident misinformation and the underlying pressure tactic. I
understand that a few days might be needed for issuing a post-mortem.

---Dan


D. J. Bernstein writes:
> Subject: Re: [pqc-forum] ROUND 3 OFFICIAL COMMENT: NTRU Prime
> From: "D. J. Bernstein" <d...@cr.yp.to>
> Date: Fri, 8 Oct 2021 14:17:37 +0200
> To: pqc-...@list.nist.gov
> Message-ID: <202110081217...@cr.yp.to>
signature.asc

D. J. Bernstein

unread,
Oct 11, 2021, 3:20:48 AM (8 days ago) Oct 11
to pqc-co...@nist.gov, pqc-...@list.nist.gov
Email from NIST dated 7 Oct 2021 15:51:54 +0000 states, regarding the
NISTPQC evaluation process, that NIST tends to discount input from
people "acting in a negative or malicious manner". I have five
clarification questions regarding this process, and I would appreciate
having the answers numbered accordingly.

1. How does NIST evaluate which people are acting in a "negative" manner
in the discounting context? For example, do the following personal
attacks issued over the past year by Daniel Apon, "Kirk Fleming",
Christopher J Peikert, Jacob Alperin-Sheriff, and Vadim Lyubashevsky
qualify as "negative"? If no, why not?

* Daniel Apon (NIST employee), pqc-forum email dated 20 Jun 2021
16:04:49 -0700, personal attack without NIST speaking up to object:
"Apparently everyone but you understands the state of the science,
and is willing to accept new results as they happen. [new
paragraph:] Stop propagandizing."

* "Kirk Fleming" (sockpuppet in violation of the transparency rules
stated in https://www.nist.gov/system/files/documents/2017/05/09/VCAT-Report-on-NIST-Cryptographic-Standards-and-Guidelines-Process.pdf),
pqc-forum email dated 24 Nov 2020 02:01:07 +0100, personal attack
without NIST speaking up to object: "This is the irrelevant hype I
mean. You are ignoring" etc.

* Christopher J Peikert, pqc-forum email dated 21 May 2021 09:30:17
-0400, personal attack without NIST speaking up to object: "... you
have ignored the correction and persist in repeating the error. (My
guess is that this is because it's central to sowing FUD-y
confusion, by conflating the prior art and NIST candidates with
2012 Ding.)"

* Jacob Alperin-Sheriff (former NIST employee), pqc-forum email dated
22 Sep 2021 23:45:09 -0400, personal attack[1] without NIST
speaking up to object: "Finally vindication for Daniel Bernstein
has been achieved!" [footnote 1:] Given the context, many readers
will see the message as a sarcastic attack (founded, I should note,
upon misinformation regarding the history), whether or not it was
intended this way. Even without the context, the gratuitous
personalization is clear.

* Vadim Lyubashevsky, pqc-forum email dated 21 May 2021 12:59:46
+0200, personal attack without NIST speaking up to object: "It's
that you're applying your usual anti-lattice crypto spin on things"
etc.

2. How does NIST evaluate which people are acting in a "malicious"
manner in the discounting context? For example, given revelations of NSA
working to undermine cryptographic standards, do NSA agents qualify as
acting in a "malicious" manner? If no, why not?

3. When the discounting process is triggered, how does it work? What
procedures are in place generally to protect against errors and abuse,
and specifically to ensure that this process does not damage the NISTPQC
evaluations mandated by 81 FR 92787 and by the call for submissions
cited in 81 FR 92787?

4. When did this discounting process begin? Was it announced before
October 2021? On what dates was it announced?

5. Where is this discounting approach to NISTPQC authorized in 81 FR
92787 or in the call for submissions cited in 81 FR 92787?

---Dan
signature.asc

Vadim Lyubashevsky

unread,
Oct 11, 2021, 6:23:23 AM (8 days ago) Oct 11
to pqc-forum, pqc-comments
On Mon, Oct 11, 2021 at 9:20 AM D. J. Bernstein <d...@cr.yp.to> wrote:

> 1. How does NIST evaluate which people are acting in a "negative" manner
> in the discounting context? For example, do the following personal
> attacks issued over the past year by Daniel Apon, "Kirk Fleming",
> Christopher J Peikert, Jacob Alperin-Sheriff, and Vadim Lyubashevsky
> qualify as "negative"? If no, why not?
>
> * Vadim Lyubashevsky, pqc-forum email dated 21 May 2021 12:59:46
> +0200, personal attack without NIST speaking up to object: "It's
> that you're applying your usual anti-lattice crypto spin on things"
> etc.

That does not qualify as negative. Given how many outright false
things you've stated on this list about Kyber and lattice crypto
(let's just take the concretely false and continued claim that
uncompressed kyber is 2x longer than compressed kyber as the most
recent example), I think that describing you as just having an
"anti-lattice spin" was actually acting in a very positive manner.

Vadim

D. J. Bernstein

unread,
Oct 11, 2021, 6:37:42 AM (8 days ago) Oct 11
to pqc-comments, pqc-forum
Vadim Lyubashevsky writes:
> That does not qualify as negative.

I believe I was perfectly clear in asking questions about NIST's newly
announced procedures. I would like authoritative answers from NIST
regarding those procedures.

> Given how many outright false
> things you've stated on this list about Kyber and lattice crypto
> (let's just take the concretely false and continued claim that
> uncompressed kyber is 2x longer than compressed kyber as the most
> recent example),

Please either (1) quote where I said something about "uncompressed
Kyber" or (2) withdraw this claim. Thanks in advance.

---Dan
signature.asc

Vadim Lyubashevsky

unread,
Oct 11, 2021, 7:06:41 AM (8 days ago) Oct 11
to pqc-forum, pqc-comments
On Mon, Oct 11, 2021 at 12:37 PM D. J. Bernstein <d...@cr.yp.to> wrote:
>
> Vadim Lyubashevsky writes:
> > That does not qualify as negative.
>
> I believe I was perfectly clear in asking questions about NIST's newly
> announced procedures. I would like authoritative answers from NIST
> regarding those procedures.

Sorry, I wanted to defend myself before NIST renders it's decision.
Promise not to interfere again.

> > Given how many outright false
> > things you've stated on this list about Kyber and lattice crypto
> > (let's just take the concretely false and continued claim that
> > uncompressed kyber is 2x longer than compressed kyber as the most
> > recent example),
>
> Please either (1) quote where I said something about "uncompressed
> Kyber" or (2) withdraw this claim. Thanks in advance.

Fair enough - I can admit when I am wrong. When you wrote:

"There are known patent threats against ... Kyber, SABER, and
NTRU LPRime (ntrulpr). These proposals use ... and a 2x
ciphertext-compression mechanism that
appears to be covered by U.S. patent 9246675 expiring 2033,"

you did not explicitly state that by using a 2x ciphertext-compression
mechanism, kyber actually compresses its ciphertext 2x. And when
Chris asked you about it in this thread, you replied with:

"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."

So there is a 2X ciphertext compression, but just not between
compressed and uncompressed Kyber. So I withdraw my claim about you
explicitly saying anything about uncompressed kyber and, based on the
above examples, also relegate my statement about you "putting an
anti-lattice crypto spin on things" from being positive to being
merely accurate.

Vadim

>
> ---Dan
>
> --
> You received this message because you are subscribed to the Google Groups "pqc-forum" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
> To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20211011103709.179679.qmail%40cr.yp.to.

Christopher J Peikert

unread,
Oct 11, 2021, 8:11:40 AM (8 days ago) Oct 11
to pqc-forum, pqc-comments
On Mon, Oct 11, 2021 at 3:20 AM D. J. Bernstein <d...@cr.yp.to> wrote:
   * Christopher J Peikert, pqc-forum email dated 21 May 2021 09:30:17
     -0400, personal attack without NIST speaking up to object: "... you
     have ignored the correction and persist in repeating the error. (My
     guess is that this is because it's central to sowing FUD-y
     confusion, by conflating the prior art and NIST candidates with
     2012 Ding.)"

This is not a "personal attack" [1], nor an "ad hominem attack" [2] (a term you recently used in another thread).

It is an evidence-based criticism of specific actions and statements (repeating factual errors after ignoring corrections, and conflating prior art with a patent, i.e., a form of FUD).

I would make the same criticism of anyone else who exhibited this behavior; you just happened to be the one to do it.

[1] "An abusive remark on or relating to somebody's person instead of providing evidence when examining another person's claims or comments." https://en.wiktionary.org/wiki/personal_attack

The above, however, is a good reminder about the original and central topic of this thread [link].

It has been more than 10 months since the official NTRU Prime FAQ alleged that Kyber and SABER use "a 2x ciphertext-compression mechanism that appears to be covered by" a patent.

For months, this "2x" claim was pointed out as being factually false on multiple occasions, and no attempt to substantiate it even emerged until a few days ago.

This attempted substantiation was based on a nonsensical comparison between compressed Kyber/SABER and a different cryptosystem over a different ring, rather than between Kyber/SABER with and without ciphertext compression.

(For Kyber, this compression is the use of Compress/Decompress on the ciphertext components (u,v), whose main purpose "is to be able to discard some low-order bits in the ciphertext which do not have much effect on the correctness probability of decryption–thus reducing the size of ciphertext").

Very soon after, it was conclusively shown that the compression is only about 1.22x for the considered Kyber parameters---not even a third of the way to 2x.

At the time of this writing, the false "2x" claim remains on the NTRU Prime FAQ.

D. J. Bernstein

unread,
Oct 11, 2021, 8:53:21 AM (8 days ago) Oct 11
to pqc-co...@nist.gov, pqc-...@list.nist.gov
A 2010 LPR ciphertext has 2 ring elements, around 3 kilobytes for 2^256
Core-SVP when parameters are chosen to optimize ciphertext size.

A patented 2012 Ding ciphertext has just 1+epsilon, around 1.5 kilobytes
for 2^256 Core-SVP. That's 2x compression compared to the relevant
baseline, namely LPR.

2014 Peikert achieved the same 1+epsilon, and said that doing better
than the LPR ciphertext size ("two R_q elements") was unobvious, the
result of an "innovation". In court this is a slam-dunk against
retroactive claims of obviousness for smaller ciphertexts than LPR.

Replacing rings with modules _in Ding's system_ makes negligible
difference in ciphertext size and will be covered by the doctrine of
equivalents. Avoiding "reconciliation" is ill-defined, so it won't even
reach a doctrine-of-equivalents analysis. Trying to avoid Ding's patent
by mixing Ding's technique with other techniques can only work if a
Markman hearing ends up with a narrow interpretation of the claims, and
I see nothing that can be used to justify such an interpretation.

The NTRU Prime FAQ correctly reports this:

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.

The baseline for "2x" is, obviously, LPR. Kyber compresses its
ciphertexts 2x compared to LPR. Recent references on pqc-forum to
"uncompressed Kyber" are irrelevant to the history, irrelevant to a
patent case, and irrelevant to the FAQ; the notion that the FAQ is
comparing Kyber to "uncompressed Kyber" is obviously incorrect. The
claim that there has been a "concretely false and continued claim that
uncompressed kyber is 2x longer than compressed kyber" is incorrect and,
unfortunately, not properly withdrawn.

---Dan
signature.asc

Christopher J Peikert

unread,
Oct 11, 2021, 9:34:41 AM (8 days ago) Oct 11
to pqc-forum, pqc-comments
On Mon, Oct 11, 2021 at 8:53 AM D. J. Bernstein <d...@cr.yp.to> wrote:
Replacing rings with modules _in Ding's system_ makes negligible
difference in ciphertext size and will be covered by the doctrine of
equivalents.

This is irrelevant to the present discussion, because _it's not what Kyber/SABER do_.

They replace rings with modules _in the LPR system_, and do ciphertext compression using a drop-low-bits technique which does not appear in the patent, and which was described in at least four well known works of prior art, including for rings and modules (see, e.g., https://eprint.iacr.org/2011/277 and search for "modulus switching"). I have pointed this out multiple times, and have yet to see your arguments acknowledge it.

Trying to avoid Ding's patent
by mixing Ding's technique with other techniques

Also irrelevant, because _it's not what Kyber/SABER do_. They don't use Ding's technique at all, and it's wrong to imply that they do.

The NTRU Prime FAQ correctly reports this:

   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.

The baseline for "2x" is, obviously, LPR.

It's not obvious; it's not even plausible. For Kyber, the reader will see "a 2x ciphertext-compression mechanism" as referring to Kyber's Compress/Decompress algorithms, which are correctly described in the spec as the mechanism for compressing ciphertexts.

(Section "Compression and Decompression": "The main reason for defining the Compress_q and Decompress_q functions is ... reducing the size of ciphertexts.")

Vadim Lyubashevsky

unread,
Oct 11, 2021, 9:35:43 AM (8 days ago) Oct 11
to pqc-forum, pqc-comments
> Replacing rings with modules _in Ding's system_ makes negligible
> difference in ciphertext size and will be covered by the doctrine of
> equivalents. Avoiding "reconciliation" is ill-defined, so it won't even
> reach a doctrine-of-equivalents analysis. Trying to avoid Ding's patent
> by mixing Ding's technique with other techniques

No one is mixing Ding's technique with anything. The encapsulation
(including compression)
in Kyber is the Encaps algorithm from
page 17 of https://web.eecs.umich.edu/~cpeikert/pubs/svpcrypto.pdf,
with the only difference that q' does not have to be the same for b_1
and b_2. That's it. I don't see how anything could be closer to what
Kyber does without actually being Kyber; and if the doctrine of
equivalents applies to Kyber from Ding's patent (who, as I mention
again, did not compress the a public key encryption scheme in the same
patent), then surely one should be able to apply it from the linked
paper.


Vadim

D. J. Bernstein

unread,
Oct 11, 2021, 10:26:22 AM (8 days ago) Oct 11
to pqc-co...@nist.gov, pqc-...@list.nist.gov
Christopher J Peikert writes:
> using a drop-low-bits technique which does not appear in the patent

See my pqc-forum message dated 1 Jan 2021 13:19:26 +0100 for a detailed
analysis of the specific claims of a dividing line here.

> The NTRU Prime FAQ correctly reports this:
>    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.
> The baseline for "2x" is, obviously, LPR.
> It's not obvious; it's not even plausible.

The text is clear: there's noisy DH + reconciliation (i.e., LPR), and
then there's ciphertexts shrinking 2x.

---Dan
signature.asc

Christopher J Peikert

unread,
Oct 11, 2021, 12:28:58 PM (8 days ago) Oct 11
to pqc-forum, pqc-comments
On Mon, Oct 11, 2021 at 10:26 AM D. J. Bernstein <d...@cr.yp.to> wrote:
Christopher J Peikert writes:
> using a drop-low-bits technique which does not appear in the patent

See my pqc-forum message dated 1 Jan 2021 13:19:26 +0100 for a detailed
analysis of the specific claims of a dividing line here.

Then see my response [link] showing a clear dividing line between the drop-some-low-bits prior art (which Kyber/SABER use) and the technique from the patent (which they don't).
 
>     The NTRU Prime FAQ correctly reports this:
>        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.
>     The baseline for "2x" is, obviously, LPR.
> It's not obvious; it's not even plausible.

The text is clear: there's noisy DH + reconciliation (i.e., LPR), and
then there's ciphertexts shrinking 2x.

The text is indeed clear: the "2x" adjective is applied specifically to Kyber/SABER's "ciphertext-compression mechanism" of dropping some low bits.

Anyway, the facts have been laid out, and readers can judge for themselves whether this paragraph is an accurate characterization.
Reply all
Reply to author
Forward
0 new messages