FHE

Let us fix a security parameter $\lambda$, 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 $\lambda$.

Intuition

Let ${\mathcal {E}}=({\mathcal {C}},{\mathcal {P}},KeyGen,Encrypt,Decrypt,Evaluate)$ be a homomorphic encryption scheme. A desirable property of ${\mathcal {E}}$ is the possibility of evaluation arbitrary functions on ciphertexts from ${\mathcal {C}}$ in a meaningful way. Clearly the complexity of $Evaluate(f,c)$ must depend on the complexity of the function $f$. To measure the latter, we use $S_{f}$, the size of a boolean circuit that computes $f$. The algorithm $Evaluate$ is efficient if there exists a polynomial $g$ such that for any function $f$ that is represented by a circuit of size $S_{f}$, the complexity of $Evaluate(f,c_{1},\dots ,c_{t},pk)$ is at most $S_{f}\cdot g(\lambda )$.

The circuit representation of $f$ breaks down the computation of $f$ 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.

Definitions

L Assume that the ciphertext ${\mathcal {C}}$ and the plaintext ${\mathcal {P}}$ have the algebraic structure of a ring and that $Decrypt:{\mathcal {C}}\to {\mathcal {P}}$ is a ring homomorphism.

Definition. A homomorphic encryption scheme ${\mathcal {E}}=({\mathcal {C}},{\mathcal {P}},KeyGen,Encrypt,Decrypt,Evaluate)$ is called leveled if the decryption algorithm is correct for a certain number of ring operations made on ${\mathcal {C}}$.

TODO: Write about the practical reasons for using a leveled scheme.

Definition. A homomorphic encryption scheme ${\mathcal {E}}$ is called compact if there exists a polynomial function $s=s(\lambda )$ such that the output length of $Eval(f,c,pk)$ is at most $s(\lambda )$ bits long, regardless of the ring homomorphism $f:{\mathcal {C}}^{t}\to {\mathcal {C}}$ or the number of ciphertext inputs $t$, for any tuple $c=(c_{1},\dots ,c_{t})\in {\mathcal {C}}^{t}$ of ciphertexts.

A homomorphic encryption scheme as above, but for which we do not require that $s(\lambda )$ is polynomial in $\lambda$ 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 ${\mathcal {C}}$ is called fully homomorphic.

In one of his seminal papers, Gentry showed that under a "circular security" assumption, a leveled homomorphic encryption scheme ${\mathcal {E}}$ which is capable of homomorphically evaluating its $Decryption$ can be transformed into a fully homomorphic encryption scheme ${\mathcal {E}}'$. Gentry called the process of transforming ${\mathcal {E}}\to {\mathcal {E}}'$ bootstrapping .

Examples

We start by presenting an encryption scheme ${\mathcal {E}}$ proposed by van Dijk, Gentry and Halevi . The encryption scheme ${\mathcal {E}}$ goes as follows.

We fix the security parameter $\lambda$ and set $N=\lambda ,P=\lambda ^{2}$ and $Q=\lambda ^{5}$.

$Keygen(\lambda ):$ Output a random odd $P$-bit integer $p$.

$Encrypt(p,m):$ To encrypt a bit $m\in \{0,1\}$, let $m'$ be a random $N$-bit integer such that $m'=m{\pmod {2}}$. Output the ciphertext $c\leftarrow m'+pq$, where $q$ is a random $Q$-bit integer number.

$Decypt(p,c):$ Ouput (c mod p) mod 2, where (c mod p) is the unique integer $c'\in (-p/2,p/2)$ such that $p$ divides $c-c'$.

Remark that ciphertexts coming out of $Encrypt$ are near-multiples of $p$. The distance from a ciphertext $c$ to the nearest multiple of $p$ is commonly called noise. The decryption algorithm is correct because the noise $m'$ has the same parity as the message (in plaintext) $m$.

This scheme is homomorphic since by simply adding, subtracting or multiplying the ciphertexts as integers we can add, subtract or multiply modulo $2$ the underlying plaintext messages. However, such operations increase the noise on the ciphertexts. Complications arise, i.e. $Decrypt$ might not work correctly, when the noise $m'$ is too large when compared to $p$. This is a recurrent issue in all homomorphic encription schemes proposed so far in the literature.

Let us emphasize this on the multiplication operation $Mult$. Let $c_{1},c_{2}$ be two ciphertexts with associated noise $m_{1}'$ and $m_{2}'$ respectively. We have that

$c\leftarrow Mult(c_{1},c_{2})=m_{1}'\cdot m_{2}'+p\cdot q'$ for some integer $q'$. As long as $|m_{1}'\cdot m_{2}'|<p/2$, we have that

($c$ mod $p$) = $m_{1}'\cdot m_{2}'$ as it should be for correct decryption.

If we want to homomorphically evaluate a function $f$ whose circuit representation has many additions, subtractions and multiplication operation, we have to be careful that the magnitude of the noise does not surpass $q/2$. This is why the scheme we just presented is not fully homomorphic, but only leveled. In particular, the encryption scheme ${\mathcal {E}}$ 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 ${\mathcal {E}}$ unless the approximate gcd problem is easy.

Gentry proved that if the scheme ${\mathcal {E}}$ has the self-referential property of being able to homomorphically evaluate its own decryption function, then one can use ${\mathcal {E}}$ to construct a fully homomorphic encryption ${\mathcal {E}}^{\dagger }$. If this is the case, the term bootstrapable was coined by Gentry for the scheme ${\mathcal {E}}$.

The simple scheme presented above is not bootstrapable, but it can be modified slightly to a new scheme ${\mathcal {E}}'$ such that ${\mathcal {E}}'$ can handle essentially the same functions as ${\mathcal {E}}$, but whose decryption circuit is simpler. This new scheme ${\mathcal {E}}'$ is now bootstrappable. In Gentry's construction of ${\mathcal {E}}'$ from ${\mathcal {E}}$, he had to add another security assumption to the scheme ${\mathcal {E}}'$, 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.