19
$\begingroup$

Grover's algorithm can search an unordered list of length $N$ in time $\sqrt{N}$ on a quantum computer. Applied to cryptography, this means that it can recover n-bit keys and find preimages for n-bit hashes with a cost of $2^{n/2}$.

But the basic version of Grover's algorithm is sequential. Each iteration uses the output of the previous iteration as input. I don't see an obvious way to parallelize the algorithm. Reducing the number of iterations significantly reduces the success probability more than linearly.

If the algorithm is inherently sequential, building a bigger computer won't speed up the attack, limiting its impact. $2^{80}$ sequential cipher invocations looks pretty hard to achieve to me. On the other hand, $2^{80}$ parallel cipher invocations is already on the edge of feasibility today using classical computers.

Assume an attacker using a quantum computer is limited to $T$ timesteps with $T<\sqrt{N}$, so they can't run Grover's algorithm with the optimum number of sequential steps. What's the cost for finding a preimage/recovering a key? What is the average cost per-break if they have multiple targets?

$\endgroup$
4
  • $\begingroup$ I didn't dive deep enough to tell if this paper answers the question (Optimal Parallel Quantum Query Algorithms), but I found this interesting quote: "Suppose one wants to search an n-bit database, with the ability to do p queries in parallel in one time-step. An easy way to make use of this parallelism is to view the database as p databases of n/p bits each, and to run a separate copy of Grover’s algorithm on each of those." $\endgroup$
    – mikeazo
    Apr 22, 2015 at 16:37
  • $\begingroup$ It doesn't directly answer the question as you are not talking about doing p queries in parallel, but 1 query parallelized. $\endgroup$
    – mikeazo
    Apr 22, 2015 at 16:38
  • $\begingroup$ @mikeazo I think I was asking the wrong question. I've changed it a bit, to be closer to what matters for attacks on cryptography. $\endgroup$ Apr 22, 2015 at 19:53
  • $\begingroup$ On Quantum.SE: Can we speed up the Grover's Algorithm by running parallel processes? $\endgroup$
    – kelalaka
    Feb 5, 2021 at 22:56

2 Answers 2

7
$\begingroup$

This is an older question, but it's come up a couple times for me recently and I want add some clarification.

If you want to speed up Grover's algorithm, you can split the search space up into $k$ chunks and run independent searches on $k$ machines. Since your search space is $\frac {N} k$, each search will complete in $O(\sqrt{ \frac {N} k})$. You only get a square-root speedup because you're losing quantum parallelization when you split up the search space. A more detailed explanation of this can be found here.

The issue of parallelization is separate from that of multiple targets. Contrary to mephisto's answer, Grover's algorithm works just fine on a search space containing $k$ correct indices/inputs, provided you modify the number of iterations to $\frac {\pi} 4 \sqrt{\frac {N} k}$. When $k$ is unknown (as is often the case), you may need to employ some cleverness to keep it $O(\sqrt{\frac {N} k})$ (see section 4 of this paper). Importantly, $N$ does not need to be "kept small" to accommodate this. The main constraint on $N$ is the underlying hardware capability.

$\endgroup$
7
$\begingroup$

We recently discussed this question with some colleagues, and this is what we came up with (no guarantees):

Grover's algorithm only outputs a correct answer if it is fed with an input set such that the target function evaluates as 1 for a single input and as 0 otherwise. The algorithm then iterates a subroutine $\sqrt{N}$ times (where $N$ is the size of the input set) to push the amplitude of the input that evaluates as 1 up. That way, the correct input is measured with a high enough probability (sorry for being vague at this point).

To use Grover's algorithm to attack a hash function's preimage resistance, you select a random subset of inputs and hope that there is one input that is actually a preimage of the target value (I guess a small number of preimages should also be OK, as all their amplitudes should be pushed up and eventually one of these is measured). Now, the runtime of Grover's algorithm depends on the size of the input set $N$. So, we want to keep this $N$ small. On the other hand, we have to select $N$ such that with significant probability there is a preimage in this set. In general, it is assumed that we need to take $N$ in the order of the output size of the hash function to get this probability high enough.

If we want to parallelize this, it should work as follows. Assume we get a quantum computer with twice the number of qubits needed to run Grover with an input set of size $N$. In that case, we can run it on two input sets of size $N$ while still taking only time $\sqrt{N}$. However, the benefits are also only linear, the probability of finding a preimage (or rather the probability of finding an input set containing a preimage) is only doubled.

Of course, we could also run it with an input set of size $N^2$, increasing our success probability exponentially, but this also increases the runtime exponentially.

$\endgroup$
2
  • 2
    $\begingroup$ As it turns out, this was also described in a paper from 1997: arxiv.org/abs/quant-ph/9711070 $\endgroup$
    – mephisto
    Aug 15, 2015 at 21:04
  • $\begingroup$ Adding probabilities of events that are not mutually exclusive is likely wrong. I believe that if one QC can find a preimage this way with probability $p$, two QCs can do it at probability $1-(1-p)^2$. $\endgroup$
    – v6ak
    Jan 11, 2020 at 10:33

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.