Cryptology ePrint Archive: Report 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.
Category / Keywords: public-key cryptography / homomorphic encryption
Date: received 8 Oct 2014
Contact author: dario fiore at imdea org
Available format(s): PDF | BibTeX Citation
Version: 20141011:235310 (All versions of this report)
Short URL: ia.cr/2014/813
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]