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.