Cryptology ePrint Archive: Report 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.

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

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]