Practical Post-Quantum Cryptography

Key Encapsulation Mechanisms (KEMs)

Key Encapsulation Mechanisms (“KEMs” for short) are used to encapsulate a shared secret that can be used to symmetrically encrypt and authenticate a message. In essence they are a more purpose-built alternative to asymmetric encryption schemes that does not allow the encapsulating party to chose the encrypted message. While this makes them a less powerful primitive, the vast majority of practical uses of asymmetric encryption only ever boilt down to that use-case in the first place, making this a largely theoretical limitation.

Formalisms

Formally speaking a KEM is a tuple consisting of three algorithms:

generate: Generates a public key pk and a secret key sk.
encapsulate: Takes a public key pk and produces a ciphertext ct and a shared secret ss.
decapsulate: Takes a ciphertext ct and a secret key sk and produces a shared secret ss’.

We say that a KEM offers δ-correctness, if the probability, that, upon honest execution of all algorithms, ss=ss’ is at least 1−δ.

We say that a KEM offers perfect correctness, if δ=0.

We say that a KEM offers Indistinguishability under Chosen Ciphertext Attacks (IND-CCA), if there is no Quantum Polynomial Time (QPT) adversary that can distinguish the shared secret ss encapsulated in a ciphertext ct^* from a random value, even if she receives the public key pk, the challenge ciphertext ct^*, and access to a decapsulation-oracle that can decapsulate all ciphertexts except for ct^*.

Established Schemes

As of March 2025, there are four KEMs that can be considered established enough for practical use. All of them were originally designed for NIST’s post-quantum competition and subsequently either chosen for standardization by NIST or approved by various European Government bodys:

ML-KEM (Module Lattice - Key Encapsulation Mechanism): NIST’s primary choice for KEMs. It is a slightly modified version of “Kyber”, a highly efficient KEM based on module-lattices. One of the remaining issues with this scheme is that there are effectively several formats for the secret key: As a very short seed (slightly slower but much more compact and arguably more secure), semi-expanded (slightly faster, significantly bigger), and both (worst of all worlds, standardized by IETF)
Frodo: Another lattice-based KEM. Unlike ML-KEM it uses unstructured lattices, which is generally assumed to be more conservative, though it bears stressing that this is merely an assumption and could also turn out to be wrong. The lack of structure gives Frodo significant overhead in size, when compared to ML-KEM.
Classic McEliece: The oldest code-based KEM. With the primary components having been designed in 1978 it is generally considered to be a very conservative choice that manage to stand up to many years of cryptanalysis. It offers a fairly unique performance profile, in that it has tiny ciphertexts, with very fast encapsulation and decapsulation, at the cost of slow key-generation and huge public keys. This makes it primarily interessting for use-cases that involve long-lived keys that are only very rarely transmitted, not so much as a general purpose KEM. but While various European government agencies approved it for use, NIST decided against standardizing it, citing a concurrent standardization-effort by ISO, recent results that, while not directly affecting the security of McEliece, could be taken as indicative that the security of the scheme is not quite as well understood as was once expected, and a lack of stated interest in a scheme with McElice’s performance profile.
HQC (Hamming Quasi-Cyclic): Another code-based scheme that was chosen by NIST as fallback for ML-KEM. It is significantly outperformed by kyber in all size- and runtime-characteristics, and primarily intended as a backup, in case of breakthroughs regarding lattices.
BIKE (Bit-Flipping Key Encapsulation): The final code-based finalist in NIST’s competition. It was not selected by NIST, who considered it less trustworthy than its primary competitor, but approved by ANSSI, though similarly with less confidence than HQC. It’s size-characteristics are worse than those of HQC, but it does offer better runtime-performance.

While other post-quantum KEMs have seen practical use, this was primarily (but not exclusively) in the context of experiments and using these schemes at this point could be considered as the equivalent to the use of non-winning AES-finalists: While there is nothing known to be inherently wrong with them, they are nowadays much more obscure schemes that are the subject to far less scrutiny by public research and should thus generally be avoided.

Table 1.1: Overview over established KEMs.
All measurements were performed on an Intel i5-1135G7 using OQS version 0.12.0. The results are rounded to two significant digits only meant to provide a very rough overview and some comparison between the listed schemes.
Name	Status	Type	Variant	λ	δ	Size [Bytes]				Average Runtime [µs]
Name	Status	Type	Variant	λ	δ	PK	Ct	SK	SS	Gen.	Enc	Dec
ML-KEM “Kyber”	Standardized (NIST)	Module Lattice (M-LWE)	ML-KEM 512	$1$	$2^{−139}$	$800$	$768$	$1632$	$32$	$15$	$15$	$14$
			ML-KEM 768	$3$	$2^{−164}$	$1184$	$1088$	$2400$		$23$	$23$	$22$
			ML-KEM 1024	$5$	$2^{−174}$	$1568$	$1568$	$3168$		$32$	$33$	$32$
Frodo	Approved (BSI, ANSSI, NCSC)	Lattice (LWE)	FrodoKEM-640-AES	$1$	$2^{−138.7}$	$9616$	$9720$	$19888$	$16$	$250$	$340$	$330$
			FrodoKEM-640-SHAKE	$1$	$2^{−138.7}$	$9616$	$9720$	$19888$	$16$	$1800$	$1900$	$1900$
			FrodoKEM-976-AES	$3$	$2^{−199.6}$	$15632$	$15744$	$31296$	$24$	$490$	$660$	$660$
			FrodoKEM-976-SHAKE	$3$	$2^{−199.6}$	$15632$	$15744$	$31296$	$24$	$4100$	$4400$	$4300$
			FrodoKEM-1344-AES	$5$	$2^{−252.5}$	$21520$	$21632$	$43088$	$32$	$980$	$1200$	$1300$
			FrodoKEM-1344-SHAKE	$5$	$2^{−252.5}$	$21520$	$21632$	$43088$	$32$	$7700$	$7800$	$7800$
Classic McEliece	Approved (BSI, NCSC)	Code (Goppa-Codes)	mceliece348864	$1$	$0$	$261120$	$96$	$6492$	$32$	$30000$	$23$	$34$
			mceliece460896	$3$		$524160$	$156$	$13608$		$110000$	$45$	$66$
			mceliece6688128	$5$		$1044992$	$208$	$13932$		$160000$	$98$	$75$
			mceliece6960119			$1047319$	$194$	$13948$		$250000$	$96$	$70$
			mceliece8192128			$1357824$	$208$	$14120$		$180000$	$130$	$74$
HQC	Chosen (NIST)	Code	hqc-128	$1$	$< 2^{-128}$	$2249$	$4497$	$56$	$64$	$1500$	$3000$	$4900$
			hqc-192	$3$	$<2^{-192}$	$4522$	$9042$	$64$		$4600$	$9200$	$14000$
			hqc-256	$5$	$<2^{-256}$	$7245$	$14485$	$72$		$8600$	$17000$	$26000$
BIKE	Approved (ANSSI)	Code	BIKE-L1	$1$	$2^{−128}$	$12323$	$12579$	$2500$	$32$	$160$	$34$	$310$
			BIKE-L3	$3$	$2^{−192}$	$24659$	$24915$	$3602$		$470$	$71$	$960$
			BIKE-L5	$5$	$2^{−256}$	$40973$	$41229$	$4896$		$1100$	$140$	$2500$

Signatures

signature-schemes are primitives that can be used to authenticate a message. Unlike KEMs, they are a traditional primitive that continues to be used unchanged.

Formalisms

Formally speaking a signature scheme is a tuple consisting of three algorithms:

generate: Generates a public key pk and a secret key sk.
sign: Takes a secret key sk and a message m and produces a signature σ.
verify: Receives a public key pk, a message m, and a signature σ and returns a boolean value indicating whether σ is valid.

We say that a signature scheme is complete, if verify accepts every honestly generated signature for a given key-pair.

We say that a signature scheme offers Existential UnForgability under Chosen Message Attacks (EUF-CMA), if there is no Quantum Polynomial Time (QPT) adversary that can with non-negligible probability create a valid and fresh signature-message-pair for an honestly generated key-pair, even if she receives the public key pk and access to a signing-oracle.

Established Schemes

As of March 2025, there are three signature schemes that can be considered established enough for practical use. All of them were originally designed for NIST’s post-quantum competition and subsequently chosen for standardization by NIST:

ML-DSA (Module Lattice - Digital Signature Algorithm): NIST’s primary choice for Signatures. It is a slightly modified version of “Dilithium” and based on module-lattices.
SLH-DSA (StateLess Hash - Digital Signature Algorithm: NIST’s much more conservative choice for signatures whose security only relies on the security of hash-functions. It is strongly based on “SPHINCS+”.
FN-DSA (FFT over NTRU-lattice - Digital Signature Algorithm.): A more compact alternative to ML-DSA that NIST announced for standardization based on Falcon. Its big downside is that it relies on floating-point operations, which makes it notoriously hard to implement securly.

Table 2.1: Overview over established signature schemes.
All measurements are rounded to two significant digits and were performed on an Intel i5-1135G7 using OQS version 0.12.0 and only meant to provide a very rough overview.
Name	Status	Type	Variant	λ	Size [Bytes]			Average Runtime [µs]
Name	Status	Type	Variant	λ	PK	σ	SK	Gen.	Sign(“”)	Vfy(“”)
ML-DSA “Dilithium”	Standardized (NIST)	Module Lattice (M-LWE)	ML-DSA-44	$2$	$1312$	$2420$	$2560$	$47$	$100$	$43$
			ML-DSA-65	$3$	$1952$	$3309$	$4032$	$83$	$170$	$75$
			ML-DSA-87	$5$	$2592$	$4627$	$4896$	$140$	$220$	$120$
SLH-DSA “SPHINCS+”	Standardized (NIST)	Hash-based	SLH-DSA-SHA2-128s	$1$	$32$	$7856$	$64$	$20000$	$150000$	$200$
			SLH-DSA-SHAKE-128s			$7856$		$34000$	$260000$	$370$
			SLH-DSA-SHA2-128f			$17088$		$320$	$7400$	$590$
			SLH-DSA-SHAKE-128f			$17088$		$550$	$13000$	$930$
			SLH-DSA-SHA2-192s	$3$	$48$	$16224$	$96$	$30000$	$280000$	$360$
			SLH-DSA-SHAKE-192s			$16224$		$52000$	$460000$	$620$
			SLH-DSA-SHA2-192f			$35664$		$470$	$12000$	$910$
			SLH-DSA-SHAKE-192f			$35664$		$800$	$21000$	$1300$
			SLH-DSA-SHA2-256s	$5$	$64$	$29792$	$128$	$20000$	$250000$	$490$
			SLH-DSA-SHAKE-256s			$29792$		$45000$	$510000$	$880$
			SLH-DSA-SHA2-256f			$49856$		$1200$	$25000$	$910$
			SLH-DSA-SHAKE-256f			$49856$		$2600$	$53000$	$1700$
FN-DSA “Falcon”	Chosen (NIST)	Lattice	Falcon-512	$1$	$897$	$666$	$1281$	$6300$	$190$	$40$
FN-DSA “Falcon”	Chosen (NIST)	Lattice	Falcon-1024	$5$	$1793$	$1280$	$2305$	$18000$	$380$	$74$

Stateful Signatures

Disclaimer: This Section is still Work in Progress!

Stateful signature-schemes are primitives that can be used to authenticate a message. Unlike regular signature schemes, they maintain a state that gets updated after every signing-operation. Old states must never be used to sign a new message, as doing so can severely damage the security of the entire scheme.

Formalisms

Formally speaking a stateful signature scheme is a tuple consisting of three algorithms:

generate: Generates a public key pk and a secret key sk.
sign: Takes a secret key sk and a message m and produces a signature σ and an updated secret key sk.
verify: Receives a public key pk, a message m, and a signature σ and returns a boolean value indicating whether σ is valid.

We say that a signature scheme is complete, if verify accepts every honestly generated signature for a given key-pair.

Established Schemes

As of March 2025, there are two families of stateful signature schemes that can be considered established enough for practical use: XMMS (eXtended Merkle Signature Scheme) and LMS (Leighton-Micali Signatures).

Table 3.1: Overview over standardized stateful signature schemes.
Name	Status	Type	Variant	𝑛	λ	Size [Bytes]			Average Runtime [µs]
Name	Status	Type	Variant	𝑛	λ	PK	σ	SK	Gen.	Sign(“”)	Vfy(“”)
XMSS RFC 8391	Standardized (IRTF)	Hash-based	XMSS-SHA2_10_256 XMSS-SHAKE_10_256	$2^10$		$67$	$2500$
			XMSS-SHA2_10_256 XMSS-SHAKE_10_256	$2^16$		$67$	$2692$
			XMSS-SHA2_10_256 XMSS-SHAKE_10_256	$2^20$		$67$	$2820$
			XMSS-SHA2_10_512 XMSS-SHAKE_10_512	$2^10$		$131$	$9092$
			XMSS-SHA2_10_512 XMSS-SHAKE_10_512	$2^16$		$131$	$9476$
			XMSS-SHA2_10_512 XMSS-SHAKE_10_512	$2^20$		$131$	$9732$
XMSS-MT RFC 8391	Standardized (IRTF)	Hash-based	XMSSMT-SHA2_20/2_256 XMSSMT-SHAKE_20/2_256	$2^20$		$67$	$4963$
			XMSSMT-SHA2_20/4_256 XMSSMT-SHAKE_20/4_256	$2^20$		$67$	$9251$
			XMSSMT-SHA2_40/2_256 XMSSMT-SHAKE_40/2_256	$2^40$		$67$	$5605$
			XMSSMT-SHA2_40/4_256 XMSSMT-SHAKE_40/4_256	$2^40$		$67$	$9893$
			XMSSMT-SHA2_40/8_256 XMSSMT-SHAKE_40/8_256	$2^40$		$67$	$18469$
			XMSSMT-SHA2_60/3_256 XMSSMT-SHAKE_60/3_256	$2^60$		$67$	$8392$
			XMSSMT-SHA2_60/6_256 XMSSMT-SHAKE_60/6_256	$2^60$		$67$	$14824$
			XMSSMT-SHA2_60/12_256 XMSSMT-SHAKE_60/12_256	$2^60$		$67$	$27688$
			XMSSMT-SHA2_20/2_512 XMSSMT-SHAKE_20/2_512	$2^20$		$131$	$18115$
			XMSSMT-SHA2_20/4_512 XMSSMT-SHAKE_20/4_512	$2^20$		$131$	$34883$
			XMSSMT-SHA2_40/2_512 XMSSMT-SHAKE_40/2_512	$2^40$		$131$	$19397$
			XMSSMT-SHA2_40/4_512 XMSSMT-SHAKE_40/4_512	$2^40$		$131$	$36165$
			XMSSMT-SHA2_40/8_512 XMSSMT-SHAKE_40/8_512	$2^40$		$131$	$69701$
			XMSSMT-SHA2_60/3_512 XMSSMT-SHAKE_60/3_512	$2^60$		$131$	$29064$
			XMSSMT-SHA2_60/6_512 XMSSMT-SHAKE_60/6_512	$2^60$		$131$	$54216$
			XMSSMT-SHA2_60/12_512 XMSSMT-SHAKE_60/12_512	$2^60$		$131$	$104520$
LMS RFC 8554	Standardized (IRTF)	Hash-based	LMS_SHA256_M32_H5
			LMS_SHA256_M32_H10
			LMS_SHA256_M32_H15
			LMS_SHA256_M32_H20
			LMS_SHA256_M32_H25
WOTS+ RFC 8391	Standardized (IRTF)	Hash-based	WOTSP-SHA2_256 WOTSP-SHAKE_256	$1$		$67$	$2144$
WOTS+ RFC 8391	Standardized (IRTF)	Hash-based	WOTSP-SHA2_512 WOTSP-SHAKE_512	$1$		$131$	$8384$
LMOTS RFC 8554	Standardized (IRTF)	Hash-based	LMOTS_SHA256_N32_W1	$1$			$8516$
			LMOTS_SHA256_N32_W2	$1$			$4292$
			LMOTS_SHA256_N32_W4	$1$			$2180$
			LMOTS_SHA256_N32_W8	$1$			$1124$

Settings

Key Encapsulation Mechanisms (KEMs)

Formalisms

Established Schemes

Signatures

Formalisms

Established Schemes

Stateful Signatures

Formalisms

Established Schemes