The security of modern communications could soon expire. The precise day, month, or year is impossible to predict because the technology capable of cracking our codes—practical, robust quantum computers—does not exist. Yet experts insist that the time to prepare is now.
“It’s beyond something you can just ignore, even though we still don’t know when it will happen,” says mathematician Michele Mosca of the Institute for Quantum Computing at the University of Waterloo in Canada. “The chance of it happening in five, 10, or 20 years is not a risk you can accept. It’s a systematic threat to the global economy, and it’s real enough that you definitely have to plan for it now.”
Today’s most successful cryptographic systems, which we depend upon to secure online transactions and communications, rely on one of two mathematical problems: factoring large numbers or finding discrete algorithms. If you’re using online encryption, buying something, or even downloading a software update for your PC, the security of that exchange probably relies on the difficulty of these mathematical challenges. For today’s computers, these problems are all but impossible to solve.
In 1994, mathematician Peter Shor described an algorithm that could unlock these codes, but it was not designed for machines that speak in the common digital language of 1s and 0s. Shor’s algorithm is designed to run on a quantum computer—one that uses quantum bits, or qubits. These qubits could exist in a superposition of an exponential number of states, and a quantum computer running Shor’s algorithm could solve both of the difficult mathematical problems that underpin most cryptography.
While the threat is theoretical, it still has contemporary implications. A malicious actor could store a cache of email encrypted with today’s cryptographic approaches, and then use quantum computing to unlock them some 10 or 15 years in the future.
Government, academia, and industry are working diligently to prepare for this post-quantum-computing world. The German government, for example, is funding seven initiatives, including efforts to increase collaboration between academia and industry. However, most experts currently are focused on the Post-Quantum Cryptography Standardization project being run by the U.S. National Institute of Standards and Technology (NIST). The goal of the project, which has many hallmarks of a competition but declines to be defined as such, is to spark the development, refinement, and testing of cryptographic algorithms that could maintain security in a world of quantum computers.
Living on the Edge
In one sense, the threat of quantum computers is not entirely new, as there is always a risk cryptography can be broken. “We live on the edge because none of the cryptographic systems we use are proven secure in the sense that there’s no mathematical proof that these things cannot be broken,” says Massachusetts Institute of Technology mathematician Vinod Vaikuntanathan. “A bunch of smart people try to attack them for 10 to 20 years, and if they can’t, then we say it’s probably good enough. But we’re always at risk of someone coming up with a clever algorithm for factoring large numbers or, with quantum computers, we’re at the risk of the underlying computing technology changing so dramatically that new attacks suddenly become possible.”
Since the problems on which most cryptography relies would be solvable in a post-quantum world, experts have to find a new, harder mathematical problem. Luckily, this effort has been underway for some time. “People have been trying to build post-quantum-secure cryptography for 20 years,” says cryptography researcher Vadim Lyubashevsky of IBM Research, Zurich. “This was already a mature field.”
Narrowing the Field
The aim of the NIST program is to transform this theoretical work into practical methods and results that can be widely attacked and tested. The initial call for proposals yielded 82 submissions, of which 69 were accepted. NIST researchers and members of the cryptography community quickly set about testing the approaches. Some were broken within a few weeks; others survived longer. When a group or individual breaks a technique, the result is announced in an NIST forum. The prize? Peer recognition. By 2019, the field narrowed to 26 candidates, and that number will be winnowed down again this year or early next.
“It’s not a paint job. It’s like replacing every brick in the foundation of your house. You can’t just throw on some quantum-safe fairy dust at the last minute.”
NIST mathematician Dustin Moody, director of the program, expects approximately a dozen candidates will emerge as finalists. NIST has encouraged several teams to merge, as their approaches were similar, and some have followed these recommendations, while others remained independent. One of the more popular methods among the entries hinges on lattices, or grids, and the difficulty of finding a point close to the origin in a lattice defined by a basis of long vectors. In two dimensions, the lattice problem can be relatively simple, but “When you go to 1,000 dimensions, this becomes insanely hard,” says Vaikuntanathan. “Nobody has been able to put a dent in this problem.”
The other advantage of the lattice-based approach is that cryptography researchers have been testing it—and attacking it without success—for years. “This gives you confidence in the security,” says Moody. “It gives you confidence that the hard problem we’re going to rely on really is going to be a hard problem.”
At the same time, Moody stresses, there are no favorites, and several other approaches have their own strengths. Mosca notes that advocates of another popular option—a code-based approach—would argue their scheme has been around and tested even longer.
Practical Considerations
The program is not merely evaluating the strength or security of the algorithms; the practical implications of real-world implementation are essential, too. For example, if the schemes are going to run on embedded systems such as Internet of Things (IoT) devices, they will need to be sufficiently lightweight that they will not demand significant compute or storage resources.
“In general, post-quantum cryptography schemes will require more resources,” says cryptographic engineer Ruben Niederhagen of the Fraunhofer Institute for Secure Information Technology (SIT) in Germany. “That’s fine if you have a large device like a smartphone or a server, but if you go down to embedded systems, which have limited computational resources and limited storage, this gets very tricky.”
Speed will be an essential quality, too. Online transactions need to be fast, so new quantum-safe algorithms should not slow down exchanges excessively, and Lyubashevsky says some post-quantum techniques may actually prove faster.
Another factor to consider will be the size of the keys that need to be exchanged. The lattice-based encryption approach, for example, might result in keys that are 8,000 bits long, instead of the 2,048-bit keys exchanged with the popular RSA technique. “If you hardcoded that your packets are going to be less than 3,000 bits, you’re going to be in trouble,” says Lyubashevsky. Systems that have placed a limit on key size will have to be adjusted, or they will not be able to run these new cryptographic standards. Also, the exchange of keys needs to be fast enough that the operation does not time out.
Regardless of which algorithms emerge from the competition, experts say it will still take years to implement a post-quantum approach. “If I say it is five years away, and tell a random enterprise they have to fix all their systems, there is no practical way they could do it,” says Mosca. “Even a simple fix takes a long time. It’s not a paint job. It’s like replacing every brick in the foundation of your house. You can’t just throw on some quantum-safe fairy dust at the last minute. You have to really start planning and working on it now.”
This is especially true for large enterprises. Niederhagen and his Fraunhofer colleagues work closely with major companies, studying their products or product lines to determine which will need to be post-quantum secure. Automobiles, power plants, trains—each of these relies on embedded devices, and the products they are manufacturing today will likely still be operational in 15 years, at which point quantum computers could be operational.
No Silver Bullet
Niederhagen says researchers who focus more on implementation are in something of a holding pattern as they wait for the new NIST standards to be released. While no date has been set, and no clear winner has emerged, Moody does offer some sense of the end-results.
Moody and other experts expect several algorithms to be selected, instead of a single victor. “There’s no perfect silver-bullet winner that will have all the properties everyone wants,” Moody says. But the work of the remaining teams, and the efforts of the larger cryptography community to attack their algorithms, should bring us closer to a more secure post-quantum future. “We’re all working for the same purpose,” Moody notes. “We want strong cryptography to protect against a future with quantum computers.”
Further Reading
Bernstein, D.J., Buchmann, J., and Dahmen, E.
Post-Quantum Cryptography, Springer, 2009.
Chen, L., Jordan, S., Liu, Y.-K., Moody, D., Peralta, R., Perlner, R., and Smith-Tone, D.
Report on Post-Quantum Cryptography, NISTIR 8105.
Kaye, P., Laflamme, R., and Mosca, M.
An Introduction to Quantum Computing, Oxford University Press, 2007.
Lyubashevsky, V., and Seiler, G.
NTTRU: Truly Fast NTRU Using NTT, IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019.
As We Enter a New Quantum Era https://www.youtube.com/watch?v=vWP4LF2hz80
Join the Discussion (0)
Become a Member or Sign In to Post a Comment