18
$\begingroup$

Simply put, if one were to build a quantum computing device with the power of, say, 20 qubits, could such a computer be used to make any kind of modern hashing algorithm useless?

Would it even be possible to harness the power of quantum computing in a traditional computing application?

$\endgroup$
  • $\begingroup$ Related but not duplicate question: cs.stackexchange.com/questions/356/… (Note so far we have no efficient algorithms for solving NP-hard problems with a quantum computer) $\endgroup$ – Ken Li Mar 21 '12 at 7:11
  • $\begingroup$ Can you point to the results that give you this suspicion? Why should quantum bits have any impact in this scenario? $\endgroup$ – Raphael Mar 21 '12 at 12:47
13
$\begingroup$

Quantum computers might have some advantage over classical computers for some cases. The most remarkable example is Shor's Algorithm which can factor a large number in polynomial time (while classically, the best known algorithm takes exponential time). This completely breaks schemes like RSA, based on the hardness of factorization.

This is not necessarily the case for hash functions. First, we need to define what it means to break a hash function. One way to break it is called pre-image attack: you give me hash value $v$, and I need to find a message $m$ such that $\operatorname{hash}(m)=v$. Another attack is the collision attack, in which you give me nothing, and I need to come up with two different messages $m_1, m_2$ that have the same hash $\operatorname{hash}(m_1)=\operatorname{hash}(m_2)$. This is easier than finding a preimage, since I'm not bound to the a specific $v$.

What can Quantum computers do? The main result is Grover's search algorithm: a method for a quantum computer to search in an unsorted database of size $N$ with time $O(\sqrt{N})$ (while classically it will take an expected time of $N/2$).

With Grover's algorithm, finding a preimage of a hash function whose output is $k$-bits takes $O(2^{k/2})$ time, rather than $O(2^k)$.

Is this a problem? Not necessarily. Hash functions are designed such that time $2^{k/2}$ is considered "safe" (in other words, the hash designers always double $k$). This is due to the Birthday paradox with which finding a collision is possible with time $O(2^{k/2})$ by a classical computer.

The nice thing about Grover's algorithm that it is optimal - every other quantum-algorithm to find an element in an unsorted database will run in time $\Omega(\sqrt{N})$.

Can quantum-computers perform better collision attacks? Actually I'm not sure about it. Grover's algorithm can be extended, such that if there are $t$ items (that is, preimages), the time to find one is reduced to $O(\sqrt{N/t})$. But this gives no collision - running the algorithm again might return the same preimage. On the other hand, if we choose $m_1$ at random, and then use Grover's Algorithm, it is probable that it will return a different message. I'm not sure if this gives better attacks.

(this answers the more general question, without restricting the computer to 20 qubits, which will not be enough to break the current 1024-bit hashes).

$\endgroup$
  • $\begingroup$ nitpick: The runtime of GNFS is sub-exponential. $\endgroup$ – CodesInChaos Jul 8 '15 at 21:10
1
$\begingroup$

From what I understand, quantum computing does have the power to easily break today's hashing algorithms. However, in the long run we will also be able to use more complex hashing algorithms, and generally it is easier to encrypt than decrypt something. I think the biggest issues to consider are when quantum computing is available only to a select few, giving them easy access to stuff protected by today's algorithms long before more advanced algorithms or even consciousness of the threat are widespread.

See here for an actually technical answer to the question on Stack Overflow.

$\endgroup$
  • 2
    $\begingroup$ AFAIK most symmetric crypto primitives will still be secure even when quantum computing becomes viable. It halves the effective block or key length in some scenarios, but crypto primitives with a current security level of 256 bits or more will still be secure, since work of the order of 128 bits is infeasible. Most asymmetric primitives currently in use will utterly break though. But not with just 20 qubits. You'll need several thousand qubits for that. $\endgroup$ – CodesInChaos Mar 21 '12 at 14:38

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.