Getty Images
In the not-too-distant future—as little as a decade, perhaps, nobody knows exactly how long—the cryptography protecting your bank transactions, chat messages, and medical records from prying eyes is going to break spectacularly with the advent of quantum computing. On Tuesday, a US government agency named four replacement encryption schemes to head off this cryptopocalypse.
Some of the most widely used public-key encryption systems—including those using the RSA, Diffie-Hellman, and elliptic curve Diffie-Hellman algorithms—rely on mathematics to protect sensitive data. These mathematical problems include (1) factoring a key’s large composite number (usually denoted as N) to derive its two factors (usually denoted as P and Q) and (2) computing the discrete logarithm that keys are based on.
The security of these cryptosystems depends entirely on classical computers’ difficulty in solving these problems. While it’s easy to generate keys that can encrypt and decrypt data at will, it’s impossible from a practical standpoint for an adversary to calculate the numbers that make them work.
In 2019, a team of researchers factored a 795-bit RSA key, making it the biggest key size ever to be solved. The same team also computed a discrete logarithm of a different key of the same size.
The researchers estimated that the sum of the computation time for both of the new records was about 4,000 core-years using Intel Xeon Gold 6130 CPUs (running at 2.1GHz). Like previous records, these were accomplished using a complex algorithm called the Number Field Sieve, which can be used to perform both integer factoring and finite field discrete logarithms.
Quantum computing is still in the experimental phase, but the results have already made it clear it can solve the same mathematical problems instantaneously. Increasing the size of the keys won’t help, either, since Shor’s algorithm, a quantum-computing technique developed in 1994 by the American mathematician Peter Shor, works orders of magnitude faster in solving integer factorization and discrete logarithmic problems.
Researchers have known for decades these algorithms are vulnerable and have been cautioning the world to prepare for the day when all data that has been encrypted using them can be unscrambled. Chief among the proponents is the US Department of Commerce’s National Institute of Standards and Technology (NIST), which is leading a drive for post-quantum cryptography (PQC).
On Tuesday, NIST said it selected four candidate PQC algorithms to replace those that are expected to be felled by quantum computing. They are: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON, and SPHINCS+.
CRYSTALS-Kyber and CRYSTALS-Dilithium are likely to be the two most widely used replacements. CRYSTALS-Kyber is used for establishing digital keys two computers that have never interacted with each other can use to encrypt data. The remaining three, meanwhile, are used for digitally signing encrypted data to establish who sent it.
“CRYSTALS-Kyber (key-establishment) and CRYSTALS-Dilithium (digital signatures) were both selected for their strong security and excellent performance, and NIST expects them to work well in most applications,” NIST officials wrote. “FALCON will also be standardized by NIST since there may be use cases for which CRYSTALS-Dilithium signatures are too large. SPHINCS+ will also be standardized to avoid relying only on the security of lattices for signatures. NIST asks for public feedback on a version of SPHINCS+ with a lower number of maximum signatures.”
The selections announced today are likely to have significant influence going forward.
“The NIST choices certainly matter because many large companies have to comply with the NIST standards even if their own chief cryptographers don’t agree with their choices,” said Graham Steel, CEO of Cryptosense, a company that makes cryptography management software. “But having said that, I personally believe their choices are based on sound reasoning, given what we know right now about the security of these different mathematical problems, and the trade-off with performance.”
Nadia Heninger, an associate professor of computer science and engineering at University of California, San Diego, agreed.
“The algorithms NIST chooses will be the de facto international standard, barring any unexpected last-minute developments,” she wrote in an email. “A lot of companies have been waiting with bated breath for these choices to be announced so they can implement them ASAP.”
While no one knows exactly when quantum computers will be available, there is considerable urgency in moving to PQC as soon as possible. Many researchers say it’s likely that criminals and nation-state spies are recording massive amounts of encrypted communications and stockpiling them for the day they can be decrypted.
