Every so often I’ll see someone trying scare people into believing that quantum computing will bring an end to privacy. The truth is quantum computing is simply the natural advancement of computing technology and cryptographers will take this into account when designing new cryptographic schemata. However, the true issue at hand is the use of protocols that are inflexible to where it is non-trivial to use updated cryptographic schemata. I will explain why here, and why it’s not the end of the world.
On Symmetric Algorithms
I have seen cases when someone would claim that quantum computing will be able to break a 256 bit AES key in an instant. This is simply not true. The advantage that quantum computing brings is that computers will be able to run more algorithms, some that will have run times much faster in relative the size of the input data versus algorithms that can be run on conventional computers. This means that individual mathematical operations will be faster on a quantum computer. This does not make a huge impact on symmetric cryptographic algorithms like AES.
Symmetric algorithms derive their strength from repetition. Operations in a symmetric algorithm have very little relation to at least one of either the key, the plain-text, or the cipher-text. This means that methods to break strong symmetric algorithms are often described as requiring more time than the age of the Universe and more memory than the capacity of all hard drives on earth, usually by several orders of magnitude.
Accelerating individual operations does not change this. Some aspects of quantum computing can solve the issue of the amount of memory required, but quantum computers are not able to handle algorithms that have long run times. Quantum computers are probabilistic machines. Information in a quantum computer degrades over time, so the longer the run time, the weaker the relation between input and output.
On Asymmetric Algorithms
The quantum algorithm that I have seen most commonly referenced in media is Shor’s Algorithm. Shor’s Algorithm is a fast method of factoring large numbers. This is significant in that it does produce a method of attacking the commonly used RSA encryption much faster than is possible with conventional computation. Right now it is very common for RSA to be used with 1024 bit keys. Those 1024 bit keys are really just one big number that happens to be the product of two prime numbers. Once those prime numbers are found the key is broken.
Shor’s Algorithm requires a quantum computer with two times more qubits than the number of bits in the number to be factored. At this time, a company called D-Wave claims to be in production of a 512 qubit computer. Other claims indicate that the NSA has one and will use it to predict the future. Marketing nonsense and insanity aside, we can assume the computer is real. A 512 qubit computer does not break modern cryptography, but it does break cryptography that should have stopped being used 5 to 10 years ago. More importantly is when a 2048 qubit computer is made available. Something of that calabure will be able to break the majority of cryptography used on the internet today and, as things are progressing, this will likely happen in 2014 or 2015.
I know it sounds grim, but this has happened before.
Up until 1996 there were strict laws in place in the U.S.A. that restricted the level of security that any cryptographic algorithm exported from the U.S. may have. In theory this was to prevent enemies of the U.S. from acquiring cryptography that is too difficult for U.S. intelligence agencies to decipher. In practice it only prevented U.S. citizens from acquiring strong cryptography.
The most commonly used encryption protocol is SSL. SSL describes how two computers that want to communicate with each other should decide upon mutually compatible methods for forming a shared secret key, for authentication, for encryption, and how to transmit encrypted message across the internet. The security of SSL is very implementation dependent. SSL includes code for strong encryption that was written outside of the U.S.A., and because of this it is not subject to U.S. export law when used outside the U.S. However, U.S. law ironically prevented a full spec version of SSL from being distributed to U.S. citizens. A separate version had to be distributed within the U.S. with a key length limit of 40 bits. To put that into perspective the complexity of breaking an ideal cipher should increase by a factor of two for every additional key bit. DES a symmetric encryption algorithm used in those days has a key size of 56 bits. By 1992 DES was already proven broken, and by 1997 a message encrypted using DES had been publicly deciphered.
Those were bad times for cryptography, but the world still turns.
Why it’s all irrelevant
If you’re like most people, and most people are, then your greatest need for encryption will be whenever you log into a web site or make online orders. Someone with a 2048 qubit quantum computer would definitely be a concern to you, but that’s not really you only concern. The type of online activities will require the use of SSL, and even a proper, strong, modern version of SSL still has the weakness of requiring a certificate authority to affirm that the computer that your computer talks to is owned by who it says it’s owned by. What this means is that ever since the early days of the use of SSL anyone sufficiently good enough at lying could get a certificate from a certificate authority in the name of your bank. Then, if they can intercept internet traffic between you and your bank, they would be able to impersonate your bank in a very convincing manner and read your log-in information once you send it.
The only way that quantum computers changes this is that, rather than asking one of many CAs for a new certificate for a cost of about $100, someone could buy a quantum computer for millions of dollars to break and use existing certificates. Also, keep in mind that some CAs have had a history of not doing enough to verify the identity of the people requesting certificates.
What we can do today
As a temporary patch, existing authentication and encryption methods can still be used a couple more years by extending the keys used. A 16Kibit RSA key can be generated in just a few minutes and should be strong enough to be unbreakable until 2018 to 2020. However, there is an issue here where some implementations of SSL are not able to handle very large keys.
To address SSL’s limitation in its authentication there are a few projects to extend it. Such extensions will still have there limitations, so I can’t recommend one, but it’s not hard to improve upon a system where the weakest link in a chain will be attacked.
The attack against SSL I described is called a “man in the middle(mitm)” attack. To learn more about this and others and ways to protect yourself I recommend educational material like Hak5.
For private communications I recommend not deferring to a third party for encryption and authentication. Any certificate authority will be subject to social engineering, and may not use keys of sufficient strength. For private communications I recommend applications like GNU Privacy Guard that let you handle the authentication directly and update your keys as needed.
What is being done to address quantum computing directly
Quantum computing does not magically solve all math problems. Smart mathematicians are working on a few candidates to replace the RSA/DSA/ECC algorithms used today. One of the candidates that is considered to be the most promising is NTRU. NTRU is a form of lattice-based cryptography. Even in light of the known abilities of a quantum computer, lattice-based problems are described as being moderately hard to very hard. That’s “very hard” as in it can’t be solved before our Sun blows up unless you find an easier way to solve it.
Laws restricting cryptography in western countries are much fairer now, and with AES we have symmetric encryption that will easily last the next few decades and we already know enough about the weaknesses of AES to begin replacing it. Soon, once we have a method of key exchange and authentication that can stand against quantum computing, thee of the four fundamentals of cryptography will be strong.