Standardization of Post-Quantum Cryptography

Standardization is crucial for interoperability and security. To enable different devices from different manufacturers that are operated by different people to communicate with each other securely, the means of communication has to be agreed upon. Without standardization, chaos would ensue; imagine each person in a city using their own traffic rules.

The main building blocks which enable security features that require standardization are cryptographic primitives, such as the Advanced Encryption Standard (AES), Secure Hash Algorithm (SHA), RSA (PKCS #1) and the (elliptic-curve) Digital Signature Algorithm (ECDSA). However, with the advent of quantum computers, the existing standards no longer provide sufficient security.

Standardization bodies such as USA’s National Institute of Standards and Technology  (NIST) or the German Federal Office for Information Security  (BSI) play an important role. By considering the use cases and assets that need to be protected, as well as the state-of-the-art mathematical research intended to break the cryptography and the anticipated increases to computation capabilities, many governing bodies are recommending fit-for-purpose algorithms for the next 10, 15 and 20 years. To decide which security mechanism to use, the appropriate key lengths must be determined—and this is a difficult task. Large cryptographic key sizes offer increased computational security at the expense of performance and bandwidth while small keys are fast to use in practice but might turn out to be insecure.

In this article, we focus on the ongoing NIST post-quantum cryptographic standardization effort which recently announced its first set of winners.

How It All Started

As quantum research made rapid strides, academic and industrial communities started to explore the computational advantages quantum computers would bring, as well as the devastating impact on modern public-key cryptography. From academia, a dedicated venue to present research on post-quantum cryptography was initiated: the first was PQCrypto 2006  in Leuven, Belgium. The increase of academic attention to this topic combined with the advancements in quantum computing eventually resulted in a desire to standardize cryptographic algorithms which are secure against this quantum threat.

In February 2016, at the post-quantum cryptography conference, Dustin Moody of NIST gave a talk titled “Post-Quantum Cryptography: NIST’s Plan for the Future ”. Here a plan was proposed for a standardization process at the end of which the ‘winners’ would be drafted into a standard. In December 2016, a formal call for proposals  went out. About a year later 69 ‘complete and proper’ submissions were received for cryptographic functionalities of public-key encryption, key encapsulation mechanisms (KEMs) and digital signatures.

NXP Proposals

Among the proposed schemes, six of the key encapsulation mechanism proposals included an NXP security expert as a co-author. Over the course of three rounds, the 69 schemes were pruned to only 15 in 2020, with extraordinarily strong NXP involvement as five out of the initial six NXP expert’s submissions remained. These submissions are called CRYSTALS-Kyber,  Classic McEliece, SIKE, Frodo-KEM  and NTRU Prime . They represent a wide variety of the design space for post-quantum cryptography including lattices, codes and isogenies with each having their own advantages and disadvantages.

July 2022: Announcement of the Winners

At the end of the nearly six-year process, NIST announced the first selection of winners of their post-quantum cryptography standardization competition in July 2022. The sole winner for KEMs is the NXP co-authored CRYSTALS-Kyber, a lattice-based proposal that was selected due to its great performance, manageable key sizes and the confidence NIST has in its lasting security capabilities.

The primary winner for the digital signature category is CRYSTALS-Dilithium,  a lattice-based scheme recommended by NIST for general use thanks to its simple design that enables secure (embedded) implementation. NIST also selected two additional schemes: Falcon for its minimal signature and public-key size for mainly applications in internet protocols, and the conservative choice, SPHINCS+,  whose security is well-understood but performance and size lags behind CRYSTALS-Dilithium and Falcon. The CRYSTALS-Dilithium algorithm will be prioritized for standardization and was already recognized by NXP as a promising candidate, creating a secure boot proof-of-concept on the automotive S32G processor in collaboration with Blackberry. (You can watch more about the CRYSTALS-Dilithium in this co-hosted webinar with NXP and Blackberry).

What Will the Future Hold?

The selection of winners will ultimately lead to standards that are planned to be released by NIST in 2024, starting with CRYSTALS-Kyber and CRYSTALS-Dilithium. NIST is targeted to release the draft standards in 2023 and will seek feedback from the academic and industrial communities for the definition of parameter sets and potential (small) tweaks to the algorithms.

In addition to the winners of Round 3, the NIST competition continues into a fourth round. This includes 4 proposals for key encapsulation mechanisms: BIKE, Classic McEliece, HQC and SIKE. They represent a selection of algorithms that are not based on lattices and NIST expects to select two of them for standardization at the end of Round 4 after further study. NXP security experts are involved with Classic McEliece, a very conservative code-based proposal, and SIKE, an isogeny-based scheme whose public keys and ciphertexts are the smallest among all candidates submitted to the standardization competition.

Compared to NIST, the German BSI also recommends more conservative alternatives. Instead they argue for less structured options such as Classic McEliece and FrodoKEM for high-security applications, both co-authored by NXP security experts. This however comes at a noticeable performance penalty, as both have significantly larger keys than CRYSTALS-Kyber.

With all these options to support, interesting times are still ahead with NXP spearheading (side-channel) secure and efficient implementations for the embedded world.

Authors

Joppe W. Bos

Joppe W. Bos is a Technical Director and cryptographer at the Competence Center Crypto & Security (CCC&S) in the CTO organization at NXP Semiconductors. Based in Belgium, he is the technical lead of the Post-Quantum Cryptography team, and has authored over 20 patents and 50 academic papers. He is the co-editor of the IACR Cryptology ePrint Archive.

Christine Cloostermans

Christine Cloostermans is a senior cryptographer at Competence Center for Cryptography and Security (CCC&S) in the CTO organization at NXP Semiconductors. She acquired her doctorate from TU Eindhoven on topics related to lattice-based cryptography. Christine is a co-author on 10+ scientific publications, and has given many public presentations in the area of post-quantum cryptography. Beyond PQC, she is active in multiple standardization efforts, including IEC 62443 for the Industrial domain, ISO 18013 for the mobile driver’s license, and the Access Control Working Group of the Connectivity Standards Alliance.

Joost Renes

Joost Renes is a Senior Cryptographer at the Competence Center for Cryptography and Security (CCC&S) in the CTO organization at NXP Semiconductors. He holds a PhD in Cryptography from Radboud University in the Netherlands and is a developer of the NIST standardization proposal SIKE. He works towards solving the many challenges related to securely implementing post-quantum cryptography on resource-constrained systems, and integrating them into security-critical protocols.

Tobias Schneider

Tobias Schneider is a senior cryptographer at the NXP Competence Center for Cryptography and Security (CCC&S) in the CTO organization at NXP Semiconductors. He is also a member of the Post-Quantum Cryptography team. He received his PhD in cryptography from Ruhr-Universität Bochum in 2017 and authored over 25 international publications. His research topics include the physical security of cryptographic implementations, in particular of post-quantum cryptography, and cyber resilience.