Skip to Main content Skip to Navigation
Reports

Single-Database Private Information Retrieval Protocols~: Overview, Usability and Trends

Abstract : A Private Information Retrieval (PIR) scheme is a protocol in which a user retrieves a record out of N from a replicated database, while hiding from the database which record has been retrieved, as long as the different replicas do not collude. A specially interesting sub-field of research, called single-database PIR, deals with the schemes that allow a user to retrieve privately an element of a non-replicated database. In these schemes, user privacy is related to the intractability of a mathematical problem, instead of based on the assumption that different replicas exist and do not collude against their users. Single-database and replicated-database PIR schemes have generated an enormous amount of research in the privacy protection field during the last two decades. However, many scientists believe, specially for single-database PIR schemes, that these are theoretical tools unusable in almost any situation. It is true that these schemes usually require the database to use an enormous amount of computational power, but considering the huge amount of applications these protocols have, it is important to evaluate precisely their usability. We present in this article an overview of the current single-database PIR schemes through the innovations they have brought to this field of research. This gives a unified view of the evolution since the first of these schemes was presented by Kushilevitz and Ostrovsky in 1997 and up to the latest trends in single-database PIR research such as trusted hardware usage, and noise-based schemes. Then, we compare the most representative of these schemes with a single set of communication and computational performance measures. We highlight 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.
Document type :
Reports
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00134415
Contributor : Philippe Gaborit <>
Submitted on : Friday, March 2, 2007 - 4:09:32 AM
Last modification on : Thursday, January 11, 2018 - 6:26:18 AM
Long-term archiving on: : Friday, September 21, 2012 - 12:20:49 PM

File

tdsc06.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00134415, version 1

Collections

Citation

Carlos Aguilar Melchor, Philippe Gaborit. Single-Database Private Information Retrieval Protocols~: Overview, Usability and Trends. [Research Report] 2007, pp.11. ⟨inria-00134415⟩

Share

Metrics

Record views

254

Files downloads

605