We construct a simple fully homomorphic encryption scheme, using only elementary modular arithmetic. We use Gentry's technique to construct a fully homomorphic scheme from a "bootstrappable" somewhat homomorphic scheme. However, instead of using ideal lattices over a polynomial ring, our bootstrappable encryption scheme merely uses addition and multiplication over the integers. The main appeal of our scheme is the conceptual simplicity. ;We reduce the security of our scheme to finding an approximate integer ged - i.e., given a list of integers that are near-multiples of a hidden integer, output that hidden integer. We investigate the hardness of this task, building on earlier work of Howgrave-Graham.

+More

fully homomorphic encryption scheme integer ged ideal lattices multiplication polynomial gentrys technique addition integers modular arithmetic

Halevi, S ,Gentry, C ,van Dijk, M ,Vaikuntanathan, V,.Fully Homomorphic Encryption over the Integers. 6110 (),3.

Halevi, S , et al."Fully Homomorphic Encryption over the Integers" 6110

Halevi, S ,Gentry, C ,van Dijk, M ,Vaikuntanathan, V,"Fully Homomorphic Encryption over the Integers"