Craig Gentry

Fully Homomorphic Encryption over the Integers

Marten van Dijk and Craig Gentry and Shai Halevi and Vinod Vaikuntanathan

We construct a simple fully homomorphic encryption scheme, using only 
elementary modular arithmetic. We use Gentry's technique to construct 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 
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.