Skip to content

The quantum threat and Post-Quantum Cryptography↑

High-level description↑

Context↑

While quantum computers carry great potential for a range of applications, large quantum computers also threaten the security of digital communications by breaking the asymmetric cryptographic algorithms used today. These algorithms are core building blocks of essential security protocols, including public-key certificates (such as X.509), secure software updates, and secure communication protocols like Transport Layer Security (TLS), Secure Shell (SSH), and Internet Key Exchange (IKE). This makes quantum computers a direct threat to digital communication security. To mitigate this risk, several standardization agencies such as NIST recommend transitioning to post-quantum cryptography.

Business risk↑

The severity of the “quantum threat”—the risk posed by using quantum-vulnerable cryptography —depends on the application and the expected lifespan of the data it protects. For example, communication data that must stay confidential for several years needs to be protected more urgently using ‘post-quantum’ cryptography as attackers can store encrypted communication now and decrypt it later once they gain access to large quantum computers. The quantum threat might also raise legal concerns. For example, failing to transition to post-quantum cryptography could potentially violate data privacy regulations and other compliance requirements.

Recommendations↑

Post-quantum algorithms already exist for the most critical cryptographic primitives such as digital signatures and key establishment. However, transitioning all protocols and applications to provide security against quantum attackers requires careful and timely planning. According to NIST, the recommended first step in the post-quantum transition is to create an inventory of cryptographic algorithms in use and their context. This enables prioritizing which protocols and applications to migrate and in what order.

Since these protocols and applications typically rely on cryptographic libraries, it’s crucial to ensure that library maintainers update their software to support post-quantum cryptography. If this isn’t possible, replacing the library with one that provides post-quantum capabilities may be necessary. Early engagement with software and hardware suppliers is essential to ensure a smooth transition and maintain business continuity.

Detailed description↑

Quantum computers are a kind of computing device, leveraging the principles of quantum physics, rather than classical electromagnetic physics, for processing data. They store, process, and transmit data using quantum states known as qubits. Small quantum computers already exist, and some of them can even be accessed by the general public. While quantum computers carry great potential for a range of applications, large quantum computers also pose a serious threat to digital communication security by being able to break the asymmetric cryptographic algorithms used today.

Security risk↑

Large, or cryptographically-relevant quantum computers will be able to break most currently used asymmetric cryptography used to secure data during communication. This is made possible by Shor’s quantum algorithm, which can efficiently solve the mathematical problems underlying cryptographic algorithms like RSA, ECDSA, and Diffie-Hellman key exchange.

Symmetric cryptography is also affected by cryptographically relevant quantum computers but to a lesser degree. Grover’s quantum algorithm allows quantum computers to search key spaces more efficiently. However, based on current knowledge, increasing key lengths may provide sufficient protection against this threat. An example of key length increase would be using AES-192 instead of AES-128.

Since communication data can be intercepted and stored today to be decrypted later using cryptographically relevant quantum computers, transitioning to post-quantum algorithms—believed to remain secure even against quantum attackers—is particularly urgent to protect data confidentiality. Although authentication systems might seem less critical from a cryptographic perspective, initiating their transition is equally important due to their large scale and complex dependencies.

While the timeline for the arrival of cryptographically relevant quantum computers remains uncertain, the potential risks are so significant that proactive measures are essential. This need for prevention has been recognized by numerous governments, including those of the United States (NIST, NSA), Canada, the United Kingdom, Australia, China, South Korea, the European Union, and many EU members, in particular France, Germany, and The Netherlands. Organizations like the US NCCoE and US CISA have also published recommendations to guide planning and implementation of the post-quantum transition.

Mitigations using Post-Quantum Cryptography↑

Researchers, standardization bodies, and industry have been developing alternative algorithms that are believed to resist quantum attacks. Unlike the integer factorization and discrete logarithm problems that quantum algorithms like Shor’s can efficiently solve (used in algorithms such as RSA, ECDSA, and ECDH), these new algorithms rely on mathematical problems that quantum computers cannot currently solve efficiently to the best of our knowledge.

This shift in security assumptions fundamentally changes the design of cryptographic algorithms, requiring updates to implementations, including standalone libraries, as well as to protocols and applications such as the Transport Layer Security (TLS) protocol. Notably, NIST has selected four post-quantum algorithms—one for key agreement and three for digital signatures, three of which have already been standardized. Additionally, NIST has detailed two more algorithms in a special publication.

Depending on policy, organizations may transition directly to post-quantum algorithms or adopt a secure combination of conventional quantum-vulnerable and post-quantum algorithms (such as described in ETSI TS 103 744). The latter approach, often referred to as using hybrid algorithms, includes techniques such as hybrid key establishment, composite signatures, or dual signatures. These methods combine the established reliability of classical cryptographic methods with the forward-looking resilience of post-quantum algorithms. These hybrid schemes provide a pragmatic solution to address both current and future security threats, offering a balanced yet urgent path for transitioning to post-quantum algorithms and protocols.

Post-quantum algorithms already exist for the most critical cryptographic primitives such as digital signatures and key establishment, such as FIPS 203, FIPS 204, FIPS 205, and Special publication 800-208 by NIST. However, transitioning all protocols and applications to provide security against quantum attackers is an ongoing effort in different standardization bodies. Therefore, an immediate migration isn’t always possible.

According to NIST, the recommended first step in the post-quantum transition is to create an inventory of cryptographic algorithms in use and their context as soon as feasible. This enables prioritizing which protocols and applications to migrate and in what order.

Since these protocols and applications typically rely on cryptographic libraries, it’s crucial to ensure that library maintainers update their software to support post-quantum cryptography. If this isn’t possible, replacing the library with one that provides post-quantum capabilities may be necessary.

Resources↑

NIST/FIPS standards↑

  • FIPS 203: This standard, based on Kyber, defines a method for two parties to securely share a secret. It is used in different protocols, such as TLS, and is intended to serve as a replacement for quantum-vulnerable key exchange methods such as the Diffie-Hellman key exchange. However, cryptographically, it is a different primitive, namely a Key Encapsulation Mechanism (KEM). As a result, careful consideration is needed when replacing key exchange methods with KEMs to account for their differing properties.
  • FIPS 204: This standard, based on Dilithium, defines a digital signature scheme designed to replace quantum-vulnerable algorithms like ECDSA and RSA. While it functions the same as current signature schemes, it produces larger signatures (2.5KB) and public keys (1.3KB), which may require careful consideration and adjustments in applications to accommodate the increased sizes.
  • FIPS 205: This standard, based on SPHINCS+, defines a digital signature scheme with a distinct trade-off compared to FIPS 204. It uses smaller public keys (32 bytes) but larger signatures (approximately 7 KB). Its security is considered particularly reliable.
  • Special Publication 800-208: This document specifies two additional digital signature schemes, based on LMS (Leighton-Micali Signature) and XMSS (eXtended Merkle Signature Scheme). Unlike the stateless schemes in FIPS 204 and FIPS 205, these are stateful signature schemes, making them particularly suitable for applications where maintaining a reliable state is feasible. For a detailed discussion of potential use cases, refer to ETSI TR 103 692.

European Telecommunications Standards Institute (ETSI)↑

ETSI largely aligns with NIST standards and has published several reports detailing these cryptographic schemes. Additionally, ETSI has released technical reports on hybrid key exchange algorithms and stateful hash-based signature schemes, among other topics. A collection of drafts from the CYBER QSG working group is available here.

  • ETSI TS 103 744: This technical specification outlines methods for combining the quantum-vulnerable ECDH key exchange with post-quantum key encapsulation mechanisms, resulting in “hybrid algorithms.” The goal is to maintain the security guarantees of current cryptography while adding security against quantum computer threats.
  • ETSI TR 103 692: This technical report focuses on state management for stateful authentication mechanisms, as used for LMS and XMSS (see NIST Special Publication 800-208).

Internet Engineering Task Force (IETF)↑

IETF has several working groups dedicated to developing post-quantum standards. An overview of ongoing activities can be found here.

  1. IETF RFC 8391: This RFC describes the stateful hash-based signature scheme XMSS (eXtended Merkle Signature Scheme) and serves as a reference for NIST Special Publication 800-208.
  2. IETF RFC 8554: This RFC describes the stateful hash-based signature scheme LMS (Leighton-Micali Signature) and serves as a reference to NIST Special Publication 800-208.
  3. IETF RFC 8784: This RFC proposes an extension to the Internet Key Exchange Protocol Version 2 (IKEv2) to enhance resistance to quantum attacks by incorporating pre-shared keys. This approach is intended as a transition solution until IKEv2 is extended to include post-quantum key agreement algorithms.

Institute of Electrical and Electronics Engineers (IEEE)↑

IEEE has published several documents related to post-quantum cryptography. These documents can be found here. Notably, the list includes IEEE P3172 Recommended Practice for Post-Quantum Cryptography Migration.