New Fully Homomorphic Encryption Over the Integers

This paper presents a new fully homomorphic encryption scheme over the integers, which is different from the fully homomorphic encryption scheme in [vDGHV10], but the somewhat homomorphic encryption is similar to that in [vDGHV10]. By using the self-loop bootstrappable technique, a ciphertext is refreshed to a new ciphertext with same message of an original ciphertext and smaller error terms. The size of ciphertext is remained fixed and the expansion of ciphertext is O(n2) in the scheme. The security of the scheme is based on the hardness of finding an approximate-GCD problem over the integers, which is given a list of integers perturbed by the small error noises.