Name
Abstract | ||
|---|---|---|
A PIR scheme is a scheme that allows a 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, based on problems close to coding theory problems known to be NP-complete [1], 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 not as good communication performance as 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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/ISIT.2008.4595308 | Toronto, ON |
Keywords | Field | DocType |
computational complexity,information retrieval,protocols,NP-complete problem,coding theory problem,communication performance,computational performance,database retrieval,fast private information retrieval protocol,lattice-based PIR scheme | Cryptographic protocol,Computer science,Usability,Coding theory,Decoding methods,Random number generation,Private information retrieval,Computation,Computational complexity theory,Distributed computing | Conference |
ISBN | Citations | PageRank |
978-1-4244-2257-9 | 21 | 0.94 |
References | Authors | |
6 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carlos Aguilar Melchor | 1 | 21 | 0.94 |
| Gaborit, P. | 2 | 63 | 4.37 |