Quantum leap: What will quantum computing mean for encryption?
Welcome to Threat Intel’s #WednesdayWisdom column, which aims to help improve your cyber security knowledge and keep you informed on important developments.
What do IBM, Google, Lockheed Martin, the National Security Agency, Microsoft, AT&T, Airbus, and Fujitsu have in common? They all want a piece of the quantum cake. All those companies, plus an ever-growing list of others, are delving into the fascinating world of quantum computing because they know that this strange, exciting, and often counter-intuitive field is set to change the world. From unraveling the complexities of molecular and chemical interactions to improving artificial intelligence, the possibilities are endless. We’re still some time away from creating quantum computers powerful enough to change the world, but it’s worth thinking about what impact they will eventually have on certain fields, such as cyber security, and, something as ubiquitous and important as encryption.
What is quantum computing?
The computers we use every day deal with bits, basic units of information that have two possible states: 1 or 0. Quantum computers, on the other hand, deal with qubits (also known as a quantum bits), and this is where things get a little crazy. Thanks to the mind-blowing world of quantum mechanics, qubits can be 1, 0, or both 1 and 0 at the same time (this is also known as quantum superposition). Multiple qubits also allow for the creation of what is known as entangled states. Wired’s Abigail Beall makes this a little easier to understand:
“A qubit can be thought of like an imaginary sphere. Whereas a classical bit can be in two states — at either of the two poles of the sphere — a qubit can be any point on the sphere. This means a computer using these bits can store a huge amount more information using less energy than a classical computer.”
There is also a difference in the way quantum computers perform computations. A useful analogy for this would be looking for a specific grain of sand on a beach. A classical computer will look at every grain of sand individually, albeit very quickly, in order to find the specific grain. Whereas a quantum computer will look at all grains simultaneously to find the one it’s looking for immediately.
What is quantum supremacy?
So quantum computers can, in theory, perform computations exponentially faster than today’s computers. But there’s a catch. For a quantum computer to be useful it needs to have many qubits, and it’s notoriously difficult to build a quantum computer with enough qubits to outperform classical computers.
The current record for the number of qubits in a quantum computer is 20 but the estimated number needed to supersede classical computers is roughly 50 qubits (D-Wave Systems has a 2,000 qubit computer but it uses something called quantum annealing, which limits the type of computations that the computer can be used for).
This 50 qubit milestone is known as quantum supremacy and, once it is reached, it is set to have grave implications for encryption.
How will quantum computing affect encryption?
Asymmetric, or public key, encryption works by creating two mathematically related keys, one that is publicly available and one that is confidential to its respective owners. Messages can be encrypted with the public key by anyone but those messages can only be decrypted by the person with the corresponding private key. Because of the way the keys are calculated, deducing the private key from the public key is unfeasible, even for today’s most powerful supercomputers. However, it would be a trivial task for a quantum computer that has reached quantum supremacy to break this encryption by cracking the mathematical problems used to calculate the keys.
Asymmetric encryption is used for everything from social media and messaging apps like WhatsApp to online payment systems and digital signatures. Once quantum supremacy is achieved security breaches will no longer be incidents that affect a few hundred thousand or even a million people, we will all be at risk. But don’t worry, it’s not all doom and gloom.
It’s estimated that quantum supremacy is anywhere from five to 10 years away but, even when it does occur, 50-plus qubit machines will cost millions of dollars. Powerful quantum computers will be out of the price range of most criminals for quite some time and it will likely be 20 to 30 years before you can buy one at PC World. Nevertheless, that’s not to say that criminals aren’t thinking ahead.
There are some experts that believe forward-thinking criminals are carrying out ‘harvest and decrypt’ schemes. This involves criminals gathering up encrypted data, by way of breaches for example, and hoarding it until a time when sufficiently powerful quantum computers are affordable. At that time, they will be able to decrypt the data, which could contain valuable information such as Social Security numbers, healthcare data, or government secrets. However, other experts believe that by the time quantum computers are obtainable by criminal data hoarders any information they have, at least in terms of government secrets, will be obsolete.
Are we all doomed?
Ironically, the very thing that is set to threaten encryption is also capable of providing a solution. Quantum key distribution has been referred to as an ‘unhackable’ communication method. This method involves sending a shared encryption key embedded in quantum entangled particles of light. Because they are entangled, if one particle is intercepted by someone attempting to eavesdrop on the communication, the key will be altered in both particles, making it useless. Yet another weird and wonderful quirk of quantum mechanics.
China has made huge advancements in this field, and recently successfully sent quantum encoded data more than 1,200km via a satellite relay. To date, this is the longest distance over which quantum key distribution has been performed. Previous efforts using fiber optics managed just over 300km. While quantum key distribution is set to revolutionize everyday encryption, it is not a silver bullet. End users and their devices will still be vulnerable to attackers who can swipe the decrypted data directly from the endpoint.
It should also be noted that the focus is on asymmetric, or public-key, algorithms, which are at a higher risk from quantum computers. Most symmetric cryptography is considered relatively secure from such attacks, especially if the key size is doubled.
Post-quantum cryptography may also help to keep our data safe when quantum supremacy arrives. Many cryptographers are hard at work designing new cryptographic algorithms that are hopefully secure against attacks using quantum computers. In fact, Google has already begun work on protecting its Chrome browser from the quantum computer threat by testing post-quantum cryptography in its experimental version of the browser known as Chrome Canary.
Update — August 25, 2017:
Michael J. Biercuk, Professor of Quantum Physics and Quantum Technology at the University of Sydney, has pointed out that 50 qubits would not be sufficient for cracking asymmetric encryption and that the number of qubits needed would be significantly higher.
Quantum computers can be built for either general purpose use or tailored for one particular purpose. A 50–100 qubit machine built to outperform a classical computer in a specific task would not have the computational power for useful factoring, i.e. cracking encryption. However, the estimated number of error-corrected qubits needed for useful factoring varies greatly.
I highly recommend Professor Biercuk’s article for an interesting look at how close (or far away) quantum computers really are from being able to crack encryption.
Check out the Security Response blog and follow Threat Intel on Twitter to keep up-to-date with the latest happenings in the world of threat intelligence and cybersecurity.
Like this story? Recommend it by hitting the heart button so others on Medium see it, and follow Threat Intel on Medium for more great content.
