A New Somewhat Homomorphic Encryption Scheme over Integers

Abstract

At Eurocrypt 2010 van Dijk et al. presented a very simple somewhat homomorphic encryption scheme over the integers. However, this simplicity came at the cost of a public key size in O(k10). Although at Crypto 2011 Coron et al. reduced the public key size to O(k7), it was still too large for practical applications. In this paper we further reduce the public key size to O(k3) by encrypting with a new form. The semantic security of our scheme is based on approximate-GCD problem of two integers. By using Gentry's techniques, we can easily convert the somewhat scheme into a practical fully homomorphic encryption scheme available in cloud computing.