An Efficient Somewhat HE scheme over Integers and Its Variation
In 2010, Dijk et al. demonstrated a simple somewhat homomorphic encryption (HE) scheme over the integers of which this simplicity came at the cost of a public key size in (O) over tilde(lambda(10)). Although in 2011 Coron et al. reduced the public key size to (O) over tilde(lambda(7)), it is still too large for practical applications, especially for the cloud computing. In this paper, we propose a new form of somewhat HE scheme to reduce further the public key size and a variation of the scheme to optimize the ciphertext size. First of all, we propose a new somewhat HE scheme which is built on the hardness of the approximate greatest common divisor (GCD) problem of two integers, where the public key size in the scheme is reduced to (O) over tilde(lambda(3)). Furthermore, we can reduce the length of the ciphertext of the new somewhat HE scheme by applying the modular reduction technique. Additionally, we give simulation results for evaluating ability of the proposed scheme.
somewhat homomorphic encryption cloud computing fully homomorphic encryption approximate-gcd problem