This work addresses the characterization of homomorphic encryption schemes both in terms of security and design. In particular, we are interested in currently existing fully homomorphic encryption (FHE) schemes and their common structures and security. Our main contributions can be summarized as follows:
We define a certain type of homomorphic encryption that we call
and identify it as the basic underlying structure of
homomorphic encryption schemes. It generalizes the already known notion of shift-type
We give an
characterization of all shift-type homomorphic encryption schemes in terms of an abstract subset membership problem.
We show that this characterization carries over to all leveled FHE schemes that arise by applying Gentry’s bootstrapping technique to shift-type homomorphic encryption schemes. Since this is the common structure of all existing schemes, our result actually characterizes the
security of all existing bootstrapping-based leveled FHE.
We prove that the
security of FHE schemes that offer a certain type of circuit privacy (for FHE schemes with a binary plaintext space we require circuit privacy for a single AND-gate and, in fact, all existing binary-plaintext FHE schemes offer this) and are based on Gentry’s bootstrapping technique is
to the circular security of the underlying bootstrappable scheme.