Getty Images
In the not-too-distant future — perhaps just a decade away, no one knows exactly how long — the cryptography that protects your banking transactions, instant messages, and medical records from prying eyes will break dramatically with the advent of quantum computing. On Tuesday, a US government agency named four replacement encryption schemes to prevent this cryptopocalypse.
Some of the most widely used public key encryption systems, including those that use the RSA, Diffie-Hellman, and Elliptic Curve Diffie-Hellman algorithms, rely on math to protect sensitive data. These math problems include (1) factoring the large composite number of a key (commonly referred to as N) to derive its two factors (commonly referred to as P and Q) and (2) calculating the discrete logarithm at which keys are 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 adversary to calculate the numbers that make them work.
In 2019, a team of researchers considered 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 estimate that the sum of the computation time for both new records was approximately 4,000 core years with Intel Xeon Gold 6130 CPUs (running at 2.1 GHz). Like previous records, these were achieved using a complex algorithm called the Number Field Sieve, which can be used to perform integer factoring as well as discrete logarithms with finite fields.
Quantum computing is still in its experimental stage, but the results have already made it clear that it can solve the same mathematical problems immediately. Increasing the keys won’t help either, since Shor’s algorithm, a quantum computing technique developed in 1994 by American mathematician Peter Shor, works orders of magnitude faster at solving integer factorization and discrete logarithmic problems.
Researchers have known for decades that these algorithms are vulnerable and are warning the world to prepare for the day when all data encrypted using these algorithms can be decrypted. The main proponents are the US Department of Commerce’s National Institute of Standards and Technology (NIST), which is at the forefront of post-quantum cryptography (PQC).
On Tuesday, NIST said it has selected four candidate PQC algorithms to replace those expected to be felled by quantum computing. These are: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON and SPHINCS+.
CRYSTALS-Kyber and CRYSTALS-Dilithium are probably the two most commonly used replacements. CRYSTALS-Kyber is used to capture digital keys that two computers that have never interacted with each other can use to encrypt data. The other three, meanwhile, are used to digitally sign encrypted data to determine 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 as there may be instances where CRYSTALS-Dilithium signatures are too large. SPHINCS+ will also be standardized to avoid relying solely on the security of signature grids. NIST is asking for public feedback about a version of SPHINCS+ with a lower maximum signature count.”
The selections announced today are likely to have a significant impact going forward.
“The NIST choices certainly matter because many large companies are required to comply with NIST standards even if their own key cryptographers disagree with their choices,” said Graham Steel, CEO of Cryptosense, a crypto management software company. makes. “But that said, I personally believe that their choices are based on good reasoning, given what we now know about the safety of these various math problems and how they interact with performance.”
Nadia Heninger, an associate professor of computer science and engineering at the University of California, San Diego, agreed.
“The algorithms NIST chooses will be the de facto international standard, barring unexpected last-minute developments,” she wrote in an email. “Many companies have waited with bated breath for these choices to be announced so they can implement them as soon as possible.”
While no one knows exactly when quantum computers will be available, it is very urgent to move to PQC as soon as possible. Many researchers say it’s likely that criminals and nation-state spies are recording and storing massive amounts of encrypted communications for the day they can be decrypted.
