The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


             Walmart Lecture Series in Cryptography and Complexity

                    Seminar Room, Room 261, Ziskind Building
                          on Monday, November 15, 2010
                                    at 14:30

                         Refreshments after the lecture



                                  Shai Halevi
                                     M.I.T.


                                 will speak on


                 Fully Homomorphic Encryption over the Integers

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.

Joint work with Marten van Dijk, Craig Gentry and Vinod Vaikuntanathan.