In July, the National Institute of Standards and Technology (NIST) announced the winners of a global competition to create new encryption standards. Somewhat mind-bogglingly, these algorithms have been designed to defend against a cyber threat that doesn’t even exist yet: quantum computers.
For the most part, today’s popular encryption standards are very strong and difficult to defeat. Powered by complex mathematical equations that normal computers can’t crack, encryption keeps your digital life hidden behind a veil of secrecy. But researchers worry about a future in which quantum computing—high-tech hardware that can solve equations at unbelievable speeds—will be able to swiftly unscramble those digital defenses without breaking a sweat.
The new “quantum-resistant” encryption standards, which won’t be officially ready for deployment for another year or two, have been designed to keep everybody one step ahead of this theoretical future threat. As a new development in the realm of internet security, NIST’s recently selected algorithms are a pretty big deal, and deserve a little unpacking. To get a sense of how computer scientists are generating these new encryption standards, Gizmodo spoke to experts involved in the contest and outside it, including the developer of a legendary algorithm that plays a determining role in the development of quantum defenses.
First, What is Quantum Computing?
I’m not going to pretend that I can adequately explain quantum computing to you, but I can give you the the CliffNotes version: “quantum” differs from “classical” computing in that it is designed to operate using the properties of quantum mechanics. Unlike today’s computers, which store data as “bits” of information, quantum machines utilize what are called “quantum bits” or “qubits,” which, if properly stabilized, have powerful properties. Theoretically, the processing power of quantum computers could be exponentially greater than the devices that exist today.
That’s, uh...that’s the best I’ve got. For a more detailed break-down of how quantum computing works, check out some of our earlier coverage.
While they might sound impressive, quantum computers are still largely hypothetical at this point. Though governments and large companies like IBM and Google have been working feverishly to create these machines, it’s not at all clear when a fully functioning quantum device will actually arrive. It could be five years, it could be twenty-five. We just don’t really know.
When they do arrive, experts predict that quantum computers will totally upend our way of life via breakthroughs in mathematics, science, medicine, and many other areas. A lot of outlandish claims have been made on this front. Due to their ability to carry out high-octane mathematical equations, some experts believe that quantum computers will do things like help cure cancer, allow us to more accurately predict the weather, foresee how markets shift and evolve, and revolutionize communication systems, among many other wonders.
Whether they will actually be able to achieve all that or not is unknown. But security experts are fairly certain that quantum machines will be able to easily break the public key encryption systems that currently secure our digital world. That’s where the new encryption standards will come in handy.
If new digital defenses are a good idea, developing them isn’t a simple process. Dustin Moody, a NIST mathematician who served as the project lead for the encryption contest, told Gizmodo that arriving at the new standards “doesn’t happen over night—it takes a number of years to do.”
Indeed, Moody said that he was originally assigned to helm the project back in 2013 and that the contest wasn’t publicly announced until 2016. It didn’t begin in earnest until a 2017 call for submissions, and it has just now concluded, approximately half a decade later. Distributable drafts of the standards won’t actually be finished for another year or two, after which they will likely start to see adoption by major corporations and governments, Moody said.
Of the 69 qualifying projects that were submitted by academics all over the world, NIST ultimately chose four as the winners. They included a project called CRYSTALS-Kyber, which will provide general encryption to secure websites, as well as three digital signatures—the cryptographic functions that verify events on the web. For the signatures, projects called CRYSTALS-Dilithium, SPHINCS+, and FALCON were selected. Each project has an individual website where you can check out the associated algorithm. NIST is also considering the inclusion of four additional projects into its new encryption standards, though they haven’t provided additional details on those yet.
NIST has consistently been at the forefront of creating the digital protections that we all rely on. The mostly widely used encryption cipher, the Advanced Encryption Standard, or AES, was generated via a previously held NIST competition. So was the third iteration of the Secure Hash Algorithm series, or SHA, the critical cryptographic function that is used ubiquitously.
However, this recent contest was spurred by advances in quantum computing—and worries that the U.S. might get caught with its pants down when the new machines finally materialize. Governments, including China, have been working overtime to make advances in this field. Thus, the concerns about quantum decryption aren’t just about keeping the average American’s text messages safe; they’re also a matter of national security for the federal government, which stores much of its secrets via encryption.
“It probably wasn’t until around 2010-ish that cryptographers started paying more attention and doing more research to find solutions to protect against these [theoretical decryption] attacks, as progress on quantum computers started growing,” Moody said. While today’s quantum computers aren’t currently powerful enough to threaten any of America’s top cryptosystems, they will be a concern in the future, he said.
You might be wondering how you’re supposed to build defenses against something that hasn’t even been invented yet. The short answer is: just because the hardware for quantum computing hasn’t fully materialized, that doesn’t mean that code for it can’t be written. Indeed, algorithms have already been developed that will run on quantum machines once they’ve arrived.
“We don’t have quantum computers, so we don’t know how fast they’ll be or how they’ll perform necessarily,” said Moody. “But there are certain algorithms that researchers have invented that they know will work on a quantum computer much, much faster than they do on our classical computers.”
One of the most important of these “post-quantum” theorems is “Shor’s algorithm,” named after MIT physicist Peter Shor, its discoverer, who originally developed it back in 1994. It is believed that, when run on a quantum machine, Shor’s algorithm will be able to obliterate our current standards of public-key encryption. Luckily, algorithms like Shor’s can also help illuminate the ways in which defenses can be built up, not just torn down.
“There is uncertainty in this—that’s one of the complexities that we’ve had to deal with,” Moody said. “We take quantum algorithms that researchers have developed and compute how much resources a quantum computer would need to attack perimeters at certain security levels,” he said. Roughly translated, this means that knowing how a future computer could attack encryption also helps to reveal what sort of cryptographic power is necessary to fend off those incursions.
Shor himself is uncertain about the future of quantum development. Speaking with Gizmodo, the mathematician said that the speed at which the new machines arrive really depends on how swiftly scientific breakthroughs in the field come over the next several decades.
“The hardware we have now is certainly not good enough under any conceivable circumstances, but it is improving,” said Shor. “It’s certainly possible that it will happen in our lifetime,” though he also noted that “it’s just very difficult to predict the future.”
“I think it depends on how many breakthroughs you think are going to happen over the next ten or twenty years,” said Shor. “With some breakthroughs, I think twenty years is a possible time frame. Without any breakthroughs, it’s going to take a lot longer than that. I’m convinced there will be some [advances], but it’s a question of how much.”