Paper 2014/1025

XPIR: Private Information Retrieval for Everyone

Carlos Aguilar-Melchor, Joris Barrier, Laurent Fousse, and Marc-Olivier Killijian


A Private Information Retrieval (PIR) scheme is a protocol in which a user retrieves a record from a database while hiding which from the database administrators. PIR can be achieved using mutually-distrustful replicated databases, trusted hardware, or cryptography. In this paper we focus on the later setting which is known as single- database computationally-Private Information Re-trieval (cPIR). Classic cPIR protocols require that the database server executes an algorithm over all the database content at very low speeds which impairs their usage. In [1], given certain assumptions, realistic at the time, Sion and Carbunar showed that cPIR schemes were not practical and most likely would never be. To this day, this conclusion is widely accepted by researchers and practitioners. Using the paradigm shift introduced by lattice-based cryptography, we show that the conclusion of Sion and Carbunar is not valid anymore: cPIR is of practical value. This is achieved without compromising security, using standard crytosystems, and conservative parameter choices.

Note: Forgot another place in which library location was present

Available format(s)
Publication info
Preprint. MINOR revision.
LatticesHomomorphic EncryptionPrivate Information Retrieval
Contact author(s)
carlos aguilar @ polytechnique org
2015-09-04: last of 3 revisions
2015-01-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carlos Aguilar-Melchor and Joris Barrier and Laurent Fousse and Marc-Olivier Killijian},
      title = {{XPIR}: Private Information Retrieval for Everyone},
      howpublished = {Cryptology ePrint Archive, Paper 2014/1025},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.