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 (TODO:cite). 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 from outputed by $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.

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.

TODO: Bootstrappable encryption