The United States has standardized the first cryptographic algorithms that are resistant to hacking on quantum computers

Today, almost all sensitive data in the world is protected by the RSA (Rivest-Shamir-Adleman) asymmetric encryption scheme, which is almost impossible to crack using modern computers. But the emergence of quantum computers could radically change the situation. Therefore, the US National Institute of Standards and Technology (NIST) introduced three post-quantum cryptography encryption schemes.

Image source: unsplash.com

New standards should become an important element of cryptographic data protection. Previous NIST cryptography standards, developed in the 1970s, are used in virtually all devices, including Internet routers, phones and laptops. NIST Cryptography Group Leader Lily Chen is confident of the need for mass migration from RSA to new encryption methods: “Today public key cryptography is used everywhere and in all devices, our goal is to replace the protocol in every device, which is not easy.”

While most experts believe that large-scale quantum computers won’t be built for at least another decade, there are two good reasons to be concerned today:

• First, many devices that use RSA, such as cars or smart home components, will be around for at least another decade. Therefore, they need to be equipped with quantum-safe cryptography before they are released into service.
• Second, an attacker could store encrypted data today and decrypt it when sufficiently powerful quantum computers become available—a “collect now, decrypt later” concept.

Therefore, security experts in various industries are calling for the threat posed by quantum computers to be taken seriously. New encryption schemes are based on an understanding of the strengths and weaknesses of quantum computing, since quantum computers are superior to classical ones only in a fairly narrow range of tasks. Quantum-resistant cryptographic methods include:

• Lattice cryptography is based on the geometric shortest vector problem, which requires finding the point closest to the origin, which is incredibly difficult to do with a large number of dimensions.
• Isogonal cryptography uses elliptic curves for encryption, which promises high resistance to decryption.
• Error-correcting code-based cryptography relies on the difficulty of reconstructing the code structure from messages containing random errors.
• Hash tree-based public key cryptography is positioned as an extension of RSA.

Today, NIST considers lattice cryptography to be the most promising method. Back in 2016, the Institute announced a public competition for the best post-quantum encryption algorithm. 82 applications were received from development teams from 25 countries. Since then, the competition has gone through four qualifying rounds and ended in 2022 with four winning algorithms named. The opinions of the cryptographic community, industrial and academic circles, as well as interested government agencies were taken into account.

The four winning algorithms had sonorous names: CRYSTALS-Kyber, CRYSTALS-Dilithium, Sphincs+ and FALCON, but after standardization they received the type designation “Federal Information Processing Standard” (FIPS) with numbers 203–206. Today NIST announced the standardization of FIPS 203, 204 and 205. FIPS 206 is expected to be standardized towards the end of the year. FIPS 203, 204 and 206 are based on lattice cryptography, while FIPS 205 is based on hash functions.

Standards include computer code for encryption algorithms, instructions for its implementation, and intended use scenarios. There are three levels of security for each protocol, designed to ensure future standards should weaknesses or vulnerabilities be discovered in the algorithms.

Earlier this year, the cryptography community’s attention was drawn to a paper by Yilei Chen of Tsinghua University, who argued that lattice cryptography is in fact poorly protected against quantum attacks. But upon further review by the community, errors were found in Chen’s argumentation, and the authority of lattice cryptography was restored.

This incident highlighted a basic problem underlying all cryptographic schemes: there is no evidence that any of the mathematical problems on which the schemes are based are actually “hard”. The only real proof of the strength of encryption, even for standard RSA algorithms, is numerous unsuccessful cracking attempts over a long period of time.

Since post-quantum cryptography standards are still very “young”, their strength is constantly subject to doubts and hacking attempts, and each unsuccessful attempt only increases confidence in them. “People tried their best to crack this algorithm. A lot of people are trying, they are trying very hard, and this actually gives us confidence,” Lily Chen said on this occasion.

Of course, the new post-quantum encryption standards presented by NIST are relevant, but the work to transfer all devices to them has only just begun. It will take a long time and significant resources to completely protect data from decryption using future quantum computers. For example, LGT Financial Services spent 18 months and about half a million dollars on only partial implementation of new algorithms, and the costs of a complete transition were difficult to estimate.