Paper 1998/003

Private Information Retrieval by Keywords

Benny Chor, Niv Gilboa, and Moni Naor

Abstract

Private information retrieval (PIR) schemes enable a user to access one or more servers that hold copies of a database and {\em privately} retrieve parts of the $n$ bits of data stored in the database. This means that the queries give each individual database no partial information (in the information theoretic or computational sense) on the identity of the item retrieved by the user. All known PIR schemes assume that the user knows the {\em physical address} of the sought item. This is usually not the case when accessing a public database that is not managed by the user. Such databases are typically presented with keywords, which are then internally translated (at the database end) to physical addresses, using an appropriate search structure (for example, a hash table or a binary tree). In this note we describe a simple, modular way to privately access data by keywords. It combines {\em any} conventional search structure with {\em any} underlying PIR scheme (including single server schemes). The transformation requires no modification in the way that the search structure is maintained. Therefore the same database will support both private and regular (non private) searches.

Metadata
Available format(s)
PS
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Contact author(s)
benny @ cs technion ac il
History
1998-02-03: received
Short URL
https://ia.cr/1998/003
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:1998/003,
      author = {Benny Chor and Niv Gilboa and Moni Naor},
      title = {Private Information Retrieval by Keywords},
      howpublished = {Cryptology ePrint Archive, Paper 1998/003},
      year = {1998},
      note = {\url{https://eprint.iacr.org/1998/003}},
      url = {https://eprint.iacr.org/1998/003}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.