Cryptographers Are Racing Against Quantum Computers
Most of the time, developers don’t have to think about encryption — it just works. But even though it’s invisible, encryption is an integral part of our technological infrastructure. It protects our privacy, allowing information to be kept secret even as it’s sent all across the internet.
Protocols such as Transport Layer Security (TLS) use encryption to prevent intruders from reading our data in transit, and it’s also used in digital signatures to verify the identities of the websites we visit.
But researchers are racing against the clock to come up with new encryption schemes, because quantum computers, with their new ways of doing calculations, can break current ones. And they are coming sooner than we think.
Symmetric and Asymmetric Cryptography Use Different Math Tricks
Encryption is fundamentally built on math tricks. All of the encryption schemes used today — to encrypt files stored on computers, to share secret information, to certify that sites are authentic and to prove we are who we say we are — fall into two categories: asymmetric and symmetric encryption.
These two categories use different types of math tricks, both involving “keys” — secret numbers known only by the sender or intended recipient. Of the two categories, symmetric encryption is less mathy — it simply scrambles a message in a very specific way, using a secret key. The receiver of the message then unscrambles it in exactly the opposite way, also using the same key.
Symmetric cryptography has both advantages and disadvantages. It’s not computationally intensive, so it can be used to encrypt large amounts of data. But its weakness is that, in order to use it securely, the sender and the receiver have to already share the same secret key. If you’re sending a message to someone for the first time, first getting the shared key over to them is a problem unto itself.
That’s where asymmetric cryptography comes in. Asymmetric cryptography doesn’t require secret keys to work; on the contrary, it’s a method for producing them. RSA is a popular algorithm for asymmetric encryption. It results in two keys — a pair — each of which can undo the operation of the other. The math that holds it all together and makes it secure is built on mathematicians’ most up-to-date understanding of prime numbers — namely, that it’s easy to find big prime numbers, but surprisingly difficult to factor the product of two large prime numbers.
Why Is It Hard to Find Prime Factors?
Finding the prime factors of small numbers is pretty easy. For example, the prime factors of 15 are 3 and 5, because 3 multiplied by 5 is 15, and 3 and 5 are both prime. But mathematicians have not found efficient ways of calculating prime factors when given a value that’s the product of two large prime numbers. In the case of RSA asymmetric cryptography, the two prime numbers being multiplied are each hundreds of digits long. It would take a powerful modern computer trillions of years to find the original two prime factors when given only their product.
In fact, prime factors are so difficult to calculate that experts estimate it would take a modern computer trillions of years to crack the standard 2,048-bit RSA encryption. There are ongoing competitions for breaking RSA; last year, a team of six researchers running a large fleet of computers managed to break a 250-bit RSA encryption — a much weaker iteration of RSA that has been out of use for over a decade.
Asymmetric Encryption Helps Secure Symmetric Encryption
Asymmetric cryptography can be used to share secret symmetric keys between senders and recipients. It works like this: if you need to send me something secure, I can give you one of the two asymmetric keys — called my “public key” — which you can use to encrypt your data. Because each key in an asymmetric key pair can undo the operation of the other key (but not its own operation), when I receive the encrypted data I can just use my “private key” to undo the encryption. Secret symmetric keys can be shared in this way as the encrypted data.
The public key in an asymmetric key pair can actually be published for anyone to use. It’s totally secure, as long as I don’t share my private key or the two prime numbers that both keys are derived from. No computer exists that can break the encryption in any practical amount of time.
Asymmetric keys are very useful. Since they work as unique pairs, they can also be used to verify identity. If everyone knows my public key, I can use my private key to encrypt a known message — for example, “Hello” — and send it to you to prove my identity. You can use my public key to reverse the encryption, see that the message is the expected “Hello,” and know that only I could have sent it. In this way, asymmetric cryptography can be used to send secrets and verify identity all at the same time.
The problem is, asymmetric cryptography is exactly the type of math problem that quantum computers know how to break.
The Race Toward Post-Quantum Security Standards
The problem goes back to prime numbers. Although mathematicians have not found a way for traditional computers to efficiently break asymmetric encryption by calculating prime factors, they’ve discovered a way for quantum computers to do it — and they can do it very quickly.
The National Institute of Standards and Technology (NIST) is a government agency that helps set standards for technology. Lily Chen, who heads NIST’s cryptographic technology group, said we will probably be dealing with the practical implications of quantum computers within 10 years.
“Experts predict that, around 2030, we’ll have full-scale quantum computers that can break asymmetric key cryptography,” Chen said. “So that will give us some time.”
Researchers have already built quantum computers, although none precise and powerful enough to break the current standards. It’s essentially a race now between the researchers working to improve the calculating power of quantum computers and those developing new encryption standards that can eventually hold up against those quantum computers. Chen said NIST is currently in the middle of a selection process for new, post-quantum security standards, while quantum researchers are working to improve their computers’ error correction abilities.
“Certainly, we should worry,” she said. “But as far as I can tell, we are still OK. The schedule is still OK to provide protection ahead of time from quantum computers.”
Asymmetric Encryption Is Most Vulnerable
For a while in the 1980s, quantum computing existed only as an interesting thought experiment. “Quantum states” are delicate and error-prone; worst of all, it seemed impossible to correct for errors without disturbing them. But in 1995, researcher Peter Shor showed that it was possible to do a kind of error correction that would preserve quantum states, proving that real quantum calculations could be done.
That was exciting news, and it was particularly interesting because of another article Shor had published the previous year. In “Algorithms for Quantum Computation: Discrete Logarithms and Factoring,” Shor demonstrated an entirely new way of calculating prime factors using quantum computers, one that could potentially reduce the calculation time from trillions of years down to eight hours.
That does not bode well for current asymmetric encryption methods. As it turns out, quantum computers can theoretically be used to break all existing implementations of asymmetric cryptography — not only RSA, but Diffie-Hellman and elliptic curve cryptography as well.
Interestingly, symmetric cryptography, the less mathy encryption scheme, is not as vulnerable. Quantum computers are only more computationally powerful than traditional computers for specific types of calculations — that happens to include calculations for finding prime factors, but no one has developed a method that would work against symmetric encryption. The most that quantum computers would affect symmetric cryptography is by requiring a slightly larger secret key.
Transitioning to a Post-Quantum World
2030 seems like a tight deadline for re-envisioning cryptography, but Chen said there is a plan in place.
“That’s why we started to do the post-quantum cryptography standards now,” she said. “We wanted to be ahead, to make sure that all the cell phones, laptops, routers, servers and everything is quantum resistant.”
NIST is currently in the third round of its process for selecting new post-quantum cryptography standards. The agency started accepting proposals from the public in 2016 — a process it has used before with the AES symmetric cryptography standard and the SHA-3 hashing standard — and the final standard is expected to be announced in 2022 or 2023.
Until then, Chen said NIST is also working on other ways to make the eventual transition to a new standard easier.
This could include physical changes to devices like laptops, phones and anything else that is electronic and needs to communicate securely with other devices. Although security algorithms are implemented using software, certain types of secure communication are tied to hardware features, and it’s also possible that new security standards would slow down current phones.
“We wanted to be ahead, to make sure that all the cell phones, laptops, routers, servers and everything is quantum resistant.”
“Of course, you can download the new software to do the new cryptography, but if you want to reach better performance, at some point you need to have the hardware implementation — the physical component,” Chen said.
But end users probably won’t be much affected, she said. Practically speaking, the first high-functioning quantum computers will likely be government affiliated and not widely available. They will probably target government secrets, not regular folks’ emails. Since users change their devices every few years anyway, it’s the device manufacturers who will handle any hardware changes, and NIST is working with them to do that, Chen said.
“In general, I wouldn’t imagine people would have to get rid of their old phones to buy a new one,” she said. “The migration will be many years, it’ll give the user plenty of time to naturally — like any other technology — go to the new cryptography.”
There’s More Research to Be Done
Apart from choosing new cryptography standards and transitioning to them, there’s still a lot of work that needs to be done. Even while quantum computers are being designed and built, there’s still much researchers don’t know about what they could be capable of, what benefits they can provide and perhaps what other security questions they raise.
“We are still in the stage of understanding quantum computers and quantum algorithms,” Chen said.
Researchers also have to ensure the chosen post-quantum security standards work well against all types of attacks — after all, getting a quantum computer to brute force its way into factoring prime numbers is not the only way to break encryption. Chen said attackers can also try and guess keys by measuring the amount of power encryption algorithms use, called side-channel attacks.
Quantum computers feel like untraveled territory, partly because of the technology itself, but also because of how far traditional computers have come. The closest analogy is the advent of the computers we use today — but when they were invented, we didn’t have an entire digital world that they could disrupt. This time, we won’t just be gaining a new technology — we’ll also have to deal with how it impacts the current paradigm.
Gloss