Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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).
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.
