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
-
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},
url = {https://eprint.iacr.org/2009/616}
}
