Cryptology ePrint Archive: Report 2015/012

Cryptanalysis of a (Somewhat) Additively Homomorphic Encryption Scheme Used in PIR

Tancrède Lepoint and Mehdi Tibouchi

Abstract: Private Information Retrieval (PIR) protects users' privacy in outsourced storage applications and can be achieved using additively homomorphic encryption schemes. Several PIR schemes with a “real world” level of practicality, both in terms of computational and communication complexity, have been recently studied and implemented. One of the possible building block is a conceptually simple and computationally efficient protocol proposed by Trostle and Parrish at ISC 2010, that relies on an underlying secret-key (somewhat) additively homomorphic encryption scheme, and has been reused in numerous subsequent works in the PIR community (PETS 2012, FC 2013, NDSS 2014, etc.).

In this paper, we show that this encryption scheme is not one-way: we present an attack that decrypts arbitrary ciphertext without the secret key, and is quite efficient: it amounts to applying the LLL algorithm twice on small matrices. Used against existing practical instantiations of PIR protocols, it allows the server to recover the users' access pattern in a matter of seconds.

Category / Keywords: cryptographic protocols / Homomorphic encryption, Private information retrieval, Cryptanalysis, Orthogonal lattices

Original Publication (with minor differences): WAHC 2015

Date: received 9 Jan 2015

Contact author: tibouchi mehdi at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Version: 20150112:071831 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]