Paper 2015/1145

Lattice Attacks on the DGHV Homomorphic Encryption Scheme

Abderrahmane Nitaj and Tajjeeddine Rachidi

Abstract

In 2010, van Dijk, Gentry, Halevi, and Vaikuntanathan described the first fully homomorphic encryption over the integers, called DGHV. The scheme is based on a set of m public integers ci=pqi+ri, i=1,,m, where the integers p, qi and ri are secret. In this paper, we describe two lattice-based attacks on DGHV. The first attack is applicable when r1=0 and the public integers ci satisfy a linear equation a2c2++amcm=a1q1 for suitably small integers ai, i=2,,m. The second attack works when the positive integers qi satisfy a linear equation a1q1++amqm=0 for suitably small integers ai, i=1,,m. We further apply our methods for the DGHV recommended parameters as specified in the original work of van Dijk, Gentry, Halevi, and Vaikuntanathan.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Homomorphic EncryptionCryptanalysisLattice reduction
Contact author(s)
abderrahmane nitaj @ unicaen fr
History
2015-11-27: received
Short URL
https://ia.cr/2015/1145
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1145,
      author = {Abderrahmane Nitaj and Tajjeeddine Rachidi},
      title = {Lattice Attacks on the {DGHV} Homomorphic Encryption Scheme},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/1145},
      year = {2015},
      url = {https://eprint.iacr.org/2015/1145}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.