*n*

^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval

Revised: December 19, 2007

Published: December 28, 2007

**Keywords:**lower bounds, private information retrieval, secret sharing, communication complexity, group representations, bilinear schemes

**ACM Classification:**H.3.3, F.1.3.e, F.1.2.b

**AMS Classification:**68P20, 68Q17, 20C20

**Abstract:**
[Plain Text Version]

A two-server *private information retrieval* (PIR) scheme
allows a user $\mathcal{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.