Key encapsulation mechanisms explained

Short answer: A key encapsulation mechanism (KEM) is a probabilistic algorithm that produces a random symmetric key and an asymmetric encryption of that key, according to a 2002 paper on KEM-DEM hybrid constructions. It is the public-key half of hybrid encryption, paired with a symmetric data encapsulation mechanism (DEM). This post is a general explainer, not a description of a specific standard.

What is the fundamental structure of a KEM?

A Key Encapsulation Mechanism is formally defined as a triple of algorithms designed to handle the specific use case of sending a key to another party. The first algorithm is key generation, which takes a security parameter as input and outputs a public and secret key pair. The second algorithm is encapsulation, which takes the recipient's public key and outputs a pair consisting of a symmetric key and a ciphertext. The third algorithm is decapsulation, which takes the secret key and the ciphertext to recover the original symmetric key.

This structure distinguishes KEMs from general public-key encryption. While public-key encryption encrypts arbitrary messages, a KEM is tailored specifically to encapsulate a symmetric key. The encapsulation algorithm is probabilistic, meaning it produces a random symmetric key each time it runs. The resulting ciphertext is sometimes referred to as an encapsulation of the key. The decapsulation process must correctly recover the key generated during encapsulation for the scheme to be useful.

How does a KEM function within hybrid encryption?

Hybrid encryption combines asymmetric and symmetric techniques to create efficient, provably secure public-key encryption schemes. Public-key cryptography alone has inherent limitations, including large key sizes and restrictions on the plaintext space. Hybrid schemes address these limitations by pairing a KEM with a Data Encapsulation Mechanism (DEM).

In this construction, the KEM handles the asymmetric portion of the security burden. It uses a shared public key to encrypt a session key. The DEM, which is a deterministic algorithm, then uses that session key to encrypt the actual message. This process produces two ciphertexts: one encrypting the message and another encrypting the session key. The DEM component must satisfy its own security conditions, and the KEM must satisfy its own, for the overall scheme to be secure. In this arrangement the symmetric part encrypts the message and the asymmetric part protects only the key.

What are the security requirements for a KEM?

The 2002 paper says a KEM and a DEM must each satisfy their own security conditions if the overall hybrid scheme is to be secure. A technical introduction on cronokirby.com adds that correctness comes first: no matter what key pair is generated, encapsulating and then decapsulating must return the same key. If this does not hold, the KEM cannot establish a shared key between two parties.

How are KEMs constructed?

The 2002 paper describes generic constructions for provably secure KEMs based on weak encryption algorithms. The authors analyse the two most popular techniques for constructing a KEM and say they are either overly complex or based on needlessly strong assumptions about the security of the underlying trapdoor function. They then propose new constructions. The paper's abstract does not give the details of those proposals, so this post does not describe them.

Limits

This is a general explainer based on a 2002 paper and two tutorials, not a description of any current standard. It does not cover how specific post-quantum KEMs are built, or which security notion a given standard uses.

FAQ

Can a KEM encrypt arbitrary messages?

No. A KEM is tailored to the specific use case of sending a key to another party. It produces a random symmetric key and an asymmetric encryption of that key, rather than encrypting arbitrary plaintext messages directly.

What is the role of the DEM in hybrid encryption?

The Data Encapsulation Mechanism (DEM) is a deterministic algorithm that takes a message and a symmetric key to encrypt the message. It handles the bulk data encryption, while the KEM handles the key exchange.

What must a hybrid scheme satisfy?

Per the 2002 paper, the KEM and the DEM must each satisfy their own security conditions for the overall scheme to be secure.

Must encapsulation and decapsulation match?

Yes. Correctness requires that encapsulating and then decapsulating returns the same key. If this property does not hold, the KEM is not useful for establishing a shared key between two parties or for public-key encryption.