Volume 3 (2007) Article 12 pp. 221-238
An   Ω(n1/3)   Lower Bound for Bilinear Group Based Private Information Retrieval
Received: May 14, 2007
Revised: December 19, 2007
Published: December 28, 2007
Download article from ToC site:
[PDF (208K)] [PS (350K)] [Source ZIP]
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.