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: ia.cr/2015/012
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]