CO6GC: Homomorphic encryption (part 1): computing with secrets

This is a post in COSIC’s Guide to Crypto! A series of blog posts in which the researchers at COSIC introduce you to the wonderful world of cryptography. Today we will tell you about homomorphic encryption.

This blogpost was written by Charlotte Bonte and Ilaria Chillotti

When it comes to protecting data, cryptography is the best known solution. Classical cryptography allows to encrypt data, to protect it during transmission or when it is stored on a device, and to decrypt it. However if back then one wanted to work with the encrypted data, it would have to be decrypted such that one could compute on it in the clear and then the result could again be encrypted for storage. Hence, manipulating this data while it was encrypted was not possible. Nowadays we have encryption schemes that solve this problem called homomorphic encryption schemes.

To give some intuition on how homomorphic encryption works, we explain it using an analogous fictional situation sketched by Gentry. Imagine you start a jewelry store, first you will have to hire people to transform your precious raw materials into jewelry. As your trusted friends do not know how to make jewelry, you will have to hire people you do not know and hence do not trust. The main question in this scenario is: how do you enable your distrusted employees to transform the valuable raw material into jewelry without giving them the opportunity to steal it? In other words, you want them to transform the materials to finished jewelry without giving them access to the raw material. Clever as you are, you come up with the following solution: you create glove boxes, that you lock with a key as in the picture below. Before your employees arrive to work you put the raw materials in the box and lock it. Your employees can manipulate the raw materials using the gloves but as the box is impenetrable, they can not steal the valuable materials. When the employee finishes his piece of jewelry and goes home, you can use your key to retrive the jewelry from the box. Like this the employee transforms the raw material into a finished piece of jewelry without having true access to the valuable raw material.

Likewise, when you are using a homomorphic encryption scheme you can encrypt your messages, hand these encryptions and a list of operations you want to perform to a server, wait until the server performs that list of operations on your encrypted data and returns you the result. Upon receiving the response from the server, you remove the layer of encryption using your decryption key and reveal the result of the computation. As the employees do not have access to the key to open the glove box, the server does not know your decrypton key and therefore can not access the raw data. As employees can only work on the raw material using the gloves of the box, the server can only operate on the encrypted data. Unlike the employees the server can not see the raw data, which is like being a blindfolded employee working with the glove box. Hence a homomorphic encryption scheme is a standard encryption scheme with a key generation, encryption and decryption algorithm (click here for a brief explanation of this) that is enriched with an extra evaluation algorithm: this latter allows computations on encrypted messages without exposing these messages in unencrypted form. As such homomorphic encryption can solve multiple problems related to data privacy. It could be used to do computations on sensitive data (medical, financial, genomic, etc.), to evaluate classification algorithms, to do electronic voting, to outsource computations and so on. In the era of the cloud computing and with all the privacy regulations on personal data (e.g. GDPR), homomorphic encryption is one of the possible solutions proposed by cryptographers.

Different types of schemes

Homomorphic encryption schemes are divided in groups depending on the type and number of operations they can perform. Schemes that can only perform one type of operation are called partially homomorphic encryption schemes. Examples of this category are the famous RSA [1] and El Gamal [2] schemes, which allow to homomorphically perform multiplications, and the Paillier scheme [3], which allows to perform homomorphic additions.

Let’s take as an example RSA. The scheme is determined by choosing two large primes \({ \color{blue} p}\) and \({ \color{blue} q}\) and assigning to \({ \color{magenta} n}\) their product. A small number \({ \color{magenta} e}\) is chosen together with \({ \color{blue} d}\), its multiplicative inverse modulo \({ \color{blue} {\varphi(n)}}=({ \color{blue} p}-1)({ \color{blue} q}-1)\). Then the pair \(({ \color{magenta} n},{ \color{magenta} e})\) is published, while the other parameters are kept secret.

An RSA encryption of a message \({\color{green} m} \mod { \color{magenta} n}\) is

\

RSA is multiplicatively homomorphic, which means that if we have two ciphertexts

\[c_1 = {\color{green} {m_1}}^{\color{magenta} e} \mod { \color{magenta} n} \]

\[c_2 = {\color{green} {m_2}}^{\color{magenta} e} \mod { \color{magenta} n} \]

and we multiply them, we obtain

\[c_1 \cdot c_2 = ({\color{green} {m_1}} \cdot {\color{green} {m_2}})^{\color{magenta} e} \mod { \color{magenta} n}\]

This is a valid encryption of the product of the two messages \({\color{green} {m_1}}\) and \({\color{green} {m_2}}\), and we were able to compute it without knowing the messages or the secret key. However, the same trick cannot be obtained with addition: that is why RSA is called partially homomorphic.

Some schemes are homomorphic with respect to both addition and multiplication, but can perform these operations only a limited number of times. We refer to these schemes as somewhat homomorphic encryption (SHE) schemes. An example of such a scheme is the one by Boneh et al. [4]: it allows to perform an unlimited number of homomorphic additions but only one homomorphic multiplication, hence one can at most compute quadratic polynomials using this scheme.

Unlimited operations

The idea of homomorphic encryption originated in the article of Rivest, Adleman and Dertouzos [5] in 1978, but researchers of homomorphic encryption have been looking for a solution that would support a complete set of operations and hence achieve functional completeness for many years. Only in 2009, Gentry constructed such a scheme [6]. His scheme was the first fully homomorphic encryption (FHE) scheme. In contrast to SHE schemes, FHE schemes have no limit in the number of operations they support. Gentry’s breakthrough idea was to use bootstrapping. Bootstrapping is performed at the point in the computation where performing extra homomorphic operations would cause problems. To explain why we cannot perform unlimited operations without a bootstrapping algorithm, we need to go a little bit into the details of homomorphic encryption.

To better understand, we use as an example a scheme called DGHV [7] that is homomorphic with respect with both addition and multiplication. DGHV uses as a secret \({\color{blue} p}\), an odd integer, and can encrypt binary messages \({\color{green} m \in \{ 0,1 \}}\). The encryption algorithm of DGHV (like the ones used in the other homomorphic schemes) is randomized, which means that the same message can be encrypted into different ciphertext, even when we are using the same key. This implies one cannot infer any information on the underlying message from a ciphertext, which is a property that all encryption schemes should have. In practice, all the homomorphic ciphertexts contain some randomness which we will refer to as noise, that is completely independent of the message.

A ciphertext will look like the following:

\

where \(q\) is a random integer larger than \({\color{blue} p}\) and \({\color{red} r}\) is the noise and it is much smaller than \({\color{blue} p}\) in a fresh encryption. To decrypt, we just reduce modulo \({\color{blue} p}\) and then modulo \(2\). DGHV is homomorphic with respect to both addition and multiplication. In fact, let’s consider two ciphertexts:

\[c_1 = {\color{blue} p}\cdot q_1 + 2\cdot {\color{red} {r_1}} + {\color{green} {m_1}}\]

\[c_2 = {\color{blue} p}\cdot q_2 + 2\cdot {\color{red} {r_2}} + {\color{green} {m_2}}\]

If we add or if we multiply them we obtain the following:

\[c_1 + c_2 = {\color{blue} p}\cdot (q_1 + q_2) + 2\cdot ({\color{red} {r_1} +\color{red} {r_2}}) + ({\color{green} {m_1} +\color{green} {m_2}}) \]

\[c_1 \cdot c_2 = {\color{blue} p}\cdot ( p \cdot q_2 \cdot q_2 + \ldots) + 2\cdot ({ 2 \cdot \color{red}{r_1} \cdot \color{red}{r_2 }+ \ldots }) + ({\color{green} {m_1} \cdot \color{green} {m_2}})\]

The first one is an encryption of the message \({\color{green} {m_1} + \color{green}{m_2} \mod 2}\) while the second is an encryption of \({\color{green} {m_1} \cdot \color{green} {m_2} \mod 2}\) (in practice a XOR and an AND).

But observe that when we perform operations on the ciphertext, we perform similar operations on their noise (in \({\color{red}{red}}\) in the formulas) which will make it grow. At some point this noise will have grown so much that it interferes with the message. If a certain limit is reached and we try to decrypt such a ciphertext, this will not result in the correct message as the noise growth caused an alteration to the message itself, that cannot be undone by the decryption algorithm. Therefore we need to estimate the amount of noise present in a homomorphic ciphertext to be able to determine the point where another computation would lead to interference between the noise and the message. It is at this point that the bootstrapping algorithm is used to reduce the noise present in the ciphertext: it requires some extra information that does depend on the secret key but not reveals any information about it.

Bootstrapping

Let us now add some properties to the glove boxes to include this notion of noise in our analogy. Assume the glove boxes contain a mechanism to input something into a glove box without being able to take something out. In addition the glove boxes become limited in the sense that each operation stiffens the gloves and hence one can only perform a limited set of operations on the raw material. As such the glove boxes correspond to somewhat homomorphic encryption schemes and the question arising is: how can we make a complicated piece of jewelry using a glove box that only allows a limited set of operations. The solution can be found in a combination of different glove boxes. You make a first glove box that contains the raw materials, you also make a second one that contains the key to open the first glove box, additionally you could create a third one containing the key to open the second one and so on. The number of glove boxes you need to create depends on the number of operations that need to be performed to create the requested piece of jewelry and the number of opeartions a glove box allows before the gloves stiffen. To create the piece of jewelry the employer starts working with the gloves of the first box until they stiffen. Then he puts the first box into the second box which already contains the key to open the first one and uses this key to open it and retrieves the partially assembled piece of jewelry. As long as the employee is able to perform extra operations on the piece of jewelry after retrieving it from the previous box, one can continue this process until the piece of jewelry is finished.

Likewise if the somewhat homomorphic encryption scheme allows additional operations after performing the bootstrapping algorithm, one can compute whichever function one requires by performing the bootstrapping at all the points in the algorithm where the noise is reaching the bound for correct decryption.

Right after Gentry’s breakthrough in 2009, homomorphic encryption was limited as the known algorithms were very slow and therefore not very useful in practice. In the last few years, the efficiency of homomorphic encryption schemes has improved and multiple solutions have been proposed by cryptographers from all over the world. The path to create a homomorphic scheme efficient for all applications is still long: in the field we are still working on fine-tuning the schemes and trying to invent new techniques to enlarge the range of homomorphic encryption.

Like every other encryption scheme, homomorphic encryption schemes are built on top of a hard problem. The schemes that are mainly studied nowadays are based on the Learning With Error (LWE) (click here for a brief explanation of this) problem and its variants. In part 2 we will go deeper into the most popular FHE schemes which rely on a variant of LWE.

For detailed information on homomorphic encryption and a more elaborate comparison to the physical jewelry store analogy, we refer the reader to take a look at Gentry’s essay. For a better mathematical background on homomorphic encryption in the early days we advise the reader to take a look at Silverberg’s paper. For an extensive introduction in homomorphic encryption we direct the reader to Halevi’s survey.

[1] Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.

[2] ElGamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on information theory31(4), 469-472.

[3] Paillier, P. (1999, May). Public-key cryptosystems based on composite degree residuosity classes. In International conference on the theory and applications of cryptographic techniques (pp. 223-238). Springer, Berlin, Heidelberg.

[4] Boneh, D., Goh, E. J., & Nissim, K. (2005, February). Evaluating 2-DNF formulas on ciphertexts. In Theory of Cryptography Conference (pp. 325-341). Springer, Berlin, Heidelberg.

[5] Rivest, R. L., Adleman, L., & Dertouzos, M. L. (1978). On data banks and privacy homomorphisms. Foundations of secure computation4(11), 169-180.

[6] Gentry, C. (2009, May). Fully homomorphic encryption using ideal lattices. In Proceedings of the forty-first annual ACM symposium on Theory of computing (pp. 169-178).

[7] Van Dijk, M., Gentry, C., Halevi, S., & Vaikuntanathan, V. (2010, May). Fully homomorphic encryption over the integers. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 24-43). Springer, Berlin, Heidelberg.

references for the pictures:
https://www.cleatech.com/product/compact-glove-boxes/
https://www.pngitem.com/middle/iToRJww_diamond-ring-big-clipart-image-and-transparent-png/
https://www.uihere.com/free-cliparts/gemstone-diamond-clip-art-diamant-cartoon-1170828