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.
Category / Keywords: public-key cryptography / ElGamal, Goldwasser-Micali, Naccache-Stern, Hybrid Scheme, Multiplicative Homomorphic Encryption, Additive Homomorphic Encryption, Fully Homomorphic Encryption, Decryption Circuit, Exponentiation, Bootstrapping Date: received 31 Oct 2013 Contact author: jhcheon at snu ac kr, kjs2002@snu ac kr Available format(s): PDF | BibTeX Citation Version: 20131103:172321 (All versions of this report) Short URL: ia.cr/2013/710 Discussion forum: Show discussion | Start new discussion