Public-key cryptosystems base their security on certain assumptions, one of these being that certain mathematical problems, while theoretically solvable, are computationally infeasible to solve. Typical examples are integer factorisation and the reverse logarithm problem which are used in cryptosystems such as RSA, DSA and Elgamal. For example, an attacker that had infinite processing power, memory and time, could derive a private key only by having a public key.
Quantum computers work with qubits instead of bits, which means that each bit could be in either 0, 1 or a superposition of these states simultaneously, in contrast to classical computers where each bit can only be in one state at a time. This leads to what is called quantum parallelism.
The real issue is to find how to utilise this parallelism to solve mathematical problems faster. Certain tasks, such as multiplication, cannot be performed much quicker by this kind of computer, while others, such as integer factorisation can. Algorithms such as Shor’s algorithm exploit the power of quantum parallelism to perform integer factorisation in exponentially less time than normal computers. For example factorising a 1024-digit number which would take billions of billions of years, with a quantum computer it could take 20 minutes. This means that cryptosystems such as RSA that rely on the computational infeasibility of breaking an integer into two primes will be considered obsolete if a quantum computer (that can handle such computation) is built.
For this reason, cryptographers are already researching what would happen in a post-quantum era and have been trying to find how to build public-key cryptosystems that rely on problems that cannot be solved by quantum computers any quicker that classical computers.
Finally, it should be stated that symmetric cryptography is thought not be affected so much by quantum computers. By using a quantum computer, Grover’s algorithm can make the search for a key quicker by needing the square root of the time of a normal brute-force search. This is significant, but it is suggested that simply doubling the key length is enough to mitigate the attack.