International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 12 January 2015

Tancrède Lepoint, Mehdi Tibouchi
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.