33
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 6
    $\begingroup$ 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. $\endgroup$
    – Thomas
    Aug 1, 2013 at 13:25

1 Answer 1

Reset to default
37
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 9
    $\begingroup$ 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. $\endgroup$
    – Samuel Neves
    Aug 1, 2013 at 15:03
  • $\begingroup$ 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 $\endgroup$
    – Cryptographeur
    Feb 4, 2014 at 14:14
  • 1
    $\begingroup$ @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. $\endgroup$
    – Reid
    Feb 4, 2014 at 14:40
  • 1
    $\begingroup$ Cheers - will have a look this evening. In that case, may I suggest you mention that even more significant fact in your answer :) $\endgroup$
    – Cryptographeur
    Feb 4, 2014 at 14:41
  • $\begingroup$ First known record of a quantum Turing machine, given by David Deutsch in 1984 (published in 1985). people.eecs.berkeley.edu/~christos/classics/… $\endgroup$
    – floor cat
    Apr 20, 2017 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.