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 $c_i=pq_i+r_i$, $i=1,\cdots,m$, where the integers $p$, $q_i$ and $r_i$ are secret. In this paper, we describe two lattice-based attacks on DGHV. The first attack is applicable when $r_1=0$ and the public integers $c_i$ satisfy a linear equation $a_2c_2+\ldots+a_mc_m=a_1q_1$ for suitably small integers $a_i$, $i=2,\ldots,m$. The second attack works when the positive integers $q_i$ satisfy a linear equation $a_1q_1+\ldots+a_mq_m=0$ for suitably small integers $a_i$, $i=1,\ldots,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},
      note = {\url{https://eprint.iacr.org/2015/1145}},
      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.