Homomorphic encryption

In the previous article, we saw how MPC can be used in to solve problems in the real world when data must remain private. This week, we will look at another cryptographic technique at the forefront of research that allows us to solve real-world problems.

What is the problem?

Consider the situation where a hospital has lots of data, that it wants to perform some complex computations on. The hospital will most likely not have the capabilities to perform these computations so they will want to outsource this task to a third party. Medical data is private so the hospital, by law, must ensure it remains private; it cannot just send data to the third party in the clear. Thinking about this problem a little bit, we may come up with the following solution:

1. Encrypt the data using public key cryptography;
2. Send the encrypted data to the third party;
3. Provide the third party with the keys to decrypt the data so they can perform the computations;
4. The third party encrypts their results and sends them back to the hospital along with the encryption keys;
5. The hospital decrypts the data.

Question:

Why may this be seen as not a satisfactory solution?

So, what is homomorphic encryption and how does it solve this problem?

Homomorphic encryption is a type of encryption that allows for computations to be done on the encrypted data which, when decrypted, gives the same result as if the computations were performed on the initial data/message.

Let us look at this process in more detail by looking at the diagram below:

Diagram of homomorphic encryption process by David Butler

First, we encrypt an initial message. We then perform a computation on the encryption. This is the same as applying a function to the encrypted message as seen above. We then decrypt the result of the computation. The property that must hold for homomorphic encryption is that the final decrypted message must be the same as if the function or computation were applied to the initial message.

Does it work?

Homomorphic encryption solves the problem described above. However, it is currently not a practical solution as implementing it is not easy. Cryptographers have shown that homomorphic encryption is possible in theory but it is not yet efficient enough to be deployed in real-world situations.

Question:

Homomorphic encryption (or Fully Homomorphic Encryption, FHE) refers to an encryption scheme such that any function can be computed on a ciphertext. Research what Somewhat or Partially Homomorphic Encryption (SHE or PHE) is and explain how it is different to FHE.

This article was written by David Butler, one of the course creators and teachers at Oxbridge Inspire. David is studying for a PhD at the Alan Turing Institute in London.

If you enjoyed this article, you might consider coming to our course in Cambridge this summer on the Mathematics behind Cryptography.