Fully Homomorphic Encryption Over the Integers

The authors 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, the 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 the approach is the conceptual simplicity. They reduce the security of the 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. They investigate the hardness of this task, building on earlier work of Howgrave-Graham.