Paper 1997/006

Protecting Data Privacy in Private Information Retrieval Schemes

Yuval Ishai and Eyal Kushilevitz

Abstract

Private Information Retrieval (PIR) schemes allow a user to retrieve the i-th bit of a data string x, replicated in k>=2 databases, while keeping the value of i private. The main cost measure for such a scheme is its communication complexity. We study PIR schemes where in addition to the user's privacy we require data privacy. That is, in every invocation of the retrieval protocol the user learns exactly a single physical bit of x and no other information. Further, we require that even a dishonest user would not learn more than a single physical data bit. We present general transformations that allow translating PIR schemes satisfying certain properties into PIR schemes that respect data privacy as well, with a small penalty in the communication complexity. Using our machinery we are able to translate currently known PIR solutions into schemes satisfying the newly introduced, stronger privacy constraint. In particular we get: a k-database scheme of complexity O(log(n) n^{1/(2k-1)}) for every k>=2; an O(log(n))-database scheme of poly-logarithmic complexity; a 2-database computational PIR of complexity O(n^c), for every constant c>0. All these require only a single round of interaction.

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)
yuvali @ cs technion ac il
History
1997-05-04: received
Short URL
https://ia.cr/1997/006
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:1997/006,
      author = {Yuval Ishai and Eyal Kushilevitz},
      title = {Protecting Data Privacy in Private Information Retrieval Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 1997/006},
      year = {1997},
      note = {\url{https://eprint.iacr.org/1997/006}},
      url = {https://eprint.iacr.org/1997/006}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.