TR06-050 Authors: Alexander Razborov, Sergey Yekhanin

Publication: 18th April 2006 18:12

Downloads: 2844

Keywords:

A two server private information retrieval (PIR) scheme

allows a user U to retrieve the i-th bit of an

n-bit string x replicated between two servers while each

server individually learns no information about i. The main

parameter of interest in a PIR scheme is its communication

complexity, namely the number of bits exchanged by the user and

the servers. A large amount of effort has been invested by

researchers over the last decade in search for efficient PIR

schemes. A number of different schemes [CGKS,BI,WY] have been

proposed, however all of them ended up with the same communication

complexity of O(n^{1/3}). The best known lower bound to date is

5*log n by [WdW]. The tremendous gap between upper and

lower bounds is the focus of our paper. We show an

Omega(n^{1/3}) lower bound in a restricted model that

nevertheless captures all known upper bound techniques.

Our lower bound applies to bilinear group based PIR schemes. A

bilinear PIR scheme is a one round PIR scheme, where user computes

the dot product of servers' responses to obtain the desired value

of the i-th bit. Every linear scheme can be turned into a

bilinear one. A group based PIR scheme, is a PIR scheme, that

involves servers representing database by a function on a certain

finite group G, and allows user to retrieve the value of this

function at any group element using the natural secret sharing

scheme based on G. Our proof relies on some basic notions of

representation theory of finite groups. We also discuss the

approaches one may take to obtain a general lower bound for

bilinear PIR.