Paper 2009/616 Original: eprint.iacr.org/2009/616 ↗
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2010-06-08: last updated
- 2009-12-14: published
- Short URL
- https://ia.cr/2009/616
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}