IACR News item: 03 November 2013
Jung Hee Cheon, Jinsu Kim
ePrint ReportTo 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.
Additional news items may be found on the IACR news page.