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

Carlos Aguilar Melchor 1 Philippe Gaborit 1
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.
Type de document :
[Research Report] 2007, pp.11
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
Contributeur : Philippe Gaborit <>
Soumis le : vendredi 2 mars 2007 - 04:09:32
Dernière modification le : jeudi 11 janvier 2018 - 06:26:18
Document(s) archivé(s) le : vendredi 21 septembre 2012 - 12:20:49


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00134415, version 1



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



Consultations de la notice


Téléchargements de fichiers