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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MAJOR revision.
Keywords
ElGamalGoldwasser-MicaliNaccache-SternHybrid SchemeMultiplicative Homomorphic EncryptionAdditive Homomorphic EncryptionFully Homomorphic EncryptionDecryption CircuitExponentiationBootstrapping
Contact author(s)
jhcheon @ snu ac kr
kjs2002 @ snu ac kr
History
2013-11-03: received
Short URL
https://ia.cr/2013/710
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/710,
      author = {Jung Hee Cheon and Jinsu Kim},
      title = {An Approach to Reduce Storage for Homomorphic Computations},
      howpublished = {Cryptology ePrint Archive, Paper 2013/710},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/710}},
      url = {https://eprint.iacr.org/2013/710}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.