English | EN 
Last week, NIST announced the first batch of four finalists in the standardization process for post-quantum cryptography. The much-anticipated event is an important milestone in the countdown towards Y2Q: the year that quantum computers will be strong enough to break RSA and ECC-based cryptography. The imminent threat of quantum computers to cybersecurity, shown by the Y2Q count-down clock from the cloud security alliance, looms ahead of us. In the urgent, and complex migration to quantum-safe technology secure, performing, and standardized post-quantum cryptography is essential. So what happened, what is the significance of the announcement, and what is next?
What happened?
NIST, the US National Institute for Standardization and Technology, has selected four post-quantum cryptography algorithms to be standardized (named CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon and Sphincs+), while four additional algorithms (BIKE, Classic McEliece, HQC, and SIKE) will remain under consideration for further study. It is the result of the third round, while the standardization project started six years ago with an initial submission of 82 candidate algorithms. Over the past six years, candidates were evaluated and selected based on security, cost and performance, and algorithm and implementation characteristics. Only a few months ago, candidate algorithm Rainbow was shown to be insecure, even for classical attacks, which shows the importance of a careful evaluation process. Over the next few years, the standardization process will continue, until a complete standard is expected by 2024. In the meanwhile, algorithm implementation might still vary slightly, although no major updates are expected.
Early on, NIST realized that multiple algorithms for different scenarios were needed.
NIST has selected algorithms for two classes of cryptographic principles: digital signatures used for authentication and key exchange for general message encryption. In these use cases, post-quantum cryptography is to replace RSA and Diffie-Hellman respectively. For each class, multiple algorithms are selected because different properties are required in various scenarios. These characteristics of post-quantum cryptography, such as key size, verification and signing performance can be significantly different from conventional cryptography. NIST recommends the following use cases for the selected algorithms:
- Kyber for accessing secure websites
- Dilithium for general-purpose digital signatures
- Falcon for use cases that require small-sized signatures
- SPHINCS+ as a backup option for signatures
Kyber, Dilithium and Falcon are based on the mathematical principle of structured lattices, while SPHINCS+ uses hash functions.
No clear-cut drop-in replacements
Although the announcement is a great step in replacing conventional algorithms with quantum-safe technology, there are many implementation challenges ahead. Due to the sometimes large public key and signature size, and low verification and signing performance of the current post-quantum cryptographic algorithms, there is not always a clear-cut drop-in replacement. Two situations, in particular, require careful selection and experimentation.
First, post-quantum cryptography might not fit well in resource constraint devices, such as IoT devices, or embedded systems. Contrary to our personal computers, these devices are characterized by small amounts of RAM, limited storage, and clock speeds measured in Megahertz, not Gigahertz. At the same time, these are some of the devices that are controlling our vital infrastructure and must remain secure, but still require cryptography that does not take seconds, let alone minutes, to execute. Additionally, IoT devices often have long system life. Cars, for example, are on the roads for decades, which makes it more difficult to update cryptography or hardware resources.
Second, selected signature algorithms are not a perfect fit for web applications. TLS, the protocol to communicate between browsers, users, and servers in countless applications, assume small and fast signatures. It includes requires several six signatures, so small performance losses can quickly stack up. The result is longer lead times to replace signatures. Not only need browsers and servers need to be updated but also certificate authorities (CAs) and everyone’s certificate management needs to be changed. The ubiquitous use of TLS and the vast amount of parameters and variables make it a daunting puzzle to secure systems such as payments infrastructure. Measuring the impact of quantum-safe protocols and configurations in particular environments is a good idea toward choosing the right protocols and configurations. This process is likely to take significant time, which is already scarce in the countdown to Y2Q.
To accommodate for these limitations, NIST will continue to look for signatures that are not lattice-based and signatures with small sizes, and fast verification.
Performance analyses of various algorithms by Cloudflare
Agility is the way forward
Clearly, the standardization by NIST only marks the beginning of a complicated migration to quantum-safe technology. Over the next few years, algorithms will continue to be fine-tuned until the final target date in 2024. Even beyond that, we can expect cryptography to have a limited shelf life. Just like 3DES, SHA-1 or MD5 have been considered broken in time due to advanced insight, we should expect that the four finalists will be broken in time. The limited validity of cryptographic algorithms and their implementations and their ubiquity calls companies to respond to these changes in a much faster and better-managed way. Crypto agility, defined by NIST as the ability of a security system to be able to rapidly switch between algorithms, cryptographic primitives, and other encryption mechanisms without the rest of the system’s infrastructure being significantly affected by these changes, seems to be the way forward. Luckily, crypto agility can be implemented today using available technology — while it also poses a big organizational challenge to companies. Proactive companies that understand the imminent threat of quantum computers, can therefore take the steps today, to protect against one of the largest security threats.
