# What security do Cryptographic Sponges offer against generic quantum attacks?

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?

-

Unless Keccak has structural weaknesses that I am not aware of, the answer is surprisingly neither 128 nor 256!

Gilles Brassard, Peter Høyer and Alain Tapp describe a sort of quantum birthday attack in their paper "Quantum Cryptanalysis of Hash and Claw-Free Functions" that effectively works by creating a table of size $\sqrt[3]{2^b}$ (versus the $\sqrt{2^b}$ for the classic birthday attack) and then utilizes Grover's algorithm to find a collision.

While the classic birthday attack thus requires ${\mathcal O}\left(\sqrt{2^b}\right)$ time and memory, the quantum birthday attack only requires ${\mathcal O}\left(\sqrt[3]{2^b}\right)$ time and memory.

This means that to provide a $b$ bit security level against quantum adversaries, a hash function must provide at least a $3b$ bit output.

In your case of 512 bit Keccak, your security level would be $170\frac{2}{3}$.

-
Now that is interesting! – Reid Sep 24 '13 at 16:02
Switching accepted answers as this is new information that changes the answer. – Nakedible Feb 10 '14 at 6:12

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 2256 operations against Grover's quantum algorithm.

Using Grover's algorithm, one can find a preimage of a n-bit hash function in time 2n/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 2128. 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 2256. However, Grover can also be applied to recover the c=512 hidden bits, but it provides no advantage: it will also cost time 2256.

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.

-
That is exactly what I thought, but wanted confirmation that I'm not missing some crucial tidbit why it wouldn't be so. Thank you! – Nakedible Aug 17 '11 at 20:26

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.

-

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.

-
Actually, I was mostly looking an answer that would be a generic attack against Keccak (or actually, against any sponge function built with a permutation), not for a quantum attack that would utilize the structure of the actual Keccak permutation. – Nakedible Aug 17 '11 at 20:30