Fully Homomorphic Encryption over the Integers

by Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan.

Oded's comments

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.

The original abstract

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.

Back to list of Oded's choices.