International PQC Requirements

International government regulatory bodies are defining the quantum-resistance requirements to be followed by technology vendors used in national or government security systems. This document analyzes international post-quantum cryptography (PQC) requirements. It aims to identify alignment and misalignment areas which could pose challenges for international vendor compliance and interoperability.

We surveyed PQC requirements laid out in various country cryptographic requirement documents in order to assess if they align or if their potential misalignments could pose challenges for international vendors that would need to comply with them. The country requirements we surveyed as of May 2024 were ones that had added PQC algorithms in their documents and included CNSA 2.0 (USA), NIST (USA), NCSC (UK), CCCS (Canada), BSI (Germany), NLNCSA (Netherlands), ANSSI (France), EU Commission, Australia, Norway, New Zealand, Japan, South Korea, UAE, Saudi Arabia, Singapore, and China. Some countries had defined transition plans and recommended quantum-resistant algorithms. Other countries were tracking the new algorithms without prescriptive recommendations. Others, like South Korea and China, were working on standardizing their own algorithms which are not the same algorithms as US NIST’s.

In more detail, there were misalignments regarding approved quantum-resistant KEMs by various national requirements. NIST is standardizing ML-KEM and has announced they will standardize one more KEM after Round 4. CNSA 2.0 recommends ML-KEM’s Level 5 variant only (ML-KEM-1024) for use in US National Security Systems (NSS). NCSC UK recommends ML-KEM-768 (Level 3). BSI Germany recommends FrodoKEM-976 and FrodoKEM-1344, mceliece460896, mceliece6688128 and mceliece8192128. BSI also announced they will include ML-KEM-768 and ML-KEM-1024 in their recommendations after ML-KEM is standardized by NIST. ANSSI France recommends ML-KEM-768 or ML-KEM-1024 and FrodoKEM as a conservative option. NLNCSA Netherlands recommends ML-KEM-768 and considers Classic McEliece and FrodoKEM as acceptable. In summary, as of May 2024, some country PQC requirements endorse FrodoKEM and Classical McEliece whereas most endorse a parameter of ML-KEM. Requiring vendors to support and certify implementations of three KEMs to comply with certain requirements would introduce overhead for implementers. Fortunately, all surveyed country PQC requirements which align with NIST algorithms, generally recommend some variant of ML-KEM which means that vendors have one KEM to implement as a common denominator. Note that a limited set of countries (discussed below) ran their own PQC projects which means they may end up requiring completely different KEMs.

There were less misalignments regarding general quantum-resistant signature algorithms, but there are more options. The IETF has already standardized Stateful Hash-Based Signatures (HBS) LMS and XMSS. NIST is standardizing ML-DSA, FN-DSA and SLH-DSA and potentially one more signature after Round 4. CNSA 2.0 recommends the Level 5 parameter of ML-DSA, ML-DSA-87 as a general signature, and single-tree LMS/XMSS for firmware signing. It is not planning to recommend SLH-DSA. NCSC UK recommends ML-DSA-65, SLH-DSA and LMS/XMSS. BSI Germany recommends SLH-DSA or ML-DSA Levels 3 and 5 and LMS/XMSS in their multi-tree variants for long-term signatures. ANSSI France recommends ML-DSA, FN-DSA Level 3 and 5, SLH-DSA and LMS/XMSS. NLNCSA Netherlands recommends all NIST signatures and LMS/XMSS. In summary, recommendations include some parameter of the NIST signatures and Stateful HBS. CNSA 2.0 and NCSC consider HBS signatures more appropriate for firmware/software signing; CNSA 2.0 makes LMS/XMSS mandatory for software/firmware signing, but other recommendations do not distinguish between firmware and general signings. ML-DSA, SLH-DSA and/or LMS/XMSS (single or multi-tree) are the common denominator from these recommendations (except for CNSA 2.0 not recommending SLH-DSA). Given that the options are three, endorsing all of these schemes introduces flexibility and complexity for vendors who still need to converge on signature algorithms with their pros and cons for their use-cases and compliance requirements. For example, vendors compelled to support for CNSA 2.0 LMS/XMSS will have to deal with state management concerns of Stateful Signatures. As another example, a vendor wanting to avoid the state management risk could chose SLH-DSA, but then it would not be able to comply with CNSA 2.0. Another challenge is how regulating bodies are expecting to verify that the signer is not reusing state. NIST SP 800-208 introduces requirements for ensuring these signatures are properly used, but creates further challenges for signers that want to comply. Hardware Security Module vendors have shared this issue with NIST in various fora. NIST is currently considering options, but generally managing state and providing flexibility for compliance is not trivial.

There was mostly alignment regarding PQ hybrid key exchange in the surveyed requirements. NIST approves it for FIPS in SP 800-56C (Section 2), with possible updates/clarifications coming with the finalization of FIPS 203. CNSA 2.0 tolerates hybrid due to protocol standards, product availability, or interoperability requirements, but recommends pure PQ especially after its set cut-off dates within 10 years. NCSC UK accepts PQ hybrids as an “interim measure”. BSI Germany and ANSSI France recommend hybrid key exchange as well. NLNCSA Netherlands also makes recommendations for hybrids. Similarly, for the European commission documentation. In summary, deploying hybrid key exchange is acceptable with requirements with the exception of CNSA 2.0 where it is only tolerated for a few years.

Requirements did not fully align regarding PQ hybrid signatures. US NIST will standardize three new PQ signatures initially and one more after Round 4, but has not recommended or rejected hybrid signatures. CNSA 2.0 recommends only pure PQ signing. NCSC UK “prefers” pure PQ signatures over an interim hybrid PQ approach and recommends a flexible transition if hybrid is chosen. BSI Germany requires hybrid signatures unless they are HBS which can be used on their own. The same applies to ANSSI France recommendations. NLNCSA Netherlands recommends hybridization in general. EU Commission recognizes there “may” be a need for hybridization. Thus, some countries (mostly in Europe) require hybrid signatures except for HBS, whereas NCSC and NSA recommend against hybrid signatures. They recognize that hybrid signatures would mean two PKI migrations which is not trivial.

There were some misalignments regarding the quantum resistance of hash functions in the surveyed requirements. NIST still recommends SHA-256 or higher. CNSA 2.0 requires SHA-384. ANSSI requires SHA-384. BSI Germany and NCSC UK consider SHA-256 secure. Some countries are more conservative than others. Generally, SHA-256 and SHA-384 are of the SHA2 family and are generally supported in implementations and standards. Thus, these requirements do not pose significant challenges for vendors that would need to comply except for some special use-cases.

There were some misalignments regarding AES sizes as well. US NIST considers AES-128 secure for years to come even if a cryptanalytically-relevant quantum computer became a reality. CNSA 2.0 has been requiring AES-256 even before the quantum computing risk. NCSC UK considers AES-128 secure. BSI Germany recommends AES-128 as well. ANSSI France recommends AES-256. So, as in the previous cases, for AES some countries are more conservative than others. Although there is misalignment with requirements regarding symmetric encryption, AES-256 and AES-128 are available in almost all implementations and standards. Thus, these misalignments do not pose significant challenges for vendors that would need to comply except for some special use-cases.