6
$\begingroup$

I just stumbled onto a series of 2017 papers about applying the Ambainis quantum collision-finding algorithm to hash functions. (disclaimer: I haven't read all of them in full yet):


From the latter:

From similar techniques [to Grover's], quantum collision search is known to attain $O(2^{n/3})$ query complexity, compared to the classical $O(2^{n/2})$. ... Our algorithm is the first to propose a time complexity that improves upon $O(2^{n/2})$, in a simple setting with a single processor.


My questions: can someone who's been following this research discuss:

  1. Implications of this for security practitioners ... will we need to triple hash lengths instead of doubling them?
  2. Is this family of quantum collision-finding attacks only effective against the sponge construction and SHA-3, or does it apply to hash functions more broadly?

Related questions that were asked and answered prior to these 2017 papers:

$\endgroup$
7
  • 2
    $\begingroup$ As far as I can tell, there's no evidence that these actually attains asymptotically better than $O(2^{n/2})$ cost in any realistic models of cost (even assuming the unrealistic premise that a qubit and a qubit operation cost the same as a bit and a bit operation), and all the quantum ones actually scale worse in cost than the best classical one, the van Oorschot–Wiener machine. $\endgroup$ Commented May 22, 2018 at 15:36
  • 1
    $\begingroup$ Note that if you were already concerned about classical attacks costing up to $2^c$, you needed to use $2c$-bit hashes already; even if the quantum scaling were $O(2^{n/3})$, you would only need $3c/2$-bit hashes, not $3c$-bit hashes. $\endgroup$ Commented May 22, 2018 at 15:38
  • $\begingroup$ Some discussion: blog.cr.yp.to/20171017-collisions.html $\endgroup$ Commented May 22, 2018 at 15:40
  • $\begingroup$ I'm missing something about $3c/2$ not $3c$ .. ? $\endgroup$ Commented May 22, 2018 at 15:40
  • 1
    $\begingroup$ Also the paper you quoted from quotes the relevant paper by Bernstein directly afterwards which essentially says that the $O(2^{n/3})$ complexity / cost is unrealistic. $\endgroup$
    – SEJPM
    Commented May 22, 2018 at 16:31

1 Answer 1

4
$\begingroup$

The query complexity, i.e. the number of times the machine evaluates the function as a black box, may be $O(2^{n/3})$, but that's not the only cost of an algorithm: the size of the machine and how long you have to run it figure in too.

So far, there are no implications of quantum algorithms for security parameters of collision-resistant hash functions. Classical algorithms are still the cheapest algorithms for generic collision-finding, and would remain so even if Grover-capable quantum computers had the decency to merely exist.

The original Brassard–Høyer–Tapp algorithm[1] precomputes $H(x_1), H(x_2), \dots, H(x_{2^{n/3}})$ and stores them in a table $C$; then it applies Grover to find a preimage of 1 under the function $f(y) = [H(y) \in C]$, which reveals a collision in $H$.

Even if the communication costs for table lookup were zero (which seems unrealistic), this costs $O(2^{n/3})$ space, and the algorithm is expected to take $O(2^{n/3})$ oracle evaluations before finding a preimage under $f$ of 1, for a total of $O(2^{n/3})$ evaluations of $H$, and a total area*time cost of $O(2^{2n/3})$—far greater than the $O(2^{n/2})$ area*time cost of standard classical algorithms like the van Oorschot and Wiener collision search algorithm based on parallel $\rho$[2].

Variants of the algorithm have been proposed, but so far none of them has beaten the $O(2^{n/2})$ cost of the best classical algorithms in any plausible cost model even if qubit operations are no more expensive than bit operations—and most of them are much more expensive in any plausible cost model[3]. See here for an overview of some of the proposed algorithms and of problems in the cost models, and for broader context.

The Ambainis algorithm[4] takes a slightly different approach of a quantum random walk to find a repetition if there is one among a sequence of $M$ elements in $O(M^{2/3})$ time, which can be converted to an algorithm for finding a collision in an $m$-bit-to-$n$-bit function in $O(2^{m/3})$ queries. But it also requires maintaining a data structure holding all $O(M^{2/3})$ queries throughout the algorithm. So the area*time cost for a collision search based on it is $O(2^{2m/3})$, which remains far beyond the $O(2^{n/2})$ cost of classical collision search for any input size $m$ that gives a collision in $n$-bit outputs with nonnegligible probability. What Czajkowski et al. describe[5] is a generic way to apply it to a sponge with $c$-bit capacity producing an $n$-bit output costing $O(\min\{2^{2c/3}, 2^{2n/3}\})$, which is essentially what you would expect.

And since the query complexity of a generic quantum collision search has a lower bound[6] of $\Omega((2^n/r)^{1/3})$ if $r$ is an upper bound on the number of colliding preimages, unless there are dramatic breakthroughs in storage costs it seems unlikely that this situation will change any time soon.

$\endgroup$
1
  • $\begingroup$ So the complexity for breaking a hash function's collision resistance is greater than $O(n^{1/3})$? $O(n^{1/3})$ would mean that the bit-equivalent collision resistance of a hash function is at most $n/3$ instead of $n/2$, right? If so, is it possible that there exists a quantum algorithm faster than BHT that could reduce it further to like $n/4$? $\endgroup$
    – Melab
    Commented Jul 26, 2023 at 19:03

Your Answer

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

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