Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
2  
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
add comment

1 Answer 1

up vote 17 down vote accepted

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

share|improve this answer
4  
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
1  
@Reid Apologies if I misunderstand, but shouldn't it be $O\left(2^{\frac{n}{2}}\right)$ for a preimage search on an $n$-bit random oracle? $O\left(\sqrt{n}\right)$ is the running time for a search on $n$ values in the output domain of the oracle. –  Stephen Touset Aug 1 '13 at 18:15
2  
@StephenTouset: Oops, you're right! When I wrote the time complexity, I was thinking $n$ was the number of possible outputs, i.e. $n = 2^k$ for some $k$, which would make $O(\sqrt{n})$ be correct. Fixed. –  Reid Aug 1 '13 at 18:21
1  
One could also write it $O(\sqrt{2^n})$. –  Paŭlo Ebermann Aug 2 '13 at 11:49
    
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 at 14:14
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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