# What exactly is the base for the KECCAK (SHA3) claim that a security strength of 256 bits is “post-quantum sufficient”?

On page 14 of "Keccak and the SHA-3 Standardization" (February 6, 2013) it says:

• Instantiation of a sponge function
• the permutation KECCAK-f
• 7 permutations: b → {25,50,100,200,400,800,1600}
• Security-speed trade-offs using the same permutation, e.g.,
• SHA-3 instance: r = 1088 and c = 512
• permutation width: 1600
• security strength 256: post-quantum sufficient
• Lightweight instance: r = 40 and c = 160
• permutation width: 200
• security strength 80: same as SHA-1

(note: emphasis mine)

Since I regard quantum cryptography to be currently walking in it's child-shoes, with a high potential of evolving substantially during the upcoming years, I just have to ask: What exactly is the base for the KECCAK claim that a security strength of 256 bits is "post-quantum sufficient"?

-
I guess they meant "post-quantum sufficient with our immediate understanding of quantum technology", which, when you think of it, is pretty reasonable, contrasted with how classical algorithms are deemed "secure" when they really are "secure against current known cryptanalytic techniques". But it's hard not to speculate when it comes to quantum cryptography - nobody knows for sure, and nobody is using quantum crypto anyway, so it looks good to add that to the list. I suppose that was the rationale, anyway. –  Thomas Aug 1 '13 at 13:25

Well, cryptographers have been contemplating a post-quantum world for some time now.

Quantum computing, although in its infancy as far as real-life computers go, has been studied in a theoretical sense for a quite a while. Shor's algorithm was published 19 years ago; Grover's, 17 years ago. These are the two most-famous quantum algorithms, I think, but the field goes back further than that: according to Wikipedia, the field was born somewhere in the 1980s.

The point is that even though quantum computing hasn't produced a usable, useful real-life quantum computer yet, it has been considered for quite a long while now. So while huge breakthroughs are still very possible, it's likely that researchers have exhausted all of the easy lines of attack. Further, since it doesn't seem that in the last 16 years any new, cryptography-threatening quantum attacks have surfaced (at least, none that I am aware of), it seems relatively safe to talk about post-quantum strength.

More to the point, the real threat against hash functions in a post-quantum world would be Grover's algorithm. Using Grover's algorithm, mounting a brute-force preimage search on an $n$-bit random oracle has time $O\left(2^{n/2}\right)$.

Although direct application of asymptotic bounds is rather imprecise, this would lead to a preimage attack in time $2^{128}$ for a 256-bit (preimage-resistant) hash function. This is still secure, and I think this is what the authors were intending when they said "post-quantum sufficient." For more information, see the question What security does Keccak offer against quantum attacks, specifically Grover's algorithm?.

-
It is also worth noting that both the Grover and Brassard-Hoyer-Tapp algorithms for quantum search and collision finding are essentially optimal, i.e., they match the asymptotic known lower-bounds. –  Samuel Neves Aug 1 '13 at 15:03
Following your own link, I was under the impression resistance was $n/3$ bit to what is basically a quantum birthday attack? Your answer implies $n/2$ bit security –  figlesquidge Feb 4 '14 at 14:14
@figlesquidge: See this paper by Bernstein, particularly the third page. In it, he argues that the BHT quantum algorithm for collision-finding will cost more than Grover's. All thanks goes to nightcracker, who provided me this citation about a month ago. –  Reid Feb 4 '14 at 14:40
Cheers - will have a look this evening. In that case, may I suggest you mention that even more significant fact in your answer :) –  figlesquidge Feb 4 '14 at 14:41