Inside the fight to protect your data from quantum computers

Data encryption is the hidden glue holding the internet together. Without it, all our digital information would be available for everyone else to see — everything from private messages to bank records. Cyberattacks aimed at “decrypting” private data can spell disaster for both corporations and individuals. Luckily, successful attacks remain relatively uncommon, which is a testament to the power of our current data encryption systems.

But modern encryption has a major foe on the horizon: the inevitable rise of quantum computers. 

“The cryptography we use today is broken if you have a quantum computer,” says Oded Regev, a computer scientist at New York University’s Courant Institute of Mathematical Sciences. Cryptographers are racing to develop new forms of cyber protection to protect against this mechanical threat. If all goes well, then standardizable solutions should emerge in the next few years — in time to stave off quantum-powered attacks. But if things don’t go as planned, then the internet could soon resemble a chaotic Wild West. “The stakes are high,” Regev says.

Quantum computers are computers that run on subatomic “qubits” rather than conventional bits — the digital 1s and 0s that allow your phone or laptop to function. Due to the quirky rules of quantum mechanics, qubits don’t have to take on a value of just 1 or 0. Instead, qubits can exist in “superposition,” which is like taking on multiple values at once. This allows quantum computers to do math differently — and, in many cases, much faster — than modern computers.

That sounds exciting, right? Well, it’s also worrying, as quantum computers can break the most prominent data encryption systems in use today.

Most modern data encryption is based on “prime factorization,” Regev says. That’s when you’re given a number, and you have to find the smallest prime numbers that multiply together to give that number. For 21, it’s 7 and 3. For 52, it’s 2 and 2 and 13. Simple enough.

But, as Regev explains, there’s no known way to quickly find the prime factors of really big numbers with conventional computers. Running through all the possibilities takes an incredibly long time. Similarly, if you tried to do the calculation in your head, it would probably take you a while to figure out that the prime factors of 7,957 are 73 and 109.

Back in the early days of the internet, Regev says, computer scientists decided to use the difficulty of prime factorization to our collective advantage, employing it as the basis for how we encrypt digital data. But these experts were shocked when a mathematician named Peter Shor finally derived an efficient prime factorization algorithm in 1995. Shor’s algorithm could find prime factors in record time, even for incredibly large numbers.

Luckily, there was a catch: Shor’s algorithm couldn’t run on conventional computers. The algorithm could only run on a quantum computer, which didn’t even exist at the time.

Fast forward to today: electronics companies and university labs have now built a number of quantum computers. The exact number is difficult to pin down; IBM alone reports having “over 20” quantum computing systems, and there are likely at least one or two dozen more across the globe. All these quantum computers are essentially still in the prototype phase; the first quantum computer to surpass a measly 100 qubits was unveiled in November 2021, according to Nature. For context, a 2019 study suggests that it would take eight hours for a quantum computer with 20 million qubits to break modern encryption. We’re clearly still far off from that reality. 

Even so, due to the unique power of quantum computers, many experts expect to see a quantum computing explosion in the coming decades. Naturally, this is worrisome for anyone who cares about digital privacy and the future of the internet at large. So it should come as no surprise that scientists are searching for a quantum-computer-proof encryption system now, before quantum computers become widespread.

This field is known as post-quantum cryptography, and it has become a popular research area among mathematicians and computer scientists alike.

Despite having “quantum” in the name, post-quantum cryptography centers around finding conventional algorithms — not quantum ones like Shor’s. “We want algorithms or encryption schemes that you can use on your phone or on your MacBook,” Regev says.

One of the cornerstones of post-quantum cryptography is an ongoing competition held by the National Institute of Standards and Technology (NIST), a bureau of the U.S. Department of Commerce. NIST’s competition seeks to find a few algorithms that are safe from quantum computer attacks and efficient enough to become industry standards. 

The competition began in 2017 with an open call for submissions, according to Dustin Moody, the NIST mathematician who oversees it. After three rounds — the latest of which ended in 2020 — 69 initial candidate algorithms have been narrowed down to seven finalists.

As candidate algorithms progressed through each round, Moody says, they were heavily scrutinized by mathematicians — all checking to see if there was any way to crack them. If so, then they were thrown away. Other algorithms were eliminated simply for being inefficient in terms of time or processing power, he adds.

There’s a good chance that the winner of this game of cyber-Survivor will be a powerful form of encryption known as a lattice-based algorithm. Around a third of the submissions that NIST’s competition initially received were lattice-based, Moody says. But now, a full five out of the seven finalist algorithms follow a lattice approach.

Although Regev is not involved in the competition, his research also centers around lattice-based cryptography. After reading a paper on lattices around 2001, “I fell in love with this mathematical object,” he recalls. As an NYU professor, Regev has come up with a very simple example of a lattice-based encryption system in order to demonstrate the concept to his students.

In his example, the goal is to get your friend to send you a secret, encrypted message, even though your correspondence is public and can be seen by anyone. For this example, the “message” you’re hoping to receive from your friend is a simple 1 (meaning “Yes”) or 0 (meaning “No”). The question is: How can your friend send you that 1 or 0 without everyone knowing which they sent?

Computer scientist Oded Regev uses this basic example to teach his students about encryption with lattices. [Concept: Oded Regev | Image: Daniel Leonard]

The critical moment in the example comes in step three, when you add random even numbers to every number in your list. Regev calls this “noise”; it takes an orderly list of multiples and turns it into something complicated and patternless. That noise is the stumbling block that prevents a quantum computer from decrypting your communication, Regev says. 

Of course, most lattice-based algorithms are more complicated than this. Plus, a genuine encryption system would use many more numbers, and much bigger ones — perhaps around 100 digits long, Regev explains. But Regev designed this example to give students a basic understanding of how lattice encryption works and how it’s theoretically safe, even from quantum computers.

Daniel Apon, a computer scientist who’s helping to direct NIST’s competition, suggests that lattice-based algorithms are succeeding in the competition because they’ve been studied for years. “[Lattices] were among the most popular research areas for academic cryptographers over the past 10 to 15 years,” Apon says. Moody adds that most of NIST’s lattice submissions are well-balanced candidates that can run fairly fast without sacrificing safety.

Still, not everyone is sure that lattices are the best way to go.

“It’s a good idea for NIST not to put all its eggs in one basket,” says Jintai Ding, a professor of mathematics at Tsinghua University. Ding is one of the lead mathematicians behind the Rainbow cryptosystem — one of the two non-lattice-based finalists of the NIST competition.

Ding isn’t opposed to lattice-based cryptography; in fact, he’s worked with lattices in his own research. But Ding notes that it’s a good idea to have a vast range of encryption algorithms at our disposal, in case there turns out to be some still-undiscovered flaw with lattices. In fact, Ding points out that another mathematician named Daniel Bernstein recently put forward a new type of attack aimed at breaking through lattices. The cryptographic community is still debating how effective this attack could be against lattice-based encryption, Ding says.

NIST plans to pick a few algorithms to standardize, Moody says, and agrees that choosing a few diverse candidates would probably be the best play.

When the competition is done, Moody adds, the U.S. government will likely be the first to adopt and standardize a post-quantum cryptographic algorithm. While governments around the world have been entering the “race” to develop effective quantum computers, the U.S. has been particularly fearful of quantum attacks coming from China. In fact, outlets like Newsweek and Scientific American have suggested that China is leading the quantum computer race, with other countries lagging behind its quantum capabilities. As a result, it’s no surprise that quantum defense has become a high priority for the American government.

After the U.S. government has protected its systems with a post-quantum encryption algorithm, Moody suggests that corporations will likely hop on and adopt the same standards. Once that happens, your data — bank data, social media data and more — will also become protected by post-quantum encryption.

This is all set to happen over the course of the next decade or so, Moody says. NIST plans to announce its winners in 2022, he explains, followed by a formal publication of the standard algorithms around 2024. Then, it’ll likely take several more years for those algorithms to see widespread adoption.

Moody and Apon are both optimistic that those winners will be able to successfully protect us all from quantum computer attacks. With a years-long competition involving close scrutiny from competitors and allies alike, NIST’s contest is theoretically weeding out the weak. Soon, if all goes well, it will leave us with the best defenses against quantum attacks that we can come up with.

Even so, the competition leaders acknowledge that it’s impossible to know whether these encryption systems have hidden flaws that someone, someday will find a way to exploit. After all, the mathematics community thought that prime factorization was a virtually foolproof encryption method until Peter Shor came up with his quantum algorithm in the 1990s. It’s always possible that a similar breakthrough could break through any of NIST’s finalist algorithms. The best evidence that that won’t happen, Regev suggests, is simply that it hasn’t happened yet. But mathematical breakthroughs are hard to predict.

Whichever algorithms are chosen, Apon points out that all of this will happen “behind the scenes” — out of view for the average internet user like you or me. Assuming everything does go well, we’ll all wake up one day to find that our data has been moved from standard encryption to post-quantum encryption. In fact, we probably won’t even know that it happened. On our end, it should all look the same.

“If we do our job right at NIST, no one should ever notice the difference,” Apon says.

Correction: An earlier version of this article said NIST planned to announce its competition’s winners in 2024. NIST will announce the winners in 2022, followed by a formal publication of the new standards around 2024. Updated March 4, 2022.