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

Abstract

We show a technique to transform a linearly-homomorphic encryption into a 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 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 where the number of additions of degree-2 terms is bounded by a constant.