A quantum of solace
Updated: Jul 12
Several questions on the recent Computer Security lecture, covered the knotty topic of Quantum Computing. A mystique seems to grown up around quantum computers -- can they solve problems that conventional computers cannot solve? The answer to seems to be a resounding "No". However quantum algorithms do seem to be more powerful than conventional ones for certain types of problem. One of the problematic algorithms is known as Shor's algorithm, which appears to allow integers to be factored using an algorithm that runs in polynomial time. So far, the largest integer that has been factored is 21, and current codes use integers that are powers of hundreds, so you can see why there is no immediate panic.
Howeve, it is true to say that if quantum computers become more than just tiny toys, there may well be a number of common cryptographic algorithms that become broken.
That said, symmetric key encryption schemes such as blowfish, DES and AES are resistant to attack (although longer keys might be needed). So the problem will be how to exchange keys in the first place, as the public key systems are crackable using powerful quantum computers. There are some promising signs that such a system is practical (via the Open Quantum Safe project for example).
The other critical observation is that quantum computers will be available to not just code breakers but code users too. And there is already a nice collection of algorithms vying for standardisation (see https://en.wikipedia.org/wiki/Post-quantum_cryptography for example).
So, for those of you worried that your Amazon account is about to be hacked by quantum criminals, I hope that provides a quantum of solace.