ROUND 3 OFFICIAL COMMENT: CRYSTALS-KYBER

[D. J. Bernstein]

NIST's email dated 9 Jun 2020 15:39:09 +0000 states "we feel that the
CoreSVP metric does indicate which lattice schemes are being more and
less aggressive in setting their parameters".

Almost all lattice submissions have reported their Core-SVP levels
(pre-quantum and post-quantum---let's focus on pre-quantum here), in
line with this statement and with previous statements from NIST that
seemed to be encouraging use of Core-SVP.

Question: What number does "the CoreSVP metric" assign to round-3
Kyber-512?

This might seem to be answered by Table 4 of the round-3 Kyber
submission, which lists 2^118 for "Core-SVP" for round-3 Kyber-512. I
have a clarification question here:

* Is the round-3 Kyber submission claiming that round-3 Kyber-512 is
2^118 in "the CoreSVP metric", the metric that NIST says it's using
to compare how "aggressive" lattice schemes are, the same metric
used in other submissions?

My current understanding is that the answer is "no", meaning that this
part of the round-3 Kyber submission needs to be disregarded for NIST's
announced comparison mechanism, and instead there needs to be a new
statement of the round-3 Kyber-512 Core-SVP level.

Here's how I arrived at this understanding. Please correct me if I've
misunderstood something.

The round-2 Kyber submission listed an even smaller number, 2^111, as
"Core-SVP" for round-2 Kyber-512. This doesn't directly contradict the
idea that round-3 Kyber-512 reaches 2^118: the round-3 submission
identifies changes from round-2 Kyber-512 to round-3 Kyber-512; perhaps
these changes increase the Core-SVP level.

A more detailed reading appears to say, however, that these changes in
the cryptosystem are _not_ enough to reach Core-SVP 2^118, and that the
only way the round-3 Kyber submission is claiming 2^118 is by _changing
the metric_, despite continuing to use the words "Core-SVP".

Specifically, there's a mechanism used in the previous literature for
claiming "Core-SVP" levels, and then there's a different, more generous,
mechanism used in the round-3 Kyber submission for claiming this 2^118.
For clarity, let's define "Kyber3-Modified-Core-SVP" as the mechanism
used in the round-3 Kyber submission. Here are two examples of
differences between Core-SVP and Kyber3-Modified-Core-SVP:

* In the literature, Core-SVP is the _minimum_ of primal and dual
attack analyses. See, e.g., Table 3 of the round-2 Kyber
submission, listing 2^111 as "core-SVP (classical)" for round-2
Kyber-512, on the basis of Table 4 saying 2^111 for dual and 2^112
for primal.

Kyber3-Modified-Core-SVP says "Primal attack only". This is not the
same metric. Presumably the original Core-SVP metric would produce
lower numbers than Kyber3-Modified-Core-SVP for round-3 Kyber-512.

Previous analyses showed some NISTPQC submissions choosing
parameters in ranges where the dual component of Core-SVP was far
above the primal component. Round-3 Kyber appears to be handling
dual attacks in a more worrisome way, by changing the metric to
disregard those attacks. A cryptosystem with several different
attacks around the same security level has several different risks
of those attacks being improved.

More to the point, whether or not one thinks dual attacks are as
much of an issue as Core-SVP indicates, omitting dual attacks
changes the metric away from Core-SVP.

* In the literature, 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.

Kyber3-Modified-Core-SVP says that it "adds 6 bits of Core-SVP
hardness" by "accounting for" rounding. This "accounting" is a
change of the metric. The wording "adds 6 bits" appears to admit
that round-3 Kyber-512 has Core-SVP at most 2^112. (Maybe even the
same 2^111 as round-2 Kyber-512; see above regarding dual attacks.)

Note that this contradicts the claim in the round-3 Kyber
submission that its "estimates of the security strength" for its
"parameter sets" are "based on the cost estimates of attacks
against the underlying module-learning-with-errors (MLWE) problem".
This also means that Theorem 1, despite being labeled "tight",
cannot justify the claimed round-3 Kyber-512 security level.

Yes, rounding poses a difficulty for attacks---it's not as if the
full samples are provided to the attacker!---but certain people
have previously criticized other submissions for focusing on the
actual cryptosystem attack problems rather than the RLWE/MLWE
problems. 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.

More to the point, even if one doesn't think that this change of
metric is reflecting a real danger, this isn't Core-SVP.

Labeling Kyber-Modified-Core-SVP as "Core-SVP" is confusing, and I don't
see how it can be justified. Example of how the submitters could easily
have predicted before the round-3 submission deadline that this labeling
would cause problems:

* Presumably, at the beginning of round 3, NIST would compile a
comparison table listing "the CoreSVP metric" for all parameter
sets in all round-3 lattice submissions, to see "which lattice
schemes are being more and less aggressive in setting their
parameters".

* For round-3 Kyber-512, presumably NIST would take 2^118, since
that's labeled as "Core-SVP" in the submission.

* In the absence of clarification, NIST would never realize that this
2^118 was calculated in a different way, and that "the CoreSVP
metric" actually assigns a smaller number to round-3 Kyber-512.

This is unfair to various other submissions that---whether or not
arguing that Core-SVP is flawed---have been reporting Core-SVP as per
NIST's requests for comparability. The Kyber submission should have been
reporting the original Core-SVP metric too, and giving any new metric a
new name to avoid confusion.

I also have some questions for NIST at this point:

* Has NIST already made its round-3 Core-SVP comparison table? If
not, why not, and what's the schedule for making this table?

Assuming the table has been made already: Can you please post it
publicly for review?

* NIST claimed in September 2020 that its public statements were
"sufficient for any submission team working in good faith to
determine what parameter sets will be uncontroversial,
controversial and unacceptable for the claimed security levels
given the current state of knowledge."

I doubt anyone will assert that the Kyber-512 parameter set is
"uncontroversial". But where is NIST drawing the line between
"controversial" and "unacceptable"? Which side of the line was
round-2 Kyber-512 on? Which side of the line is round-3 Kyber-512
on? How do we determine the answers to these questions from
publicly available information? Also, just to confirm, NIST agrees
that no version of Kyber-512 qualifies as "uncontroversial"?

If NIST is unable to promptly answer these questions, shouldn't it
be admitting for the record that the September 2020 claim quoted
above wasn't true when it was made, and still isn't true now?
Shouldn't it also be posting an analysis of how it ended up making
such a claim, so as to help prevent similar errors in the future?

Looking forward to clarifications, answers, and retractions as
appropriate.

---Dan

P.S. I should note---with all due respect---that all available evidence
is consistent with the theory that NIST's strategy for handling concerns
regarding the Kyber-512 security level is to adjust the NISTPQC security
criteria so as to continue accepting the latest version of Kyber-512
(rather than suffering the public-relations problems of rejecting it).
If this theory is correct then evidently Kyber-512 isn't "unacceptable".
But NIST hasn't endorsed this theory, and it doesn't seem plausible that
this unannounced strategy would have been the basis for NIST's claim
that we were all supposed to have been able to figure out the dividing
lines between "unacceptable", "controversial", and "uncontroversial".

[Martin R. Albrecht]

I’m confused: Core-SVP is a methodology for estimating the cost of blockwise lattice reduction algorithms like BKZ not a methodology for setting up lattices from LWE.

--

_pgp: https://keybase.io/martinralbrecht
_www: https://malb.io

[Christopher J Peikert]

I'll echo Martin; the central objection here doesn't make any sense to me. Core-SVP can be applied to a variety of lattice problems, including R/M/LWE with or without rounding. Increasing the amount of rounding will, all else being equal, tend to increase the Core-SVP hardness. This is not a change in the Core-SVP metric itself; it is a change in the lattice problem being analyzed under that metric.

     Yes, rounding poses a difficulty for attacks---it's not as if the
     full samples are provided to the attacker!---but certain people
     have previously criticized other submissions for focusing on the
     actual cryptosystem attack problems rather than the RLWE/MLWE
     problems. Also, certain people have been claiming that it's a
     problem if cryptosystem parameters provide less security in other
     cryptosystems;

Is this referring to my message on 17 September 2020 ( https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/LHQ308jHVF4/m/VvHaHPGxBgAJ ) ?

If so, it (again) misrepresents my position, which is: "Given that variants of NIST-approved algorithms are likely to be adopted for such applications, I think it's very important to consider the robustness of the underlying LWE/LWR problems to variations like [revealing many samples]."

I don't recall anyone "criticizing other submissions for focusing on the actual cryptosystem attack problems rather than the RLWE/MLWE problems." Please provide unambiguous references, so that readers can tell whether you are accurately representing others, or putting words in their mouths.

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.

Incorrect. The idea of reducing ciphertext size (thus saving bandwidth) by rounding away some low bits -- which is exactly what Kyber does -- had publicly appeared by September 2009, predating Ding's 2012 patent application by more than two years.

See, e.g., Section 4.2 of https://web.eecs.umich.edu/~cpeikert/pubs/svpcrypto.pdf , especially the Encaps algorithm and the preceding discussion: "When using a large value of q ... the efficiency of the prior schemes is suboptimal, because the plaintext-to-ciphertext expansion factor ... is at least lg q. Fortunately, it is possible to improve their efficiency (without sacrificing correctness) by discretizing the LWE distribution more ‘coarsely’ using a relatively small modulus q'."

Sincerely yours in cryptography,

Chris

[D. J. Bernstein]

'Martin R. Albrecht' via pqc-forum writes:
> I’m confused: Core-SVP is a methodology for estimating the cost of
> blockwise lattice reduction algorithms like BKZ not a methodology for
> setting up lattices from LWE.

Then what exactly do you believe "the CoreSVP metric" is that NIST is
using to evaluate "which lattice schemes are being more and less
aggressive in setting their parameters"?

By its own words, this "CoreSVP metric" is a "metric" for "parameters".
If the thing you're calling "Core-SVP" refuses to turn an LWE instance
into a lattice, then how could NIST have been using it to evaluate
"parameters"?

If you're saying you're already confused by NIST's statement, then it's
even more clear that there's something that needs resolution here.

If you _aren't_ confused by NIST's statement, then what exactly are you
saying you _are_ confused about in my message? Do you claim that it's
clear that the "metric" NIST is using for "parameters" gives 2^111 for
round-2 Kyber-512 and 2^118 for round-3 Kyber-512?

---Dan

[Vadim Lyubashevsky]

Dear Dan, all,

   * In the literature, Core-SVP is the _minimum_ of primal and dual
     attack analyses. See, e.g., Table 3 of the round-2 Kyber
     submission, listing 2^111 as "core-SVP (classical)" for round-2
     Kyber-512, on the basis of Table 4 saying 2^111 for dual and 2^112
     for primal.

     Kyber3-Modified-Core-SVP says "Primal attack only". This is not the
     same metric. Presumably the original Core-SVP metric would produce
     lower numbers than Kyber3-Modified-Core-SVP for round-3 Kyber-512.

The version of "core-SVP" hardness that you enjoin we use is not the version used by other candidates, which actually contradicts your intent for a fair comparison on the same metric.

Indeed, the Kyber core-SVP-dual attack assumes (following the original NewHope paper)
very conservatively that the SVP oracle provides exponentially many short
vectors of the same length as the shortest one. This assumption has not reached
consensus; for example the LWE-estimator of Albrecht et al. assumes a
single vector, and concludes that the dual attack costs about 2^30 times
the cost of the primal attack. This version of core-SVP-dual is the metric
used by Saber, for example. The NTRU Round 3 specs do not even mention the
dual attack.

Dismissing the dual attack therefore *aligns* the Kyber metrics with the other schemes rather than diverging from them. Given recent developments, we agree that the conservative assumptions for the dual attack are too unrealistic (as discussed in the "beyond core-SVP" section); hence our alignment to the literature.

For completeness, we note that with the conservative assumption, the dual attack has a core-SVP cost of 2^117, against the 2^118 we report for the primal attack. This is analogous to the Round 2 version where the Core-SVP costs were 2^111 and 2^112, respectively.

We must say that we are actually heartened that a disagreement over 1 bit of security provokes such passion in you. It certainly points to the maturity of the science behind lattice cryptanalysis when this is what's left to discuss :).  

 

     Note that this contradicts the claim in the round-3 Kyber
     submission that its "estimates of the security strength" for its
     "parameter sets" are "based on the cost estimates of attacks
     against the underlying module-learning-with-errors (MLWE) problem".
     This also means that Theorem 1, despite being labeled "tight",
     cannot justify the claimed round-3 Kyber-512 security level.

On page 1 of the Round 3 changelog, we state "Relying on the rounding noise to add error is akin to the LWR assumption, but our reliance on it is quite small. First, it only adds 6 bits of Core-SVP hardness, and second, we are adding noise and rounding, which presumably has less algebraic structure than just rounding. In short, without the LWR assumption, our new parameter set for Kyber512 still has 112 bits of core-SVP hardness as before, while with a weak version of the LWR assumption, it has 118 bits."  We believe that we are being very clear with what we are claiming for Kyber512 (Kyber768 and Kyber1024 are still based purely on MLWE as before).    

 

     Yes, rounding poses a difficulty for attacks---it's not as if the
     full samples are provided to the attacker!---but certain people
     have previously criticized other submissions for focusing on the
     actual cryptosystem attack problems rather than the RLWE/MLWE
     problems. 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

If users skip rounding, they're not using Kyber. Maybe a non-rounded version of Kyber-like schemes could be useful for something (e.g. it's less efficient for ZK proofs to prove knowledge of large errors), but those would probably have many other differences and will have to be independently analyzed anyway.  

     

P.S. I should note---with all due respect---that all available evidence
is consistent with the theory that NIST's strategy for handling concerns
regarding the Kyber-512 security level is to adjust the NISTPQC security
criteria so as to continue accepting the latest version of Kyber-512
(rather than suffering the public-relations problems of rejecting it).

We are not sure what you mean here.  What adjustments did NIST make? At the end of Round 2, NIST publicly recommended that we should increase security a bit by widening the error distribution, and we did.  As far as we are aware, this is all that has happened.

Best,

Vadim 

(on behalf of the Kyber team)

 

--
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/20201201091007.670723.qmail%40cr.yp.to.

[D. J. Bernstein]

In https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf, NIST
repeatedly refers to "Core-SVP" as a number attached to each lattice
parameter set (e.g. "DILITHIUM has the lowest CoreSVP security strength
parameter set of any of the lattice schemes still in the process"). I've
also quoted NIST stating its belief that "the CoreSVP metric does

indicate which lattice schemes are being more and less aggressive in

setting their parameters". All of these quotes have been visible for
months, along with many indications of their importance.

However, when I question the round-3 Kyber submission's claim that
round-3 Kyber-512 has Core-SVP 2^118, suddenly people jump in to attack
the whole notion that Core-SVP attaches a number to each parameter set.
Why did none of the same people speak up to object to NIST repeatedly
pointing to Core-SVP as a metric for lattice parameter sets, a metric
used by NIST for comparisons? Why do these objections to the Core-SVP
concept appear only when Kyber's Core-SVP claim is challenged?

Christopher J Peikert writes:
> Core-SVP can be applied to a variety of lattice problems, including
> R/M/LWE with or without rounding.

Please clarify. You're saying that "Core-SVP" takes "lattice problems"
(e.g., RLWE with specific parameters) as input?

Martin seems to be saying that Core-SVP _doesn't_ take a lattice problem
as input (he says it's "not a methodology for setting up lattices from
LWE"; he seems to indicate that it's simply the function mapping beta to
(3/2)^(beta/2), or (13/9)^(beta/2) post-quantum), so you appear to be
contradicting him rather than, as you claim, echoing him.

Meanwhile NIST's description of Core-SVP as being attached to each
"parameter set" certainly doesn't match the type of input that Martin is
claiming. It also doesn't match the type of input that you're
claiming---it uses extra rules to specify the "problem" for a parameter
set, because omitting such rules would break the idea of comparing
parameter sets according to their Core-SVP values.

> "Given that variants of NIST-approved algorithms are likely to be
> adopted for such applications, I think it's very important to consider
> the robustness of the underlying LWE/LWR problems to variations like
> [revealing many samples]."

Why do you believe that the message you're quoting isn't an example of

"claiming that it's a problem if cryptosystem parameters provide less

security in other cryptosystems"? You've put quite a bit of effort into
claiming that you're being misrepresented, without making clear to
readers what exactly you're disagreeing with.

As a reminder, the context for the quote that you give included claims
such as "Importantly, it appears that the requisite assumptions may be
broken in some cases, so the resulting mKEM would be insecure" and "if
the number of recipients exceeds ... then instantiating the mKEM with
NTRU Prime will be insecure." (Whether the claims were correct isn't
relevant here.) Surely you aren't going to try to argue that a claim of
insecurity isn't claiming a problem.

> I don't recall anyone "criticizing other submissions for focusing on the actual
> cryptosystem attack problems rather than the RLWE/MLWE problems." Please
> provide unambiguous references

Here's an example:

https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/V1RNjpio5Ng/m/uniJDvESBAAJ

This says, e.g., "one cannot directly rely on the Ring-LWE hardness
assumption to argue security of the encryption procedure", and readers
who check the context won't believe you if you try to argue that this
isn't being presented as criticism.

Even with the fog of confusion that's suddenly blanketing Core-SVP, it
seems reasonably clear that one can't rely on RLWE/MLWE hardness
assumptions to argue for round-3 Kyber-512's 2^118 Core-SVP security
claim. Perhaps one can rely on those assumptions to argue for a 2^112
Core-SVP security claim, but it seems very likely that 2^112 Core-SVP is
below the minimum security level allowed in NISTPQC (even if 2^118 is
above the minimum, which is far from clear at this point).

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

What I wrote was correct. "In this way" isn't spelling out the details,
but anyone who looks for the cited publications will find

* your 2014 paper presenting a compact noisy-DH encryption scheme
with compressed reconciliation (and claiming as its "main technical
innovation" a "low-bandwidth" reconciliation technique that
"reduces the ciphertext length" of previous "already compact"
schemes "nearly twofold, at essentially no cost") and

* Ding's patent two years earlier on a compact noisy-DH encryption
scheme with compressed reconciliation (the same 2x improvement in
ciphertext size compared to LPR).

The 2012 version of the LPR paper (and talks going back to April 2010)
presented a compact noisy-DH encryption scheme with reconciliation, but
didn't compress the reconciliation. Quotient NTRU is much older and is
as compact as compressed LPR, but it isn't a noisy-DH encryption scheme
with reconciliation; some people have published one paper after another
claiming that this is an important distinction, which led to a bunch of
NISTPQC submissions using compact noisy-DH encryption with compressed
reconciliation, and NTRU isn't prior art for a patent on that.

If it was so obvious that the LPR reconciliation could be compressed,
why wasn't it already compressed in the LPR paper (which highlighted
size as an issue), and why was your 2014 paper claiming that all
previous schemes were 2x larger? It's hard enough to convince judges
that things are obvious to people of ordinary skill in the art even when
there _aren't_ subsequent papers claiming that those things are new!

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. This is what's usually called "LPR"---but the Eurocrypt
2010 (May 2010) version of the LPR paper, sent to Springer in February
2010, presented a much _bigger_ RLWE cryptosystem. The 2012 version of
the paper switched to compact noisy-DH encryption with reconciliation.

If compact noisy-DH encryption with reconciliation was already an
obvious cryptosystem from publications in 2009, then why do people
credit it to 2010 LPR, and why did the original version of the LPR paper
present a much bigger cryptosystem? Could it _possibly_ be that the
authors didn't figure out the smaller cryptosystem until after sending
the paper to Springer, and that what you claim years later to be obvious
wasn't in fact obvious at the time? Why is a court supposed to believe
that things are obvious when there are subsequent papers from acclaimed
experts taking credit for these "innovations" or, even more extreme,
presenting worse results?

> The idea of reducing ciphertext size (thus saving bandwidth) by
> rounding away some low bits -- which is exactly what Kyber does -- had
> publicly appeared by September 2009

[ ... ]

> See, e.g., Section 4.2 of https://web.eecs.umich.edu/~cpeikert/pubs/
> svpcrypto.pdf

That wasn't a "compact" cryptosystem, so it deviates from "what Kyber
does" in a way that's essential for exactly the topic at hand.

Most patents, like most publications, are on combinations of previous
ideas, and pointing out how various pieces appeared in previous work
doesn't convince courts that the new combinations are obvious.

---Dan

[Christopher J Peikert]

On Wed, Dec 2, 2020 at 12:15 PM D. J. Bernstein <d...@cr.yp.to> wrote:

In https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf, NIST
repeatedly refers to "Core-SVP" as a number attached to each lattice
parameter set (e.g. "DILITHIUM has the lowest CoreSVP security strength
parameter set of any of the lattice schemes still in the process").

Dan, can you clarify whether you consider "amount of rounding" (e.g., number of low bits dropped) to be part of a lattice scheme's "parameter set"? I certainly do, and I think most others would too, since rounding is a form of additive "error."

As we know, different amounts of rounding will tend to yield different Core-SVP hardness numbers. Round-3 Kyber does a small amount of rounding that Round-2 Kyber didn't do; as one would expect, this slightly increased the associated Core-SVP hardness. What's the objection?

(If this thread exists only because of some semantic dispute about whether "amount of rounding" is part of the "parameter set" or not, I will be disappointed but not surprised.)

 

However, when I question the round-3 Kyber submission's claim that
round-3 Kyber-512 has Core-SVP 2^118, suddenly people jump in to attack
the whole notion that Core-SVP attaches a number to each parameter set.

I don't see anybody disputing that notion. I see people (rightly) considering "amount of rounding" as part of Kyber's parameter set that is analyzed with Core-SVP.

> I don't recall anyone "criticizing other submissions for focusing on the actual
> cryptosystem attack problems rather than the RLWE/MLWE problems." Please
> provide unambiguous references

Here's an example:

   https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/V1RNjpio5Ng/m/uniJDvESBAAJ

This says, e.g., "one cannot directly rely on the Ring-LWE hardness
assumption to argue security of the encryption procedure", and readers
who check the context won't believe you if you try to argue that this
isn't being presented as criticism.

Thanks for the reference. But I read it as a neutral observation -- as "Not sure what implications this remark has, though" makes clear -- so will file this as another example of you mischaracterizing others.

 

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

What I wrote was correct. "In this way" isn't spelling out the details,

What you wrote was not even close to correct, but it's neat to see you try to backtrack like this. "In this way" referred specifically to Round-3 Kyber rounding away low bits (of Z_q elements), which -- again -- is described in detail in the 2009 paper that predates that patent application by more than two years.

> The idea of reducing ciphertext size (thus saving bandwidth) by
> rounding away some low bits -- which is exactly what Kyber does -- had
> publicly appeared by September 2009
  [ ... ]
> See, e.g., Section 4.2 of https://web.eecs.umich.edu/~cpeikert/pubs/
> svpcrypto.pdf

That wasn't a "compact" cryptosystem, so it deviates from "what Kyber
does" in a way that's essential for exactly the topic at hand.

No, Kyber's "compactness" -- obtained from its use of a (degree-256) polynomial ring -- is entirely orthogonal to its use of rounding, and hence irrelevant to your incorrect claim.

(There are plenty of constructions in the literature with every combination of "uses polynomial ring" or not, and "uses rounding" or not.)

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.

Despite multiple attempts by different experts, I have never seen a demonstration of how Kyber/SABER could fall under that patent's claims -- every attempt failed to meet at least three central requirements.

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.

(Since this issue is quite far afield from the ostensible topic of this thread, I'll omit the technical details here, but am happy to share with whoever is interested.)

[Vadim Lyubashevsky]

Hi Dan, all, 

The 2012 version of the LPR paper (and talks going back to April 2010)
presented a compact noisy-DH encryption scheme with reconciliation, but
didn't compress the reconciliation.

No version of the LPR paper presents "reconciliation".  The LPR papers presented a *public key encryption* scheme.  There is a very important distinction here.  In a *key exchange scheme* using "reconciliation" (see e.g. Jintai's talk https://csrc.nist.gov/CSRC/media/Presentations/Ding-Key-Exchange/images-media/DING-KEY-EXCHANGE-April2018.pdf where the word reconciliation is explicitly used so there can be no confusion as to what it means), the users end up with a random shared key that neither party explicitly chose.  In a public key encryption scheme, the sender chooses the message that he wants both parties to have. Of course one can trivially convert a key exchange scheme into an encryption scheme (by adding an xor with the message), but this is not what's happening in Kyber/Saber.  You can see that there is a fundamental difference between the two approaches in the fact that there is slight bias in the shared key in Ding's scheme (see e.g. page 9 of https://patentimages.storage.googleapis.com/53/08/b7/b93d5b6b131e46/US9246675.pdf and consider when j=1 and t=2.  Then an element y in the range [-(q-1)/2,(q-1)/2] is biased towards 0 when looking at y mod 2).  So this bias would propagate itself into a public key encryption scheme if using an xor construction. But such a bias would simply never exist in a direct construction of a public key encryption scheme because the sender can pick the message from whatever distribution he wanted (e.g. an unbiased one).  These are just different ways of doing things that achieve the same eventual goal (Ding's scheme is actually slightly more efficient as a CPA-KEM, by 1 bit per shared message bit; but is then equal in size to PKE with compression after being converted to a CCA-KEM).

Also notice that Jintai has a Ring-LWE encryption scheme (page 14 of https://patentimages.storage.googleapis.com/53/08/b7/b93d5b6b131e46/US9246675.pdf) which is like LPR and *does not* (unless I am reading something wrong) do any rounding / compression - so it just outputs two elements D1,D2 (which could be matrices over some ring).   

-Vadim

[D. J. Bernstein]

I would like the NISTPQC security requirements and security claims for
Kyber-512 to be stated clearly so that cryptanalysts who publish papers
breaking Kyber-512---showing that it doesn't meet its security claims,
or doesn't meet the NISTPQC security requirements, or both---don't have
to worry about retroactive revisions of the claims and/or requirements.
This is an example of a scientific requirement called "falsifiability".

The gargantuan ambiguities in the NISTPQC security requirements are
entirely under NIST's control, but the change in how round-3 Kyber
calculates "Core-SVP" is a different story.

Each column on the "Estimate all the {LWE, NTRU} schemes!" page always
led readers to believe that it was a clearly defined function mapping
parameter sets to security claims. One of these functions from parameter
sets to security claims was repeatedly labeled "Core-SVP" by NIST and
others. None of the current commentators spoke up to claim that this was
nonsense or that it had conflicting definitions.

Many submissions were already using Core-SVP, because they were simply
copying what NewHope was doing (or at least they were trying to; we've
seen failures, such as LightSABER miscalculating 2^125 when the correct
calculation says 2^118). Other submissions pointed out inaccuracies in
Core-SVP and made various efforts to reduce the inaccuracies, leading to
a variety of different functions, usually larger than Core-SVP. The
submissions prioritizing accuracy were then criticized for supposedly
being less conservative and supposedly interfering with comparisons.

By the beginning of round 2, everyone was trying to report Core-SVP. For
example, the round-2 NTRU Prime submission presented a detailed review
of how the "Estimate" page computed this metric, and reported the output
of this metric for each round-2 NTRU Prime parameter set. The submission
_also_ presented the most comprehensive available survey of inaccuracies
and potential inaccuracies in Core-SVP, and reported the results of
alternative metrics aimed at addressing the three most glaring Core-SVP
inaccuracies. All of the different metrics were clearly labeled.

How did NIST respond to this? By criticizing NTRU Prime for supposedly
measuring "generic lattice security differently", and by asking whether
the parameter sets "actually meet their claimed security categories"---a
question that NIST did not ask regarding lower-security, more aggressive
parameter sets in other proposals.

This brings me to Kyber-512. My current understanding is that the
following three mechanisms, when applied to round-3 Kyber-512, produce
the following "Core-SVP" numbers:

* The mechanism used on the "Estimate" page: <=2^112 (see below).
* The mechanism used in the round-2 Kyber submission: <=2^112.
* The mechanism used in the round-3 Kyber submission: 2^118.

The reason for this change is that the round-3 Kyber submission switched
to a new mechanism of mapping parameter sets to security levels, knowing
that this mechanism is new, while continuing to prominently label the
output as "Core-SVP". Procedurally, this labeling is an attack against
NIST's announced use of "the CoreSVP metric" to compare "which lattice

schemes are being more and less aggressive in setting their parameters".

Allowing this would not be fair to other submissions. Is NIST going to
criticize Kyber for measuring "generic lattice security differently"? Is
it going to ask Kyber to report Core-SVP by "the CoreSVP metric" that
every other lattice submission was pretty much forced to use, meaning
that round-3 Kyber-512 drops from 2^118 to <=2^112? Sure, Kyber argues
that Core-SVP is an underestimate of _actual_ security, but submissions
that already argued this in more detail were criticized for this and
weren't given exemptions from NIST's announced comparison procedures.

Vadim Lyubashevsky writes:
> We must say that we are actually heartened that a disagreement over 1
> bit of security provokes such passion in you.

Given the attack literature, the claim that round-3 Kyber-512 meets the
minimum NISTPQC security requirements is skating on _extremely_ thin
ice. For example, regarding NIST's undefined set of "classical gates",
round-3 Kyber-512 claims to be 8 bits harder to break than AES-128, plus
_or minus_ 16 bits!

Clearly 1 bit of change, or the full 7 bits covered in my message, could
push Kyber-512 below what NIST calls the "floor" of category 1. Clearly
this is also why the Kyber submission spent so much effort on claiming
these extra 7 bits: changing Kyber-512 to a new parameter set, changing
to a different mechanism of computing its "Core-SVP" claims as noted
above, and---in some ways the most amazing change---abandoning the tight
link between Kyber and MLWE.

Many people seem to believe that the security levels of RLWE and MLWE
are thoroughly understood (while the same people sometimes express
doubts regarding the security levels of RLWR and MLWR). This supposed
understanding, in turn, has been repeatedly portrayed as the core reason
that users are supposed to trust the security claims for specific KEMs
such as NewHope-512 and the three different versions of Kyber-512.
People who believe all this should be

* enthusiastic about the fact that, for RLWE/MLWE cryptosystems, the
Core-SVP metric on parameter sets is actually an evaluation of the
underlying RLWE/MLWE instances;

* disturbed by Kyber-512 choosing an MLWE size that doesn't seem to
meet NISTPQC's minimum security requirements; and

* disturbed by Kyber-512 switching to a different metric---one that
isn't evaluating the MLWE instances---to be able to claim to meet
NISTPQC's minimum security requirements.

Maybe a complete attack analysis would show that a direct attack on
Kyber-512 is below the "floor" anyway, in which case further security
losses don't matter---but showing this would also need clarity from NIST
regarding the definitions of the NISTPQC security requirements. We also
don't have NIST's answer to the question of where Kyber-512 falls among
"unacceptable" and "controversial" and "uncontroversial"; NIST claimed
in September that we could all determine the dividing lines here from
NIST's public statements.

> We believe that we are being very clear with what we are claiming for
> Kyber512

Does the round-3 Kyber submission claim that the MLWE instance inside
round-3 Kyber-512 is as hard to break as AES-128?

This was claimed by the round-1 and round-2 Kyber submissions regarding
round-1 Kyber-512 and round-2 Kyber-512, right? The category assignments
and "Core-SVP" claims were hardness claims for those MLWE instances? Is
the round-3 Kyber submission making this claim for round-3 Kyber-512?

If not, then is the Kyber team going to withdraw the statement in the
round-3 submission that the "estimates of the security strength" for
round-3 Kyber-512 are "based on the cost estimates of attacks against
the underlying module-learning-with-errors (MLWE) problem"?

If not, how can this statement be reconciled with the 2^118 Core-SVP
claim regarding round-3 Kyber-512?

Also, is the Kyber team withdrawing the claim that Theorem 1 is "tight"
for Kyber-512? If not, what exactly does this claim mean, and how can
this be reconciled with the handling of Kyber-512?

If the MLWE instance inside Kyber-512 _is_ being claimed to meet the
specified security level, then this claim needs to clearly stated so
that cryptanalysts breaking it aren't faced with a subsequent "No, we
never meant that". If the MLWE instance _isn't_ being claimed to meet
the specified security level then various other claims regarding the
relationship between Kyber and MLWE need to be clearly withdrawn.

Finally, just to confirm the numbers, am I correctly understanding the
Kyber submission to be claiming that ignoring dual attacks increases
"Core-SVP" for round-3 Kyber-512 from 2^111 to 2^112 (this is also a
statement about the MLWE instance), and that accounting for rounding
(which is what breaks the MLWE link) then increases 2^112 to 2^118? What
is the "primal" block size that Kyber claims to be optimal for the MLWE
problem, leading to the 2^112 claim? (Multiplying by 0.292 and rounding
compresses multiple possible block sizes into one number, even if it's
clear which rounding mechanism is being used.)

> If users skip rounding, they're not using Kyber.

I agree. However, if you take rounding into account for an RLWE/MLWE
system, then you're breaking the supposedly tight, frequently advertised
link between that system and the underlying RLWE/MLWE problem, and
you're not using "the Core-SVP metric" that NIST said it's using for
comparing parameters across lattice submissions.

> for example the LWE-estimator of Albrecht et al. assumes a single
> vector, and concludes that the dual attack costs about 2^30 times the
> cost of the primal attack

I agree that there's a conflict in the literature between multiple
definitions of the dual component of Core-SVP, and that for some ranges
of parameters this affects the final Core-SVP number, possibly by many
bits (although not so many for Kyber). Thanks for pointing this out.

Perhaps this conflict has already corrupted NIST's use of Core-SVP to
compare "which lattice schemes are being more and less aggressive in
setting their parameters". Everyone should support (1) figuring out the
effects of any previous confusion caused by conflicting definitions, and
(2) resolving the definitional conflict so that the conflict doesn't
create unfair comparisons going forward.

Here are three possibilities for a unified definition:

(1) most favorable to the attacker, the assumption in round-2 Kyber:
assume sieving generates essentially as many short vectors as its
run time;

(2) assume some intermediate number of vectors;

(3) least favorable to the attacker, the "Estimate" assumption:
assume sieving generates only 1 short vector, the other vectors
being useless.

The round-3 Kyber submission argues briefly for #3. I'm puzzled by this
argument, for several reasons.

First, is the Kyber team seriously claiming that dual attacks are as
wimpy as indicated in #3? Isn't the actual situation for known attacks
something in the #2 range---possibly much closer to #1 than to #3?

The statement in the submission that "most" vectors will be "sqrt(4/3)
larger" doesn't contradict #2. "Most" doesn't mean "all but 1"; more
importantly, these are probabilistic processes, and a larger number of
longer vectors could do more damage than a smaller number of shorter
vectors. Perhaps this can be quantified along the lines of analyses of
Bleichenbacher's attack.

Second, regarding the claim that obtaining many short vectors is
inconsistent with "dimensions for free": Let's assume, arguendo, that
this claim is true and remains true, rather than being an artifact of
the overload on cryptanalysts. Isn't the "dimensions for free" speedup
asymptotically swamped by the many-vectors speedup? More precisely,
isn't this subexponential vs. exponential? Is there a concrete claim
that the asymptotics are misleading: that up through dimension d,
covering all cryptographic dimensions, one should take "dimensions for
free" and use only the shortest vector? Where is d quantified? Where is
this claim justified?

In general, the way that Core-SVP was constructed was by taking the best
asymptotics and replacing o(1) with 0 (a fundamentally flawed procedure
for people who care about accuracy, but that's not the point here). The
subexponential speedup from "dimensions for free" isn't visible in this
process. The Kyber team wasn't calling earlier for the Core-SVP metric
to be revised on the basis of "dimensions for free". Why are "dimensions
for free" suddenly supposed to be taken into account in the definition?

Third, the whole push for every submission to use Core-SVP came from the
general idea that Core-SVP is (relatively) simple but "conservative",
meaning that it supposedly underestimates attack costs. Doesn't this
mean that, if there's a conflict between two "Core-SVP" definitions, one
definition more "conservative" and the other less "conservative", the
less "conservative" definition should be eliminated?

> It certainly points to the maturity of the science behind lattice
> cryptanalysis when this is what's left to discuss :).  

In case the above statement causes confusion despite the smiley, let me
point to the graph in https://video.cr.yp.to/2020/0813/video.html as a
quantified reason to be terrified of lattice-based cryptography. This
graph reflects only one type of risk, and beyond this there are many
further risks in lattice-based cryptography and specifically NISTPQC
lattice KEMs, as illustrated by a variety of attack advances published
_this year_, including very fast attacks against some supposedly safe
systems. We haven't seen the end of this story.

For people trying to downplay lattice risks: Have you ever taken a
quantitative approach to analysis of the risks of improved attacks, and
used this quantification to compare lattices to other options? If not,
aren't you concerned about the possibility of spreading misinformation,
damaging allocation of precious cryptanalytic resources, damaging the
processes for selecting cryptographic systems, and generally increasing
security risks for cryptographic users?

Someone asking for clarity regarding Kyber-512's security claims
shouldn't have this portrayed as implicitly denying other risks.

> P.S. I should note---with all due respect---that all available evidence
> is consistent with the theory that NIST's strategy for handling concerns
> regarding the Kyber-512 security level is to adjust the NISTPQC security
> criteria so as to continue accepting the latest version of Kyber-512
> (rather than suffering the public-relations problems of rejecting it).
> We are not sure what you mean here.  What adjustments did NIST make?

For example, in August 2020, NIST made a preliminary (still not fully
defined) proposal to add memory costs, in violation of NIST's previously
announced "minimum" criteria for metrics. For references and further
analysis of this ongoing change in the NISTPQC evaluation criteria, see
Section 5.5 of https://cr.yp.to/papers.html#categories.

Without this change from NIST, the Kyber statement

We do not think that even a drop as large as 2^16 would be
catastrophic, in particular given the massive memory requirements
that are ignored in the gate-count metric

regarding round-3 Kyber-512 simply wouldn't be relevant to the NISTPQC
evaluation process. Showing that known attacks use only 2^(151-16) =
2^135 "gates" (assuming NIST defines the "gates"!) would eliminate
Kyber-512.

_With_ NIST pushing enough extra "memory" factors into the definitions
of the NISTPQC "categories", such attacks wouldn't eliminate Kyber-512.
Furthermore, if NIST never clearly defines the extra "memory" factors,
or doesn't commit to leaving the definitions unchanged, then NIST is
free to respond to even better attacks by inserting further "memory"
factors into the "category" definitions. A sufficiently large attack
advance will put an end to this, presumably, but the minimum NISTPQC
security requirements should have been nailed down years ago.

Kyber is far from unique in arguing that memory-access costs are
important---of course they exist in reality!---but to exactly what
extent are they included in the metrics that NIST uses to define the
minimum security levels allowed in NISTPQC? The lack of an answer has
led to the NISTPQC security requirements being continually interpreted
in incompatible ways, with memory-is-expensive interpretations used to
say that Kyber-512 is safe against known attacks, and memory-is-cheap
interpretations used to criticize other submissions.

Most submissions have tremendous flexibility in parameter choices, and
will be able to comfortably target whatever security levels NIST asks
for---as soon as NIST _defines_ the security targets, rather than hiding
behind pseudo-definitions with conflicting interpretations. Kyber is
different, forced by its "framework" (which NIST has praised!) to make a
big jump from 512 to 768. This limited flexibility should be treated
negatively according to the NISTPQC criteria. If NIST were actually
enforcing objective boundaries for its five "categories" then those
boundaries would be likely to illustrate Kyber's limited flexibility.
Manipulating the boundaries can easily hide this, making Kyber look
better than it actually is. See https://cr.yp.to/papers.html#categories.

---Dan

[Christopher J Peikert]

Let's stipulate, consistent with NIST's statements, that Core-SVP can attach a number to each lattice scheme parameter set.

At the risk of repeating myself, it seems to me that Dan's entire objection about the Round-3 Kyber Core-SVP analysis is premised on *not* considering "amount of rounding" as part of a lattice scheme's "parameter set." If one *does* consider it as a parameter -- and one should! -- then I see no grounds for the objection. (Despite my request, Dan's long message did not offer any clarity on this central point; I think he should address it directly.)

For cryptanalytic purposes, ignoring rounding leaves out very important information, and can even produce perverse Core-SVP numbers.

For example, ignoring rounding would lead us to conclude that all of the NTRU Prime parameters have *trivial* Core-SVP hardness (~2^0), because NTRU Prime uses rounding alone for ciphertext "error"; without such rounding, the scheme would become trivially insecure to lattice attacks.

Of course, the NTRU Prime submission did *not* report trivial Core-SVP hardness, because the authors (Dan included) rightly included the rounding in their Core-SVP analysis. Obviously, other submissions should not be criticized for doing the same.

On Fri, Dec 4, 2020 at 12:06 PM D. J. Bernstein <d...@cr.yp.to> wrote:

This brings me to Kyber-512. My current understanding is that the
following three mechanisms, when applied to round-3 Kyber-512, produce
the following "Core-SVP" numbers:

   * The mechanism used on the "Estimate" page: <=2^112 (see below).
   * The mechanism used in the round-2 Kyber submission: <=2^112.
   * The mechanism used in the round-3 Kyber submission: 2^118.

The reason for this change is that the round-3 Kyber submission switched
to a new mechanism of mapping parameter sets to security levels,

I don't think this is accurate. Round-3 Kyber introduced rounding that was not present in its previous versions. The updated Core-SVP analysis reflected the existence of that rounding, presumably in a manner consistent with how other submissions had treated rounding. This is not a "new mechanism," it is the ordinary mechanism applied to new parameters.

 

in some ways the most amazing change---abandoning the tight
link between Kyber and MLWE. 

Here there is an unstated premise that "MLWE" (and later, "the MLWE instance inside Kyber-512") does *not* include the rounding -- even though rounding is widely understood to be a form of error (the 'E' in MLWE). I don't agree with this premise, for the same reasons given above.

Of course, it's also well known that MLWE with extra rounding is at least as hard as MLWE *without* such rounding (all other parameters being equal), so one could also claim a tight reduction from decision-MLWE w/o rounding to, say, breaking the CPA security of the pre-FO version of Kyber.

I agree that it would be good to get a precise statement from the Kyber team concerning what they mean by "MLWE," and the consequences.

 

Many people seem to believe that the security levels of RLWE and MLWE
are thoroughly understood (while the same people sometimes express
doubts regarding the security levels of RLWR and MLWR).

Again, please provide unambiguous references, so the reader can check whether you are accurately representing what "many people" "seem to believe" and express.

(The reader may wish to check previous messages in this thread regarding this issue.)

[Vadim Lyubashevsky]

Hi Chris,

Thank you for distilling that email into one question.

Here there is an unstated premise that "MLWE" (and later, "the MLWE instance inside Kyber-512") does *not* include the rounding -- even though rounding is widely understood to be a form of error (the 'E' in MLWE). I don't agree with this premise, for the same reasons given above.

Of course, it's also well known that MLWE with extra rounding is at least as hard as MLWE *without* such rounding (all other parameters being equal), so one could also claim a tight reduction from decision-MLWE w/o rounding to, say, breaking the CPA security of the pre-FO version of Kyber.

I agree that it would be good to get a precise statement from the Kyber team concerning what they mean by "MLWE," and the consequences.

Relying just on MLWE, Kyber512 has CoreSVP of 112 with tight reductions and everything as before.  If you're willing to accept that rounding also adds noise which contributes to hardness -- which does appear to be true according to today's cryptanalysis (and something that several proposals base all of their security on) -- then Kyber512 has CoreSVP of 118.  While we felt somewhat uncomfortable basing the security of our scheme entirely on the MLWR assumption, we felt OK risking (a maximum of) 6 bits on it. 

Best,

Vadim

(On behalf of the Kyber team)

 

[dustin...@nist.gov]

All,

CoreSVP was the most widely used technique for estimating the security of lattice schemes at the end of Round 2. The differences between teams' methodologies in computing CoreSVP were not large enough to affect our decisions or the 2nd Round report. If, by the end of the 3rd Round, there are other, widely agreed-upon estimation techniques that better approximate real attack costs, then we will consider those instead. This is consistent with our prior statement that "We have not and will not specify a set of ‘rules’ that must be used to evaluate the security of every candidate without regard to whether using these ‘rules’ would accurately reflect the level of security of every candidate."

The Kyber Round 3 specification provides estimates for gate cost in the RAM model of the best-known classical attacks against their updated parameters. These estimates exceed our estimates for the cost of attacking AES at each security category. Additionally, the Kyber team claims known quantum speedups are too small to be relevant for assessing categories 1, 3, and 5. If this analysis is correct, then Kyber clearly meets the security categories defined in the CFP. If the analysis is found to be incorrect, or if new attacks arise, then we will re-examine the situation.

This email serves to respond to process questions that arose in this thread. The merit of technical claims is a research matter for the community to address.

NIST PQC Team  

[D. J. Bernstein]

Quoting the first entry in https://ntruprime.cr.yp.to/faq.html (from
October):

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

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
here" and

(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
original thread.)

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
9246675:

* 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
isn't novel.

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

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

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
cryptosystem:

* "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
error X_B;

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

Namely?

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.

---Dan

[Vadim Lyubashevsky]

Hi Dan, all,

I don't want to get into an argument because it never leads anywhere and because I obviously do not have the requisite competence to discuss patent law.  I am just including some extra facts.  

 

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

I wrote about this in a previous email, but I will repeat it again. Jintai did not present a new *cryptosystem*.  His KEM construction is quite different from LPR / Kyber / Saber with compression.  In fact, as you can see from page 13 onward, where he actually needs a *cryptosystem* for something else, he uses LPR (or something similar based on Module-LWE, which also already appeared prior) *without any compression / rounding*. So given this, it seems hard to argue that his reconciliation-using KEM obviously implies Module-LWE encryption with compression.  (I am not arguing the other direction that LWE with compression implies reconciliation because I don't care about invalidating anything).   

 

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;  

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:

 

You did not list the prior work that the El Gamal-like LPR encryption scheme (i.e. with small secrets / errors) is actually derived from, and which precedes this patent.  (And I know that you know it because we discussed it ... but it's possible you forgot because it was a while ago). I am referring to this paper which appeared at TCC 2010 (https://eprint.iacr.org/2009/576.pdf).  Now observe the encryption scheme in section 3 (for the definition of the \odot symbol, it's easiest to look at the example on page 3. In particular, A \odot s = As+e, where e is the "carry" vector) and go through the checklist that you made comparing the claim and LPR.  Everything in this cryptosystem -- in particular the fact that all the secrets and errors have small norms -- matches except for the "belonging to the ring R" part.  If we wanted to use something like NewHope (where all elements indeed belong to a ring), then one could start arguing how relevant this distinction is. I suppose it could be relevant if one needed commutativity (which one doesn't for NewHope or LPR). But I don't even need to bother with that -- the elements in the equation As+e in Kyber / Saber are not ring elements! They are vectors and there is no commutativity -- i.e. As =/= sA.  So the only possibly difference between the claim and the TCC paper is the algebraic properties that are induced by having A (and s and e) be a ring element, and Kyber / Saber don't use that.

There is one thing that you might nitpick at: A\odot s = As+e, but the e is not random in the cryptosystem. But in the talk I gave at TCC 2010 (https://www.dropbox.com/s/s4utim5y2jd3rov/subset_sum_tcc.ppt?dl=0) on slide 15, the cryptosystem is described generically with the only restriction being that all the errors and secrets are small. Now you might again nitpick that one can't really be sure that I gave this talk during TCC (Feb. 9 - 11, 2010).  Luckily, Oded Goldreich was there and he "blogged" about the talk (by "blogged", I mean put a postscript file on his website http://www.wisdom.weizmann.ac.il/~oded/X/tcc10.ps) and dated it.  He summarizes this talk in section 7 and mentions that the noise could be random.  So what exactly do Kyber/Saber use from the patent instead of from the TCC paper/talk?   If anything, it's clear that this patent did not mention very relevant prior art.

Best,

Vadim

[Christopher J Peikert]

On Fri, Dec 11, 2020 at 10:08 AM D. J. Bernstein <d...@cr.yp.to> wrote:

Quoting the first entry in https://ntruprime.cr.yp.to/faq.html (from
October):

   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 multiple problems with this paragraph.

The second clause is factually incorrect: Kyber and SABER (at least) do not even use a "2x ciphertext-compression mechanism," much less one described in the cited patent. The (less than 2x) compression mechanism they do use (1) was published more than two years prior to the cited patent, and (2) does not even appear in that patent. See below for details.

(To be clear, "ciphertext-compression mechanism" refers to the schemes' method of dropping [or "rounding away"] some low bits of Zq elements, which is what the above points are addressing.)

The first clause, which concludes that the other patent covers any scheme with a "noisy DH + reconciliation" structure, is far too imprecise and broad. The patent, like any other, is limited to specific methods that must meet particular requirements. I still have not seen a demonstration of how Kyber or SABER could be covered by the patent's claims (see below for more).

 

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

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

This is absurdly tortured interpretation, but another interesting attempt to backtrack. Read your own statement: "the idea of saving bandwidth in this way" can only be referring to its antecedent, which is Kyber's "rounding" (which does indeed save bandwidth).

"[T]he idea of saving bandwidth in this way" -- namely, rounding away some low bits of Zq elements, exactly as Kyber does -- was already published by September 2009, more than two years prior to Ding's patent submission (details appear in my prior messages).

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

Readers don't need to follow the references to Ding's 2012 patent in order to see that your chronology and assignment of credit are wrong, because they can see that (a) the rounding method Kyber uses was first described by 2009, and (b) 2009 happened before 2012.

Moreover, the "rounding" method described in Ding's patent isn't what Kyber does. (Vadim has given many details on this.) So the attempt to shoehorn Ding's patent into a discussion of Kyber's rounding is an irrelevant distraction.

 

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.

Nobody claimed to "kill the patent," so this a strawman. I only killed your attribution of "the idea of saving bandwidth in this way."

However: the idea of applying rounding Zq-coefficients **of polynomials** (which are the source of Kyber's and SABER's efficiency) was also published by August 2011, several months before Ding's patent submission. See https://eprint.iacr.org/2011/401.pdf and search for "ring-LWE."

So, even this attempt to make an artificial distinction on efficiency -- which is based only on how the Zq-elements were obtained prior to rounding them -- also fails. 

 

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.

If you're looking for even more prior art saying that large "unstructured" matrices are interchangeable with polynomials that compactly represent "structured" matrices (and are faster to compute with) -- the very principle giving Kyber/SABER their efficiency and compactness -- then look no further than this 2008 chapter by Micciancio and Regev, and references therein: https://cims.nyu.edu/~regev/papers/pqc.pdf .

Specifically see Section 4.2, which details how "The efficiency of lattice-based cryptographic functions can be substantially improved replacing general matrices by matrices with special structure."

Of course, as they write, "A fundamental question that needs to be addressed whenever a theoretical construction is modified for the sake of efficiency, is if the modification introduces security weaknesses."

For example, almost all of the LPR'10 paper is devoted to addressing this question for LWE; only one introductory paragraph informally sketches an example cryptosystem. This is because, as the paper says, "Most [LWE] applications can be made more efficient, and sometimes even practical for real-world usage, by adapting them to ring-LWE. This process is often straightforward..." So yes, this form of interchange was well established prior to the patent application.

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

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:

This is not what I requested.

You concluded that "the entire idea of noisy-DH encryption with reconciliation" was covered by the patent.

I requested a justification of that broad claim, or even something more limited: "a demonstration of how Kyber/SABER could fall under that patent's claims."

You've possibly shown that the specific LPR cryptosystem is covered, which might be a problem for NTRU LPRime -- but that doesn't imply anything about Kyber/SABER. Saying that they are somehow "LPR-like," and hence covered, won't do. You need to match up the limitations of the patent's claims to Kyber/SABER themselves.

> -- every attempt failed to meet at least three central requirements.

Namely?

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.

No and no; the failures were not on minor things like signs, and there were indeed at least three major issues.

Here are some details. In an attempt to match up the patent's claims to Kyber/SABER, one would need to show (with respect to Claim 1):

1. what the elements X_A, Y_A, X_B, Y_B, P_A, P_B, etc. correspond to, and what *common ring* R they all belong to;

2. what "internal composition law" f on R satisfies the requisite "X_l * f(Y_l) - Y_I * f(X_I) has a small norm" property;

3. how both entities A and B use the *same* f in computing P_A and P_B using the provided equations.

Despite multiple attempts, I have never seen even one of these items successfully demonstrated for Kyber/SABER, much less all three at once.

(To be clear, this is not meant to be an exhaustive list of the problems with applying the patent to Kyber/SABER, and nothing I've written should be taken as endorsing either of the cited patents' validity.)

 

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

You haven't even checked the patent claim's against Kyber/SABER, yet you make such a confident assessment? This is FUD.

[Robert Ransom]

On 12/11/20, D. J. Bernstein <d...@cr.yp.to> wrote:

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

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

The other reason that you picked the European patent rather than US
9,094,189 is that both of the independent claims in the U.S. patent,
claims 1 and 21, are explicitly limited to rings of one of two forms:

* R = F_q[x]/(X^n - 1) "with n equal to 6000", or

* R = Z/pZ "with p equal to 2500".

Other constraints are specified in the patent for each of those two
classes of rings. Note that I did not introduce any error or omit any
formatting from the integer ring; the patent really does specify that
p is equal to the number two thousand, five hundred.


I have not yet obtained the patent wrapper to find out whether the
U.S. patent was limited to those two classes of rings for any
particular reason.

[D. J. Bernstein]

Robert Ransom writes:
> both of the independent claims in the U.S. patent,
> claims 1 and 21, are explicitly limited to rings of one of two forms:
> * R = F_q[x]/(X^n - 1) "with n equal to 6000", or
> * R = Z/pZ "with p equal to 2500".

The doctrine of equivalents will cover other rings. The specific patent
claim that I analyzed in detail in the message you're replying to _also_
names a ring that's different from the NISTPQC choices, and I explained
in that message why this doesn't matter. No court will find a
"substantial" difference between F_q[x]/(x^6000-1) and F_q[x]/(x^512+1)
unless there was prior art forcing the choice of number and/or sign---
and how could there have been, since this patent filing predated LPR?

It's understandable that most people reading patent claims won't realize
that courts go beyond the literal meaning and extend the coverage to
include anything that's "substantially" the same. This is a perfect
example of what I said about errors in NISTPQC evaluations, and about
the importance of detailed public analyses.

> The other reason that you picked the European patent rather than US
> 9,094,189

Nope. The European patent already surviving a round of litigation is
useful information, and something I already tweeted about in early July:

https://twitter.com/hashbreaker/status/1279677625410088963

One of the followups there asked about x^n-1, and I replied (briefly)
that this doesn't matter given the doctrine of equivalents.

> I have not yet obtained the patent wrapper to find out whether the
> U.S. patent was limited to those two classes of rings for any
> particular reason.

The file might have interesting information, and a public analysis would
be useful. Some care in allocating human resources is warranted, since
there's a high risk of error in the analysis if it's coming from someone
who doesn't know the basics of how courts interpret patents.

---Dan

[Christopher J Peikert]

something I already tweeted about in early July:

   https://twitter.com/hashbreaker/status/1279677625410088963

Wait -- since July you've been claiming (with certainty) that the patent covers, e.g., Kyber and SABER, without ever showing how these systems are covered by the patent's specific limited claims?

It's far past time to do so, or retract the claim. As of now, it is baseless -- and in my opinion, should be seen as FUD.

[D. J. Bernstein]

Vadim Lyubashevsky writes:
> Everything in this cryptosystem -- in particular
> the fact that all the secrets and errors have small norms -- matches
> except for the "belonging to the ring R" part.

Mathematically, I don't understand what distinction you're trying to
draw here. Simply zero-padding any vector or matrix produces a square
matrix, and matrix-vector multiplication is exactly multiplication in
the ring of square matrices. If the goal were to kill Claim 1 of the
2010 patent then it would be worth going through this in detail. (A
claim is invalidated by any example appearing in the prior art.)

My analysis focused, however, on Claim 19 of the patent, matching it up
point by point to the subsequent LPR cryptosystem. Claim 19 uses a
_polynomial_ ring, making it much more efficient than the matrix case.
So the matrix cryptosystem you mention doesn't match Claim 19, and it's
worse in a way that a court will easily understand.

The defendant's lawyers can still try to argue that the LPR cryptosystem
was _obvious_ to someone of ordinary skill in the art given the 2009
work, but, if it was obvious, then why does the last slide of your
February 2010 presentation say "'Ideal Lattice' analogue" with a
question mark under "Open Problems"? And why does the May 2010 Springer
version of the LPR paper feature a larger, slower cryptosystem, replaced
by the LPR cryptosystem only in a subsequent revision of the paper?

> If anything, it's clear that this patent
> did not mention very relevant prior art.

Do you think you can show that the applicants _knew_ about relevant
publications that they didn't mention to the patent office? "Inequitable
conduct" by patent holders can effectively invalidate an entire patent,
so this could be a useful line to explore.

---Dan

[Andrea Basso]

Hi Dan, hi all,

I have looked into the first patent (US9094189B2) and I do not believe
it covers SABER. I also suspect it does not cover Kyber either, but I
have not investigated it much.

As a disclaimer, I have worked as a patent engineer in the past, but I
do not have much experience with cryptographic patents or US patent law.
Also, I am a member of the SABER team (although I am speaking for
myself), so there is an inherent conflict of interest, as for most other
people who have participated in the debate.

Firstly, the US and European are slightly different, so it is better to
treat them separately. Claim 1 of the US patent specifies that the ring
R can either be F_q[x]/<x^n+1> or Z/pZ, and in the first case the value
of the exponent n must be 6000 and the norm of X_A, X_B, Y_A and Y_B
must be 35. Clearly, this does not apply to either Kyber nor SABER. Now,
the doctrine of equivalents cannot be applied here because of
prosecution history estoppel. That means that if claims are amended
during prosecution, the subject matter that has been excluded cannot
then be covered by the doctrine of equivalents. This is exactly the case
here. The full history of the US prosecution of the patent can be found
on the USPTO website (https://globaldossier.uspto.gov/). One can see
that the claim 1 initially filed in 2013 does not contain any mention of
specific values of the exponent n nor of the norms. After the examiner
complained that claim 1 was indefinite (see the non-final rejection from
February 2014), the specific values requirements were introduced with
the amended claims submitted in 2015. Thus, the US patent does not cover
neither Kyber nor Saber.

For the EU patent, the situation is slightly less straightforward since
claim 1 does not have the same limitations. However, the EU patent also
does not cover SABER, mainly due to its reliance on LWR. Whether the
function f(X) is interpreted as either f(X) = A*X or f(X) = p/q*A*X, the
computations for the intermediate values P_A and P_B are clearly
different. Once again, the differences and their effects are substantial
enough that the doctrine of equivalents does not apply to this case.

One thing to note here is that while the application is done at the
European Patent Office, once granted the patent is converted into
individual patents for each European country. Thus prosecution only
takes place at the national level. The patent, according to information
on Espacenet
(https://worldwide.espacenet.com/patent/search/family/042753478/publication/EP2537284B1?q=EP2537284B1),
has lapsed in all countries but Germany, France, Switzerland and the UK.
At a first look, the requirements for the application of the doctrine of
equivalents in these four countries are more stringent than in the US.
In particular, Germany and Switzerland seem to require the replace
features be obvious in light of the original patent, which is clearly
not the case here. The UK and France require the replace features have
the same consequences as the original claims, and if MWLE-based systems
fall under the patent (and that's a big if), MWLR have clearly different
advantages/disadvantages. Thus, the EU patent also does not cover SABER
in the four countries where it is active.

This is what I gathered on a first look. I suspect there are many other
reasons why the patent does not cover SABER. If, instead, there is any
mistake with this reasoning, please let me know. I also have not had a
chance to look into the second patent, but at a glance it seems like it
does not cover SABER either.

All the best,
Andrea

[Christopher J Peikert]

My analysis focused, however, on Claim 19 of the patent, matching it up
point by point to the subsequent LPR cryptosystem. Claim 19 uses a
_polynomial_ ring, making it much more efficient than the matrix case.
So the matrix cryptosystem you mention doesn't match Claim 19, and it's
worse in a way that a court will easily understand.

The defendant's lawyers can still try to argue that the LPR cryptosystem
was _obvious_ to someone of ordinary skill in the art given the 2009
work

Yes, the technique of improving efficiency by replacing "unstructured" matrices with "structured" ones corresponding to polynomials was well documented prior to the patent. Again, see this 2008 survey by Micciancio and Regev (in a book you edited!), and the many references therein: https://cims.nyu.edu/~regev/papers/pqc.pdf .

Section 4.2 details how "The efficiency of lattice-based cryptographic functions can be substantially improved replacing general matrices by matrices with special structure," and specifically considers replacing each square n-by-n matrix with a circulant or anti-circulant matrix. These correspond to polynomials in the rings Z_q[x]/(x^n-1) or Z_q[x]/(x^n+1).

Applying this mechanical transformation to the TCC'10 cryptosystem (which also precedes the patent) yields the "LPR" cryptosystem that you've claimed is covered by the patent.

but, if it was obvious, then why does the last slide of your
February 2010 presentation say "'Ideal Lattice' analogue" with a
question mark under "Open Problems"?

Because, as Micciancio and Regev also write, "A fundamental question that needs to be addressed whenever a theoretical construction is modified for the sake of efficiency, is if the modification introduces security weaknesses."

Applying the mechanical transformation from unstructured matrices to structured ones/polynomials is obvious. Supporting the resulting system's *security* by, e.g., a connection to worst-case "ideal lattices" is highly non-obvious.

 

And why does the May 2010 Springer
version of the LPR paper feature a larger, slower cryptosystem, replaced
by the LPR cryptosystem only in a subsequent revision of the paper?

Both versions of the LPR paper informally describe just one example cryptosystem, because applications are not the paper's focus. Almost all of the paper is devoted to formally defining Ring-LWE and giving a connection to worst-case ideal lattices (i.e., addressing the "security" question stated in MR'08).

Regarding applications, the paper says (Springer version): "This scheme and its security proof are a direct translation of the ‘dual’ scheme from [13] based on the standard LWE problem, and similarly direct adaptations are possible for most other LWE-based schemes..." This is essentially restating for LWE the general approach described in MR'08. Again, performing this direct adaptation on the TCC'10 cryptosystem yields the "LPR" cryptosystem.

The "larger, slower" example sketched in the Springer version is much more versatile, because it can be made identity-based and more. (For those who know the jargon, it is the Ring-LWE adaptation of the widely used "dual Regev" LWE system from GPV'08.) However, its full CPA-security proof based on Ring-LWE relies on a non-trivial "regularity" lemma that we ultimately decided to break out into a separate paper devoted to applications (the LPR'13 "toolkit" paper).

The smaller example system is much more feature-limited, but it has an elementary and self-contained CPA-security proof based on Ring-LWE, following the strategy from the TCC'10 work.

Again, both example systems are "direct adaptations ... of other LWE-based schemes," using a well documented approach, all of which preceded the patent application.

[D. J. Bernstein]

Focusing here on the application to Kyber of Claim 19 of the 2010 patent
that I mentioned. I already spelled out the application to LPR.

Christopher J Peikert writes:
> 1. what the elements X_A, Y_A, X_B, Y_B, P_A, P_B, etc. correspond
> to, and what *common ring* R they all belong to;

The simplest answer in court is the doctrine of equivalents.
Generalizing from r*r to r*m, while preserving the sizes of the
communicated objects, is not a "substantial" difference.

But, just for fun, let's imagine an alternate universe without the
doctrine of equivalents, and see how easy it is to dispense with these
three alleged showstoppers.

Kyber-768 uses the ring ((\Z/q)[x]/(x^256+1))^(3x3). Kyber chooses
various matrix entries to be zero, but there's nothing in the patent
requiring the entries to be nonzero. Kyber _describes_ those matrices
differently, as vectors, but the plaintiff's lawyers will provide a
translation table from the operations on vectors to the identical
operations on matrices. What was the difficulty supposed to be here?

> 2. what "internal composition law" f on R satisfies the requisite "X_l * f(Y_l)
> - Y_I * f(X_I) has a small norm" property;

Again the doctrine of equivalents is the easiest approach, but let's
stick to the alternate universe and focus on the 3x3 matrix ring.

In a nutshell, the answer is the same as what I already gave for LPR: f
multiplies by some public random ring element. This is also what the
examples in the patent description do, with the small-norm difference
being uniformly 0. (Obviously whoever wrote the patent was trying to
state more generally what makes the system work.)

Presumably Dr. Peikert's objection here is to the patent notation in the
non-commutative case: the system doesn't work without transpositions, or
equivalently multiplying in a different order. The notation is sloppy
even in the commutative case: e.g., the patent sometimes has f taking
two inputs, as in "f(X_A,Y_A) = X_A.h + Y_A". But "Aha! The patent is
sloppy, and will be punished for this!" is wishful thinking, much like
"Aha! This NISTPQC submission is sloppy, and will be punished for this!"

What will actually happen is an initial hearing to establish the exact
meaning of, e.g., this "small norm" requirement. The defendant's lawyers
will propose definitions that try to make this sound as restrictive as
possible---but they'll run into the "X_A.h + Y_A" example stated for any
ring, and the court won't accept definitions that exclude this example.

The plaintiff's lawyers will propose a definition with the necessary
transpositions filled in, will explain that this is exactly what makes
the example work in the generality stated, and will pull out one example
after another from the math/physics literature where it was left to the
reader to fill in the "obvious" transpositions. I don't like this
notation, but I've seen it many times (even Sage will automatically
transpose sometimes!) and it's an easy winner in court.

> 3. how both entities A and B use the *same* f in computing P_A and P_B using
> the provided equations.

Let's again take the alternate universe, no doctrine of equivalents, and
see what happens with the 3x3 matrix ring.

The transpose-as-necessary approach will end up with f multiplying the
Alice inputs by a public random ring element h, and multiplying the Bob
inputs by the same h on the opposite side---equivalently, transposing
the Bob inputs, then multiplying by h transpose, then transposing back.

The objection here is that Alice's inputs aren't being handled by f the
same way as Bob's inputs, so f is no longer _one_ function, but rather
_two_ functions, and in our alternate universe this means we can't find
_one_ function f that brings Kyber within this patent claim! Game over!

But wait a minute. Is it actually two functions? Let's look at the input
matrices. Alice's inputs are 3x3 matrices of the form

a1 0 0
a2 0 0
a3 0 0

while Bob's inputs are 3x3 matrices of the form

b1 b2 b3
0 0 0
0 0 0

so we can simply define f to handle Alice's matrices in the Alice way,
and handle Bob's matrices in the Bob way, and return anything on the
overlapping inputs

c 0 0
0 0 0
0 0 0

which the plaintiff's lawyers will have an expert testify will never
actually occur in Kyber, so what's computed here is exactly what Kyber
computes. What was the difficulty supposed to be here?

---Dan

[D. J. Bernstein]

Andrea Basso writes:
> Now, the doctrine of equivalents cannot be applied here because of
> prosecution history estoppel. That means that if claims are amended
> during prosecution, the subject matter that has been excluded cannot
> then be covered by the doctrine of equivalents.

No. See _Festo v. Shoketsu_, 535 U.S. 722 (2002), where the Supreme
Court specifically rejected this view.

The usual situation where prosecution-history estoppel kicks in is that
a claim was amended _to avoid the prior art_, but that's not the
situation here, according to your description of the history. In other
situations, the patentee simply has to argue that the reason for the
amendment doesn't surrender the particular equivalent in question.

> the EU patent also does
> not cover SABER, mainly due to its reliance on LWR

Huh? The notation is different, and some numbers are described in a
different format (omitting some known-to-be-zero bits), but I don't see
how this is relevant to anything in the patent claim. Rounding f(Y_A) to
obtain S_A in a restricted set is simply a matter of choosing X_A
appropriately; nothing in the patent claim rules out this choice.

> Germany and Switzerland seem to require the replace features be
> obvious in light of the original patent

The bits I've read about the German analysis sound very different from
this, and are fairly close to the U.S. analysis, but I'll let someone
more familiar with German patent law comment.

---Dan

[Vadim Lyubashevsky]

Hi Dan, all,

On Sun, Dec 13, 2020 at 3:56 PM D. J. Bernstein <d...@cr.yp.to> wrote:

Vadim Lyubashevsky writes:
> Everything in this cryptosystem -- in particular
> the fact that all the secrets and errors have small norms -- matches
> except for the "belonging to the ring R" part.

Mathematically, I don't understand what distinction you're trying to
draw here. Simply zero-padding any vector or matrix produces a square
matrix, and matrix-vector multiplication is exactly multiplication in
the ring of square matrices. If the goal were to kill Claim 1 of the
2010 patent then it would be worth going through this in detail. (A
claim is invalidated by any example appearing in the prior art.) 

My analysis focused, however, on Claim 19 of the patent, matching it up
point by point to the subsequent LPR cryptosystem. Claim 19 uses a
_polynomial_ ring, making it much more efficient than the matrix case.
So the matrix cryptosystem you mention doesn't match Claim 19, and it's
worse in a way that a court will easily understand.

Sorry, I misunderstood that earlier you were referring to just LPR and not also to Kyber / Saber.  I don't really care about the actual LPR cryptosystem (e.g. as used in NewHope or NTRULPrime), and was always just talking about Kyber/Saber.  So let's just focus on those from now on.

Let's go back to the European Patent 2537284.  Just to understand, you're saying that Claim 19 (which specifies the polynomial ring to use) and Claim 1 (in which the ring could actually be interpreted as a matrix of ring elements), covers Kyber / Saber.  Let's ignore the inconsistency of Claim 19 being very specific with what the ring R is and then you changing the precise definition. So let's just look at claim 1. 

I agree that one could interpret Kyber/Saber as a cryptosystem with just matrix multiplication (where, for efficiency, one really wouldn't do matrix multiplication).  But that is not what claim 1 is doing! I know you already mentioned this, but I am going to restate one of the offending lines for clarity.   Reading lines 53 - 55 on page 17 "for any pair of elements X and Y of R, such that X and Y have a norm that is small relative to the elements f(X) and f(Y), then X.f(Y) - Y.f(X) has a small norm".  I guess you see that if f(X) is defined as MX, then for this to hold true, you would need  XMY - YMX to be close to 0, which would only happen if we have commutativity (and this is certainly not true for Kyber / Saber).  In your last email, you made a reference to something of this sort and said that it's wishful thinking to think that a patent will be punished for this.  Really?  Here is a pretty fun example.  Look at slide 9 of https://www.wipo.int/edocs/mdocs/aspac/en/wipo_ip_bkk_19/wipo_ip_bkk_19_p_3.pdf and a more detailed explanation of this here: http://www.waltmire.com/2016/11/08/burnt-dough-difficulties-patent-drafting/#:~:text=Chef%20lost%20when%20it%20sued,%2C%20Inc.%2C%20358%20F.)  So now, do you really think that "accidentally" implying commutativity will be forgiven? And this is on top of the fact that every single example of an instantiation (claims 19 -24) is a commutative ring.  I think that it's quite clear that there is no accident or typo here -- claim 1 is simply about commutative rings, and this is how the authors always meant it to be.  Your chain of events for how claim 1 can be made to fit Kyber / Saber sounds like the plaintiffs will allowed to rewrite their patent on the spot.  With the amount of changes your hypothetical court is allowing, I can avoid every possible patent by converting El Gamal to Kyber / Saber.

I initially wrote a bit more explaining how interpreting (and rewriting) claim 1 to include Kyber / Saber would also imply that it includes the TCC 2010 cryptosystem, and therefore the claim would be thrown out because it patents prior art, as you said ... and so the only hope of the claimants is to actually insist that the patent only covers commutative rings and then maybe (big maybe) they can have a case just against the NewHope-type schemes.  But I don't see how this matters anymore.  Kyber / Saber simply do not fit into claim 1 as written.  

Best,

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/20201213145628.246775.qmail%40cr.yp.to.

[Christopher J Peikert]

To elaborate and expand on Vadim's most recent comments and others from this thread, let's see how a case attempting to show that Kyber (or alternatively, SABER) infringes on the patent would likely play out.

The defendant would argue that the patent is invalid on account of prior art (among other reasons). This argument is straightforward: a "person skilled in the art" -- let's call this skilled person Skip -- could have easily used existing publications to come up with a system that is covered by the patent's claims, as follows:

1. Take the TCC'10 cryptosystem (say, the one presented at the conference).

2. Improve its efficiency by mechanically applying the "unstructured matrices -> polynomials" transformation detailed in Section 4.2 of Micciancio-Regev'08. (See previous messages for details.)

3. Show how the resulting system is covered by Claim 1 of the patent (this is obvious).

I see no reason to dispute this argument, and every reason to accept it. (Notably, there has not been any quarrel with any part of this argument in this thread. Also, Step 2 does not require Skip to demonstrate anything about the *security* of the resulting system; only the construction matters.)

In the likely event that the court accepts this argument, the patent is invalidated and the defendant wins, case closed.

But let's suppose, as a hypothetical, that the court does not accept the above argument. This would require it to conclude that Skip -- despite his skill in the art and the detailed instructions provided in MR'08 -- could *not* have easily performed the above steps. The court clearly does not think much of Skip's abilities! So, for the rest of the case we would have to treat them as very limited.

Next, the plaintiff would argue that Kyber infringes on the patent, perhaps using the argument Dan laid out.

Since Skip's skills are so limited, all the "doctrine of equivalents" parts of that argument are highly questionable -- if Skip can't even apply the explicit directions in MR'08, how can he see how to interchange all these other purportedly equivalent objects? But let's focus on another serious issue:

> 2. what "internal composition law" f on R satisfies the requisite "X_l * f(Y_l)

> - Y_I * f(X_I) has a small norm" property;

In a nutshell, the answer is the same as what I already gave for LPR: f
multiplies by some public random ring element. This is also what the
examples in the patent description do, with the small-norm difference
being uniformly 0. (Obviously whoever wrote the patent was trying to
state more generally what makes the system work.)

Presumably Dr. Peikert's objection here is to the patent notation in the
non-commutative case

The non-commutative case is indeed a major problem, but it's not just a matter of notation.

The court simply cannot accept Dan's argument that the patent is broad enough to cover non-commutative matrix rings, because the very same argument would also make the patent cover prior art like th