I apologize in advance for going all “Big Bang Theory” in this post but I think that the science behind this story is important in order to understand its relevance. If anything please keep reading to see if you can guess why the picture accompanying this post is of the video game character Q*bert and the actor Pauly Shore.
In a paper published in the Journal Science, a group of MIT and University of Innsbruck researchers designed a scalable quantum computer. The quantum computer was able to factor the number 15 using 5 qubits and laser pulses. Why is this important and what does it have to do with cryptography?
A qubit, or quantum bit, is a unit of information in quantum computing. Whereas in classical computers a bit is characterized by either a 0 or a 1, a qubit can be a 0, a 1 or both. Well not really both but something in between 0 and 1 based on superposition or wave propagation in quantum mechanics. A good analogy is a coin which is either heads or a tails in a classical computer but in quantum computing could be heads, tails or any angle as it spins on the table before dropping. Since qubits can exist in multiple states simultaneously, quantum computing has the potential to solve very difficult problems much faster than classical computers. I could go into it in more detail but I think you would close this window.
One difficult problem that quantum computers can solve is factoring large numbers into primes, which is the basis of public key cryptography. In public key cryptography the public key is known to everyone and is used for encryption while the private key is kept secret and is used for decryption. Both keys are based on the same two prime numbers. If a hacker can retrieve the prime numbers by factoring the public key it would be possible to determine the private key and decrypt the message.
In 1994 Peter Shor developed a quantum algorithm to calculate the prime factor of large numbers and thereby paved the way for a quantum computer-enabled hacker to retrieve a private key. There have been others that have used Shor’s Algorithm in quantum systems to factor numbers. What makes the MIT study so important is that they implemented Shor’s Algorithm with only 5 qubits and that the system is scalable. This creates the potential to use the same design to factor much larger numbers and break modern cryptography.
At the end of last year the NSA announced that they were transitioning away from Suite B algorithms for classified and unclassified systems. This was odd considering the effort and expense many manufacturers had undergone to implement Suite B. Here is the reason they gave in the announcement. “Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, which has made it clear that elliptic curve cryptography is not the long term solution many once hoped it would be….We look forward to your continued support as we work together to improve information security for National Security customers against the threat of a quantum computer being developed.”
I like how the NSA uses the term “the threat of a quantum computer” as if it is Godzilla coming out of the sea to destroy our major cities. Quantum computers may break public key cryptography but they will also herald quantum cryptography which will allow amazing things like preventing man in the middle attacks.
If you are concerned and would like to do something to protect mission critical systems TELEGRID would recommend incorporating quantum-resistant cryptographic techniques. For instance, symmetric key cryptography has thus far been proven to be quantum resistant and when used alongside public key cryptography can create a defense in depth strategy. Another idea is to increase key sizes in order to make it more difficult to factor your public keys.
The next wave of quantum computing will be very exciting for cryptography and the MIT report shows that it is much closer than we think.
Eric Sharret is Vice President of Business Development at TELEGRID.
Disclaimer: The opinions expressed here do not represent those of TELEGRID Technologies, Inc. TELEGRID Technologies, Inc. will not be liable for any errors, omissions, or delays in this information or any losses, injuries, or damages arising from its display or use. All information is provided on an as-is basis.