Cryptographers Are Racing Against Quantum Computers

Today’s security schemes will soon be obsolete.

Written by Tammy Xu
Cryptographers Are Racing Against Quantum Computers
Image: Shutterstock / Built In
UPDATED BY
Brennan Whitfield | Feb 08, 2024

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.

MORE ON QUANTUM COMPUTINGWill There Be a Quantum Computing Revolution?

 

What Is Post-Quantum Cryptography?

Post-quantum cryptography, also known as quantum-resistant cryptography, is the development of cryptographic techniques unable to be solved by quantum and classical computers. Quantum computers currently lack the processing power to solve traditional cryptographic algorithms, but it’s predicted that quantum technology will eventually become powerful enough to make it possible. Shor’s algorithm in particular, a quantum algorithm able to find the prime factors of an integer, is hypothesized to be able to break traditional cryptographic systems when applied by a large-scale quantum computer, leading cryptographers to invest in post-quantum cryptography research. 

Currently, it’s thought that symmetric cryptographic algorithms and hash functions would be the most secure against quantum cryptographic attacks, while asymmetric cryptography would be the most vulnerable. 

 

Symmetric vs. Asymmetric Cryptography

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.
 

Symmetric Cryptography

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.

 

Asymmetric Cryptography 

Asymmetric cryptography doesn’t require secret keys to work; on the contrary, it’s a method for producing them. RSA is a popular algorithm used 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.

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; in 2020, 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.

RelatedWhat Is End-to-End Encryption?

 

How Does Asymmetric Encryption Work?

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.

asymmetric encryption
In asymmetric cryptography, the sender uses the receiver’s public key to encrypt the message. Only the receiver’s private key can undo the encryption — not even the receiver’s public key can do it. | Image: Shutterstock

 

Asymmetric Encryption Is Most Vulnerable to Quantum Attacks

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 in 1994. 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.

RelatedHow to Neutralize Quantum Security Threats

 

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.”

 

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 started accepting post-quantum cryptography standard proposals from the public in 2016 — a process it has used before with the AES symmetric cryptography standard and the SHA-3 hashing standard. The agency identified four candidate algorithms for standardization in 2022, and developed three Federal Information Processing Standards (FIPS) drafts from these chosen algorithms in 2023. Following the revision of the FIPS drafts based on public comment feedback, which closed in November 2023, NIST will conduct a final review and approval process for the standards.

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.

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.

MORE ON QUANTUM COMPUTINGWill Quantum Computers Replace Their Classical Counterparts?

 

There’s More Quantum 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.

 

Frequently Asked Questions

Post-quantum cryptography refers to the development of cryptographic methods unable to be solved by quantum and classical computers.

Post-quantum cryptography involves creating cryptographic algorithms that are secure against cryptographic attacks by quantum computers.

Quantum encryption, or quantum cryptography, involves using properties of quantum mechanics to improve cryptographic security.

Post-quantum cryptography algorithms are not guaranteed to be unhackable, but the goal is to make encryption and other cryptography methods as secure as possible to combat against eventual quantum-powered attacks.

Hiring Now
Veritone
Artificial Intelligence • Computer Vision • HR Tech • Machine Learning • Software
SHARE