I've been writing a very careful analysis of the cost of a hybrid attack
against Kyber-512. As part of this, I've been reviewing the security
claims made in the Kyber submission document regarding Kyber-512. I'm
filing this comment because
* I'm unable to verify and
* I'm able to disprove parts of
the submission's argument that Kyber-512 meets category 1, the minimum
security requirement in NIST's call for submissions, against the attacks
that were already described in the submission document.
Rules: Category 1 says that every attack "must require computational
resources comparable to or greater than those required for key search on
a block cipher with a 128-bit key (e.g. AES128)". This requirement must
be met in "_all_ metrics that NIST deems to be potentially relevant to
practical security". One of the metrics already mentioned in the call is
"classical gates"; NIST estimates that AES-128 key search uses about
2^143 "classical gates".
Consequently, to comply with the minimum security requirements, each
parameter set needs each known attack to use "comparable to or greater
than" 2^143 "classical gates", no matter what happens in other metrics
(such as security against quantum attacks, which I originally thought
was the point of post-quantum cryptography---silly me!).
Procedurally, NIST has stated "We're not going to kick out a scheme just
because they set their parameters wrong. ... We will respond to attacks
that contradict the claimed security strength category, but do not bring
the maturity of the scheme into question, by bumping the parameter set
down to a lower category, and potentially encouraging the submitter to
provide a higher security parameter set." It's obviously important here
whether parameters can survive in category 1---this makes the difference
between bumping the parameters down and eliminating them.
Attacks against Kyber-512: The starting issue here is already clear in
Table 4 in the submission document. The popular "Core-SVP" machinery for
claiming security levels, applied to Kyber-512, claims pre-quantum
security 2^112 against primal attacks (more precisely, 2^112.24 from
beta=385, evidently considering only multiples of 5; my recalculation
reaches 2^111.252 from beta=381 with the most popular formulation of
Core-SVP, or 2^111.544 from beta=382 with the second most popular) and
pre-quantum security 2^111 against dual attacks.
It's also clear how the submission document responds to this problem,
namely by disputing the accuracy of Core-SVP. Page 21 of the submission
document, under "Gates to break AES vs. core-SVP hardness", gives five
brief arguments that BKZ-beta, the main bottleneck in these attacks, is
much more expensive than claimed by Core-SVP. The document says "it
seems clear that in any actual implementation of an attack algorithm the
product of the cost of those items will exceed 2^30".
Multiplying 2^30 by 2^111 gives 2^141. Perhaps this is close enough to
count as "comparable" to 2^143. Note that this response does not claim
_any_ security margin (despite other provisions in the call about being
"conservative in assigning parameters to a given category"), so a
mistake at any point can easily be fatal to the conclusion.
The general structure of this response makes sense, but the details
don't. Two of the five stated arguments simply don't apply, and I don't
see how the other three arguments reach the claimed 2^30.
Inapplicable arguments: The submission document says that Core-SVP
ignores "the additional rounding noise (the LWR problem, see [13, 8]),
i.e. the deterministic, uniformly distributed noise introduced in
ciphertexts via the Compress_q function".
The document says, however, that the standard Kyber-512 attack uses 410
samples. That's a key-recovery attack, making the ciphertext rounding
irrelevant. Similarly, the reported Kyber-768/Kyber-1024 attacks are
key-recovery attacks. So this argument is incorrect.
The document also says that Core-SVP ignores "the cost of access into
exponentially large memory". This doesn't help Kyber-512 close the gap
to 2^143 "classical gates": "classical gates" ignore communication
Of course, real attacks can't simply ignore communication costs. For
example, counting "classical gates" allows memory-intensive operations
such as sorting in an essentially linear number of gates, whereas the
1981 Brent--Kung area-time theorem says that such operations have AT
exponent >=1.5. This Kyber-512 attack would be bottlenecked by access to
an insane amount of memory. However, if the attack doesn't have enough
"classical gates" then, according to the rules, Kyber-512 doesn't meet
Before the call for submissions, I objected to "craziness such as
unit-'time' access to massive storage arrays". I would love to see NIST
announcing that it no longer "deems" this debunked metric "potentially
relevant to practical security". But, unless and until NIST makes such
an announcement, it seems that---unfortunately---we have to consider the
consequences of the "classical gates" metric.
Other arguments: Having two of the five arguments disappear doesn't mean
that the "exceed 2^30" conclusion is wrong, so let's look at the other
three arguments. The document says that Core-SVP ignores
* "the (polynomial) number of calls to the SVP oracle that are
required to solve the MLWE problem";
* "the gate count required for one 'operation'"; and
* "additional cost of sieving with asymptotically subexponential
Regarding the first argument, the traditional estimate is that BKZ-beta
costs 8d times as much as SVP-beta, but https://eprint.iacr.org/2019/089
says its experiments are more than 4 times faster than this. Let's guess
an overall cost ratio close to 2^11 here. (Maybe a bit more or less,
depending on how many BKZ tours are really required.)
Regarding the second argument, https://eprint.iacr.org/2019/1161
estimates slightly more than 2^12 bit operations per near-neighbor
"operation". So, okay, we're up to 2^23, which might seem safely on the
path to 2^30, but this presumes that the third argument also works.
The third argument is alluding to the procedure that was used to obtain
the 2^(0.292 beta) formula for the number of "operations" in SVP-beta:
* There is an asymptotic analysis, under plausible heuristic
assumptions, concluding that the 2016 BDGL SVP-beta algorithm uses
(3/2+o(1))^(beta/2) "operations". Here 3/2+o(1) means something
that _converges_ to 3/2 as beta goes to infinity, but this says
nothing about any specific beta, such as beta=381. Note that the
same algorithm with the known "dimensions for free" speedups still
costs (3/2+o(1))^(beta/2), with a different o(1).
* There is an unjustifiable replacement of (3/2+o(1))^(beta/2) with
(3/2)^(beta/2). For example, this converts the "dimensions for
free" speedup factor into speedup factor 1, which is very wrong.
* There is a minor change from 3/2, which is around 2^0.5849625, down
to 2^0.584 = 2^(2*0.292). For example, for beta=381, this moves
(3/2)^(381/2), which is around 2^111.435, down to 2^111.252.
The issue is the middle step in this procedure, suppressing the o(1).
This fake math is sometimes supplemented with speculation that this is a
"lower bound", i.e., that the o(1) is nonnegative, i.e., that the actual
(3/2+o(1))^(beta/2) has "additional cost" beyond (3/2)^(beta/2). But why
shouldn't this o(1) be negative? Sure, the calculations in
and the more detailed calculations in https://eprint.iacr.org/2019/1161
show some increases beyond (3/2)^(beta/2), but why should we think that
these aren't outweighed by the known "dimensions for free" speedups?
Another part of the submission document claims that the "hidden
sub-exponential factor is known to be much greater than one in practice"
but this claim (1) mixes up the separate factors considered above---of
course the experimental timings see memory costs etc.---and (2) doesn't
account for "dimensions for free".
Summary: The Kyber documentation gives five brief arguments that its
security level is much higher than claimed by Core-SVP, and says "it
seems clear that in any actual implementation of an attack algorithm the
product of the cost of those items will exceed 2^30". However,
* one of the arguments (ciphertexts) is simply wrong for these Kyber
* another argument (memory) ignores the announced rules regarding
* a third argument (the o(1)) still lacks justification and could
easily end up _reducing_ Kyber's security, and
* the remaining two arguments aren't enough to rescue Kyber-512
One could try adding a further argument that Core-SVP is inaccurate in
its delta formula, but as far as I know all experiments are consistent
with the theory that this inaccuracy _overestimates_ security levels---
there's actually a high chance of success with noticeably smaller beta.
One can also object to the Core-SVP usage of "expected" norms of
secrets, but fixing this again looks bad for Kyber-512---none of the
secrets have fixed weights, so there's an unnecessarily wide range of
norms, which means that even smaller choices of beta frequently work.
Does the Kyber team continue to claim that Kyber-512 meets NIST's
minimum security requirements? If so, why?
Followup questions: The quotes above show that the proposal of Kyber-512
(and, more broadly, the Kyber submission's assignment of parameters to
security categories) relies on disputing the accuracy of Core-SVP---for
example, accounting for the number of SVP-beta calls in BKZ-beta, and
accounting for the cost of memory. There's a lot to be said for this
approach. Core-SVP is indisputably inaccurate, and it's very easy to
believe that the cost of memory makes known attacks against Kyber-512
more expensive than AES-128 key search, so Kyber-512 would qualify as
category 1 if NIST's rules weren't forcing consideration of an
However, given that the Kyber submission document handles Kyber-512 in
this way, I don't understand why other parts of the same document say
things like this:
We choose to ignore this polynomial factor, and rather evaluate only
the core SVP hardness, that is the cost of one call to an SVP oracle
in dimension b, which is clearly a pessimistic estimation (from the
defender's point of view). This approach to deriving a conservative
cost estimate for attacks against LWE-based cryptosystems was
introduced in [7, Sec. 6]. ...
We follow the approach of [7, Sec. 6] to obtain a conservative lower
bound on the performance of both sieving and enumeration for the
dimensions that are relevant for the cryptanalysis of Kyber. This
approach works in the RAM model, i.e., it assumes that access into
even exponentially large memory is free.
Does the submission in fact ignore these costs? If we "ignore this
polynomial factor" and assume that "access into even exponentially large
memory is free" and disregard the inapplicable ciphertext argument then
how does the submission rescue Kyber-512? If we _account_ for these
factors then how does the submission argue that the resulting higher
cost for sieving is a "lower bound" for enumeration, especially quantum
enumeration? (Never mind the more recent posting
mentioning an "overshoot" idea to reduce the enumeration exponent.)
This incoherence in the Kyber submission is problematic. It's too easy
for readers to see all of these descriptions of Kyber as supposedly
using "conservative" assignments of security levels, and to miss how
much Kyber-512 is on the bleeding edge. Consider, e.g., NIST IR 8240,
which complained that a submission was using "a cost model for lattice
attacks with higher complexity than many of the other lattice-based
candidates". This might sound like Kyber, which had inserted a factor
>2^30 into its cost model, most importantly a huge factor from "the cost
of access into exponentially large memory"---but, no, NIST was talking
about another submission and didn't note this aspect of Kyber.
Other submissions: I've been focusing on Kyber here, but there are other
submissions that have proposed parameters with Core-SVP claiming
security levels below 2^128. I think this is the complete list:
* NTRU: 2^106 for ntruhps2048509.
* Kyber: 2^111 for kyber512.
* NewHope: 2^112 for newhope512.
* SABER: 2^125 for lightsaber.
(The incentives here are a problem. There are many reasons to think that
the efficiency of bleeding-edge parameters will attract attention and
reward the submission as a whole, while complaints about security will
at worst have _those parameters_ removed, according to NIST's rules. The
crude pixelation of security levels into five categories also distracts
attention from serious efforts to show efficiency-security tradeoffs.)
The presentations of these parameters differ. NTRU is clear in labeling
ntruhps2048509 as category 1 _only if_ costs of memory access are added.
Kyber, NewHope, and SABER have blanket claims of category 1. Kyber and
NewHope both repeatedly claim "conservative" evaluations of security but
don't actually use those evaluations in assigning security categories.
Kyber ciphertext size jumps by 48% if these parameters are eliminated.
NewHope ciphertext size jumps by 97%. SABER ciphertext size jumps by
48%, although the 2^125 for lightsaber is quite a bit larger than the
2^111 for kyber512 and the 2^112 for newhope512, so maybe this jump
isn't needed. NTRU has a denser parameter space and suffers less from
having ntruhps2048509 removed.
The next step up as measured by Core-SVP is NTRU Prime, specifically
2^129 for sntrup653 and 2^130 for ntrulpr653. NTRU Prime disputes the
Core-SVP accuracy in much more detail than the other submissions. Like
NTRU, NTRU Prime defines replacement metrics to take memory access into
account for assigning categories, and has a dense parameter space;
unlike NTRU, NTRU Prime avoids proposing any bleeding-edge parameters.
The Core-SVP list continues with 131 for round5n10d, 133 for round5n15d,
136 for ntruhrss701, 145 for ntruhps2048677, 146 for round5n1, 147 for
lac128, 148 for frodo640, 153 for sntrup761, 154 for babybear, 155 for
ntrulpr761, etc. Each step up here makes it harder to imagine that the
standard attack uses fewer "classical gates" than AES-128 key search:
there would need to be more and more severe inaccuracies in Core-SVP.