Cryptographers are in the business of being paranoid, but their fears over quantum computers might be justified. Within the next 10 to 15 years, a quantum computer could solve some problems many millions of times faster than a classical computer and, one day, crack many of the defenses used to secure the internet.
“The worst-case scenario is quite bad,” says
, associate professor of computer science and engineering at the University of Michigan, who has been studying cryptography for two decades.
That is why Dr. Peikert and hundreds of the world’s top cryptographers are involved in a competition to develop new encryption standards for the U.S., which would guard against both classical and quantum-computing cyberattacks.
This summer, federal officials announced the 15 algorithms that will be considered for standardization, meaning the winners would become a part of the architecture of the internet, protecting people’s sensitive data.
Next, researchers will spend about a year trying to break them to see which ones hold up, and test them to get the best balance of performance and security.
computers are still in the early stages of development. The machines harness the properties of quantum physics, including superposition and entanglement, to radically speed up complex calculations related to finance, health care and manufacturing that are intractable for today’s computers. These machines are being built by startups and technology companies such as International Business Machines Corp. and
Google. They are still several years away from being fully commercialized.
While traditional computers store information as either zeros or ones, quantum computers use quantum bits, or qubits, which represent and store information as both zeros and ones simultaneously.
Some researchers estimate that it would take a machine with 250 million qubits to break today’s public-key cryptography. Today’s early-stage quantum computers have a tiny fraction of that power.
The initiative is being managed by the National Institute of Standards and Technology, an agency of the U.S. Department of Commerce. NIST has asked entrants to design encryption algorithms that they think could withstand a cyberattack from a quantum computer. The competition began in 2017 with about 70 algorithms.
The 15 remaining algorithms include seven methods that could be standardized by 2023, and eight alternates, which would take more time to study but still show promise.
“We can’t prove that they won’t ever be broken, but that’s the case with all cryptography,” says Dustin Moody, a mathematician at NIST who is leading the post-quantum cryptography competition.
The goal of the competition is to replace today’s commonly used public-key cryptography methods, including a popular one called RSA that would be particularly at risk if and when a powerful quantum computer comes to market. Named after its developers Ron Rivest, Adi Shamir and Leonard Adleman, RSA is used to secure things such as email, online banking, e-commerce and electronic communications such as those in the health-care industry.
RSA is vulnerable to quantum computers because it is based on integer factorization, which is essentially reverse multiplication, using numbers that can be about 1,000 digits long.
It is not possible for regular computers, even supercomputers, to quickly factor numbers that are that long. Quantum computers, though, are capable of solving integer factorization problems perhaps many millions of times faster than a classical computer.
If bad actors ever got their hands on a powerful enough quantum computer, they could break into anything encrypted with RSA, representing a huge swath of the internet. The threat is real even now, cryptographers say, because hackers could be collecting massive amounts of data, waiting to attack when a quantum computer comes into existence, a practice known as “harvest and decrypt.”
“We got very unlucky that the one thing that quantum computers can have this exponential speedup for is exactly what we based our cryptography on in the 1980s,” says
, a cryptographer at
Europe, a security department of IBM. Dr. Lyubashevsky is a co-author on three of the finalist submissions.
Several of the most promising cryptographic systems in the NIST competition are based on so-called mathematical lattices, which can resemble geometric shapes that can have more than 1,000 dimensions.
Researchers to date haven’t found an algorithm that can solve, and therefore break, an encryption method based on a secure lattice, either on a classical or quantum computer. It would be surprising if someone did: Lattices have been studied in cryptography for about 25 years, says Rachel Player, a lecturer in information security at Royal Holloway, University of London.
Still, Dr. Player and other cryptographers will spend the next year or so trying to come up with algorithms that attack and test the remaining submissions, including those based on lattices. “It would be really cool to discover this algorithm, but then you spent so long working to build this, it would be a shame to break it,” says Dr. Player, who was involved in a lattice-based submission that didn’t make it to the finals.
Two of the finalist algorithms are named Crystals Dilithium and Crystals Kyber. Crystals is short for Cryptographic Suite for Algebraic Lattices. Crystals Kyber is used to securely share keys, and Crystals Dilithium is used for authentication. Fans may recognize the names from “Star Wars” (lightsabers are made from kyber crystals) and “Star Trek” (dilithium crystals are used in the warp drive).
“We have some fun with it,” says
, a distinguished engineer at
, who leads the Microsoft Research security and cryptography team.
Dr. LaMacchia is a co-author on two of NIST’s alternates, including one called FrodoKEM. The name is a nod to Frodo Baggins in J. R. R. Tolkien’s “The Lord of the Rings.” The cryptographic scheme is based on prior work that used a lattice that included an algebraic ring, Dr. LaMacchia says. Researchers decided to ditch the ring to strengthen the security of the algorithm, and they made another modification in adding a key encapsulation model, or KEM.
Other organizations around the world, such as the European Telecommunications Standards Institute, are researching algorithms that are resistant to quantum computing attacks and are providing industry guidance.
So are private companies, particularly in financial services, including
& Co. Research in the area of post-quantum cryptography began nearly six years ago, says
, president of technology at Visa. “The data we have is sensitive, and it is vast in quantity, so protecting that data is job number one for us,” he says.
Visa and JPMorgan plan to begin adopting NIST’s new standards when they become available, which will require coordination with industry organizations. It can take as long as 15 years for internet activity to be secured by the new encryption methods, experts say.
The NIST challenge is unique because it is mostly theoretical. These experts are trying to design cryptographic systems that will be secure against quantum computers, which they don’t know how to build and can only assume will exist, Dr. Peikert says.
For many cryptographers, coming up with new encryption standards by 2023 will represent the culmination of 10 or 15 years of work in the area known as post-quantum cryptography.
“I see standardization as a bittersweet moment,” says Dr. Peikert, who was also a co-author on the FrodoKEM submission. “It means we’re effectively done with something. It’s over. And for researchers like me, who work more on the theoretical side, we’re much more excited by what’s going to be great 15 years from now.”
Copyright ©2020 Dow Jones & Company, Inc. All Rights Reserved. 87990cbe856818d5eddac44c7b1cdeb8