Key encapsulation mechanism

Not to be confused with key wrap.

A key encapsulation mechanism, to securely transport a secret key ${\displaystyle k}$ from a sender to a receiver, consists of three algorithms: Gen, Encap, and Decap. Circles shaded blue—the receiver's public key ${\displaystyle pk}$ and the encapsulation ${\displaystyle c}$—can be safely revealed to an adversary, while boxes shaded red—the receiver's private key ${\displaystyle sk}$ and the encapsulated secret key ${\displaystyle k}$—must be kept secret.

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] [4]}

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. The receiver who knows the private key corresponding to the public key can recover the same random secret key from the encapsulation by the KEM's decapsulation 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]}

Difference from public-key encryption

A public-key encryption scheme.

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. ^{[10] [5]}

Definition

Syntax

A KEM consists of three algorithms: ^{[1] [2] [3] [11] [12]}

1. Key generation, ${\displaystyle ({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()}$, takes no inputs and returns a pair of a public key ${\displaystyle {\mathit {pk}}}$ and a private key ${\displaystyle {\mathit {sk}}}$.
2. Encapsulation, ${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$, takes a public key ${\displaystyle {\mathit {pk}}}$, randomly chooses a secret key ${\displaystyle k}$, and returns ${\displaystyle k}$ along with its encapsulation ${\displaystyle c}$.
3. Decapsulation, ${\displaystyle k':=\operatorname {Decap} ({\mathit {sk}},c')}$, takes a private key ${\displaystyle {\mathit {sk}}}$ and an encapsulation ${\displaystyle c'}$, and either returns an encapsulated secret key ${\displaystyle k'}$ or fails, sometimes denoted by returning ${\displaystyle \bot }$ (called ‘bottom’).

Correctness

A KEM is correct if, for any key pair ${\displaystyle ({\mathit {pk}},{\mathit {sk}})}$ generated by ${\displaystyle \operatorname {Gen} }$, decapsulating an encapsulation ${\displaystyle c}$ returned by ${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$ with high probability yields the same key ${\displaystyle k}$, that is, ${\displaystyle \operatorname {Decap} ({\mathit {sk}},c)=k}$. ^{[2] [3] [11] [12]}

Security: IND-CCA

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. ^{[2] [3] [11] [12]}

Specifically, in the IND-CCA game:

1. The key generation algorithm is run to generate ${\displaystyle ({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()}$.
2. ${\displaystyle {\mathit {pk}}}$ is revealed to the adversary.
3. The adversary can query ${\displaystyle \operatorname {Decap} ({\mathit {sk}},c')}$ for arbitrary encapsulations ${\displaystyle c'}$ of the adversary's choice.
4. The encapsulation algorithm is run to randomly generate a secret key and encapsulation ${\displaystyle (k_{0},c):=\operatorname {Encap} ({\mathit {pk}})}$, and another secret key ${\displaystyle k_{1}}$ is generated independently at random.
5. A fair coin is tossed, giving an outcome ${\displaystyle b\in \{0,1\}}$.
6. The pair ${\displaystyle (k_{b},c)}$ is revealed to the adversary.
7. The adversary can again query ${\displaystyle \operatorname {Decap} ({\mathit {sk}},c')}$ for arbitrary encapsulations ${\displaystyle c'}$ of the adversary's choice, except for ${\displaystyle c}$.
8. The adversary returns a guess ${\displaystyle b'\in \{0,1\}}$, and wins the game if ${\displaystyle b=b'}$.

The IND-CCA advantage of the adversary is ${\displaystyle \left|\Pr[b'=b]-1/2\right|}$, that is, the probability beyond a fair coin toss at correctly distinguishing an encapsulated key from an independently randomly chosen key.

Examples and motivation

RSA

Traditional RSA encryption, with ${\displaystyle t}$-bit moduli and exponent ${\displaystyle e}$, is defined as follows: ^{[13] [14] [15]}

• Key generation, ${\displaystyle ({\mathit {pk}},{\mathit {sk}}):=\operatorname {Gen} ()}$:

1. Generate a ${\displaystyle t}$-bit semiprime ${\displaystyle n}$ with ${\displaystyle 2^{t-1}<n<2^{t}}$ at random satisfying ${\displaystyle \gcd(e,\lambda (n))=1}$, where ${\displaystyle \lambda (n)}$ is the Carmichael function.
2. Compute ${\displaystyle d:=e^{-1}{\bmod {\lambda }}(n)}$.
3. Return ${\displaystyle {\mathit {pk}}:=n}$ as the public key and ${\displaystyle {\mathit {sk}}:=(n,d)}$ as the private key. (Many variations on key generation algorithms and private key formats are available. ^[16] )

• Encryption of ${\displaystyle (t-1)}$-bit message ${\displaystyle m}$ to public key ${\displaystyle {\mathit {pk}}=n}$, giving ${\displaystyle c:=\operatorname {Encrypt} ({\mathit {pk}},m)}$:

1. Encode the bit string ${\displaystyle m}$ as an integer ${\displaystyle r}$ with ${\displaystyle 0\leq r<n}$.
2. Return ${\displaystyle c:=r^{e}{\bmod {n}}}$.

• Decryption of ciphertext ${\displaystyle c'}$ with private key ${\displaystyle {\mathit {sk}}=(n,d)}$, giving ${\displaystyle m':=\operatorname {Decrypt} ({\mathit {sk}},c')}$:

1. Compute ${\displaystyle r':=(c')^{d}{\bmod {n}}}$.
2. Decode the integer ${\displaystyle r'}$ as a bit string ${\displaystyle m'}$.

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.

Even if ${\displaystyle m}$ is always a random secret key, such as a 256-bit AES key, when ${\displaystyle e}$ is chosen to optimize efficiency as ${\displaystyle e=3}$, the message ${\displaystyle m}$ can be computed from the ciphertext ${\displaystyle c}$ 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 ${\displaystyle m}$. ^{[13] [14]}

Since the message ${\displaystyle m}$ 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 ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ at random and use that to derive a secret key using a key derivation function ${\displaystyle H}$, roughly as follows: ^{[19] [8]}

• Key generation: As above.
• Encapsulation for a public key ${\displaystyle {\mathit {pk}}=n}$, giving ${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$:

1. Choose an integer ${\displaystyle r}$ with ${\displaystyle 0\leq r<n}$ uniformly at random.
2. Return ${\displaystyle k:=H(r)}$ and ${\displaystyle c:=r^{e}{\bmod {n}}}$ as its encapsulation.

• Decapsulation of ${\displaystyle c'}$ with private key ${\displaystyle {\mathit {sk}}=(n,d)}$, giving ${\displaystyle k':=\operatorname {Decap} ({\mathit {sk}},c')}$:

1. Compute ${\displaystyle r':=(c')^{d}{\bmod {n}}}$.
2. Return ${\displaystyle k':=H(r')}$.

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

Elgamal

Traditional Elgamal encryption is defined over a multiplicative subgroup of the finite field ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ with generator ${\displaystyle g}$ of order ${\displaystyle q}$ as follows: ^{[20] [21]}

• Key generation, ${\displaystyle (pk,sk):=\operatorname {Gen} ()}$:

1. Choose ${\displaystyle x\in \mathbb {Z} /q\mathbb {Z} }$ uniformly at random.
2. Compute ${\displaystyle y:=g^{x}{\bmod {p}}}$.
3. Return ${\displaystyle {\mathit {sk}}:=x}$ as the private key and ${\displaystyle {\mathit {pk}}:=y}$ as the public key.

• Encryption of a message ${\displaystyle m\in \mathbb {Z} /p\mathbb {Z} }$ to public key ${\displaystyle {\mathit {pk}}=y}$, giving ${\displaystyle c:=\operatorname {Encrypt} ({\mathit {pk}},m)}$:

1. Choose ${\displaystyle r\in \mathbb {Z} /q\mathbb {Z} }$ uniformly at random.
2. Compute: $${\displaystyle {\begin{aligned}t&:=y^{r}{\bmod {p}}\\c_{1}&:=g^{r}{\bmod {p}}\\c_{2}&:=(t\cdot m){\bmod {p}}\end{aligned}}}$$
3. Return the ciphertext ${\displaystyle c:=(c_{1},c_{2})}$.

• Decryption of a ciphertext ${\displaystyle c'=(c'_{1},c'_{2})}$ for a private key ${\displaystyle {\mathit {sk}}=x}$, giving ${\displaystyle m':=\operatorname {Decrypt} ({\mathit {sk}},c')}$:

1. Fail and return ${\displaystyle \bot }$ if ${\displaystyle (c'_{1})^{(p-1)/q}\not \equiv 1{\pmod {p}}}$ or if ${\displaystyle (c'_{2})^{(p-1)/q}\not \equiv 1{\pmod {p}}}$, i.e., if ${\displaystyle c'_{1}}$ or ${\displaystyle c'_{2}}$ is not in the subgroup generated by ${\displaystyle g}$.
2. Compute ${\displaystyle t':=(c'_{1})^{x}{\bmod {p}}}$.
3. Return ${\displaystyle m':=t^{-1}c'_{2}{\bmod {p}}}$.

This meets the syntax of a public-key encryption scheme, restricted to messages in the space ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ (which limits it to message of a few hundred bytes for typical values of ${\displaystyle p}$). By validating ciphertexts in decryption, it avoids leaking bits of the private key ${\displaystyle x}$ through maliciously chosen ciphertexts outside the group generated by ${\displaystyle g}$.

However, this fails to achieve indistinguishability against chosen ciphertext attack. For example, an adversary having a ciphertext ${\displaystyle c=(c_{1},c_{2})}$ for an unknown message ${\displaystyle m}$ can trivially decrypt it by querying the decryption oracle for the distinct ciphertext ${\displaystyle c':=(c_{1},c_{2}g)}$, yielding the related plaintext ${\displaystyle m':=mg{\bmod {p}}}$, from which ${\displaystyle m}$ can be recovered by ${\displaystyle m=m'g^{-1}{\bmod {p}}}$. ^[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 ${\displaystyle p}$. ^[22]

Since the message ${\displaystyle m}$ 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 ${\displaystyle t}$ and dispense with ${\displaystyle m}$ and ${\displaystyle c_{2}}$ altogether, as a KEM, using a key derivation function ${\displaystyle H}$: ^[1]

• Key generation: As above.
• Encapsulation for a public key ${\displaystyle {\mathit {pk}}=y}$, giving ${\displaystyle (k,c):=\operatorname {Encap} ({\mathit {pk}})}$:

1. Choose ${\displaystyle r\in \mathbb {Z} /q\mathbb {Z} }$ uniformly at random.
2. Compute ${\displaystyle t:=y^{r}{\bmod {p}}}$.
3. Return ${\displaystyle k:=H(t)}$ and ${\displaystyle c:=g^{r}{\bmod {p}}}$ as its encapsulation.

• Decapsulation of ${\displaystyle c'}$ with private key ${\displaystyle {\mathit {sk}}=x}$, giving ${\displaystyle k':=\operatorname {Decap} ({\mathit {sk}},c')}$:

1. Fail and return ${\displaystyle \bot }$ if ${\displaystyle (c')^{(p-1)/q}\not \equiv 1{\pmod {p}}}$, i.e., if ${\displaystyle c'}$ is not in the subgroup generated by ${\displaystyle g}$.
2. Compute ${\displaystyle t':=(c')^{x}{\bmod {p}}}$.
3. Return ${\displaystyle k':=H(t')}$.

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, ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ 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.

References

1. Galbraith, Steven (2012). "§23.1.1: The KEM/DEM paradigm". Mathematics of Public-Key Cryptography. Cambridge University Press. pp. 471–478. ISBN   978-1-107-01392-6.
2. Shoup, Victor (May 2000). Preneel, Bart (ed.). Using Hash Functions as a Hedge against Chosen Ciphertext Attack. Advances in Cryptology – EUROCRYPT 2000. Lecture Notes in Computer Science. Vol. 1807. Bruges, Belgium: Springer. pp. 275–288. doi: 10.1007/3-540-45539-6_19 . ISBN   978-3-540-67517-4.
3. Cramer, Ronald; Shoup, Victor (2003). "Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack". SIAM Journal on Computing. 33 (1). Society for Industrial and Applied Mathematics: 167–226. doi:10.1137/S0097539702403773.
4. FIPS 203 (Draft): Module-Lattice-Based Key-Encapsulation Mechanism Standard (PDF), National Institute of Standards and Technology, 2023-08-24, doi: 10.6028/NIST.FIPS.203.ipd
5. Barnes, R.; Bhargavan, K.; Lipp, B.; Wood, C. (February 2022). Hybrid Public Key Encryption. Internet Engineering Task Force. doi: 10.17487/RFC9180 . RFC 9180.
6. Kaliski, B.; Jonsson, J.; Rusch, A. (November 2016). Moriarity, K. (ed.). PKCS #1: RSA Cryptography Specifications Version 2.2. Internet Engineering Task Force. doi: 10.17487/RFC8017 . RFC 8017.
7. Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (October 1996). "8. Public-Key Encryption". Handbook of Applied Cryptography (PDF). CRC Press. pp. 283–319. ISBN   0-8493-8523-7.
8. Ferguson, Niels; Kohno, Tadayoshi; Schneier, Bruce (2010). "12. RSA". Cryptography Engineering. Wiley. pp. 195–211. ISBN   978-0-470-47424-2.
9. Callas, J.; Donnerhacke, L.; Finney, H.; Shaw, D.; Thayer, R. (November 2007). OpenPGP Message Format. Internet Engineering Task Force. doi: 10.17487/RFC4880 . RFC 4880.
10. "Post-Quantum Cryptography: FAQs". National Institute of Standards and Technology. 2024-07-19. Archived from the original on 2024-06-26. Retrieved 2024-07-20.
11. Dent, Alexander W. (2002), A Designer’s Guide to KEMs, Cryptology ePrint Archive, International Association for Cryptologic Research
12. Hofheinz, Dennis; Hövelmanns, Kathrin; Kiltz, Eike (November 2017). Kalai, Yael; Reyzin, Leonid (eds.). A Modular Analysis of the Fujisaki-Okamoto Transformation. Theory of Cryptography – TCC 2017. Lecture Notes in Computer Science. Vol. 10677. Baltimore, MD, United States: Springer. pp. 341–371. doi: 10.1007/978-3-319-70500-2_12 . ISBN   978-3-319-70499-9.
13. Aumasson, Jean-Philippe (2018). "10. RSA". Serious Cryptography: A Practical Introduction to Modern Encryption. No Starch Press. pp. 181–199. ISBN   978-1-59327-826-7.
14. Stinson, Douglas R. (2006). "5. The RSA Cryptosystem and Factoring Integers". Cryptography Theory and Practice (3rd ed.). Chapman & Hall/CRC. pp. 161–232. ISBN   978-1-58488-508-5.
15. Rivest, R.L.; Shamir, A.; Adleman, L. (1978-02-01). "A method for obtaining digital signatures and public-key cryptosystems" (PDF). Communications of the ACM. 21 (2). Association for Computer Machinery: 120–126. doi: 10.1145/359340.359342 .
16. Švenda, Petr; Nemec, Matúš; Sekan, Peter; Kvašňovský, Rudolf; Formánek, David; Komárek, David; Matyáš, Vashek (August 2016). The Million-Key Question—Investigating the Origins of RSA Public Keys. 25th USENIX Security Symposium. Austin, TX, United States: USENIX Association. pp. 893–910. ISBN   978-1-931971-32-4.
17. Bleichenbacher, Daniel (August 1998). Krawczyk, Hugo (ed.). Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. Advances in Cryptology – CRYPTO '98. Lecture Notes in Computer Science. Vol. 1462. Santa Barbara, CA, United States: Springer. pp. 1–12. doi: 10.1007/BFb0055716 . ISBN   978-3-540-64892-5.
18. Coron, Jean-Sébastien; Joye, Marc; Naccache, David; Paillier, Pascal (May 2000). Preneel, Bart (ed.). New Attacks on PKCS#1 v1.5 Encryption. Advances in Cryptology – EUROCRYPT 2000. Lecture Notes in Computer Science. Vol. 1807. Bruges, Belgium: Springer. pp. 369–381. doi: 10.1007/3-540-45539-6_25 . ISBN   978-3-540-67517-4.
19. Shoup, Victor (2001), A Proposal for an ISO Standard for Public Key Encryption (version 2.1), Cryptology ePrint Archive, International Association for Cryptologic Research
20. Galbraith, Steven (2012). "§20.3: Textbook Elgamal encryption". Mathematics of Public-Key Cryptography. Cambridge University Press. pp. 471–478. ISBN   978-1-107-01392-6.
21. Elgamal, Taher (August 1984). Blakley, George Robert; Chaum, David (eds.). A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. Advances in Cryptology – CRYPTO 1984. Lecture Notes in Computer Science. Vol. 196. Santa Barbara, CA, United States: Springer. pp. 10–18. doi: 10.1007/3-540-39568-7_2 . ISBN   978-3-540-15658-1.
22. Koblitz, Neal (January 1987). "Elliptic Curve Cryptosystems" (PDF). Mathematics of Computation. 48 (177). American Mathematical Society: 203–209. doi: 10.1090/S0025-5718-1987-0866109-5 .

See also

• Key Wrap
• Optimal Asymmetric Encryption Padding
• Hybrid Cryptosystem