FHE

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 )$.

Definitions

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