International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol

Authors:
Carlos AGUILAR MELCHOR
Philippe GABORIT
Download:
URL: http://eprint.iacr.org/2007/446
Search ePrint
Search Google
Abstract: A PIR scheme is a scheme that allows an user to get an element of a database without giving any information about what part of the database he is interested in. In this paper we present a lattice-based PIR scheme, using an NTRU-like approach, in which the computational cost is a few thousand bit-operations per bit in the database. This improves the protocol computational performance by two orders of magnitude when compared to existing approaches. Our scheme has worse communication performance than other existing protocols, but we show that practical usability of PIR schemes is not as dependent on communication performance as the literature suggests, and that a trade-off between communication and computation leads to much more versatile schemes.
BibTeX
@misc{eprint-2007-13726,
  title={A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol},
  booktitle={IACR Eprint archive},
  keywords={Cryptographic Protocols / Private Information Retrieval, Lattices, Privacy},
  url={http://eprint.iacr.org/2007/446},
  note={Short version presented in WEWORC, in July 2007, Bochum, Germany carlos.aguilar@unilim.fr 13844 received 27 Nov 2007, last revised 27 Nov 2007},
  author={Carlos AGUILAR MELCHOR and Philippe GABORIT},
  year=2007
}