Let us fix a security parameter , a variable that measures the input size of the computational problem. In the case of the encryption scheme, both the requirements of the cryptographic algorithms as well as the security of the scheme are expressed in terms of .
Let be a homomorphic encryption scheme. A desirable property of is the possibility of evaluation arbitrary functions on ciphertexts from in a meaningful way. Clearly the complexity of must depend on the complexity of the function . To measure the latter, we use , the size of a boolean circuit that computes . The algorithm is efficient if there exists a polynomial such that for any function that is represented by a circuit of size , the complexity of is at most .
The circuit representation of breaks down the computation of into AND, OR, and NOT gates. To evaluate these it is enough to be able to add, subtract and multiply. Therefore, to obtain a fully homomorphic encryption scheme, all we need is a scheme that supports arbitrary additions, subtractions and multiplications on the ciphertexts, so as it does on their underlying encrypted messages.
L Assume that the ciphertext and the plaintext have the algebraic structure of a ring and that is a ring homomorphism.
Definition. A homomorphic encryption scheme is called leveled if the decryption algorithm is correct for a certain number of ring operations made on .
TODO: Write about the practical reasons for using a leveled scheme.
Definition. A homomorphic encryption scheme is called compact if there exists a polynomial function such that the output length of is at most bits long, regardless of the ring homomorphism or the number of ciphertext inputs , for any tuple of ciphertexts.
A homomorphic encryption scheme as above, but for which we do not require that is polynomial in is called bounded .
Definition. A scheme that is compact and for which the decryption algorithm is correct for any number of ring operations made on is called fully homomorphic.
In one of his seminal papers, Gentry showed that under a "circular security" assumption, a leveled homomorphic encryption scheme which is capable of homomorphically evaluating its can be transformed into a fully homomorphic encryption scheme . Gentry called the process of transforming bootstrapping .
We start by presenting an encryption scheme proposed by van Dijk, Gentry and Halevi . The encryption scheme goes as follows.
We fix the security parameter and set and .
Output a random odd -bit integer .
To encrypt a bit , let be a random -bit integer such that . Output the ciphertext , where is a random -bit integer number.
Ouput (c mod p) mod 2, where (c mod p) is the unique integer such that divides .
Remark that ciphertexts coming out of are near-multiples of . The distance from a ciphertext to the nearest multiple of is commonly called noise. The decryption algorithm is correct because the noise has the same parity as the message (in plaintext) .
This scheme is homomorphic since by simply adding, subtracting or multiplying the ciphertexts as integers we can add, subtract or multiply modulo the underlying plaintext messages. However, such operations increase the noise on the ciphertexts. Complications arise, i.e. might not work correctly, when the noise is too large when compared to . This is a recurrent issue in all homomorphic encription schemes proposed so far in the literature.
Let us emphasize this on the multiplication operation . Let be two ciphertexts with associated noise and respectively. We have that
for some integer . As long as , we have that
( mod ) = as it should be for correct decryption.
If we want to homomorphically evaluate a function whose circuit representation has many additions, subtractions and multiplication operation, we have to be careful that the magnitude of the noise does not surpass . This is why the scheme we just presented is not fully homomorphic, but only leveled. In particular, the encryption scheme can homomorphically evaluate polynomials of fairly low degree, where not a lot of multiplications are involved.
The semantic security of the scheme can be reduced to an approximate gcd problem]. That is, it was proved that an attacker cannot efficiently break the semantic security of unless the approximate gcd problem is easy.
Gentry  proved that if the scheme has the self-referential property of being able to homomorphically evaluate its own decryption function, then one can use to construct a fully homomorphic encryption . If this is the case, the term bootstrapable was coined by Gentry for the scheme .
The simple scheme presented above is not bootstrapable, but it can be modified slightly to a new scheme such that can handle essentially the same functions as , but whose decryption circuit is simpler. This new scheme is now bootstrappable. In Gentry's construction of from , he had to add another security assumption to the scheme , namely the hardness of the sparse subset sum problem.
In Alice's jewellery store analogy presented on the Homomorphic encryption page, the bootstrapping process is analogous to Alice giving a worker a glovebox #1, containing the raw materials and many additional gloveboxes. In box #2, Alice placed the key to box #1, box #3 contains the key to box number #2 and so on. To assemble a complicated piece, the worker manipulates the materials in box #1 until the gloves on the box become impractical. Then, he places box #1 inside box #2. Using the keys inside, he opens box #1 with the key, extracts the partially assembled piece and continues to assembly until the gloves of box #2 become impractical. When the worker finally finishes the assembly inside box #n, he hands the box to Alice. This process works as long as the worker can open box #i within box #(i+1) and still do a little bit of work on the pieces inside before the gloves of the box #(i+1) stiffen. As long as Alice has enough resources (i.e. gloveboxes and time for the manufacturing process) then her jewellery store can assemble any piece, no matter how complicated it is.
- van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully hohomomorphic encryption over the integers, In EUROCRYPT 2010, pp. 24 - 43
- C. Gentry. Computing arbitrary functions of encrypted data. In "Communications of the ACM", 2010.