What security does Keccak offer against quantum attacks, specifically Grover's algorithm?

Question

In the face of non-quantum attacker, Keccak[r=1088,c=512] with 512 bits of output provides:

• Collision resistance up to $2^{256}$ operations
• Preimage resistance up to $2^{256}$ operations
• Second preimage resistance up to $2^{256}$ operations

In general however, using quantum computing, specifically Grover's Algorithm, hash functions can be attacked more efficiently. Daniel J. Bernstein wrote about quantum attacks against all the second round SHA-3 candidates. However, in that paper, all the attacks against Keccak variants are against truncated hashes with an internal capacity of twice the hash length, for example Keccak[r=1152,c=448] with 224 bits of output.

My question is, if the full 512 bit hash output length of Keccak[r=1088,c=512] is used, does this provide security up to $2^{256}$ operations against quantum attackers using Grover's algorithm, or is security limited to half of the preimage strength, that is, only $2^{128}$ operations?

If the question is trivial to answer, please feel free to speculate about the relevance or practicality of quantum attacks against hash functions or symmetric cryptographic primitives in general.

Answer 1

In short, the answer is yes, if the full 512 bit hash output length of Keccak[r=1088,c=512] is used, this provides security up to 2²⁵⁶ operations against Grover's quantum algorithm.

Using Grover's algorithm, one can find a preimage of a n-bit hash function in time 2^n/2 with a quantum computer. This is a generic attack in the sense that it applies to any n-bit hash function.

For the 256-bit output of Keccak[r=1088,c=512] (or, for that matter, any 256-bit hash function), the quantum attacker can apply Grover generically and find a preimage in time 2¹²⁸. Similarly, for the full 512-bit output of Keccak[r=1088,c=512], the quantum attacker can apply Grover generically and find a preimage in time 2²⁵⁶. However, Grover can also be applied to recover the c=512 hidden bits, but it provides no advantage: it will also cost time 2²⁵⁶.

In general, the attacker can choose between applying Grover generically or to apply it to find the c hidden bits, and he will choose the fastest option of course.

Answer 2

First, lets get some thing clear over here. The analysis of Grover's algorithm is asymptotic, so it is fairly unfair to perform something as concrete as the setting you have mentioned.
Grover's algorithm gives you an asymptotic upper bound of $O(\sqrt{N})$ for searching in an unsorted array of size $N$ so I have trouble understanding how one can claim that it will require $2^{512}$ operations. To me, from the point of view of analysis, it seems wrong analysis. What you should see is the constant factor in the Grover's algorithm and for that I will refer you to the original paper of Grover's algorithm and work out the mathematics there. You will see that it won't give you the number of operations to be $2^{512}$ for preimage resistance as well, rather it will give you a constant multiplied to it.

However, if you want to make an asymptotic analysis, you cannot have a particular instantiation of a hash function, rather you have to consider a family of hash functions. This is a common mistake people tend to do. In that case, all you know is that the upper bound is $O(\sqrt{N})$ and a lower bound is $\Omega(N^{1/3})$ by S. Aaronson's paper on Quantum lower bounds for the collision and the element distinctness problems.

Answer 3

No, it isn't a trivial question to answer but, I presume that you have read Peter Shor's article on polynomial time prime factorization and discrete logarithms using quantum computers? Essentially, many cryptographic constructs are based on the hardness of these two problems meaning that if they can be solved in polynomial time, then they are essentially broken.

Whether or not this applies to Keccak is another story, however, according to its specification, the expected success of any shortcut attack with a workload equivalent of N calls to KECCAK-f[r+c] or its inverse shall be less than or equal to $1-exp(-N(N+1)2^{-(c+1)})$. They do, however, exclude the weakness that KECCAK-f[r+c] can be described compactly, and executed efficiently.

Also, if you have a look at the Keddak sponge function family web site, it should provide you with the results of the latest cryptographic attacks against Keccak.