Could quantum computing eventually be used to make modern day hashing trivial to break?

Problem Detail: 

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?

Asked By : nicatronTg

Answered By : Ran G.

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).}

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/586