In the not-too-distant future—maybe just a decade, no one knows for sure how long—the cryptography that protects your banking transactions, chat messages, and medical records from prying eyes will spectacularly break with the advent of quantum computing. On Tuesday, a US government agency named four backup encryption schemes to avert this cryptopocalypse.
Some of the most widely used public-key cryptosystems—including those using the RSA, Diffie-Hellman, and Diffie-Hellman elliptic curve algorithms—rely on mathematics to protect sensitive data. These math problems involve (1) factoring the large composite number of a key (usually denoted N) to derive its two factors (usually denoted P and Q), and (2) computing the discrete logarithm on which the keys based.
The security of these cryptosystems depends entirely on the difficulty of classical computers in solving these problems. While it’s easy to generate keys that can encrypt and decrypt data at will, it’s practically impossible for an attacker to calculate the numbers that make them work.
In 2019, a team of researchers factored a 795-bit RSA key, making it the largest key size ever solved. The same team also calculated a discrete logarithm of another key of the same size.
The researchers estimated that the sum of the computation times for both new records using Intel Xeon Gold 6130 CPUs (at 2.1 GHz) was about 4,000 core years. Like previous records, these were created using a complex algorithm called Number Field Sieve, capable of performing both integer factors and discrete finite field logarithms.
Quantum computing is still in the experimental phase, but the results have already shown that it can solve the same mathematical problems immediately. Even increasing the size of the keys does not help, since Shor’s algorithm, a quantum computing method developed by the American mathematician Peter Shor in 1994, works orders of magnitude faster when solving integer factorizations and discrete logarithmic problems.
Researchers have known for decades that these algorithms are vulnerable and are warning the world to brace for the day when all data encrypted with them can be decrypted. Proponents include the US Department of Commerce’s National Institute of Standards and Technology (NIST), which is driving a post-quantum cryptography (PQC) initiative.
On Tuesday, NIST said it had selected four candidate PQC algorithms to replace those expected to be felled by quantum computing. They are: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON and SPHINCS+.
CRYSTALS-Kyber and CRYSTALS-Dilithium are probably the two most commonly used substitutes. CRYSTALS-Kyber is used to create digital keys that two computers that have never interacted with each other can use to encrypt data. The remaining three, meanwhile, are used to digitally sign encrypted data to verify who sent it.
“CRYSTALS-Kyber (key generation) and CRYSTALS-Dilithium (digital signatures) were both selected for their strong security and excellent performance, and NIST expects them to perform well in most applications,” NIST officials wrote. “FALCON is also standardized by NIST as there may be use cases for which CRYSTALS dilithium signatures are too large. SPHINCS+ will also be standardized to avoid relying solely on grid security for signatures. NIST is requesting public feedback on a version of SPHINCS+ with a lower maximum signature count.”
The selection announced today is expected to have a significant impact going forward.
“The NIST decisions certainly matter, as many large companies are required to comply with NIST standards even if their own chief cryptographers disagree with their decisions,” said Graham Steel, CEO of Cryptosense, a company that makes cryptographic management software . “Nevertheless, I personally believe their decisions are based on sound reasoning given what we currently know about the safety of these various math problems and the trade-off with performance.”
Nadia Heninger, associate professor of computer science and engineering at the University of California, San Diego, agreed.
“The algorithms that NIST selects will be the de facto international standard barring unexpected last-minute developments,” she wrote in an email. “Many companies have been waiting with bated breath for these decisions to be announced so they can implement them as soon as possible.”
Although no one knows exactly when quantum computing will be available, there is great urgency to move to PQC as soon as possible. Many researchers find it likely that criminals and nation-state spies are recording vast amounts of encrypted communications and hoarding them for the day they can be decrypted.