**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.

**Category / Keywords: **public-key cryptography / Homomorphic Encryption, Cryptanalysis, Lattice reduction

**Date: **received 26 Nov 2015

**Contact author: **abderrahmane nitaj at unicaen fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20151127:175522 (All versions of this report)

**Short URL: **ia.cr/2015/1145

[ Cryptology ePrint archive ]