Homomorphic Encryption

As briefly mentioned in the previous article on the broad overview of secure multiparty computation, homomorphic encryption is one way to achieve MPC, and it is widely to implement various MPC algorithms. Let’s review the definition of homomorphic encryption:

Let �=�(�1,�2,…,��) where � is a function to be computed and �1,…,�� be the inputs. ��� is a homomorphic encryption function if

        ���(�(�1,�2,…,��))=�(���(�1),���(�2),…,���(��))

In other words, homomorphic encryption functions allow one to perform computations on encrypted data. Of course, computation on the encrypted data gives you encrypted outputs, and the outputs are not useful unless they can be decrypted to produce sensible values. Therefore, homomorphic encryption functions need to come with a corresponding decryption function using which the final encrypted results can be recovered. Let’s denote the decryption function by ���, we should have the following relation:

        ���(���(�(�1,�2,…,��)))=���(�(���(�1),���(�2),…,���(��)))=�(�1,�2,…,��)

As you may have imagined, it is difficult to find such a pair of encryption and decryption functions ���−��� that would work perfectly regardless of what function � is. However, it is not too difficult to come up with some homomorphic encryption functions that would work when we put some restrictions on the form that function � can take on. For example, suppose function � can only consist of multiplications, then the following set of homomorphic encryption-decryption functions might just work:

        ���(�)=�� ��� �

        ���(�)=�� ��� �

Where �, � and � are some carefully chosen numbers so that (��)�=� ��� � for any given �. For the curious readers, you can refer to the WikiPedia page https://en.wikipedia.org/wiki/RSA_(cryptosystem) to learn about how these numbers are generated to satisfy the above equation. To refrain from diverging too far into the mathematical details, please take my word for it that (��)�=� ��� � is ensured, and let’s see how the above homomorphic encrytion-decryption functions work for this very simple �(�1,�2,�3)=�1⋅�2⋅�3 that only consists of multiplications.

It is easy to see that

�(���(�1),���(�2),���(�3))=�(�1� ��� �,�2� ��� �,�3� ��� �)

=(�1� ��� �)⋅(�2� ��� �)⋅(�3� ��� �)

=�1�⋅�2�⋅�3� ��� �

=(�1⋅�2⋅�3)� ��� �

=�(�1,�2,�3)� ��� �

=���(�(�1,�2,�3))

This fulfills the requirement that ���(�(�1,�2,…,��))=�(���(�1),���(�2),…,���(��)).

Now the decryption:

���(�(���(�1),���(�2),���(�3)))=���(�(�1,�2,�3)� ��� �)

=(�(�1,�2,�3)� ��� �)� ��� �

=(�(�1,�2,�3)�)� ��� �

=�(�1,�2,�3) ��� �

So this shows that we can indeed recover the correct result of multiplication from the output of computing function � on the encrypted inputs (strictly speaking, there are some constraints on the inputs x_1,x_2,x_3 that �1⋅�2⋅�3<�, but let’s ignore that for now).

The homomorphic system above is called unpadded RSA (since it leverages the RSA cryptosystem), and 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 �. There are many other partially homomorphic crypto systems, and here is a list: https://en.wikipedia.org/wiki/Homomorphic_encryption. In many cases, partially homomorphic crypto systems are powerful enough to solve our problems.

Now you have a sense of what homomorphic encryption is. The next question is: how would homomorphic encryption help us achieve secure multiparty computation? Well, there is indeed no easy way to answer this question because you really would have to utilize homomorphic encryption in creative ways under different circumstances. I could give a trivial example based on the unpadded RSA homomorphic crypto system.

Imagine that there are three people Alice, Bob and Charlie each holding on to some number �,�,� that they wish to keep secret, and they wanted to collectively compute the multiplicative product of their numbers without revealing the number they have 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 ���−��� pair, and sends the ���function to Alice, Bob and Charlie

2. Alice, Bob and Charlie computes �′=���(�),�′=���(�),�′=���(�) respectively and send them to Nancy

3. Nancy multiplies the numbers she received from Alice, Bob and Charlie to obtain �′=�′⋅�′⋅�′, and send �′ back to Sarah

4. Sarah then computed �=���(�′) and send it back to Alice, Bob and Charlie

Now, � is really just the multiplicative product �⋅�⋅�.

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.