2022-08-14

Some KEMs and Some Proofs

• #cryptography
• #foundations
• #kems

In this post, I'd like to provide a technical introduction to key encapsulation mechanisms (KEMs), with a focus on proving the security of various constructions.

A key encapsulation mechanism is like a public key encryption scheme, tailored to the specific use case of sending a key to the other party. This can be used to establish shared key between two parties. One of them runs the KEM, getting a shared key and a ciphertext, and then sends that ciphertext to the other person. That person can unwrap the ciphertext to recover the shared key. From that point on, the parties can use that shared key to communicate privately.

In this way, you can think of KEMs as a generalization of key exchanges, which don't have to be symmetric. In fact, you can use a key exchange to construct a KEM, as we'll see later.

In this post, we'll go over:

• How to define KEMs.
• How to capture the security of KEMs with games.
• How these notions of security compare with other variations.
• How to construct a secure KEM from RSA.
• How to construct a secure KEM using Elliptic Curves.

There are other important topics around KEMs that I'd also like to touch upon, but this sample is already quite a hefty serving if you include all of the proofs; those will have to wait for a future post.

Background

For a high level overview of KEMs, I'd recommend Neil Madden's post on the subject.

This post is more focused on the technical side of things, and on provable security. I'll be using state separable proofs pervasively throughout this post, so I'd recommend reading my post on the subject if you'd like to get up to speed.

Defining KEMs

To begin, let's formally define what a KEM is.

A key encapsulation mechanism (KEM), is a scheme similar to public key encryption. This scheme consists of three algorithms:

The first algorithm, $\text{Gen}$, creates a new key pair, consisting of a private key, and its corresponding public key.

The second algorithm, $\text{Encap}$, takes in a public key, for the recipient, and returns a symmetric key and an encapsulation (also called a ciphertext).

With $\text{Decap}$, a recipient can use their private key to extract a symmetric key from the ciphertext.

This scheme also needs to satisfy some notion of correctness. Intuitively, decapsulating should return the same key that was encapsulated.

More formally, the following procedure must always succeed:

No matter what key pair comes out of $\text{Gen}$, encapsulating and then decapsulating must return the same key. If this didn't hold, your KEM wouldn't be very useful for establishing a shared key between two parties, or for public key encryption, which are two of the main use cases for KEMs.

$\text{IND}$ Security

Naturally, having a correct scheme is easy if you don't care about security. The usual notion of security is similar to that of public key encryption. The basic idea is that you shouldn't be able to tell whether or not a specific key is hidden inside of the ciphertext. In particular, you shouldn't be able to distinguish between receiving a random key, and receiving the key inside of a ciphertext.

We formalize this as a pair of games, in the state separable style:

In one version of the game, we get the key inside the encapsulation, and in the other version of the game, we get a completely random key. An adversary should not be able to distinguish between the two games.

This means that the adversary can't learn any information about the key from the ciphertext.

[!note] Note: In this variant, you can query the challenge multiple times. This is equivalent to only being able to query once, although the security gets worse as a linear function of the number of queries you do. For simplicity, I'll stick with the multi-query variants for the rest of this post.

This variant of security can also be referred to as $\text{IND-CPA}$. This is because the adversary is able to create encapsulations themselves, because they know the public key. This kind of query is a chosen plaintext, hence the chosen plaintext attack (CPA) in the name.

With symmetric encryption, on the other hand, you need to have a secret key to even encrypt data, so the $\text{CPA}$ capability is a meaningful distinction.

$\text{IND-CCA}$ Security

An even stronger variant of security also allows the adversary to make decapsulation queries on ciphertexts of their choice. We call these chosen ciphertext attacks (CCA). This models situations where we might know the keys inside certain ciphertexts. While in practice these leakages could be quite limited, having a more expansive model of security covers many more situations, and we can construct schemes which satisfy this general model.

We model this with a pair of games, like before:

This is the same as the previous $\text{IND}$ game, except that we now have the ability to make decapsulation queries. In order to make the game not trivially easy to win, we keep track of which challenge ciphertexts have been produced, and refuse decapsulation queries for that set. Otherwise, you could ask for the decapsulation for a ciphertext you saw earlier, and compare the result with the key you received before.

Equivalence with Other Definitions

[!note] Note: You can skip this section. It's mainly concerned with resolving a small discrepancy in definitions between this post and the broader literature.

In the games we've seen so far, the adversary only sees one of the keys. We can also model a situation where the adversary sees both of the keys:

Instead of giving them one of the keys like before, we give them both, but we swap their order. The adversary has to tell which key is which.

One natural question is whether or not this new game is equivalent to our previous definitions.

It is.

As a bit of a warmup, let's prove this equivalence.

$\text{IND-Both-CCA} \leq 2 \cdot \text{IND-CCA}$

The idea of this reduction is that we can replace $k_0$ from the first encapsulation with a random key, because of $\text{IND-CCA}$ security. This then allows us to swap $k_0$ with $k_1$, and then walk our way backwards, giving us a bound for $\epsilon(\text{IND-Both-CCA}_b)$.

We start by extracting out the encapsulation in $\text{IND-Both-CCA}_b$, using $\text{IND-CCA}$:

Using this, we can already march some of the way forward, giving us:

Now, one thing we can note is that:

To notice this, first expand out the game:

Because both $k_0$ and $k_1$ get sampled at random, it doesn't matter which order they have.

We can now align these togethers to get:

which gives us our result.

$\square$

Now, for the other direction.

$\text{IND-Both-CCA} \leq \text{IND-CCA}$

The idea of this proof is that we can emulate $\text{IND-CCA}$ using $\text{IND-Both-CCA}$ by dropping one of the keys. The question is: which key do we drop? Because we can't distinguish between $k_0$ and $k_1$, it doesn't matter which one we choose, essentially.

First, let's define the following wrapper package:

This perfectly emulates $\text{IND-CCA}_b$ when composed with $\text{IND-Both-CCA}_0$:

With $\text{IND-Both-CCA}_1$ on the other hand, the bit is flipped:

This is enough for us to write:

Which gives us the reduction we sought.

$\square$

Real-or-Random is Essential

These definitions turned out to be equivalent, but both fit into a kind of "real-or-random" paradigm: one of the keys is randomly selected, while the other is related to the ciphertext. This is a general kind of paradigm, which can be used to define the security of other schemes as well. It's useful to stay within this paradigm, since phrasing all of our security definitions in terms of real-or-random makes it easier to do reductions.

One alternative paradigm, that gets used for public key encryption, is "left-or-right". With this approach, instead of having a random output and a real output, you instead have two outputs, and you try and distinguish between them.

For the KEM case, this would give the following game:

Unfortunately, this definition fails to capture a useful notion. The issue is that we have no guarantee that the key is sufficiently random, which makes it not usable for encryption later.

As an example, consider the following KEM:

This KEM always returns the same key for encapsulation and decapsulation, which makes it completely useless to construct a secure public key encryption scheme. It does, however, satisfy the $\text{IND-LR}$ definition of security above. This is because $(0, 0, c_b)$ contains no information about $b$.

Constructing KEMs

We've now seen a bit of how KEMs work in theory, but we've yet to actually see an example of making one. In this section, we go over a few potential constructions of KEMs, and show that they're secure, under appropriate assumptions.

From RSA

Let's start with RSA. There are thousands of good explanations of RSA, so I'll settle for a bad, but short, explanation.

In RSA, your public key consists of a modulus $N$, and a number $e$. Your secret key consists of a factorization $p, q$ such that $N = p \cdot q$, along with a secret exponent $d$, such that

These parameters give us a trapdoor permutation for the set $\mathbb{Z}/(N)$:

The function $F$ is a permutation, with $F^{-1}$ its inverse. Computing the inverse should be hard without knowing the secret exponent $d$, or being able to factor $N$.

We make this security notion precise with the following game:

The adversary makes guesses for the pre-image of the permutation, and it should be difficult for them to succeed in their guess. If the adversary has a good strategy for guessing, then they'll be able to figure out what $b$ is.

We can use RSA to create a KEM. The pre-image $x$ will be our key, and then $y := x^e \mod N$ is our ciphertext, hiding the key. The recipient can use their secret to unwrap $x$ from this ciphertext. Now, because $\mathbb{Z}/(N)$ may not be a very useful key by itself, we also make use of a hash function $H : \mathbb{Z}/(N) \to \bold{K}$, so that we can derive a more useful key from $x$.

For example, if we wanted to use our key for encryption with AES, or ChaCha20, we'd want to use a hash function from integers to 256 bit keys.

More formally, we define the following KEM:

Because the RSA function is a permutation, correctness is satisfied.

As for security, this isn't a trivial matter. First, we'll model our hash function $H$ as a random oracle, where the outputs will be generated perfectly at random, on demand. Second, rather than considering normal $\text{IND-CCA}$ security, instead we'll consider $\text{IND-CCA-1}$ security, where the adversary can only make a single challenge query. Making $Q$ challenge queries instead of just a single one only decreases security by a factor of $Q$, as can be shown via a hybrid argument. (My post on state-separable proofs contains a proof of this in the general case).

$\text{IND-CCA-1} \leq 2 \cdot \text{RSA}$

First, let's write down the $\text{IND-CCA-1}$ game in this context.

The $(1)$ notation means that $\texttt{Challenge}$ can only be queried a single time. We've also replaced the hash function with a lazily initialized table of random values. This is why we're doing our proof in the "random oracle model", since the hash function is being modelled this way.

Next, we follow the same strategy as in Theorem 12.2 of Boneh and Shoup.

Rather than having our table $h$ be used for the pre-images $x$, instead we'll setup a table $h'$ for the images $y$. This will allow us to minimize our use of the secret key $d$ in decapsulation queries, which makes it easier to extract out the RSA functionality for our package.

Since we only have a single challenge query, we can generate the instance before $\texttt{Challenge}$ is called. We'll also be able to do a lot of tricks with the decapsulation queries, but it's easier to explain those after seeing the new game:

The big trick we've pulled in this game is in our decapsulation function. By having a hash table for the images $y$, we avoid the need to make use of the secret key $d$ when decapsulating. Whereas we'd normally compute $x \gets y^d \mod N$, and then query $\texttt{H}(x)$, because our hash function then computes $x^e \mod N$ to index into our table, we can avoid all of that, and use the table ourselves.

Naturally, we have $\text{IND-CCA-1}_b = \Gamma^0_b$.

From this point on, it's relatively straight sailing.

We start by extracting out the RSA functionality:

Now we use the $\text{RSA}_0$ game to determine if we need to return $k_0$ in our hash function. Next, note that if we switch to using $\text{RSA}_1$, we get the following game:

And in this game, the difference between $k_0$ and $k_1$ is just a matter of naming. Because of this, $\Gamma^2_0 = \Gamma^2_1$.

We can now tie everything together, to get:

And this yields our result.

$\square$

From Groups

Another way to construct a KEM is with a cryptographic group, like a suitable elliptic curve.

This is a group $\mathbb{G}$ of prime order $q$, generated by $G$, and with an associated field of scalars $\mathbb{F}_q$.

A key pair for the KEM will be a scalar $a$, for the private key, and a point ${A := a \cdot G}$, for the public key. In order to encapsulate a key, we generate a random scalar $b$, set ${B := b \cdot G}$ as our encapsulation, and $H(b \cdot A)$ as the key. The receiver can set $H(a \cdot B)$ as their key, arriving at the same result because of commutativity:

More formally, given a cryptographic group $\mathbb{G}$, and a hash function $H : \mathbb{G}^2 \to \bold{K}$, we define the KEM as follows:

One slight difference from the brief presentation above is that we hash both $B$ and $C$, rather than just $C$. This makes the security proof easier.

To characterize the security of the KEM, we need to have some kind notion of security for the group itself. The notion we'll be relying on (at least, in our proof), is the "interactive computational Diffie-Hellman" problem. This states, essentially, that given two points $A = a \cdot G$ and $B = b \cdot G$, it should be hard to find $C = ab \cdot G$, even given access to an oracle which tells you whether or not two points $\hat{B}$ and $\hat{C}$ satisfy the relation $a \cdot \hat{B} = \hat{C}$.

We capture this notion through a guessing game:

This notion suffices to prove $\text{IND-CCA}$ security of the KEM:

$\text{IND-CCA-1} \leq 2 \cdot \text{ICDH}_b$

We'll model our hash function as a random oracle, like with RSA.

Let's start by explicitly writing down the $\text{IND-CCA-1}$ game in this context:

Next, like with the RSA kem proof, we need to minimize our use of the secret key when decapsulating. We follow the same strategy as in Theorem 12.4 of Boneh and Shoup.

We replace our hash table for pairs $(B, C)$ with a table for $B$, when $C = a \cdot B$, and a table for $(B, C)$, when $B$ and $C$ are not related. Since we only have a single challenge query, we can also lift generation of those values outside the challenge.

This gives us the following game:

Basically, we maintain the invariant that $a \cdot \hat{B} = \hat{C} \implies h[\hat{B}, \hat{C}] = h'[\hat{B}]$. this allows us to make decapsulation queries without making use of the secret key. This will make extracting out the $\text{ICDH}$ game much easier. This extraction is also made easier in that the query $a \cdot \hat{B} = \hat{C}$ is precisely the kind of query we can do in this game.

The next step is to extract out $\text{ICDH}$:

Now, notice that in the game $\Gamma^1_b \circ \text{ICDH}_1$, $k_0$ isn't used anywhere but inside of $\texttt{Challenge}$, because $\texttt{Guess}$ always returns $0$. This means that the difference between $k_0$ and $k_1$ becomes a matter of naming, so:

This is enough to make our full walk, and tie everything together:

$\square$

And Other Methods

Another method that's going to be increasingly important is using lattices to construct KEMs.

Both of the schemes I've mentioned in this post, using RSA, and using elliptic curves, will be broken by future quantum computers. This is why NIST started a competition in order to standardize KEMs secure against quantum computers.

Many of the candidates were based on lattices, including the finalist, Kyber.

Other candidates used different primitives, like isogenies, or random codes.

Composing KEMs

Talking about the post-quantum KEMs segues nicely into this next topic. Right now, we have very well tested and trusted KEMs, which aren't secure against quantum computers. We also have a new KEM which should be secure against quantum computers, but given its novelty, you may not trust it that much yet.

Because of this, many people are trying to deploy both schemes together in a hybrid fashion. This means that you can get post-quantum security if the new KEM stands the test of time, but you also don't sacrifice classical security if the new KEM you include happens to be flawed.

To achieve this, what you want is a way to combine KEMs, mixing together KEMs $A$ and $B$ to create a new KEM, which should be secure as long as at least one of the two ingredients is. If $A$ is broken, that's fine as long as $B$ is secure, and vice versa.

This construction is called a KEM combiner, and it can combine two KEMs in this way, without having to inspect how the KEMs work internally at all. The paper [^[GHP18]] goes over this notion of combiners, and presents a very elegant construction.

To encapsulate, you call each of the individual KEMs first, giving you $(k_A, c_A)$ and $(k_B, c_B)$. Next, $(c_A, c_B)$ becomes your ciphertext. Now, you need some way to combine all of this information to derive a single key $k$. One idea would be to simply xor the two keys, giving you $k \gets k_A \oplus k_B$. Unfortunately, this is not IND-CCA secure, because the resulting key is malleable.

The idea in this paper is instead to use a kind of pseudo-random function (PRF) to derive the result:

This is a special kind of PRF called a split-key PRF.

Split-Key PRFs in Theory

More formally, a split-key PRF is a function: