So if—and when—researchers build a quantum computer that can carry out Shor’s algorithm, is encryption dead?
All hope is not lost, thanks to two developments: quantum cryptography and post-quantum encryption.
The quantum world has additional tricks up its sleeve, in addition to superposition and entanglement, that can provide protections against code-breaking abilities.
In the 1920s, physicist Werner Heisenberg showed that it’s impossible to fully measure anything, such as an atom, with complete precision. When you measure a property in an atom, such as position, you disturb it and sacrifice the precision with which you can measure a complementary property, such as its momentum—its velocity multiplied by its mass.
A famous joke has a police officer pulling over Heisenberg in his car for a traffic stop. The officer says, “Do you know how fast you were going?” Heisenberg replies, “No, but I know where I am.”
But the uncertainty principle is not only about limits in precision. Physicists have exploited it to create something known as quantum cryptography. With it, they have made the most secure encryption codes that humans have ever devised.
The uncertainty principle indicates that measuring any object will disturb it. Quantum encryption relies on the fact that eavesdropping—trying to gain information on a message—is a form of measurement and will disturb a system in a way that can be detected.
Now the amount of disturbance is very small—proportional to Planck’s constant, one of the smallest quantities in physics. But if you use very small objects, or very small packets of energy such as photons to help establish cryptographic keys, then it’s possible to create a cryptography system that will detect any eavesdropper.
Fortunately for online banking and the internet, quantum cryptography was proposed in the 1980s, before Shor suggested his algorithm capable of breaking encryption. NIST has been involved in many areas of research in quantum cryptography, such as establishing cryptographic keys using streams of single photons, known as quantum-key distribution (QKD), and using these to create cryptography networks. And commercial devices started appearing in the 1990s. QKD systems have been implemented in the real world and have been used successfully in limited applications in government and the banking industry.
Quantum cryptography also has applications in secure communication. Researchers in China recently used the technique to make a secure video call to colleagues in Austria who were 2,500 kilometers (approximately 1,600 miles) away.
Most QKD systems use photons that travel through fiber-optic cables. The photons carry 0s and 1s of information. The information includes the secret key that the sender (usually dubbed “Alice” in descriptions of quantum cryptography) transmits to a receiver (named “Bob”). Then Alice uses the secret key to encrypt the message she wants to transmit. Bob uses the same key to decrypt the message. If an eavesdropper (named “Eve”) tries to intercept the key, the photons are disturbed in a way that Alice and Bob can detect. So, in the event of eavesdropping, Alice simply creates a brand new key and waits until one is successfully transmitted to Bob without eavesdropping. Then Alice transmits the message, scrambled in a way that can only be unscrambled with the key.
However, quantum cryptography systems have been expensive, and it has been challenging to make them widespread and practical. Even though quantum physics can provide the most fundamentally secure form of encryption, it has been shown that even cryptography systems based on quantum properties can be hacked under real-world conditions; for example, when electrical static or noise—governed by the rules of classical physics—inevitably gets introduced in the system. Basically, the components of a quantum cryptographic system can generate noise such as electrical static, whose behavior is governed by the rules of classical physics. This noise can give away what the system is doing, and thereby, make it insecure.
More fundamentally, however, quantum cryptography isn’t solving the most important cybersecurity problem that we are facing today. Quantum cryptography is designed to protect communications between two trustworthy parties from being intercepted by an eavesdropper.
But what if the person on the other side is a cyberattacker? Eavesdroppers are currently not the biggest concern in cybersecurity.
Secure encryption methods must be in place if and when a quantum computer that can run Shor’s algorithm is introduced. Quantum cryptography devices could serve part of this need, but they may be too impractical to implement on a major scale. So, researchers have developed a new field, called post-quantum encryption, that is exploring a whole range of alternatives.
“When quantum computers are a reality, our current public key cryptography won’t work anymore,” says NIST computer scientist Matt Scholl. “So, we need to start designing now what those replacements will be.”
Shor’s algorithm would crack cryptographic keys that rely on the factoring of large numbers. But there are many ways of encrypting data, using mathematical functions that do not involve factoring. And for some of these mathematical functions, quantum computers wouldn’t be much better than ordinary computers at trying to break them. Despite their name, many post-quantum algorithms are based on classical mathematics techniques that predate quantum information.
“You can use classical to stop quantum,” says Scholl.
NIST has been anticipating the quantum threat for a while. Researchers are already developing post-quantum algorithms, in case quantum computers become a reality. NIST is even calling upon the public for assistance in developing strategies and approaches for post-quantum algorithms.