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 .