Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. WAHC 2015
- Keywords
- Homomorphic encryptionPrivate information retrievalCryptanalysisOrthogonal lattices
- Contact author(s)
- tibouchi mehdi @ lab ntt co jp
- History
- 2015-01-12: received
- Short URL
- https://ia.cr/2015/012
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2015/012,
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},
url = {https://eprint.iacr.org/2015/012}
}
