International Association
for Cryptologic Research

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.