In 2009, Gentry provided first eveidence to the possibility of fully homomorphic encryption scheme. The current work strengthens this evidence by presenting a relatively simple construction that is based on a more elementary assumption. The work is based on Gentry's approach, which first constructs a scheme that can handle its own decryption function (i.e., provides homomorphic encryption w.r.t this function), and then transforms it to a full fleged scheme.
We describe a very simple ``somewhat homomorphic'' encryption scheme using only elementary modular arithmetic, and use Gentry's techniques to convert it into a fully homomorphic scheme. Compared to Gentry's construction, our somewhat homomorphic scheme merely uses addition and multiplication over the integers rather than working with ideal lattices over a polynomial ring. The main appeal of our approach is the conceptual simplicity.
We reduce the security of our somewhat homomorphic scheme to finding an approximate integer gcd -- 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.