1. Why do we need PQC? What motivated its development?
Classical cryptography's strength is based on the difficulty of solving specific mathematical problems. This difficulty arises from the inability of current computing units to perform such operations in a reasonable amount of time. But quantum computers will change the game. While quantum computers are already available for research and experimentation, their widespread practical use is still several years away. What is considered impossible today could become easily achievable tomorrow.
Post-Quantum Cryptography (PQC) is a field of cryptography focused on developing cryptographic algorithms that run on standard devices and are secure against attacks performed using powerful quantum computers.
In particular, two algorithms developed decades ago (Shor's and Grover's algorithms), if ever correctly implemented on quantum computers with the right characteristics, could solve problems on which the security of the current systems is based. These problems are currently intractable for classical computers.
2. Which cryptographic mechanisms and algorithms are impacted?
RSA, DSA, Diffie-Hellman, and any algorithms based on the Elliptic-curve cryptography (such as ECDSA, EdDSA, ECDH, ECIES, SM2, X25519, and X448) are considered vulnerable. These algorithms are used in higher-level protocols (for instance, TLS, Secure Boot, and Secure Firmware Upgrade functionalities) to guarantee the authenticity, integrity, and confidentiality of the information processed.
RSA, DSA, and Diffie-Hellman are based on integer factorization, while any of the ECC algorithms mentioned are based on the discrete logarithm problem. Both mathematical problems are considered solvable in polynomial time by a powerful quantum computer, thereby compromising their security. Since the compromise is related to the underlying mathematical problem, increasing the key size does not resolve the issue. And the algorithms themselves will no longer be secure.
3. Which algorithms can still be used?
Symmetric cryptography is still considered safe; AES and SHA-3 are examples of cryptographic algorithms that you can continue to use.
4. Types of PQC algorithms
Different PQC algorithms are based on distinct mathematical problems, such as lattices, codes, hash functions, and multivariate polynomials. This diversity ensures that if one type of algorithm is broken or weakened, the rest remain secure.
Moreover, relying on multiple algorithms reduces the risk of a single point of failure. If all systems depend on one algorithm and it is broken, the consequences are catastrophic. Multiple algorithms provide a safety net.
PQC algorithms are more invasive compared to classical cryptography (consider, for example, key sizes, performance, and memory consumption). Various cryptographic applications have different requirements in terms of speed, memory usage, and security levels. Having a wide range of algorithms allows the selection of the most appropriate one for each specific use case.
Lattice-based cryptography
Probably the most important family of PQC algorithms is lattice-based cryptography, which relies on the hardness of lattice problems, such as Learning With Errors (LWE) and Shortest Vector Problem (SVP), believed to be resistant to quantum attacks. It offers strong security guarantees and efficient implementations, making it a leading candidate for post-quantum cryptographic standards. Examples of lattice-based cryptographic schemes include ML-KEM, ML-DSA, and FN-DSA.
Hash-based cryptography
Another important family is hash-based cryptography, which leverages the security of cryptographic hash functions to create secure digital signatures resistant to quantum attacks. It offers strong security guarantees and simplicity, making it a reliable choice for post-quantum cryptography. Notable examples include SLH-DSA, LMS, and XMSS.
Code-based cryptography
Code-based cryptography is also worth mentioning. It is based on the difficulty of decoding random linear codes, a problem believed to be resistant to quantum attacks. It offers strong security and has been studied extensively, making it a reliable candidate for post-quantum cryptographic applications. Classic McEliece, HQC, and BIKE are prominent examples of code-based cryptographic schemes.
5. Which PQC algorithm for which use case?
LMS and XMSS (both standardized by NIST in October 2020, see SP 800-208) are Stateful Hash-Based Signature (HBS) schemes, where a private key is composed of a limited number of One-Time Signature (OTS) keys. As the name suggests, it is important that the OTS keys are used just once; otherwise, the security of the scheme is compromised. The state is therefore important to track which OTS keys were used and which were not. It is mandatory to keep this state secret and to avoid any reset or tampering, as the reuse of the same internal OTS key completely compromises the scheme.
As mentioned before, the private key is composed of a limited number of OTS keys, meaning that a limited number of different signatures can be computed with a single private key. As a direct consequence, the key validity, in terms of the number of remaining signatures available, must be monitored by developers. When the bound limit is reached, a new key pair must be generated.
Due to the issues to securely maintain a state, and to the imposed limit of signatures that are computable using the same private key, the stateful HBS schemes (LMS and XMSS) cannot be used in general network protocols such as TLS. These are restricted to specific scenarios. For example, in a Secure Boot use case, where you just need to verify a signature (using the public key) a limited number of times during a device's lifetime (and considering that a device can have up to 1,000 or 10,000 updates), these algorithms are suggested.
LMS and XMSS can be extremely fast, and their quantum security is based on hash functions, which are well-studied and known cryptographic elements, making them perfect candidates to replace ECDSA/EdDSA/RSA-PSS. Hybridization is not required, and performance can be further boosted by leveraging hardware hash engines often found on embedded devices.
ML-DSA, on the other hand, is a digital signature algorithm with standard characteristics. This means that it can be used in general use cases where there cannot be limits on the number of signatures computed with the same private key. Therefore, ML-DSA can replace ECDSA/EdDSA/RSA-PSS in protocols and higher-level applications. One negative aspect of ML-DSA must be seriously considered: the signature generation process time is unbounded due to the internal signature rejection process. Theoretically, even with an extremely low probability, it could last forever.
ML-KEM provides key encapsulation and decapsulation functionalities, allowing encryption of a key using an asymmetric scheme. This algorithm could replace RSA-OAEP and could also be used in place of currently used key exchange mechanisms to establish a secret key between two parties. Since we do not have a corresponding PQC algorithm to replace (Elliptic curve) Diffie-Hellman key exchange, instead of commonly deriving a shared secret, one party could create a random key, encrypt it with the public key of the other party, and then send the encrypted key over an insecure network. The other party could then decrypt the value using its own private key.
One important remark relates to the size of the elements involved, such as keys, signatures, and ciphertexts. These PQC schemes drastically increase these sizes (for example, with signatures larger than 1 KB) compared to classic cryptography. Users should be aware of this drawback and carefully adapt their applications, taking this constraint into consideration.
6. Additional resources
ANSSI, PQC Transition in France, ANSSI views (Mar. 2023)
ANSSI, Follow up position paper on Post-Quantum Cryptography (Oct. 2023)
BSI, Cryptographic Mechanisms: recommendations and key lengths (Feb. 2024)
NIST, Transitioning the Use of Cryptographic Algorithms and Key Lengths (IPD) (Oct. 2024)
NIST, Transition to Post-Quantum Cryptography Standards, NIST IR 8547 (IPD) (Nov. 2024)