UPDATE: Graham recently contributed to this article in The Economist on Post-Quantum Cryptography.
Computers that exploit quantum mechanical properties offer the promise of (supposedly) unbreakable cryptography and other exciting applications, but they will also cause a huge, immediate problem: the day a large, practical quantum computer is developed, all existing widely-used asymmetric cryptography will be broken.
This will have serious consequences: massive amounts of secret information exchanged over the internet under public-key or hybrid cryptography could be revealed. Computers will no longer be able to ensure the updates they are downloading and installing are legitimate, since code signing will be broken. The owner of the first powerful quantum computer (which will probably be a large state organisation, who will keep it a secret) could have the power to take over almost every computer and mobile phone connected to the Internet. Even though nobody knows when this will occur, it makes sense to start preparing.
The solution is not quantum cryptography, but post-quantum cryptography: algorithms that run on classical computers now, and resist attack by future quantum computers. The trouble is, they don’t exist yet, or at least not in a practical form.
NIST has launched a competition to find and standardise practical quantum-resistant algorithms. The first round of the competition closed at a conference this April. Researchers around the world are racing to break and/or improve the submissions. You can see them all here – there is plenty of exotic and infrequently used mathematics being employed, like supersingular isogenies, lattices and quasi-cyclic codes.
In the end, unlike for previous NIST competitions such as that which fixed the standard algorithm for symmetric cryptography (the AES standard), there will be more than one winner. That’s because there are going to be some painful trade-offs around performance, size of key, size of ciphertext or signature, etc. that will mean difficult decisions for future application developers.
Meanwhile, large companies are already starting their post-quantum crypto migration, without waiting for the results. This is because the job is so huge: imagine you’re a big software company with more than 5000 applications. Every one of these applications employs cryptography in multiple ways, in some cases hidden in legacy libraries and components without up-to-date documentation. Finding each use, deciding what to replace it with and making the changes to the application is a huge undertaking. A good first step is to complete your cryptography map, finding out what is used and where, something which Cryptosense Analyzer can help you do.