11
$\begingroup$

Using a quantum computer, Grover's algorithm can search an unordered list of length $N$ in time $\sqrt{N}$. Applied to cryptography this means that it can recover $n$ bit keys and find preimages for $n$ bit hashes with cost $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 at 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$
  • $\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 '15 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 '15 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$ – CodesInChaos Apr 22 '15 at 19:53
5
$\begingroup$

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

Grovers algorithm only outputs a correct answer if it is feed with a 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 high enough probability (sorry for being vague at this point).

To use Grovers algorithm to attack a hash functions 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 Grovers 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 to find a preimage (or rather the probability to find an input set which contains 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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