Key encapsulation mechanism

In cryptography, a key encapsulation mechanism, or KEM, is a public-key cryptosystem that allows a sender to generate a short secret key and transmit it to a receiver securely, in spite of eavesdropping and intercepting adversaries.

[1][2][3] Modern standards for public-key encryption of arbitrary messages are usually based on KEMs.

[4][5] A KEM allows a sender who knows a public key to simultaneously generate a short random secret key and an encapsulation or ciphertext of the secret key by the KEM's encapsulation algorithm.

[1][2][3] The security goal of a KEM is to prevent anyone who doesn't know the private key from recovering any information about the encapsulated secret keys, even after eavesdropping or submitting other encapsulations to the receiver to study how the receiver reacts.

[1][2][3] The difference between a public-key encryption scheme and a KEM is that a public-key encryption scheme allows a sender to choose an arbitrary message from some space of possible messages, while a KEM chooses a short secret key at random for the sender.

[1][2][3] The sender may take the random secret key produced by a KEM and use it as a symmetric key for an authenticated cipher whose ciphertext is sent alongside the encapsulation to the receiver.

This serves to compose a public-key encryption scheme out of a KEM and a symmetric-key authenticated cipher in a hybrid cryptosystem.

[1][2][3][5] Most public-key encryption schemes such as RSAES-PKCS1-v1_5, RSAES-OAEP, and Elgamal encryption are limited to small messages[6][7] and are almost always used to encrypt a short random secret key in a hybrid cryptosystem anyway.

[8][9][5] And although a public-key encryption scheme can conversely be converted to a KEM by choosing a random secret key and encrypting it as a message, it is easier to design and analyze a secure KEM than to design a secure public-key encryption scheme as a basis.

So most modern public-key encryption schemes are based on KEMs rather than the other way around.

[2][3][11][12] Security of a KEM is quantified by its indistinguishability against chosen-ciphertext attack, IND-CCA, which is loosely how much better an adversary can do than a coin toss to tell whether, given a random key and an encapsulation, the key is encapsulated by that encapsulation or is an independent random key.

, that is, the probability beyond a fair coin toss at correctly distinguishing an encapsulated key from an independently randomly chosen key.

, is defined as follows:[13][14][15] This naive approach is totally insecure.

For example, since it is nonrandomized, it cannot be secure against even known-plaintext attack—an adversary can tell whether the sender is sending the message ATTACK AT DAWN versus the message ATTACK AT DUSK simply by encrypting those messages and comparing the ciphertext.

simply by taking real number cube roots, and there are many other attacks against plain RSA.

[13][14] Various randomized padding schemes have been devised in attempts—sometimes failed, like RSAES-PKCS1-v1_5[13][17][18]—to make it secure for arbitrary short messages

is almost always a short secret key for a symmetric-key authenticated cipher used to encrypt an arbitrary bit string message, a simpler approach called RSA-KEM is to choose an element of

, roughly as follows:[19][8] This approach is simpler to implement, and provides a tighter reduction to the RSA problem, than padding schemes like RSAES-OAEP.

[19] Traditional Elgamal encryption is defined over a multiplicative subgroup of the finite field

as follows:[20][21] This meets the syntax of a public-key encryption scheme, restricted to messages in the space

(which limits it to message of a few hundred bytes for typical values of

By validating ciphertexts in decryption, it avoids leaking bits of the private key

through maliciously chosen ciphertexts outside the group generated by

However, this fails to achieve indistinguishability against chosen ciphertext attack.

[20] Traditional Elgamal encryption can be adapted to the elliptic-curve setting, but it requires some way to reversibly encode messages as points on the curve, which is less trivial than encoding messages as integers mod

is almost always a short secret key for a symmetric-key authenticated cipher used to encrypt an arbitrary bit string message, a simpler approach is to derive the secret key from

altogether, as a KEM, using a key derivation function

:[1] When combined with an authenticated cipher to encrypt arbitrary bit string messages, the combination is essentially the Integrated Encryption Scheme.

Since this KEM only requires a one-way key derivation function to hash random elements of the group it is defined over,

in this case, and not a reversible encoding of messages, it is easy to extend to more compact and efficient elliptic curve groups for the same security, as in the ECIES, Elliptic Curve Integrated Encryption Scheme.

Flow diagram of a key encapsulation mechanism, relating the inputs and outputs of the Gen, Encap, and Decap algorithms of a KEM
A key encapsulation mechanism, to securely transport a secret key from a sender to a receiver, consists of three algorithms: Gen, Encap, and Decap. Circles shaded blue—the receiver's public key and the encapsulation —can be safely revealed to an adversary, while boxes shaded red—the receiver's private key and the encapsulated secret key —must be kept secret.
Flow diagram of a public-ken encryption scheme, relating the inputs and outputs of its Gen, Encrypt, and Decrypt algorithms
A public-key encryption scheme.