Next steps in preparing for post-quantum cryptography

In the NCSC's 2020 white paper, Preparing for Quantum Safe Cryptography, we described the threat that quantum computers pose to current cryptography, and the work by organisations such as the US National Institute of Standards and Technology (NIST) and the European Telecommunications Standards Institute (ETSI) to counter this threat.

Quantum computers use properties of quantum mechanics to compute in a fundamentally different way from today's digital, 'classical', computers. They are, theoretically, capable of performing certain computations that would not be feasible for classical computers. Although advances in quantum computing technology continue to be made, quantum computers today are still limited, and suffer from relatively high error rates in each operation they perform.

In the future, it is possible that error rates can be lowered such that a large, general-purpose quantum computer could exist. It is, however, hard to predict when this may happen as many engineering and physical challenges must be overcome first. Many nations are investing heavily in quantum computing, and assuming developers overcome these challenges in future, most traditional public key cryptography (PKC) algorithms in use today will be vulnerable to attack. A quantum computer that will be able to run these attacks is referred to as a cryptographically-relevant quantum computer (CRQC).

Traditional PKC includes algorithms based on integer factorisation (such as RSA), and algorithms based on the discrete logarithm problem (such as Finite Field Diffie-Hellman, ECDH, DSA, ECDSA, EdDSA). These algorithms are primarily used for:

• key establishment (used to agree a shared cryptographic key for secure communication)
• digital signatures (used to underpin proof-of-identity and trust on a network)

For key establishment and encryption, there is a risk from an attacker collecting and storing data today and decrypting it at some point in the future. Given the cost of storing vast amounts of old data for decades, such an attack is only likely to be worthwhile for very high-value information. This means that for organisations that need to provide long-term cryptographic protection of very high-value data, the possibility of a CRQC in the future is a relevant threat now.

The threat to digital signatures is that an adversary in possession of a CRQC could forge signatures to impersonate the legitimate private key owner, or tamper with information whose authenticity is protected by a digital signature. This attack should be considered before a CRQC exists, particularly when deploying keys for high-value trust anchors that are intended to have a long operational lifetime.

In contrast with PKC, the security of symmetric cryptography is not significantly impacted by quantum computers, and existing symmetric algorithms with at least 128-bit keys (such as AES) can continue to be used. The security of hash functions such as SHA-256 is also not significantly affected, and secure hash functions can also continue to be used.

The best mitigation against the threat of quantum computers to traditional PKC is post-quantum cryptography (PQC). Also known as 'quantum-safe cryptography' or 'quantum-resistant cryptography', PQC algorithms will replace the vulnerable PKC algorithms used today for both key establishment and digital signatures.

The security of PQC algorithms is based on mathematical problems that are believed to be intractable for both classical and quantum computers. These algorithms will not necessarily be drop-in replacements for the current PKC algorithms in protocols or systems, so system owners should begin planning for the migration to PQC.

For users of commodity IT, such as those using standard browsers or operating systems, the switchover to PQC will be delivered as part of a software update and should happen seamlessly (ideally without end-users even being aware). This process has begun already, with new PQC algorithms being used in conjunction with traditional PKC algorithms. To ensure devices are updated to PQC when it is available, system owners should ensure they follow the NCSC’s guidance on keeping devices and software up to date.

System owners of enterprise IT (such as those who own IT systems designed to meet the demands of a large organisation) should communicate with their IT system suppliers about their plans for supporting PQC in their products.

For a minority of systems with bespoke IT or operational technology, such as those that implement PKC in proprietary communications systems or architectures, system and risk owners will need to choose which PQC algorithms and protocols are best to use.

Technical system and risk owners of both enterprise and bespoke IT should begin or continue financial planning for updating their systems to use PQC. As systems are updated in-service or replaced as they come to the end of their supported lifecycle, new IT should either use PQC or be capable of being upgraded to PQC once robust implementations based on final standards are available. These PQC upgrades can be planned to take place within broader technology refreshes.

Since 2016, NIST has been running a process to standardise PQC algorithms, backed up by academic scrutiny from the international cryptography community. This process has been followed closely by standards-defining organisations including:

• the Internet Engineering Task Force (IETF), who have been working on updating their protocols to be resistant against a quantum computer
• ETSI, who have been producing migration and deployment guidance

In August 2024, NIST published one algorithm standard for key establishment:

• ML-KEM (CRYSTALS-Kyber)

and two additional algorithm standards for digital signatures:

• ML-DSA (CRYSTALS-Dilithium)
• SLH-DSA (SPHINCS+)

These algorithms provide a vital first step in securely migrating systems to post-quantum cryptography. However, more work will still be required to create trusted implementations of these algorithms that can be used in protocols and systems. The NCSC recommends that operational systems only use PQC based on robust implementations of these final standards. Implementations based on earlier draft standards may not be fully compatible with the final standards.

These algorithms will need to be implemented in protocols before they can be used on the internet and in other networks. The IETF is in the process of updating the most widely-used security protocols. This includes ensuring that PQC algorithms can be incorporated into key exchange and signature mechanisms in existing protocols such as TLS and IPsec. IETF implementations of post-quantum protocols are subject to change until they are published as RFCs. The NCSC strongly advises that operational systems should use protocol implementations based on RFCs, not on Internet Drafts.

Note: Two previously standardised, stateful hash-based signature algorithms also offer protection against a quantum computer, but can only be used in a subset of use cases. They are Leighton-Micali Signatures (LMS) and eXtended Merkle Signature Scheme (XMSS).

The following table gives the NCSC recommended algorithms, their functions, and specifications:

The above algorithms support multiple parameter sets that offer different levels of security. The smaller parameter sets generally require less power and bandwidth, but also have lower security margins. Conversely, the larger parameter sets provide higher security margins, but require greater processing power and bandwidth, and have larger key sizes or signatures. The level of security required can vary according to the sensitivity and the lifetime of the data being protected, the key being used, or the validity period of a digital signature. The highest security level may be useful for key establishment in cases where the keys will be particularly long lived or protect particularly sensitive data that needs to be kept secure for a long period of time. It may also be useful for digital signatures where the keys have a particularly long lifetime, such as in a root of trust.

Note that:

• All of these parameter sets provide an acceptable level of security for personal, enterprise and OFFICIAL-tier government information.
• ML-KEM and ML-DSA are algorithms suitable for general purpose use. The NCSC recommends ML-KEM-768 and ML-DSA-65 as providing appropriate levels of security and efficiency for most use cases.
• Users may wish to use the smaller parameter sets in situations where key/signature size is a consideration, or where it may help address performance issues, such as in constrained devices.

Hash-based signatures

Hash-based signatures such as SLH-DSA, LMS and XMSS rely on different security assumptions than ML-DSA. They are not suitable for general purpose use as the signatures are large and the algorithms are much slower than ML-DSA. However, these algorithms may be a good fit for use cases such as signing firmware and software where speed is not a bottleneck.

For LMS and XMSS, the security of these algorithms critically depends on users correctly managing the state (that is, knowing which one-time keys have been used for signing so it can be guaranteed that they are never used again). Cases where state management is a more tractable problem include firmware and software signing. ETSI have created advice on how to do this in their Technical Report TR 103 692 v1.1.1. LMS and XMSS should only be used in situations where it is possible to manage state in a trusted manner for the lifetime of the signing key.

SLH-DSA provides a more robust alternative for situations where it may be difficult or impossible to guarantee a one-time key is not re-used, as state management is not straightforward and mistakes can be detrimental to security. This increased robustness comes with significantly larger signature sizes and greater signing time than either LMS or XMSS, although the verification performance is similar.

A PQ/T hybrid scheme (as defined in this IETF Draft) is one that combines one (or more) PQC algorithms with one (or more) traditional PKC algorithms where all component algorithms are of the same type. For example, a PQC signature algorithm combined with a traditional PKC signature algorithm to give a PQ/T hybrid signature.

There are greater costs to PQ/T hybrid schemes than those with a single algorithm. PQ/T hybrid schemes will be more complex to implement and maintain and will also be less efficient. However, there may sometimes be a need for a PQ/T hybrid scheme, due to interoperability, implementation security, or constraints imposed by a protocol or system:

Interoperability

In a large network, it will be necessary to adopt a phased approach to the introduction of PQC. This will lead to a period where both PQC and traditional PKC algorithms need to be supported simultaneously. Flexible protocols incorporating PQ/T hybrid schemes will make it possible for systems with different security policies to interoperate, and should also allow for a migration to a PQC-only future.

Implementation security

PQC is an emerging technology and, while NIST has a robust process to ensure the security of the PQC algorithms, it will take time for assurance in implementations of these algorithms within protocols and systems to be developed. Therefore, users may wish to consider using PQC in combination with traditional PKC with the aim of building a system which remains secure, even if one of the implementations is insecure.

Protocol constraints

Some protocols may have technical constraints that mean it is difficult to remove the traditional PKC algorithm when adding support for PQC. An example of this is the need to avoid IP layer fragmentation in IKEv2.

Additional considerations for PQ/T hybrid schemes

There are many ways to combine a PQ key establishment algorithm with a traditional key establishment algorithm to obtain a PQ/T hybrid key establishment scheme. For example, using a PQ/T hybrid key establishment mechanism such as in the draft for Hybrid TLS (Hybrid key exchange in TLS 1.3) or at the protocol level such as in the design for IKE (RFC 9370). These two protocols have been modified to incorporate PQ/T hybrid schemes in a relatively simple and backwards-compatible way.

PQ/T hybrid key establishment mechanisms should be designed carefully to ensure the hybridisation mechanism does not allow additional attacks.

Proposed PQ/T hybrid schemes for authentication can be significantly more complex than those used for confidentiality, due to the need to make sure both signatures verify in a robust way. There has also been significantly less research activity into PQ/T schemes for authentication than for confidentiality, and there is not yet guidance or a consensus on how to do this in a secure way.

Public key infrastructures (PKIs) make use of authentication algorithms to create, store, verify and revoke digital certificates. Within a PKI, it is difficult to change an individual signature algorithm in isolation. PQ/T hybrid authentication within a PKI requires either a PKI which can generate and sign traditional and post-quantum digital signatures, or two parallel PKIs (one for traditional and one for post-quantum digital signatures). This additional complexity and the difficulty in migrating PKIs mean that a single migration to a fully post-quantum PKI is preferred to adopting an intermediate PQ/T hybrid PKI.

Recommendations on PQ/T hybrid schemes

In the future, if a CRQC exists, traditional PKC algorithms will provide no additional protection against an attacker with a CRQC. At this point, a PQ/T hybrid scheme will provide no more security than a single post-quantum algorithm but with significantly more complexity and overhead. If a PQ/T hybrid scheme is chosen, the NCSC recommends it is used as an interim measure, and it should be used within a flexible framework that enables a straightforward migration to PQC-only in the future.

With this in mind, technical system and risk owners should weigh the reasons for and against PQ/T hybrid schemes including interoperability, implementation security, and protocol constraints, as well as the complexity, cost of maintaining a more complex system, and the need to complete the migration twice (once to a PQ/T hybrid scheme and again to PQC-only algorithms as a future end state).

• Most PKC algorithms in use today will be vulnerable to a CRQC. The best mitigation against the threat of quantum computers to traditional PKC is PQC.
• The security of symmetric cryptography is not significantly impacted by quantum computers, and existing symmetric algorithms with appropriate key sizes can continue to be used.
• PQC upgrades can be planned to take place as systems are being updated or replaced.
• ML-KEM (Kyber) and ML-DSA (Dilithium) are algorithms standardised by NIST that are suitable for general purpose use. All proposed parameter sets provide an acceptable level of security for personal, enterprise and OFFICIAL-tier government information. The NCSC recommends ML-KEM-768 and ML-DSA-65 as providing appropriate levels of security and efficiency for most use cases.
• If a PQ/T hybrid scheme is chosen, the NCSC recommends it is used as an interim measure that allows a straightforward migration to PQC-only in the future.