What I have been missing from all articles about this topic is an actual explanation what the primary technical criticism is all about. So I've skimmed djb's blog post about the issue and what he's arguing about the complexity is the following:
According to djb, the analysis of Kyber512 done by NIST argues the following:
- It will likely take 2^95 iterations for an attack on the algorithm to succeed.
- There are 2^25 bit operations (calculations) required per iteration.
- There are 2^35 memory accesses required per iteration.
- Hence there are 2^(95 + 25 + 35) = 2^155 operations required to attack the algorithm. (According to NIST.)
djb points out that this is very misleading, since the total amount of time a single iteration takes is not 2^25 * 2^35 (=2^60), but instead something like 2^25 + 2^35 (which is just a little more than 2^35), so you'll get a total complexity of 2^95 * 2^35 = 2^(95 + 35) = 2^130. (And NIST is themselves targetting 2^140 operations for their new standard.)
I haven't looked at the original NIST document analyzing Kyber512 to see if djb's claim about what they're arguing is indeed an accurate representation, but if djb isn't misunderstanding and/or misrepresenting the analysis in the original NIST document (i.e. the bullet points I provided here are indeed what NIST is using to calculate the attack complexity), then this is a huge blunder (and one has to wonder whether this is intentional), because djb is 100% correct that this is a mistake that nobody with even just an undergrad degree in CS should be able to make, let alone somebody's job it is to analyze crypto algorithms.
And while I have not read the original analysis by NIST, I tend to believe djb here, because if djb had simply misunderstood the NIST analysis and the bullet points above are not what the analysis is using to estimate attack complexity, then the person at NIST responding to this could easily refute that, instead of some BS such as It’s a question for which there isn’t scientific certainty and intelligent people can have different views.
Sure, there are certainly areas where intelligent people can reasonable disagree about things (for example in how high the threshold for security should be set for the future), but in this case? NIST's analysis is either correct when it comes to the possible attack complexity, or it isn't, and that shouldn't be a matter of debate.