You are looking at a specific version 20080224:183704 of this paper. See the latest version.

Paper 2007/446

A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol

Carlos AGUILAR MELCHOR and Philippe GABORIT

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Short version presented in WEWORC, in July 2007, Bochum, Germany
Keywords
Private Information RetrievalLatticesPrivacy
Contact author(s)
carlos aguilar @ unilim fr
History
2008-02-24: revised
2007-12-05: received
See all versions
Short URL
https://ia.cr/2007/446
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.