Paper 2015/012

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

Tancrède Lepoint and Mehdi Tibouchi


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. WAHC 2015
Homomorphic encryptionPrivate information retrievalCryptanalysisOrthogonal lattices
Contact author(s)
tibouchi mehdi @ lab ntt co jp
2015-01-12: received
Short URL
Creative Commons Attribution


      author = {Tancrède Lepoint and Mehdi Tibouchi},
      title = {Cryptanalysis of a (Somewhat) Additively Homomorphic Encryption Scheme Used in {PIR}},
      howpublished = {Cryptology ePrint Archive, Paper 2015/012},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.