Homomorphic encryption

From certFHE Community KB
Jump to navigation Jump to search

Intuitive idea

Suppose one would like to delegate the ability of processing its data without giving away access to it. This type of situation becomes more and more frequent with the widespread use of cloud computing. To store unencrypted data in the cloud is very risky and, for some types of data such as medical records, can even be illegal.

On the other hand, at first thought encrypting data seems to cancel out the possible benefits of cloud computing unless one gives the cloud the secret decryption key, sacrificing privacy. Fortunately, there are methods of encrypting data in a malleable way, such that the encryption can be manipulated without decrypting the data.

To explain the ideas in a tangible manner, we are going to use a physical analogy: Alice, who owns a jewellery store and wants her workers to process raw precious materials into jewellery pieces. Alice is constantly concerned about giving her workers complete access to the materials in order to minimise the possibility of theft. The analogy was coined by Gentry [1] and we follow the presentation in his paper.

Alice's plan

Use a transparent impenetrable glovebox (see image) secured by a lock for which only Alice has the key. Using the gloves, a worker can assemble pieces of jewellery using the materials that were previously locked inside the box by Alice. When the pieces are finished, she unlocks the box with her key and extracts them.

The locked glovebox with the raw precious materials inside is an analogy for an encryption of some data which can be accessed only using the decryption key. The gloves should be regarded as the malleability or the homomorphic property of the encryption. The finished piece of jewellery in the box can be thought of as the encryption of , a desired computation using the initial data. The lack of physical access to the raw precious materials in the box is an analogy for the fact that knowing encryptions of or does not give any information about or , without the knowledge of the decryption key.

Of course, Alice's jewellery store, like any analogy, does not represent some aspect of homomorphic encryption very well and one does not have to take it too literally. Some flaws of this analogy are discussed in Section 4 of Gentry's aforementioned article.


Every encryption scheme is composed of three algorithms: and and two sets (the plaintext space) and (the ciphertext space). All of the algorithms must be efficient, in the sense that they must run in polynomial time with respect to an a priori fixed security parameter . Encryption schemes can be symmetric or asymmetric. We will focus here on the asymmetric case (commonly known as public key encryption).

Basically, given a security parameter , one generates using KeyGen a pair . The next two algorithms describe how to associate to a plaintext a ciphertext using the public key and viceversa, how to associate to a ciphertext a plaintext , using the secret key such that .

A homomorphic encryption scheme has a fourth algorithm , which is associated to a set of permitted functions. For any function and any ciphertexts with , the algorithm outputs a ciphertext that encrypts . In other words, we want that . As a shorthand we say that can handle functions in . For a function , is not guaranteed to output anything meaningful.

As described so far, it is trivial to construct an encryption scheme that can handle all functions. We can just define to output without processing the ciphertexts at all. Then, we modify slightly. To decrypt first decrypt to obtain and then apply to them. But this does not fit the purpose of delegating the processing of information. In the jewellery store analogy, this is as if the worker sends the box back to Alice without doing any work on the raw precious materials. Then Alice has to assemble the jewellery herself.

The purpose of delegating computation is to reduce one's workload. In terms of running times, in a practical encryption scheme, decrypting should require the same amount of computation as decrypting or any of the ciphertexts for that matter. Some schemes require additionally that is of the same size as . This property, called compactness, whose precise definition can be found in [2] (Definition 3.4). Also, in a practical encryption scheme, the algorithms , and should be effectively computable. In terms of complexity, one usually requires that these algorithms should be polynomial in a security parameter .

An encryption scheme is fully homomorphic (FHE) if it can handle all functions, is compact and the is efficient. The trivial solution presented above is not fully homomorphic, since the size of the cirphertexts outputed by depend on the function being evaluated. Moreover, in the trivial example the time needed to decrypt such a ciphertext depends on the evaluated function as well.


Below we list a few examples of homomorphic encryption schemes. We hope that just presenting the public key together with the is enough to give the reader a clear picture of the whole scheme.

In the ElGamal cryptosystem, in a cyclic group of order with generator , if the public key is , where , and is the secret key, then the encryption of a message is , for some random . The homomorphic property is then


In the Goldwasser–Micali cryptosystem, if the public key is the modulus and quadratic non-residue , then the encryption of a bit is , for some random . The homomorphic property is then

where denotes addition modulo 2, (i.e. Exclusive disjunction).

Other examples include the RSA , Paillier and the Benaloh encryption schemes.


  1. C. Gentry. Computing arbitrary functions of encrypted data. In "Communications of the ACM", 2010.
  2. Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE, R. Ostrovsky editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs 2011, pp. 97 - 106