The cryptocurrency is near! NIST is rolling out new encryption standards to prepare

In the not-too-distant future – as little as a decade, perhaps no one knows exactly how long – the cryptography that protects your bank transactions, chat messages and medical records from prying eyes will break spectacularly with the advent of quantum computing. On Tuesday, a US government agency designated four replacement encryption systems to avert this cryptocurrency.

Some of the most commonly used public key encryption systems – including those using RSA, Diffie-Hellman and elliptical curve Diffie-Hellman algorithms – rely on mathematics to protect sensitive data. These mathematical problems include (1) factorizing a key’s large compound number (usually denoted as N) to derive the two factors (commonly denoted as P and Q) and (2) calculating the discrete logarithm on which keys are based.

The security of these cryptosystems depends entirely on the difficulty of classical computers in solving these problems. Although it is easy to generate keys that can encrypt and decrypt data as desired, it is impossible from a practical point of view for an opponent to calculate the numbers that make them work.

In 2019, a team of researchers took 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 time for both of the new records was approximately 4,000 core years using Intel Xeon Gold 6130 CPUs (running at 2.1 GHz). Like previous records, these were obtained using a complex algorithm called Number Field Sieve, which can be used to perform both integer factorization and discrete final field logarithms.

Quantum data processing is still in the experimental phase, but the results have already made it clear that it can solve the same mathematical problems immediately. Increasing the size of the keys does not help either, since Shor’s algorithm, a quantum calculation 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 that these algorithms are vulnerable and have warned the world to prepare for the day when all data encrypted with them can be decrypted. The head of the proposers is the US Department of Commerce’s National Institute of Standards and Technology (NIST), which is leading the way in post-quantum cryptography (PQC).

On Tuesday, NIST said it chose four candidate PQC algorithms to replace those expected to be fielded by quantum computing. They are: CRYSTALS-Cyber, CRYSTALS-Dilithium, FALCON and SPHINCS +.

CRYSTALS-Cyber ​​and CRYSTALS-Dilithium are probably the two most commonly used substitutes. CRYSTALS-Cyber ​​is used to establish digital keys that two computers that have never interacted with each other can use to encrypt data. The remaining three are meanwhile used for digital signing of encrypted data to determine who sent them.

“CRYSTALS-Cyber ​​(key establishment) and CRYSTALS-Dilithium (digital signatures) were both chosen for their strong security and excellent performance, and NIST expects them to work well in most applications,” wrote NIST officials. “FALCON will also be standardized by NIST as there may be use cases where CRYSTALS-Dilithium signatures are too large. SPHINCS + will also be standardized to avoid relying solely on the security of the grid for signatures. NIST requests public feedback on a version of SPHINCS + with a lower number of maximum signatures. “

The elections announced today are likely to have a significant impact going forward.

“The NIST choices certainly matter because many large companies have to comply with NIST standards even if their own chief cryptographers do not agree with their choices,” said Graham Steel, CEO of Cryptosense, a company that creates cryptography management software. “Having said that, I personally believe that their choice is based on sound reasoning, given what we know right now about the safety of these various mathematical problems, and the balance of 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, except for any unexpected last-minute developments,” she wrote in an email. “Many companies have been waiting with bated breath for these choices to be announced so they can implement them ASAP.”

Although no one knows exactly when quantum computers will be available, there is a significant urgency to move to PQC as soon as possible. Many researchers say that it is likely that criminals and nation-state spies register huge amounts of encrypted communications and store them for the day they can be decrypted.