# DIMACS Special Year on Networks Seminar

## Title:

Computationally Private Information Retrieval

## Speaker:

- Niv Gilboa
- Department of Computer Science, Technion

## Place:

- Bell Labs Murray Hill Building, Room: 2B-232
**Note:** Visitors not from the MH building should use the east side
entrance "stairway 9", and call Avishai Wool, phone number 6576,
to let them in. Since entering the MH building takes time,
visitors are requested to arrive no later than 1:45pm.
- Lucent Host: Avishai Wool

## Time:

- 2:00 p.m
- Thursday, May 1, 1997 - NOTE CHANGE IN DAY

Abstract:
Private information retrieval (PIR) schemes enable a user to
access k replicated copies of a database (k >= 2), and privately
retrieve one of the n bits of data stored in the databases. This means
that the queries give each individual database no partial information
(in the information theoretic sense) on the identity of the item
retrieved by the user. Today, the best two database scheme (k=2) has
communication complexity O(n^{1/3}), while for any constant number,
k, the best k database scheme has communication complexity
O(n^{1/(2k-1)}). The motivation for the present work is the
question whether this complexity can be reduced if one is willing to
achieve {\em computational privacy}, rather than {\em information
theoretic privacy}. (This means that privacy is guaranteed only with
respect to databases that are restricted to polynomial time computations.)

We answer this question affirmatively, and show that the computational
approach leads to substantial savings. For every e > 0, we present a
two database computational PIR scheme whose communication complexity
is O(n^e). This improved efficiency is achieved by a combination of a
novel balancing technique, together with careful application of pseudo
random generators. Our schemes preserve some desired properties of
previous solutions. In particular, all our schemes use only one round
of communication, they are fairly simple, they are memoryless, and the
database contents is stored in its plain form, without any encoding.

Joint work with Benny Chor.

Document last modified on April 24, 1997