Skip to main content

Homomorphic Encryption and Secure Multiparty Computation (MPC)

· 4 min read

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

Homomorphic Encryption Definition


y=f(x1,x2,...,xn)y = f(x_1, x_2, ..., x_n)

where ff is a function to be computed and x1,...,xnx_1, ..., x_n are the inputs.

encenc is a homomorphic encryption function if:

enc(f(x1,x2,...,xn))=f(enc(x1),enc(x2),...,enc(xn))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 decdec, we should have the following relation:

dec(enc(f(x1,x2,...,xn)))=dec(f(enc(x1),enc(x2),...,enc(xn)))=f(x1,x2,...,xn)\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 (encdecenc-dec) that would work perfectly regardless of what function ff is can be challenging. However, it is possible to create homomorphic encryption functions when restrictions are added to the form of function ff.

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

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

Where ee, dd and nn are some carefully chosen numbers so that (xe)d=xmodn(x^e)^d = x \mod n for any given xx. 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(x1,x2,x3)=x1x2x3f(x_1, x_2, x_3) = x_1 * x_2 * x_3 that only consists of multiplications. It is clear that:

f(enc(x1),enc(x2),enc(x3))=f(x1emodn,x2emodn,x3emodn)=(x1emodn)(x2emodn)(x3emodn)=x1ex2ex3emodn=(x1x2x3)emodn=f(x1,x2,x3)emodn=enc(f(x1,x2,x3))\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(x1,x2,...,xn))=f(enc(x1),enc(x2),...,enc(xn))enc(f(x_1, x_2, ..., x_n)) = f(enc(x_1), enc(x_2), ..., enc(x_n)).

For the decryption process:

dec(f(enc(x1),enc(x2),enc(x3)))=dec(f(x1,x2,x3)emodn)=(f(x1,x2,x3)emodn)dmodn=(f(x1,x2,x3)e)dmodn=f(x1,x2,x3)modn\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 ff 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 ff. 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 aa, bb, cc 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 decdecdec-dec pair, and sends the encenc function to Alice, Bob and Charlie.
  2. Alice, Bob and Charlie compute a=enc(a)a' = enc(a), b=enc(b)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=abcd' = a' * b' * c', and send dd' back to Sarah.
  4. Sarah then computed d=dec(d)d = dec(d') and sends it back to Alice, Bob and Charlie.

Now, dd is really just the multiplicative product abca * 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.