DIMACS Special Year on Networks Seminar


Computationally Private Information Retrieval


Niv Gilboa
Department of Computer Science, Technion


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


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

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