A Hybrid Scheme of Public-Key Encryption and Somewhat Homomorphic Encryption

We introduce a hybrid homomorphic encryption that combines public-key encryption (PKE) and somewhat homomorphic encryption (SHE) to reduce the storage requirements of most somewhat or fully homomorphic encryption (FHE) applications. In this model, messages are encrypted with a PKE and computations on encrypted data are carried out using SHE or FHE after homomorphic decryption. To obtain efficient homomorphic decryption, our hybrid scheme combines IND-CPA PKE without complicated message padding with SHE with a large integer message space. Furthermore, if the underlying PKE is multiplicative, the proposed scheme has the advantage that polynomials of arbitrary degree can be evaluated without bootstrapping. We construct this scheme by concatenating the ElGamal and Goldwasser-Micali schemes over a ring ℤ N for a composite integer N whose message space is ℤ N × . To accelerate the homomorphic evaluation of the PKE decryption, we introduce a method to reduce the degree of the exponentiation circuit at the cost of additional public keys. Using the same technique, we present an efficient partial solution to an open problem which is to evaluate mod q mod p arithmetic homomorphically for large p. As an independent interest, we also obtain a generic method for converting from private-key SHE to public-key SHE. Unlike the method described by Rothblum, we are free to choose the SHE message space.