## 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.