Paper 2013/710

An Approach to Reduce Storage for Homomorphic Computations

Jung Hee Cheon and Jinsu Kim

Abstract

We introduce a hybrid homomorphic encryption by combining public key encryption (PKE) and somewhat homomorphic encryption (SHE) to reduce storage for most applications of somewhat or fully homomorphic encryption (FHE). In this model, one encrypts messages with a PKE and computes on encrypted data using a SHE or a FHE after homomorphic decryption. To obtain efficient homomorphic decryption, our hybrid schemes is constructed by combining IND-CPA PKE schemes without complicated message paddings with SHE schemes with large integer message space. Furthermore, we remark that if the underlying PKE is multiplicative on a domain closed under addition and multiplication, this scheme has an important advantage that one can evaluate a polynomial of arbitrary degree without recryption. We propose such a scheme by concatenating ElGamal and Goldwasser-Micali scheme over a ring $\Z_N$ for a composite integer $N$ whose message space is $\Z_N^\times$. To be used in practical applications, homomorphic decryption of the base PKE is too expensive. We accelerate the homomorphic evaluation of the decryption by introducing a method to reduce the degree of exponentiation circuit at the cost of additional public keys. Using same technique, we give an efficient solution to the open problem~\cite{KLYC13} partially. As an independent interest, we obtain another generic conversion method from private key SHE to public key SHE. Differently from Rothblum~\cite{RothTCC11}, it is free to choose the message space of SHE.