Paper 2009/616

Fully Homomorphic Encryption over the Integers

Marten van Dijk, Craig Gentry, 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.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Published in Eurocrypt 2010.
Keywords
Approximate GCDHomomorphic Encryption
Contact author(s)
shaih @ alum mit edu
History
2010-06-08: revised
2009-12-14: received
See all versions
Short URL
https://ia.cr/2009/616
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/616,
      author = {Marten van Dijk and Craig Gentry and Shai Halevi and Vinod Vaikuntanathan},
      title = {Fully Homomorphic Encryption over the Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2009/616},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/616}},
      url = {https://eprint.iacr.org/2009/616}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.