Welcome to the resource topic for
**1997/006**

**Title:**

Protecting Data Privacy in Private Information Retrieval Schemes

**Authors:**
Yuval Ishai, 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.

**ePrint:**
https://eprint.iacr.org/1997/006

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .