Cryptology ePrint Archive: Report 2009/616

Fully Homomorphic Encryption over the Integers

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

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.

Category / Keywords: public-key cryptography / Approximate GCD, Homomorphic Encryption

Publication Info: Published in Eurocrypt 2010.

Date: received 11 Dec 2009, last revised 8 Jun 2010

Contact author: shaih at alum mit edu

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20100608:141747 (All versions of this report)

Discussion forum: Show discussion | Start new discussion