Theory of Computing
-------------------
Title     : An &nbsp; &Omega;(<i>n</i><sup>1/3</sup>) &nbsp; Lower Bound for Bilinear Group Based Private Information Retrieval
Authors   : Alexander Razborov and Sergey Yekhanin
Volume    : 3
Number    : 12
Pages     : 221-238
URL       : https://theoryofcomputing.org/articles/v003a012

Abstract
--------

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 on two servers while each
server individually learns no information about  i. 
The main parameter of interest in a PIR scheme is its
communication complexity: the number of bits exchanged 
by the user and the servers.  Substantial effort has 
been invested by researchers over the last decade in
the search for efficient PIR schemes.   A number of 
different schemes (Chor et al., 1998, Beimel et al., 2005, 
Woodruff and Yekhanin, CCC'05) have been proposed; however, 
all of them result in the same communication complexity of
O(n^{1/3}).   The best known lower bound to date is  5 log n 
by Wehner and de Wolf (ICALP'05).   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 the user
computes the dot product of the servers' responses to obtain 
the desired value of the  i-th bit. Every linear scheme can be 
turned into a bilinear one with an asymptotically negligible
communication overhead. A group-based PIR scheme is a PIR 
scheme in which the servers represent the database by a
function on a certain finite group  G and the user retrieves
the value of this function at any group element using the
natural secret sharing scheme based on  G. Our proof
relies on the representation theory of finite groups.