Quantum computing uses the laws of quantum mechanics to vastly accelerate work considered computationally very expensive for traditional computers. It operates at the subatomic level, using things like entanglement and superposition to communicate and process information. My prediction for 2016 is that a quantum computer will be used to successfully crack 40-bit encryption, a feat first accomplished in 1997 using what’s now considered ancient hardware. Quantum computing threatens cryptography that is at the very bedrock of today’s Internet. From banks and financial institutions, government and corporate security, all the way to digital signatures of the root zone of the Internet, everyone is at risk. Once perfected, it would be trivially easy to break all of it.
While I will leave the deep mathematics of the cryptography as an exercise for the reader, the principle behind these now vulnerable encryption methods was sound. It boils down to the complexity of factoring a very large semiprime number into its primes. When you know the primes (these compose the private key) it’s easy to decrypt the message, but if you don’t, it’s very hard. MIT announced recently it has been able to factor the number 15 into 3×5 using a quantum computer with 5 atoms in superposition, or quantumly entangled. This was first accomplished in 2001, so at face value, it doesn’t seem like much progress has been made in the last 15 years. But when the NSA starts sending out memos outlining their plans to transition away from the current standards to quantum resistant algorithms, it raises more than a few eyebrows.
So what can we do? There are some algorithms that are currently not well suited for cracking by a quantum computer, but oftentimes there are serious tradeoffs to consider. For example, with the McEliece family of algorithms, the key is a lattice that’s typically around 500KB. That is a substantial overhead compared to the couple of kilobytes needed today. Some devices with limited storage might not even be capable of using it. It certainly could not be used to validate a 100 byte DNS message. For things like that there’s still life in the current encryption methods by rolling your keys fast enough, and perhaps make life more difficult for the attackers by creating new session keys throughout the SSL connection. It wouldn’t stop later decryption if the entire communication was captured, but it would help mitigate man-in-the-middle attacks.
Quantum computing itself may hold the key to future security and privacy. If quantum algorithms can be developed, it would practically be considered magic. The whole notion of quantum entanglement, in which two particles are entangled, works at a distance, in what Einstein called “spooky” physics. Not only could this immensely speed up network communication, it would be impossible to eavesdrop on, and you would know if it were somehow tampered with.
Quantum networks are probably years away. If a quantum computer manages to break 40-bit encryption this year, it will be more than a proof of concept. It will mean the game is over. They have overcome the challenges that has been holding it back for the past 15 years. With the NSA and NASA heralding their plans for a post-quantum cryptography world, I suspect it has already been done. Now they just need to announce it.