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.