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.