MPC Techniques Series, Part 7: Homomorphic Encryption
By Claudio Orlandi, Associate Professor and Chief Cryptographic Protocol Designer at Partisia
In previous blog posts we explained how secret-sharing is a useful tool for performing secure Multiparty Computation (MPC) when we can assume that a majority of the participants are honest.
However, there are many situations in which it is simply not realistic to assume that a majority of the participants in a protocol are honest. It could simply be because you are too paranoid to trust anyone else, or it could be because you want to perform an MPC protocol with two parties only — in which case saying that there is an honest majority is the same as saying that *everyone* is honest!
To perform MPC in the presence of a dishonest majority, cryptographers have developed two main tools: Oblivious Transfer (often combined with Garbled Circuits) and homomorphic encryption, which I am going to introduce here.
Before talking about homomorphic-encryption, it might be useful to recall how public-key encryption works: in public-key encryption there is a public key (let’s call it pk) and a secret key (let’s call it sk). As the names suggest, the owner of this key pair should make sure that sk stays private, while pk can be freely published on their homepage, Twitter bio, email signature, etc.
Once you get hold of someone’s public key, you can encrypt their data and be sure that they will be the only one who will ever be able to retrieve it. You can think of a public-key as one of these locks that can be locked with a “click” by pushing it. And you can think of the secret key as the key that allows one to open the lock. If you want others to be able to send you private information you can simply give them an open lock. They can then put their message in a box, put the lock on it, and close it.
The interesting part about public-key encryption is that having the public-key doesn’t help in any way to decrypt the content, in the same way as being in possession of an open lock really doesn’t help you unlock a closed one. Only by using the (secret) key the lock can be opened and the data retrieved.
Using public-key encryption, different users can encrypt their data and send it to the receiver via a proxy server. Since the data is encrypted, the server learns nothing. The receiver, who owns the secret key, can retrieve all the encrypted data from the proxy and decrypt it.
Shortly after public-key encryption was discovered in the late 70s, cryptographers started dreaming about the idea of “computing on encrypted data”. In the example above, it would be great if we could allow the server not only to store the data, but to perform computation on it too. This is interesting both from a privacy and an efficiency perspective. Consider an example in which the users are participants in a study and submit some sensitive data, and the receiver is a researcher who is interested in learning some aggregate function of the data, say the average. From an efficiency perspective, the researcher is only interested in learning one number, the average. Why should the researcher have to download all the data that the user submitted? And perhaps even more interesting, from a privacy perspective, the researcher is only supposed to learn the average. Why should the researcher have access to all the individual records?
Homomorphic encryption is a solution to both of the above problems. A homomorphic encryption scheme is a public-key encryption where it is possible to perform mathematical operations on the ciphertexts which somehow get translated into operations on the underlying plaintext data. This means that, in the example above, homomorphic encryption allows the server to compute the average of the encrypted values by only ever manipulating the ciphertexts and without ever learning their content. Craig Gentry, the inventor of fully-homomorphic encryption, uses the metaphor of a glovebox (one of these boxes with two gloves sticking into them used to manipulate dangerous materials) which has been painted black. You can manipulate the content of the box, but you cannot see what’s inside.
More concretely, imagine two ciphertexts c1, c2 which are obtained by encrypting two values x1, x2 using the public key pk i.e.:
In a homomorphic encryption, if you add those two ciphertexts together, say c3=c1+c2, the resulting ciphertext c3 will contain the sum of the two plaintexts. In other words, if you decrypt this sum you get:
For simplicity in this example we assume that the operation on the ciphertexts and the operation on the plaintext is the same. In some cases the operations are different, for instance by multiplying two ciphertext you get the addition of the plaintext. This is irrelevant for this high level description.
Many classical encryption schemes have partial homomorphic properties. Even the famous RSA or ElGamal cryptosystem allow us to perform some meaningful homomorphic operations. However, it was only about a decade ago (in 2009) when the first fully homomorphic-encryption was discovered. By fully we mean that both additions and multiplications can be computed, and therefore you can compute any function on the encrypted data. If this sounds too good to be true, the catch is that (at least with current state of the art) using fully-homomorphic encryption schemes make the computation extremely slow. For small or simple functions, however, this can already be implemented in practice.
How does it work?
The math behind homomorphic encryption schemes is fascinating, wonderful, and beyond the scope of this post. But I can’t let you leave before I give you a glimpse into how homomorphic encryption schemes work. I will use the homomorphic encryption scheme “over the integers” of van Dijk et al. as a reference here.
In this scheme the secret key is a (large) odd integer p. The scheme allows encrypting bits, that is the message can only be either 0 or 1. An encryption of a bit b will be a number c such that:
c mod p mod 2 = b
This means that you take the number c, divide by p, find the remainder (call it d), and then look at whether d is even or odd to determine the plaintext b. To allow others to encrypt, the public key will be a set of random multiples of p where a small quantity of noise has been added, all multiplied by 2. That is the public key is a set of values x1, x2, …, x3 such that:
Where qi is some large random number and ri is some small random number.
To encrypt using this public key one can take a random subset of the x’s and add them to the message. For instance, for each value i=1, 2, … one can flip a coin and if the coin is heads, then you add xi to the bit and if it’s tails you don’t add xi. Understanding the security of the scheme is beyond the point of the scheme, but let me just say that it is connected to a mathematical problem called the “approximate greatest common divisor problem”. Note that without the noise ri it would be very easy to recover the secret key p from the public key (by computing the greatest common divisor of the x values), but thanks to the ri the system is secure.
Let’s now see why the scheme is homomorphic.
Say you have two ciphertext c1 and c2 where:
c1= 2(Q1*p+R1) + b1 and c2= 2(Q2*p+R2) +b2
Where the capital Q’s and R’s indicate the sums of elements in the public key. If you add the two together you get something of the form:
c1+c2= 2(Q3*p+ R3) + b1+b2
Where Q3=Q1+Q2 and R3=R1+R2. Remember that decrypting requires to take modulo p, and then modulo 2. When taking modulo p the term Q3*p disappears, and we are left with:
c1+c2 mod p = 2R3 + b1+b2
Once you take modulo 2, you get exactly b1+b2 modulo 2, *if* the value 2R3 is less than p, otherwise you might get a decryption error.
It is possible to check (but the math is a bit more cumbersome) that if you compute c1*c2 you will get a similar expression where:
c1*c2 mod p = 2R3 + b1*b2
That is, you get the product of the messages plus some error term (which will be approximately R1*R2) and, if the error term is less than p, you will get correct decryption.
The good news is that I just showed you an encryption scheme that allows one to perform both additions and multiplications directly “in the encrypted domain”, meaning that anyone (without access to the secret key) can compute arithmetic functions of encrypted data. The bad news is that this annoying error term means that you can only perform a limited number of operations before the error term becomes larger than the modulo p and therefore the decryption is no longer correct. Unfortunately, all homomorphic encryption schemes we know of (that support both operations) have this annoying error term in one way or another. To allow for “fully” homomorphic encryption, that is one that allows an unbounded number of operations on encrypted data, one has to use a wonderfully clever technique called “bootstrapping” or “noise refreshing”, which allows to remove the noise from a ciphertext by evaluating the decryption circuit of the scheme itself using its own homomorphic properties! Yes, you read well, and it is as magical as it sounds!
About the author:
Claudio is Associate Professor in Computer Science at Aarhus University and co-founder of Partisia Infrastructure. He is a leading researcher on secure multiparty computation and zero-knowledge protocols. Claudio has a broad interest in the theory and practice of cryptographic protocols, with a focus on efficient constructions of advanced cryptographic primitives, threshold cryptography, privacy-preserving technologies, theory and practice of cryptographic protocols.