PQC’s Standardization

Standardization is crucial for interoperability and security. To enable different devices from different manufacturers that different people operate 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.

Introduction

The foundational elements supporting security features that necessitate standardization primarily consist of cryptographic primitives, including widely-used algorithms such as the Advanced Encryption Standard (AES), Secure Hash Algorithm (SHA), RSA (PKCS #1), and the (elliptic-curve) Digital Signature Algorithm (ECDSA). However, the rise of quantum computers has rendered these established standards insufficient in providing the required level of security.

Key standardization bodies like the National Institute of Standards and Technology (NIST) in the USA or the German Federal Office for Information Security (BSI) play a crucial role in this context. These entities consider various factors, such as use cases, assets requiring protection, advancements in mathematical research targeting cryptographic vulnerabilities, and anticipated improvements in computational capabilities. They then recommend algorithms tailored for specific purposes over the next 10, 15, and 20 years. The challenge lies in determining appropriate key lengths, as larger cryptographic key sizes enhance computational security but can impact performance and bandwidth. In contrast, smaller keys are faster but may compromise security.

How did it start?

The journey’s origins can be traced back to the accelerated progress in quantum research, prompting both academic and industrial communities to delve into the potential computational advantages of quantum computers. Simultaneously, there was a growing awareness of the potential threats quantum computing posed to modern public-key cryptography. Responding to this, the academic community established a dedicated platform for research on post-quantum cryptography, with PQCrypto 2006 in Leuven, Belgium, being the inaugural event. The escalating academic focus on this subject and the rapid advancements in quantum computing led to a collective recognition of the need to standardize cryptographic algorithms resilient against quantum threats.

Dustin Moody of NIST presented a pivotal talk titled “Post-Quantum Cryptography: NIST’s Plan for the Future,” unveiling a comprehensive plan for a standardization process in February 2016 at the post-quantum cryptography conference. The envisaged outcome was the identification of ‘winning’ algorithms that would be incorporated into a standardized framework. This vision materialized in December 2016 when a formal call for proposals was issued. Approximately a year later, the response was robust, with 69 submissions deemed ‘complete and proper’ for cryptographic functionalities encompassing public-key encryption, key encapsulation mechanisms (KEMs), and digital signatures.

Winners’ Announcement in July 2022

After an extensive process spanning nearly six years, NIST concluded its post-quantum cryptography standardization competition in July 2022, unveiling the inaugural set of winners. Its selection was driven by stellar performance, manageable key sizes, and NIST’s confidence in its enduring security capabilities.

Turning to the digital signature category, the primary champion is CRYSTALS-Dilithium, another lattice-based scheme recommended by NIST for general use. Its straightforward design facilitates secure (embedded) implementation. NIST also recognized two additional schemes: Falcon, acknowledged for its minimal signature and public-key size, ideal for applications in internet protocols, and the conservative option, SPHINCS+, known for its well-understood security despite trailing in performance and size compared to CRYSTALS-Dilithium and Falcon. Notably, CRYSTALS-Dilithium takes precedence for standardization and has already earned acclaim from NXP as a promising candidate, demonstrated by a secure boot proof-of-concept on the automotive S32G processor in collaboration with Blackberry.

Plan for the future

The culmination of the selection process will pave the way for anticipated standards slated for release by NIST in 2024, with the initial focus on CRYSTALS-Kyber and CRYSTALS-Dilithium.

Beyond the winners of Round 3, the NIST competition extends into a fourth round, featuring four proposals for key encapsulation mechanisms: BIKE, Classic McEliece, HQC, and SIKE. These proposals, not lattice-based, offer diverse algorithmic approaches, and NIST plans to select two for standardization after Round 4 following further scrutiny. Notably, NXP security experts contribute to Classic McEliece, a conservative code-based proposal, and SIKE, an isogeny-based scheme known for having the smallest public keys and ciphertexts among all competition candidates.

In contrast to NIST, the German BSI recommends more conservative alternatives, advocating for less structured options such as Classic McEliece and FrodoKEM for high-security applications, both co-authored by NXP security experts. However, it’s essential to acknowledge that this choice entails a noticeable performance penalty, given the significantly larger keys compared to CRYSTALS-Kyber.

Conclusion

In conclusion, the journey toward post-quantum cryptography underscores the critical importance of standardization in ensuring interoperability and security. As quantum computers pose a threat to established cryptographic standards, the efforts led by institutions like NIST and the German BSI become pivotal in navigating this evolving landscape. The meticulous selection process, spanning years and culminating in the announcement of winners, reflects a commitment to identifying resilient algorithms against quantum threats. The recognition of CRYSTALS-Kyber and CRYSTALS-Dilithium as initial focal points for standardization marks a significant milestone, with anticipated standards set to be released in 2024.

The ongoing competition, extending into a fourth round, introduces alternative proposals and demonstrates the continuous adaptability required in the face of quantum advancements. As the cryptographic community collaborates to define the future of secure communication, the balance between security, performance, and adaptability remains at the forefront of considerations for the post-quantum era.