For much of the past decade, cybersecurity experts have been warning of a looming threat: the advent of quantum computers.
These machines, which use principles of quantum physics to represent information, will one day be powerful enough to crack the most widely used encryption systems, rendering almost all digital communication insecure.
The question has always been exactly when that day would arrive. The most common digital encryption technique, RSA, which was invented in 1977, is based on multiplying two large prime numbers. One way to break it is to figure out what those two large primes were. In 1994, mathematician Peter Shor invented an algorithm, that if run on a sufficiently powerful quantum computer, would easily find these two primes. But at the time, quantum computers were still purely theoretical machines.
The first working quantum computers were built over a decade ago. But most were either not designed in a way that would allow them to run Shor’s algorithm. Others were simply not powerful enough to do so for a very large prime multiple. The moment when cybersecurity experts would have to worry about quantum computer-equipped hackers seemed a long way off—at least a quarter century by some estimates—and there were far more pressing threats.
But not anymore. Last year, Google claimed it had achieved a milestone known as “quantum supremacy,” having built a quantum computer capable of performing a calculation that could not be done on a traditional computer in a reasonable length of time.
Google’s machine is still unable to break RSA. But the rapid progress in building quantum hardware along with some clever advancements in algorithms mean the timeline for Shor’s algorithm rendering RSA obsolete have been moved up considerably. If lucky, we may have more than decade of data privacy protection left, experts say. But some think we have at best five years—maybe less.
In 2016, the U.S. National Security Agency issued a stark warning that government agencies and companies “must act now” to begin moving to a new encryption standard that is safe from quantum computer-based attacks. The only problem? No one was sure exactly what that encryption standard should be.
That’s why the National Institute of Standards and Technology (NIST), an agency with the U.S. Department of Commerce that is responsible for recommending standards that are often adopted by both government and business, began a competition almost three years ago to select new encryption techniques that would be resistant to attacks from quantum computers.
These new “post-quantum” encryption and digital signature methods will likely become mandatory for all U.S. government departments and for many companies that do business with the government, especially in defense and intelligence. Because of the size of the U.S. market, they are also likely to become the new global security standard. NIST is now on the verge of picking the winning encryption algorithms—and ushering in a new era in cybersecurity.
In July, the standards agency announced that it had winnowed an initial group of 82 candidates down to a long-list of 15, including four main finalists for encryption and three for digital signatures, which use cryptography to verify whether electronic messages and documents are authentic. (Eight alternates will advance to the final round as well.) NIST has said it will announce its final endorsements for a new encryption standard within the next 18 months.
So what does the NIST long-list tell us about the future of cybersecurity? Well, there’s a good chance that it will involve something called lattice-based cryptography. Three of the four encryption finalists come from this family of algorithms.
Lattice-based cryptography is based on the unique mathematical properties of grids of evenly-spaced points, or lattices. Because the points are evenly spaced, it turns out that from just two coordinates of the grid it is possible to compute all the points within the same lattice. But figuring out whether any given point is in the lattice can be difficult if the lattice is in many thousands of dimensions and if the angles between points in the grid are far from perpendicular. A number of encryption schemes have been created that use these properties to create a public key and a private key that work together—because they are calculated from the same lattice—but in which it is extremely difficult to derive the private key from the public key alone.
But some cybersecurity experts are surprised that NIST has leaned so heavily towards this kind of post-quantum encryption. That’s because while lattice-based problems are mathematically difficult and, unlike RSA, are not susceptible to Shor’s algorithm, they have not been mathematically proven to be impervious to a quantum computer-based attack. “We say that quantum algorithms cannot break them yet,” Delaram Kahrobaei, a professor of cybersecurity at the University of York, in England, says. “But tomorrow someone comes up with another quantum algorithm that might break them.”
Kahrobaei says she is disappointed to see that candidates from other families of potential post-quantum algorithms did not make it onto the final list for the public key encryption competition. This includes multivariate cryptography, which is based on the difficulty of solving systems of complex quadratic equations (remember those from high school algebra?), and group-based cryptography, which is the area that Kahrobaei herself works on. It is based on yet another area of mathematics involving transforming a set of numbers by combining elements, often according to elaborate geometric patterns, such as braids. One candidate from the multivariate cryptography family, an algorithm called Rainbow, did make onto the list of finalists in the digital signature portion of the competition, and another, called GeMSS, was selected as an alternate in that contest.
The only non-lattice post-quantum encryption candidate among the NIST finalists comes from a cryptographic family known as code-based algorithms. These all involve adding some sort of error to data—like a classic code where you shift the alphabet over two letters so that A is encoded as C and B as D, and so on. This error is then corrected to decrypt the message. The post-quantum algorithm NIST has chosen is called Classic McEliece, named for an error-correcting code algorithm invented by mathematician Robert McEliece in the late 1970s. It applies a different random error to each piece of information that’s encoded—which in theory makes it impossible to break without knowing the key.
“McEliece’s system has been around for 41 years and been attacked by the crypto community for all that time without finding a vulnerability,” Andersen Cheng, the co-founder and chief executive officer of Post-Quantum Group, a London-based cybersecurity company that joined forces with another team, led by Daniel Bernstein, a noted cryptographer at the University of Illinois in Chicago, to work on the Classic McEliece submission that made it to the long list of NIST finalists.
In 2019, the German Federal Office for Information Security (BSI), concerned that the NIST process was taking too long, recommended the Classic McEliece as one of its two recommended post-quantum encryption standards. (The other was a lattice-based method that is among NIST’s alternate candidates.) Cheng says he suspects that NIST, like the German government, will ultimately endorse two standards—Classic McEliece and one of the lattice methods.
The only drawback of the McEliece algorithm, Cheng says, is that the relatively lengthy keys the method uses, and the computational complexity of the algorithm, means it takes more time for a computer to encrypt and decrypt information than with its lattice-based competitors. “It’s slower by a few milliseconds,” Cheng says. But he says that for exchanging encryption keys—which is mostly what the algorithm would be used for—the method is still actually faster than RSA.
While there are researchers from established tech companies, such as IBM, Intel, and the chipmaker ARM, involved in the race to find quantum-secure encryption algorithms, what’s notable is how relatively few established cybersecurity firms are contenders in the NIST contest. Post-Quantum is among several startups that entered the competition—and which are poised to profit from the move to a new generation of encryption.
Kahrobaei says she expects a host of new companies to spring up to help commercialize post-quantum encryption, just as RSA Security—the company that was founded in 1982 to commercialize the RSA algorithm—became a dominant player in the cybersecurity space for the past three decades.
Cheng says that Post-Quantum Group, which was founded in 2009, once struggled to get chief information security officers and chief information officers at major banks and corporations to take the threat of quantum computers seriously. But, he says, the NIST process has belatedly focused their attention. “Now they know they have to do something in 18 months-time and they are starting to ask questions, ‘what can they do?’ ” he says.
This story has been updated to correct the definition of multivariate cryptography and to note that one multivariate cryptography algorithm did make into the list of finalists in the digital signature portion of the NIST competition. It has also been updated to clarify the type of encryption keys the Classic McEliece algorithm would likely be used to exchange.
