MPC FHE: Key-Switching

In this blogpost, we describe the key-switching operation, which is a key primitive (no pun intended) within Multiparty Computation Fully Homomorphic Encryption (MPC-FHE).

The jump from FHE to MPC-FHE

In previous blogposts, we introduced the notion of Fully Homomorphic Encryption (FHE), which allows parties to perform arbitrary computations on encrypted data, without decrypting it.

On a higher application-based level, our current notion of FHE looks like the following:

• The user has some data and wants to keep it private, so they encrypt it under their secret key $\mathsf{sk}$ to obtain $\operatorname{Enc}_{\mathsf{sk}}(m)$.
• The user can now give this encrypted data to a server. The server computes some function on the encrypted data $\operatorname{Enc}_{\mathsf{sk}}(f(m))$ using the “homomorphic” nature of the scheme, without learning $m$.
• The server can give $\operatorname{Enc}_{\mathsf{sk}}(f(m))$ back to the user, and the user decrypts under $\mathsf{sk}$ to get $f(m).$

Note that this application only supports computation on a single user’s data. What happens if we instead we have parties $A$ and $B$, with secret data $a$ and $b,$ respectively, and they wish to compute $f(a,b)$ without revealing other information about $a$ or $b$? This general problem is called Multiparty Computation Fully Homomorphic Encryption, or MPC-FHE for short.

The main issue we run into with trying to plug in our existing primitive (“server computes arbitrary function on private data”) is that now each user’s data is encrypted under different secrets (say we have $\operatorname{Enc}_{\mathsf{sk}_a}(m_a)$ and $\operatorname{Enc}_{\mathsf{sk}_b}(m_b)$), while evaluating OR/AND gates homomorphically require that inputs are encrypted under the same private key.

One operation that solves this is called “key-switching”, which can be stated somewhat formally as follows:

• Given $\operatorname{Enc}_{\mathsf{sk}}(m)$, how do we get $\operatorname{Enc}_{\mathsf{sk}'}(m)$ where $\mathsf{sk}' \neq \mathsf{sk}$? What do we need to get this?

With this, we can switch all parties’ encrypted inputs to the same key, and then proceed with our homomorphic evaluation of $f(a,b).$

How key-switching works

So now that we’ve described the problem that we’re trying to solve and why we need it in MPC-FHE, what does the solution look like?

Current MPC-FHE schemes generally use Learning With Error (LWE) FHE schemes, which is what we will use as our basis to discuss key switching. We briefly explain the mechanics of LWE below.

Learning with Errors (LWE)

For simplicity, we’ll look at the symmetric-key version of LWE, where we just have a secret key $\mathsf{sk}$ that is used both to encrypt and to decrypt. We talked about LWE in a previous post, so we’ll just briefly remind ourselves how it works.

Our secret key is a tuple $S = (s_1, \dots, s_n) \in \mathbb{Z}_q^n$. Suppose we have a message $m$, which is a single bit. Usually a bit is 0 or 1, but this time we’re going to encode it as either $0$ or $q/2$. (If $q$ is odd, just use $(q-1)/2$ instead.)

What are the parameters $q$ and $n$? There are lots of possible values. You should imagine that $1000 \leq q \leq 2^{256}$: in other words, $q$ could be as small as a few thousand, or it could be as big as a cryptographically-sized prime. And $n$ might lie in the range $10 \leq n \leq 1000$.

To encrypt $m$, we will give any tuple

$$\operatorname{Enc}_{S}(m) = (x_1, x_2, \ldots, x_n, y)$$

such that

$$x_1 s_1 + x_2 s_2 + \cdots + x_n s_n + \varepsilon = y + m,$$

where $\varepsilon$ is “small”.

We haven’t said exactly what “small” means, but you should imagine that $\varepsilon$ is much smaller than $q$.

This encryption scheme is nondeterministic: Given $m$, there are lots of different ways to encrypt it. In fact, you can choose $x_1, \ldots, x_n$ however you like, pick a random small error $\varepsilon$, and then compute $y$.

In the other direction, decryption is easy if you know the secret key $s$. Given the encryption

$$\operatorname{Enc}_{S}(m) = (x_1, \ldots, x_n, y),$$

simply compute

$$m - \varepsilon = x_1 s_1 + x_2 s_2 + \cdots + x_n s_n - y.$$

Now you know $m$ is either $0$ or $q/2$, and so you can just round off the error $\varepsilon$ to recover $m$. This works as long as you know $\left | \varepsilon \right | < q/4$.

Before we get to key switching, let’s explore some simple operations on ciphertexts.

Addition

To get an encryption of $m+m'$ under $S$, we can simply add (component-wise) the encryptions of $m$ and $m'$ under $S$. If

$$\begin{align} x_1 s_1 + x_2 s_2 + \cdots + x_n s_n + \varepsilon = y + m \text{and} \\ x_1' s_1 + x_2' s_2 + \cdots + x_n' s_n + \varepsilon' = y' + m', \end{align}$$

then

$$(x_1 + x_1') s_1 + (x_2 + x_2') s_2 + \cdots + (x_n + x_n') s_n + (\varepsilon + \varepsilon') = (y + y') + (m + m').$$

In other words,

$$(x_1 + x_1', \ldots, x_n + x_n', y + y')$$

is a perfectly good encryption of $m + m'$.

The only important point is that the errors add: if the original two encryptions have errors $\varepsilon$ and $\varepsilon'$, the new encryption will have error $\varepsilon + \varepsilon'$.

Scalar multiplication:

To get an encryption of $cm$ under $S$, where $c \in \mathbb{Z}_q$ is some scalar, we can just multiply (component-wise) our ciphertext by $c$. This works, except that it multiplies the error $\varepsilon$ by $c$. In other words, if the orginal ciphertext has error $\varepsilon$, the new ciphertext will have error $c \varepsilon$.

If $c$ is a small constant, this might not be a big problem: we just have to keep track of the error and make sure it stays below the threshold $q/4$. But if $c$ is big, or if the error is already getting close to the limit, we can’t do scalar multiplication.

Key switching

Now that we have our addition and scalar multiplication tools above, we can finally tackle key switching. Suppose we start with a message $m$ encrypted under secret $S = (s_1, \dots, s_n)$, which looks like

$$\operatorname{Enc}_{S}(m) = (x_1, \dots, x_n, y = - m + \sum_{i=1}^n x_i s_i + \varepsilon)$$

and we want to end up with $m$ encrypted under a new secret $T = (t_1, \dots, t_n)$, which looks like

$$\operatorname{Enc}_{T}(m) = (x_1', \dots, x_n', y' = - m + \sum_{i=1}^n x_i' t_i + \varepsilon_T).$$

We notice there’s an annoying extra masking term $\sum_{i}^n x_i s_i$ in $\operatorname{Enc}_{S}(m)$ that we need to get rid of. We can get rid of this with the addition tools we presented above, but how do we get access to $s_1, \dots, s_i$ if it’s the secret key? It turns out we don’t need direct access.

Remember, to recover $m$, we just need to be able to compute

$$m - \varepsilon = x_1 s_1 + \cdots + x_n s_n - y.$$

But we don’t actually need to recover $m$, only its encryption $\operatorname{Enc}_{T}(m)$ under $T$. So what if we have the encryptions of $s_i$ under our new secret key $T$: $$\operatorname{Enc}_T(s_1), \operatorname{Enc}_T(s_2), \dots, \operatorname{Enc}_T(s_i)?$$

Then we can try to compute the linear combination

$$\operatorname{Enc}_T(m - \varepsilon) = \operatorname{Enc}_T(x_1 s_1 + \cdots + x_n s_n - y).$$

(We’re not worried about that error $\varepsilon$ on the left, as long as it is much smaller than $q$.
When we finally decrypt, $\varepsilon$ will just get added to the final decryption error.)

The right-hand side involves a sum of $n + 1$ terms. Now we can pull the addition out of the encryption, at the cost of adding $n+1$ errors. We can choose $q$ to be much, much bigger than $n$, so if we start with a small enough error, this won’t be an issue:

$$\operatorname{Enc}_T(m - \varepsilon) = \operatorname{Enc}_T(x_1 s_1) + \cdots + \operatorname{Enc}_T(x_n s_n) - \operatorname{Enc}_T(y).$$

Now we come to the tricky part. We know $\operatorname{Enc}_T(s_i)$, and we want to learn $\operatorname{Enc}_T(x_i s_i)$, but we can’t just do a scalar multiplication by $x_i$. If $x_i$ is big, the error will grow out of control.

The solution is to give the evaluator more than just encryptions of $s_i$. Instead of just $\operatorname{Enc}_T(s_i)$, we give them the full array $$\operatorname{Enc}_T(s_i), \operatorname{Enc}_T(2 s_i), \operatorname{Enc}_T(2^2 s_i), \ldots, \operatorname{Enc}_T(2^r s_i),$$ where $2^r$ is the largest power of $2$ less than $q$.

How does this help us?

Binary.

Write $x_i$ in binary: $$x_i = b_{i, 0} + 2 b_{i, 1} + 2^2 b_{i, 2} + \ldots + 2^r b_{i, r}.$$ This formula looks complicated, but it really just says that $x_i$ is a sum of a bunch of powers of $2$. (Remember, all the coefficients $b_{i, j}$ are either $0$ or $1$.)

So now $$x_i s_i = \sum_j 2^j b_{i, j} s_j$$ and

$$\operatorname{Enc}_T(x_i s_i) = \sum_j b_{i, j} \operatorname{Enc}_T(2^j s_i).$$

So we’ve expressed each $\operatorname{Enc}_T(x_i s_i)$ as a sum – and because it’s a sum, the error stays under control.

To recap: In order to allow key switching, the encryptor (who chooses the secret keys) has to send to the evaluator encryptions $$\operatorname{Enc}_T(s_i), \operatorname{Enc}_T(2 s_i), \operatorname{Enc}_T(2^2 s_i), \ldots, \operatorname{Enc}_T(2^r s_i),$$ for each $i$. (This amounts to a total of $nr$ ciphertexts – if $n$ and $r$ are large, this might be a lot of data!)

If the evaluator has some ciphertext under the old key $S$,

$$\operatorname{Enc}_S(m) = (x_1, \ldots, x_n, y),$$

the evaluator knows that

$$m \approx x_1 s_1 + \cdots + x_n s_n - y.$$

The evaluator simply has to expand the $x_i$’s in binary as $$x_i = b_{i, 0} + 2 b_{i, 1} + 2^2 b_{i, 2} + \ldots + 2^r b_{i, r},$$ and then compute the new encryption

$$\operatorname{Enc}_T(m) = \sum_{i, j} b_{i, j} \operatorname{Enc}_T(2^j s_i) - \operatorname{Enc}_T(y).$$

Easy!