Shift-type homomorphic encryption and its application to fully homomorphic encryption

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 shift-type and identify it as the basic underlying structure of all existing homomorphic encryption schemes. It generalizes the already known notion of shift-type group homomorphic encryption. • We give an IND-CPA 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 IND-CPA security of all existing bootstrapping-based leveled FHE. • We prove that the IND-CPA 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 equivalent to the circular security of the underlying bootstrappable scheme.