Paper 2014/813

Boosting Linearly-Homomorphic Encryption to Evaluate Degree-2 Functions on Encrypted Data

Dario Catalano and Dario Fiore

Abstract

We show a technique to transform a linearly-homomorphic encryption into a homomorphic encryption scheme capable of evaluating degree-2 computations on ciphertexts. Our transformation is surprisingly simple and requires only one very mild property on the underlying linearly-homomorphic scheme: the message space must be a public ring in which it is possible to sample elements uniformly at random. This essentially allows us to instantiate our transformation with virtually all existing number-theoretic linearly-homomorphic schemes, such as Goldwasser-Micali, Paillier, or ElGamal. Our resulting schemes achieve circuit privacy and are compact when considering a subclass of degree-2 polynomials in which the number of additions of degree-2 terms is bounded by a constant. As an additional contribution we extend our technique to build a protocol for outsourcing computation on encrypted data using two (non-communicating) servers. Somewhat interestingly, in this case we can boost a linearly-homomorphic scheme to support the evaluation of any degree-2 polynomial while achieving full compactness.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
homomorphic encryption
Contact author(s)
dario fiore @ imdea org
History
2014-10-11: received
Short URL
https://ia.cr/2014/813
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/813,
      author = {Dario Catalano and Dario Fiore},
      title = {Boosting Linearly-Homomorphic Encryption to Evaluate Degree-2 Functions on Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2014/813},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/813}},
      url = {https://eprint.iacr.org/2014/813}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.