Technical Report CS0904

Title: Protecting Data Privacy in Private Information Retrieval Schemes
Authors: Yuval Ishai and Eyal Kushilevitz
PDFNot Available
Abstract: Private Information Retrieval (PIR) schemes allow a user to retrieve the $i$-th bit of a data string $x$, replicated in $k \ge 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 {\em 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. 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\cdot n^{1/(2k-1)})$ for every $k\ge 2$; an $O(\log n)$-database scheme of poly-logarithmic complexity; and a 2-database computational PIR scheme of complexity $O(n^c)$, for every constant $c>0$. All these schemes require only a single round of interaction.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1997
To the main CS technical reports page

Computer science department, Technion