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.
Category / Keywords: Cryptographic Protocols / Private Information Retrieval, Lattices, Privacy Publication Info: Short version presented in WEWORC, in July 2007, Bochum, Germany Date: received 27 Nov 2007, last revised 24 Feb 2008 Contact author: carlos aguilar at unilim fr Available formats: PDF | BibTeX Citation Version: 20080224:183704 (All versions of this report) Discussion forum: Show discussion | Start new discussion