The cryptographic community is planning for time when (if) a large-scale quantum computer — a Cryptographically Relevant Quantum Computer (CRQC) — will be built. If one is, then it will be able to break all current public schemes for encryption and digital signatures, such as RSA, Diffie-Hellman and ECDSA. Post-quantum cryptography (PQC) is the development of cryptographic algorithms considered to be secure against an attack by a CRQC. You will sometimes see PQC referred to as quantum-proof, quantum-safe, or quantum-resistant.
These are based on the original submitted algorithms Kyber, Dilithium and SPHINCS+, respectively.
The first algorithm provides public key encryption using a Key-Encapsulation Mechanism (KEM), and the last two provide digital signature schemes. These are intended to replace the algorithms RSAES, RSASSA, ECDSA and ECDH.
All these algorithms are provided in our CryptoSys PQC, a programmer's library that provides all the basic functions for the above three algorithms. It is free. See CryptoSys PQC
Note that cryptographic hash and symmetric encryption algorithms (e.g. SHA-256 and AES-128) are not threatened by advances in quantum computing.
The Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM) (formerly Kyber) is a key-encapsulation mechanism (KEM) that can be used to establish a shared secret key between two parties. For an explanation of KEM see below.
ML-KEM uses lattice-based cryptography. Its security is related to the computational difficulty of solving certain systems of noisy linear equations, specifically the so-called Module Learning With Errors (MLWE) problem.
ML-KEM has three parameter sets in increasing order of security category: ML-KEM-512, ML-KEM-768 and ML-KEM-1024.
The sizes in bytes of the keys and ciphertext used in ML-KEM are shown in the following table.
| encapsulation key | decapsulation key | ciphertext | shared secret key | security category | |
|---|---|---|---|---|---|
| ML-KEM-512 | 800 | 1632 | 768 | 32 | 1 |
| ML-KEM-768 | 1184 | 2400 | 1088 | 32 | 3 |
| ML-KEM-1024 | 1568 | 3168 | 1568 | 32 | 5 |
The private decapsulation key can be represented in a much shorter "seed" form.
The Module-Lattice-Based Digital Signature Algorithm (ML-DSA) (formerly Dilithium) is digital signature scheme. It provides algorithms for key generation, signature generation, and signature verification: see below.
ML-DSA is based on the Module Learning With Errors problem. ML-DSA has three parameter sets in increasing order of security category: ML-DSA-44, ML-DSA-65 and ML-DSA-87. The numbers 44, 65 and 87 refer to the size ($k\times \ell$) of the matrix $\mathbf{A}$ used in the calculations.
The sizes in bytes of the keys and signatures are shown in the following table.
| private key | public key | signature size | security category | |
|---|---|---|---|---|
| ML-DSA-44 | 2560 | 1312 | 2420 | 2 |
| ML-DSA-65 | 4032 | 1952 | 3309 | 3 |
| ML-DSA-87 | 4896 | 2592 | 4627 | 5 |
The private key can be represented in a much shorter "seed" form.
Note the much larger sizes of the keys and signatures compared to classical signature algorithms. The private keys and signatures for ML-DSA are in the order of 2 to 5 kB, compared to the classical ECDSA algorithm P-256 with a private key of 32 bytes and a signature 64 bytes long.
The Stateless Hash-Based Digital Signature Algorithm (SLH-DSA) is a digital signature scheme based on SPHINCS+. It provides algorithms for key generation, signature generation, and signature verification: see below.
The security of SLH-DSA relies on the security properties of hash functions, in particular the difficulty of finding preimages for hash functions (preimage resistance).
SLH-DSA is a stateless hash-based signature scheme, which avoids the problems of stateful hash-based schemes (like LMS and XMSS). Stateful hash-based schemes require the signer to maintain a state index to prevent the use of any previously-used private keys: re-using a key can destroy the security of the scheme. SLH-DSA does not have this limitation and is designed to sign up to $2^{64}$ messages with one key, effectively an unlimited number.
There are 12 parameter sets for SLH-DSA. These are made up of three security categories 128/192/256 corresponding to security parameters $n = 16, 24, 32$. Six of these parameter sets use the SHA2 hash functions from [FIPS.180-4] (specifically SHA-256 and SHA-512) and the other six use SHAKE from [FIPS.202]. There are slow "s" and fast "f" variants which trade off speed against size when generating signatures.
The sizes in bytes of the keys and signatures are shown in the following table.
| n | private key | public key | signature size | security category | |
|---|---|---|---|---|---|
| SLH-DSA-SHA2-128s SLH-DSA-SHAKE-128s | 16 | 64 | 32 | 7 856 | 1 |
| SLH-DSA-SHA2-128f SLH-DSA-SHAKE-128f | 16 | 64 | 32 | 17 088 | 1 |
| SLH-DSA-SHA2-192s SLH-DSA-SHAKE-192s | 24 | 96 | 48 | 16 224 | 3 |
| SLH-DSA-SHA2-192f SLH-DSA-SHAKE-192f | 24 | 96 | 48 | 35 664 | 3 |
| SLH-DSA-SHA2-256s SLH-DSA-SHAKE-256s | 32 | 128 | 64 | 29 792 | 5 |
| SLH-DSA-SHA2-256f SLH-DSA-SHAKE-256f | 32 | 128 | 64 | 48 856 | 5 |
Note the huge signature sizes for SLH-DSA, up to 48 kB!
The private keys for ML-DSA and ML-KEM can be stored in a much shorter "seed" form: 32 bytes for ML-DSA and 64 bytes for ML-KEM. This seed is used in the $\textsf{KeyGen}$ algorithm to generate a key pair in a deterministic manner. The longer private keys generated using KeyGen are known as the "expanded" key. This seed form is a more convenient way to store and distribute the private keys.
Generate a public key $pk$ and a private key $sk$ using fresh randomness each time. The signing party keeps the private key secret and publishes the public key.
The signer signs the message $M$ using the private key $sk$ to produce the signature $\sigma$. $\textsf{Sign}$ can either be used in the "hedged" variant with fresh randomness each time or in a deterministic manner.
Anyone in possession of the public key $pk$ can verify the signature $\sigma$ over the original message $M$.
Both the PQC digital signature schemes have a "pure" variant as described above, generating the signature over the original message $M$, and a "pre-hash" version where the input to the $\textsf{Sign}$ function is a message digest of the original message $H(M)$ using a hash function $H$. In the pre-hash variant, the hash function $H$ must be specified in the input and its identity is incorporated in the signature.
ML-DSA also has a ExternalMu variant, where the value of $\mu$ ("mu") is pre-computed and passed as input instead of the message and context. This is suitable for long messages and has the advantage that the signature is mathematically equivalent to the "pure" variant. It requires the value of the public key $pk$. In simplified form, the value of $\mu$ is computed as follows, where M is the message to be signed, ctx is the context string which may be empty, 0xNN is a one-byte representation of the length of the context string [0-255] and $H()$ is the SHAKE256 function with a fixed output of 64 bytes.
mu = H( H(pk) || 0x01 || 0xNN || ctx || M )
KEM provides three functions: $\textsf{KeyGen}$, $\textsf{Encaps}$ and $\textsf{Decaps}$.
The recipient generates an encapsulation key $ek$ ("public key") and a decapsulation key $dk$ ("private key"). The recipient keeps the decapsulation key secret and provides the encapsulation key to the originator.
The originator employs the encapsulation algorithm with the recipient's public encapsulation key $ek$ to generate the shared secret key $ss$ and an associated ciphertext $ct$. The ciphertext $ct$ is passed to the recipient. Some authors, e.g. NIST, use the notation $(c, K)$ instead of $(ct, ss)$.
The recipient uses their private decapsulation key $dk$ and the ciphertext $ct$ in the decapsulation algorithm to compute the shared secret key $ss$.
For added security or to derive a key of a different length, L, a Key Derivation Function (KDF) — for example, HKDF —
can be used on $ss$, perhaps with some optional sharedInfo,
ss' = KDF(ss, sharedInfo, L)
Once the shared secret key is established between the two parties, either party can encrypt some confidential data $M$ using a conventional symmetric encryption algorithm with the shared secret key, $C = \textsf{Encrypt}(ss, M)$ and send $C$ over an open channel to the other party, who can decrypt $M = \textsf{Decrypt}(ss, C)$.
Here is a protocol diagram showing the use of KEM
| Recipient | Originator | ||
|---|---|---|---|
$(ek, dk) \leftarrow \textsf{KeyGen}()$ | (perform key generation) | ||
| $\overset{ek}{\longrightarrow}$ | |||
| $(ct, ss) \leftarrow \textsf{Encaps}(ek)$ | (perform encapsulation) | ||
| $\overset{ct}{\longleftarrow}$ | |||
| $ss \leftarrow \textsf{Decaps}(dk, ct)$ | (perform decapsulation) | ||
| (exchange messages using symmetric encryption) | |||
| $C \leftarrow \textsf{Encrypt}(ss, M)$ | (encrypt message using $ss$) | ||
| $\overset{C}{\longleftarrow}$ | |||
| $M \leftarrow \textsf{Decrypt}(ss, C)$ | (decrypt message) | ||
| $C_1 \leftarrow \textsf{Encrypt}(ss, M_1)$ | (pass message in opposite direction) | ||
| $\overset{C_1}{\longrightarrow}$ | |||
| $M_1 \leftarrow \textsf{Decrypt}(ss, C_1)$ | (repeat at will) |
For the PQC schemes, rather than specifying security levels as 128/192/256 "bits of security", NIST has specified five security categories based on the range of existing security strengths in symmetric cryptography. These are, in order of increasing strength:
For example, NIST assumes that a brute-force collision attack on SHA256 will be technologically feasible before a brute-force key search attack on AES192.
See our papers with some background and theory on the algorithms used in the NIST PQC schemes.
To contact us, please send us a message. To comment on this page, see comments below.
This page last updated 8 July 2025
Comments