FHE

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