Homomorphic Encryption and Secure Multiparty Computation (MPC)

As briefly mentioned in the previous article on the broad overview of secure multiparty computation, homomorphic encryption is one way to achieve secure Multiparty Computation (MPC). It is widely used to implement various MPC algorithms.

Homomorphic Encryption Definition

Let

y = f(x_1, x_2, ..., x_n)

where $f$ is a function to be computed and $x_1, ..., x_n$ are the inputs.

$enc$ is a homomorphic encryption function if:

enc(f(x_1, x_2, ..., x_n)) = f(enc(x_1), enc(x_2), ..., enc(x_n))

In other words, homomorphic encryption functions allow one to perform computations on encrypted data. However, computation on the encrypted data gives you encrypted outputs, which are not useful unless they can be decrypted to produce sensible values. Therefore, homomorphic encryption functions need to come with a corresponding decryption function that can be used to recover the final encrypted results.

Let's denote the decryption function as $dec$, we should have the following relation:

\begin{align*}
dec(enc(f(x_1, x_2, ..., x_n))) &= dec(f(enc(x_1), enc(x_2), ..., enc(x_n))) \\
&= f(x_1, x_2, ..., x_n)
\end{align*}

Finding a pair of encryption and decryption functions ($enc-dec$) that would work perfectly regardless of what function $f$ is can be challenging. However, it is possible to create homomorphic encryption functions when restrictions are added to the form of function $f$.

For example, suppose function $f$ can only consist of multiplications. The following set of homomorphic encryption-decryption functions might just work:

enc(x) = x^e \mod n \\
dec(x) = x^d \mod n

Where $e$, $d$ and $n$ are some carefully chosen numbers so that $(x^e)^d = x \mod n$ for any given $x$. For the curious readers, please refer to this WikiPedia page to learn about how these numbers are generated to satisfy the above equation.

To illustrate how this works, let's consider a simple function $f(x_1, x_2, x_3) = x_1 * x_2 * x_3$ that only consists of multiplications. It is clear that:

\begin{align*}
f(enc(x_1), enc(x_2), enc(x_3)) &= f(x_1^e \mod n,x_2^e \mod n, x_3^e \mod n) \\
                                &= (x_1^e \mod n) * (x_2^e \mod n) * (x_3^e \mod n) \\
                                &= x_1^e * x_2^e * x_3^e \mod n \\
                                &= (x_1 * x_2 * x_3)^e \mod n \\
                                &= f(x_1,x_2,x_3)^e \mod n \\
                                &= enc(f(x_1,x_2,x_3))
\end{align*}

This fulfills the requirement that $enc(f(x_1, x_2, ..., x_n)) = f(enc(x_1), enc(x_2), ..., enc(x_n))$.

For the decryption process:

\begin{align*}
dec(f(enc(x_1), enc(x_2), enc(x_3))) &= dec(f(x_1,x_2,x_3)^e \mod n) \\
                                      &= (f(x_1,x_2,x_3)^e \mod n)^d \mod n\\ 
                                      &= (f(x_1,x_2,x_3)^e)^d \mod n\\
                                      &= f(x_1,x_2,x_3) \mod n
\end{align*}

We can indeed recover the correct result of multiplication from the output of computing function $f$ on the encrypted inputs.

The homomorphic system above, called unpadded RSA (since it leverages the RSA cryptosystem), is one example of the so-called partially homomorphic crypto systems. As the name suggests, they are "partial" because they don't work on any arbitrary function $f$. There are many other partially homomorphic crypto systems which you can find here.

Homomorphic Encryption and Secure Multiparty Computation

Now you might wonder: how does homomorphic encryption help us achieve secure multiparty computation? The answer to this question requires some creativity as you would have to utilize homomorphic encryption in different ways under different circumstances. Let's illustrate with an example based on the unpadded RSA homomorphic crypto system.

Consider three people Alice, Bob and Charlie each holding on to some number $a$, $b$, $c$ that they wish to keep secret. They want to collectively compute the product of their numbers without revealing their individual numbers to each other. Their objective could be reached with the kind help of two other people Sarah and Nancy.

They proceed as follows:

1. Sarah generates the unpadded RSA $dec-dec$ pair, and sends the $enc$ function to Alice, Bob and Charlie.

2. Alice, Bob and Charlie compute $a' = enc(a)$, $b' = enc(b)$, $c' = enc(c)` respectively and send them to Nancy.

3. Nancy multiplies the numbers she received from Alice, Bob and Charlie to obtain $d' = a' * b' * c'$, and send $d'$ back to Sarah.

4. Sarah then computed $d = dec(d')$ and sends it back to Alice, Bob and Charlie.

Now, $d$ is really just the multiplicative product $a * b * c$.

In the above procedure, none of Alice, Bob and Charlie revealed their secretive numbers to anyone else but all of them learned the multiplicative product of the numbers they had.