%% Razborov - Yekhanin \documentclass{toc} \tocdetails{% volume=3, number=12, year=2007, firstpage=221, received={May 14, 2007}, revised={December 19, 2007}, published={December 28, 2007} } \runningauthor{A.~Razborov and S.~Yekhanin} \runningtitle{Lower Bound for Private Information Retrieval} \copyrightauthor{Alexander Razborov and Sergey Yekhanin} \newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}} \newcommand{\ans}{\textrm{ans}} \newcommand{\que}{\textrm{que}} \begin{document} \begin{frontmatter}[classification=float] \title{An $\Omega(n^{1/3})$ Lower Bound for Bilinear Group-Based Private Information Retrieval\thanks{A preliminary version of this paper appeared in the proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS'06)~\cite{RY}.}} \tocpdftitle{An $\Omega(n^{1/3})$ Lower Bound for Bilinear Group-Based \\ Private Information Retrieval\thanks{A preliminary version of this paper appeared in the proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS'06)~\cite{RY}.}} \tocpdfauthor{Alexander Razborov and Sergey Yekhanin} \author[Sasha]{Alexander A. Razborov\thanks{Supported by the Charles Simonyi Endowment and NSF grant ITR-0324906.}} \author[Sergey]{Sergey Yekhanin\thanks{Supported by NSF grant CCR 0219218.}} \tockeywords{lower bounds, private information retrieval, secret sharing, communication complexity, group representations, bilinear schemes} \begin{abstract} A two-server \emph{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) %%~\cite{CGKS,BIK,WY} 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). %% ~\cite{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 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. \end{abstract} \tocams{68P20, 68Q17, 20C20} %Computational difficulty, modular representations \tocacm{H.3.3, F.1.3.e, F.1.2.b}% Retrieval Models, %%Relations among complexity measures, Interactive and reactive computation \end{frontmatter} \section{Introduction} Private information retrieval (PIR) was introduced in a seminal paper by Chor, Goldreich, Kushilevitz, and Sudan~\cite{CGKS}. In such a scheme a server holds an $n$-bit string $x$ representing a database, and a user holds an index $i\in [n]$. At the end of the protocol the user should learn $x_i$ and the server should learn nothing about $i$. A trivial PIR protocol is to send the whole database $x$ to the user. While this protocol is perfectly private, its communication complexity is prohibitively large. (Note for comparison that in the non-private setting there is a protocol with only $\log n+1$ bits of communication.) This raises the question of how much communication is necessary to achieve privacy. It has been shown in~\cite{CGKS} that when information-theoretic privacy is required the above trivial solution is in fact optimal. To get around this Chor et al. suggested replicating the database among $k>1$ non-communicating servers. For the case of two servers Chor et al.~\cite{CGKS} obtained a PIR protocol with $O(n^{1/3})$ communication complexity. In spite of the large amount of subsequent research, this bound remains the best known to date. In contrast to two-server PIR schemes, PIR schemes involving three or more servers have undergone several steps of improvement. The initial three-server PIR scheme of Chor et al.~\cite{CGKS} had communication complexity $O(n^{1/3})$. Later Ambainis~\cite{Amb} suggested a scheme with $O(n^{1/5})$ communication, and Beimel et al.~\cite{BIKR} further reduced the communication to $O(n^{1/5.25})$. Finally, in a recent paper Yekhanin~\cite{Y_nice} achieved $O(n^{1/32,582,658})$ communication, and showed that communication can be further reduced to $n^{o(1)}$ under a plausible number-theoretic assumption regarding the density of Mersenne primes (see also~\cite{KY}). The best known (unconditional) upper bound for communication complexity of $k$-server PIR when $k$ is considered as a parameter can be obtained by a combination of results from~\cite{BIKR} and~\cite{Y_nice} and is $n^{O\left(\frac{\log\log k}{k\log k}\right)}$. On the lower bounds side the progress has been scarce. We list the known results for the two-server case. The first nontrivial lower bound of $4\log n$ is due to Mann~\cite{Mann}. Later it was improved to $4.4\log n$ by Kerenidis and de Wolf~\cite{KdW} using the results of Katz and Trevisan~\cite{KT}. The current record of $5\log n$ is due to Wehner and de Wolf~\cite{WdW}. The proofs of the last two bounds use quantum arguments. The PIR literature existing today is extensive. There are a number of generalizations of the basic PIR setup that have been studied. Most notably those are: computational PIR (\ie, PIR based on computational assumptions), PIR with privacy against coalitions of servers, PIR with fixed answer sizes, robust PIR, etc. Private information retrieval schemes are also closely related to locally decodable codes (LDC). For a survey of PIR and LDC literature see~\cite{Gasarch,Y_thesis}. In the present paper we study the communication complexity of PIR in the most basic, two-server case. There are two reasons why this case in especially attractive. Firstly, determining the communication complexity of optimal two-server PIR schemes is arguably the most challenging problem in the area of PIR research. There has been no quantitative progress for this case since the problem was posed. Although to date a number of different two-server PIR schemes are known~\cite{CGKS,BIK,WY} all of them have the same communication complexity of $O(n^{1/3}).$ Secondly, the work of~\cite{BIKR} implies that a large improvement in the upper bound for two-server PIR would yield better PIR protocols for all other values of $k$. \subsection{Our results} Our main result is an $\Omega(n^{1/3})$ lower bound for a restricted model of two-server PIR. Our restrictions revolve around a novel, though quite natural, combinatorial view of the problem. We show that two-server PIR is essentially a problem regarding the minimal size of an {\it induced universal graph} for a family of graphs with a certain property.\footnote{We actually prefer to use language of matrices rather than graphs, but of course graph formulations are easy to obtain. A graph $G$ is called induced universal for a graph family $\mathcal F$ if every graph $F\in\mathcal F$ is an induced subgraph of $G$.} This view allows us to identify two natural models of PIR, namely, {\it bilinear} PIR, and \emph{bilinear group-based} PIR. 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. A \emph{group-based} PIR scheme is a PIR scheme that involves the servers representing the database by a function on a certain finite group $G$, and allows the user to retrieve the value of this function at any group element using the natural secret sharing scheme based on $G$. We establish an $\Omega(n^{1/3})$ lower bound for communication complexity of any bilinear group-based PIR scheme, that holds regardless of the underlying group $G$ and regardless of the algorithms run by the servers. The model of bilinear group-based PIR generalizes all PIR protocols known to date, thus our lower bound demonstrates a common shortcoming of the existing upper bound techniques. It also helps to explain why the (hitherto somewhat arbitrary looking) numerical value $O(n^{1/3})$ in fact represents quite a natural barrier for techniques of this sort. It turns out that the communication complexity of bilinear group-based PIR schemes over a group $G$ can be estimated in terms of the number of low-dimensional principal left ideals in the group algebra $\mathbb{F}_q[G]$. Our main technical result is an upper bound for this quantity obtained by an argument relying on the representation theory of finite groups. \subsection{Related work} Apart from the work on general lower bounds for PIR protocols surveyed above, there has been some effort to establish (stronger) lower bounds for various restricted models of PIR~\cite{Itoh_lower,GKST, WdW}. In particular, Itoh~\cite{Itoh_lower} obtained polynomial lower bounds on the communication complexity of one-round PIR schemes under the assumption that each server returns a multilinear or affine function of its input. Goldreich et al.~\cite{GKST} introduced the notion of \emph{linear} PIR protocols, \ie, protocols where the servers are restricted to return linear combinations of the database bits to the user, and also the notion of \emph{probe complexity}, \ie, the maximal number of bits the user needs to read from the servers' answers in order to compute $x_i$. Goldreich et al. obtained polynomial lower bounds for the communication complexity of two-server linear PIR schemes whose probe complexity is constant. Later, their results were extended by Wehner and de Wolf~\cite{WdW} who showed that the restriction of linearity can in fact be dropped. See also~\cite{BFG}. It is not easy to match the restricted models surveyed above against one another or against our model, as the restrictions are quite different. We do not impose any restriction on the functions computed by the servers as in~\cite{Itoh_lower}, and do not restrict the user to read only a small number of bits from servers' answers as in~\cite{GKST}. We show that our bilinearity restriction is weaker than the linearity restriction of~\cite{GKST}, since every linear protocol can be easily turned into a bilinear one. However, we insist that the PIR scheme should employ group-based secret sharing, and that the user should be able to privately reconstruct not only the database bits but also some extra functions of the database (given by the values at group elements that do not correspond to database bits). \subsection{Outline} In \expref{Section}{sec:prelim} we introduce our notation and provide some necessary definitions. In \expref{Section}{sec:combinatorialPIR} we present our combinatorial interpretation of two-server PIR, and identify the models of bilinear PIR and bilinear group-based PIR. \expref{Section}{sec:complexityBilinGBPIR} contains the main technical contribution of the paper. We introduce the necessary algebraic tools and establish an $\Omega(n^{1/3})$ lower bound for communication complexity of any bilinear group-based PIR scheme. In \expref{Section}{sec:conclusion} we discuss possible interpretations of our results and pose an open problem. In the appendix we review currently known two-server PIR schemes and demonstrate that all of them are bilinear group-based. \section{Preliminaries}\label{sec:prelim} Let $[s]\eqdef\{1,\ldots,s\}$. We assume that $q$ is a prime power and use the notation $\mathbb{F}_q$ to denote a finite field of $q$ elements. We assume that the database contains entries from the alphabet $[q],$ rather than just a binary alphabet. We also assume some implicit bijection between $[q]$ and $\mathbb{F}_q$. Throughout $\log$ stands for the $\log$ base $q$. The notation $a\circ b$ stands for concatenation of strings $a$ and $b$. A two-server PIR scheme involves two servers, $\mathcal{S}_1$ and $\mathcal{S}_2$, each holding the same $n$-bit string $x$ (the database), and a user $\mathcal{U}$ who knows $n$ and wishes to retrieve some bit $x_i$, $i \in [n],$ without revealing the value of $i$. We restrict our attention to one-round information-theoretic PIR protocols. The following definition is a non-uniform variant of the definition from~\cite{BIKR}. \begin{definition}\label{2PIRdef} A two-server PIR protocol is a triplet of non-uniform algorithms $\mathcal P=(\mathcal Q, \mathcal A, \mathcal C)$. We assume that each algorithm is given $n$ as advice. At the beginning of the protocol, the user $\mathcal U$ tosses random coins and obtains a random string $r$. Next, $\mathcal U$ invokes $\mathcal Q(i,r)$ to generate a pair of queries $(\que_1,\que_2)$. $\mathcal{U}$ sends $\que_1$ to $\mathcal{S}_1$ and $\que_2$ to $\mathcal{S}_2$. Each server $\mathcal S_j$ responds with an answer $\ans_j=\mathcal A(j,x,\que_j)$. (We assume without loss of generality that servers are deterministic.) Finally, $\mathcal U$ computes its output by applying the reconstruction algorithm $\mathcal C(\ans_1,\ans_2,i,r)$. A protocol as above should satisfy the following requirements: \begin{itemize} \item {\bf Correctness :} For any $n,\ x \in [q]^n$, and $i\in [n]$, the user outputs the correct value of $x_i$ with probability $1$ (where the probability is over the random strings $r$). \item {\bf Privacy :} Each server individually learns no information about $i$. More precisely, we require that for any $n$ and for any $j=1,2$, the distributions $\que_j(i,r)$ are identical for all values $i\in [n]$. \end{itemize} \end{definition} The \emph{communication complexity} of a PIR protocol $\mathcal P$ is the function of $n$ measuring the total number of bits communicated between the user and the servers, maximized over all choices of $x\in [q]^n$, $i\in [n]$, and random inputs. \begin{definition}\label{linear2PIRdef}~\cite{GKST} A \emph{linear} PIR scheme is a PIR scheme where the answer function $\mathcal A(j,x,\que_j)$ is linear in $x$ for arbitrary fixed values of $j$ and $\que_j$. In other words, every bit of an answer is a certain linear combination of the database bits. \end{definition} \section{A combinatorial view of two-server PIR}\label{sec:combinatorialPIR} \begin{definition} A generalized Latin square ($\textrm{GLS}[n,T]$ for short) is a square matrix $Q$ of size $T$ by $T$ over an alphabet $[n]\cup\{*\}$ such that: \begin{itemize} \item For every $i\in [n]$ and $j\in [T]$, there exists a unique $k\in [T]$ such that $Q_{jk}=i$; \item For every $i\in [n]$ and $j\in [T]$, there exists a unique $k\in [T]$ such that $Q_{kj}=i$. \end{itemize} \end{definition} In particular, every row (or column) of a $\textrm{GLS}[n,T]$ contains precisely $(T-n)$ stars. We call the ratio $n/T$ the \emph{density} of the generalized Latin square. It is easy to see that generalized Latin squares of density $1$ are simply Latin squares. Let $Q$ be a $\textrm{GLS}[n,T]$, and let $\sigma: [n]\to [q]$ be an arbitrary map. By $Q_\sigma$ we denote the matrix of size $T$ by $T$ over the alphabet $[q]\cup\{*\}$ that is obtained from $Q$ by replacing every non-star entry $i$ in $Q$ by $\sigma(i)$. We say that a matrix $C\in [q]^{T\times T}$ is a \emph{completion} of $Q_\sigma$ if $C_{ij}=\left({Q_\sigma}\right)_{ij}$ whenever $\left({Q_\sigma}\right)_{ij}\in [q]$. For matrices $C\in [q]^{c\times c}$ and $A\in [q]^{\ell \times \ell}$ we say that $C$ \emph{reduces} to $A$ if there exist two maps $\pi_{1}: [c]\to [\ell]$ and $\pi_2: [c]\to [\ell]$ such that for any $j,k\in [c]$, $C_{jk}=A_{\pi_1(j),\pi_2(k)}$. Note that we do not impose any restrictions on the maps $\pi_1$ and $\pi_2$; in particular $c$ can be larger than $\ell$. \begin{definition} Let $Q$ be a $\textrm{GLS}[n,T]$ and $A\in [q]^{\ell\times \ell}$. We say that $A$ \emph{covers} $Q$ (notation $Q \hookrightarrow A$) if, for every $\sigma: [n]\to [q]$, there exists a completion $C$ of $Q_\sigma$ such that $C$ reduces to $A$. \end{definition} \begin{theorem}\label{PIRandGLS} The following two implications are valid: \begin{itemize} \item A pair $Q\hookrightarrow A$, where $Q$ is a $\textrm{GLS}[n,T]$ and $A\in [q]^{\ell \times \ell}$, yields a two-server PIR protocol with communication $\log T$ from $\mathcal U$ to each $\mathcal{S}_j$ and communication $\log \ell$ from the $\mathcal{S}_j$'s back to $\mathcal{U}$. \item A two-server PIR protocol with queries of length $t(n)$ and answers of length $a(n)$, where the user tosses at most $\tau(n)$ random coins, yields a pair $Q\hookrightarrow A$, where $Q$ is a $\textrm{GLS}\left[n,nq^{t(n)+\tau(n)}\right]$ and $A$ is a $q$-ary square matrix of size $nq^{t(n)+a(n)}$. \end{itemize} \end{theorem} \begin{proof} We start with the first part. We assume that the matrix $A$ is known to all parties $\mathcal{U}$, $\mathcal{S}_1$, and $\mathcal{S}_2$. At the preprocessing stage, the servers use the database $x\in [q]^n$ to define the map $\sigma:[n]\to [q]$, setting $\sigma(i)\eqdef x_i$. Also, they find an appropriate completion $C$, and fix maps $\pi_1:[T]\to [\ell]$ and $\pi_2:[T]\to [\ell]$, such that for all $j,k$: $C_{jk}=A_{\pi_1(j),\pi_2(k)}$. Next, the following protocol is executed. $$ \begin{array}{|lll|} \hline \mathcal U & : & \mbox{Picks a location $j,k$ in $Q$ such that} \\ & & \mbox{\ \ \ \ \ \ \ \ $Q_{jk}=i$ uniformly at random.} \\ \mathcal U\to \mathcal S_1 & : & j \\ \mathcal U\to \mathcal S_2 & : & k \\ \mathcal U\gets \mathcal S_1 & : & \pi_1(j) \\ \mathcal U\gets \mathcal S_2 & : & \pi_2(k) \\ \mathcal U & : & \mbox{Outputs $A_{\pi_1(j),\pi_2(k)}$.} \\ \hline \end{array} $$ It is straightforward to verify that the protocol above is private, since a uniformly random choice of a location $j,k$ such that $Q_{jk}=i$ induces uniformly random individual distributions on $j$ and $k$. Correctness follows from the fact that $C$ reduces to $A$. Total communication is given by $2(\log T + \log \ell)$. \smallskip Now we proceed to the second part. Consider a two-server protocol $\mathcal P=(\mathcal Q, \mathcal A, \mathcal C)$. First we show that one can modify $\mathcal P$ to obtain a new PIR protocol $\mathcal P^\prime=(\mathcal Q^\prime, \mathcal A^\prime, \mathcal C^\prime)$ such that $\mathcal C^\prime$ depends only on $\ans_1^\prime$ and $\ans_2^\prime$, but not on $i$ or $r$. The transformation is simple: \begin{itemize} \item First $\mathcal Q^\prime$ obtains a random string $r$ and invokes $\mathcal Q(i,r)$ to generate $(\que_1,\que_2)$. Next $\mathcal Q^\prime$ tosses $\log n$ extra random coins to represent $i$ as a random sum $i=i_1+i_2 \mod n $, sets $\que_1^\prime=\que_1\circ i_1$, $\que_2^\prime=\que_2\circ i_2$, and sends $\que_1^\prime$ to $\mathcal{S}_1$ and $\que_2^\prime$ to $\mathcal{S}_2$. \item For $j=1,2$, $\mathcal A^\prime$ extracts $\que_j$ from $\que_j^\prime$, runs $\mathcal A$ on $(j,x,\que_j)$, and returns $\ans_j\circ \que_j^\prime$. \item Finally, $\mathcal C^\prime$ extracts $\que_1,\que_2,\ans_1,\ans_2$, and $i$ from $\ans_1^\prime$ and $\ans_2^\prime$, and performs a brute force search over all possible random coin tosses of $\mathcal Q$ to find some random input $r^\prime$ such that $\mathcal Q(i,r^\prime)=(\que_1,\que_2)$. $\mathcal C^\prime$ runs $\mathcal C$ on $(\ans_1,\ans_2,i,r^\prime)$ and returns the answer (if no such $r^\prime$ exists, $\mathcal C^\prime$ answers arbitrarily). Note that the string $r^\prime$ may in fact be different from the string $r$; however the correctness property of $\mathcal P$ implies that even in this case $\mathcal C^\prime$ outputs the right value. \end{itemize} Now consider the protocol $\mathcal P^\prime$. Let $Q_j^\prime$ denote the range of queries to server $j$, and $A_j^\prime$ denote the range of answers from server $j$. The variable $\que_j^\prime$ ranges over $Q_j^\prime$, and the variable $\ans_j^\prime$ ranges over $A_j^\prime$. Let $R(\que_j^\prime,i)$ denote the set of random strings $r$ that lead to the query $\que_j^\prime$ to server $j$ on input $i$. Formally, \begin{align*} R(\que_1^\prime,i) &= \bigl\{r\in [q]^{\tau(n)} \mid \exists \ \que_2^\prime: Q(i,r)=(\que_1^\prime,\que_2^\prime)\bigr\}\,, \\ R(\que_2^\prime,i) &= \bigl\{r\in [q]^{\tau(n)}\mid \exists \ \que_1^\prime: Q(i,r)=(\que_1^\prime,\que_2^\prime)\bigr\}\,. \end{align*} Note that the privacy property of the protocol $\mathcal P^\prime$ means that the cardinalities of $R(\que_j^\prime,i)$ are independent of $i$. We denote these cardinalities by $r(\que_j^\prime)$. It is easy to see that $r(\que_j^\prime)$ is always an integer between $1$ and $q^{\tau(n)}$. Now we are ready to define the matrices $Q$ and $A$. Rows of $Q$ are labelled by pairs $(\que_1^\prime,s_1)$, where $s_1\in [r(\que_1^\prime)]$. Columns of $Q$ are labelled by pairs $(\que_2^\prime,s_2)$, where $s_2\in [r(\que_2^\prime)]$. We set $Q_{(\que_1^\prime,s_1),(\que_2^\prime,s_2)}=i$ if there exists a string $r\in R(\que_1^\prime,i)\cap R(\que_2^\prime,i)$ such that $r$ is the string number $s_1$ in $R(\que_1^\prime,i)$ and the string number $s_2$ in $R(\que_2^\prime,i)$ with respect to lexicographic ordering of these sets; otherwise we set $Q_{(\que_1^\prime,s_1),(\que_2^\prime,s_2)}=*$. The definition of the protocol $\mathcal P^\prime$ easily implies that for every pair $(\que_1^\prime,\que_2^\prime)$ there can be at most one $i$ such that $R(\que_1^\prime,i)\cap R(\que_2^\prime,i) \neq \emptyset$, therefore $Q$ is correctly defined. Consider now an arbitrary pair $\left(i,(\que_1^\prime,s_1)\right)$, where $s_1 \in [r(\que_1^\prime)]$. Let $r$ be the random string number $s_1$ in lexicographic ordering of $R(\que_1^\prime,i)$. Let $\mathcal {Q}^\prime(i,r)=(\que_1^\prime,\que_2^\prime)$, and let $s_2$ be the number of $r$ in lexicographic ordering of $R(\que_2^\prime,i)$. The column of $Q$ labelled $(\que_2^\prime,s_2)$ is the unique column such that $Q_{(\que_1^\prime,s_1),(\que_2^\prime,s_2)}=i$. Thus we proved that every row of $Q$ contains exactly one entry labelled $i$. A similar argument proves this claim for columns. Thus $Q$ is a generalized Latin square. Now we proceed to the matrix $A$. Rows of $A$ are labelled by possible values of $\ans_1^\prime$, similarly columns of $A$ are labelled by possible values of $\ans_2^\prime$. We set $A_{\ans_1^\prime,\ans_2^\prime}= \mathcal{C}^\prime(\ans_1^\prime,\ans_2^\prime)$. The matrix $A$ defined above may not be square, however one can always pad it to a square shape. It remains to show that $Q\hookrightarrow A$. Given a map $\sigma: [n]\to [q]$ we consider the database $x$, where $x_i=\sigma(i)$. We use the protocol $\mathcal P^\prime$ to define maps $\pi_1$ from the row set of $Q$ to the row set of $A$, and $\pi_2$ from the column set of $Q$ to the column set of $A$. We set $\pi_1(\que_1^\prime,s_1)=\mathcal A^\prime(1,x,{\rm que}_1^\prime)$ and $\pi_2(\que_2^\prime,s_2)=\mathcal A^\prime(2,x,\que_2^\prime)$. The correctness property of $\mathcal P^\prime$ implies that the maps $\pi_1,\pi_2$ reduce a certain completion of $Q_\sigma$ to $A$. %%% ToC Edit. Author check last sentence above for correctness. \end{proof} The theorem above represents our combinatorial view of two-server PIR protocols. A PIR protocol is just a pair $Q\hookrightarrow A$, where $Q$ is a generalized Latin square and $A$ is a $q$-ary matrix. Every PIR protocol can be converted into this form, and in case the number of user's coin tosses is linear in the query length such conversion does not affect the asymptotic communication complexity. \subsection{Bilinear PIR} The combinatorial interpretation of PIR suggested above views PIR as a problem of reducing certain special families of matrices to some fixed matrix. A nice example of a nontrivial matrix where one can say a lot about matrices that reduce to it is a Hadamard matrix. \begin{definition}\label{Hadamard}A Hadamard matrix $H_{m}$ is a $q^m$ by $q^m$ matrix where rows and columns are labelled by elements of $\mathbb{F}_q^m$ and matrix cells contain the dot products of corresponding labels. I.e. $(H_m)_{v_1,v_2}=(v_1,v_2)$. \end{definition} \begin{lemma}\label{subHadamard} Let $M$ be a square matrix with entries from $\mathbb{F}_q$; then $M$ reduces to a Hadamard matrix $H_m$ if and only if the rank of $M$ is at most $m$. \end{lemma} \begin{proof} Clearly, the rank of $H_m$ is $m$; therefore the rank of any matrix that reduces to $H_m$ is at most that large. To prove the converse, observe that $M$ can be written as a sum of $m$ matrices $M=M^1+\ldots+M^m$, where each $M^j$ is of rank at most one. Let $t$ be the dimension of $M$. For every $i\in [m]$ set the $i$-th coordinate of $m$ long vectors $v^1,\ldots,v^t\ $ $u^1,\ldots,u^t$ so that $v^j_iu^k_i=M^i_{jk}$. Now the maps $\pi_1: [t]\to [q^m],$ $\pi_2: [t]\to [q^m]$ defined by $\pi_1(j)=v^j,$ $\pi_2(k)=u^k$ embed $M$ into $H_m$. \end{proof} The above lemma is important since it allows us to reduce the proof that $Q\hookrightarrow H_m$ for some generalized Latin square $Q$ to showing that for every $\sigma: [n]\to \mathbb{F}_q$, $Q_\sigma$ can be completed to a low rank matrix. \begin{definition} We say that a two-server PIR scheme $Q\hookrightarrow A$ is \emph{bilinear} if $A=H_m$ for some value of $m$. \end{definition} Another way to formulate the above definition is to say that a PIR scheme is bilinear if $\mathcal U$ computes the dot product of the servers' answers to obtain the value of $x_i$. The next lemma shows that the restriction of bilinearity is weaker than that of linearity. \begin{lemma}\label{linBilin} Every linear PIR protocol can be turned into a bilinear PIR protocol with the same asymptotic communication complexity. \end{lemma} \begin{proof} In a linear PIR protocol the user receives two strings $\ans_1,\ans_2$ of linear combinations of database bits from the servers. The $n$-dimensional unit vector corresponding to the $i$-th bit of the database is guaranteed to be in the joint span of the combinations from $\ans_1$ and $\ans_2$. The final output of $\mathcal U$ is a sum of two dot products $(c_1,\ans_1)+(c_2,\ans_2)=x_i$, for some vectors $c_1$ and $c_2$ that are computed by the user along with queries $(\que_1,\que_2)$. The idea behind turning a linear protocol into a bilinear one is simple. After generating $(\que_1,\que_2)$ along with $c_1$ and $c_2$, $\mathcal U$ represents $c_1$ and $c_2$ as sums of random strings $c_1=c_{11}+c_{12}$, $c_2=c_{21}+c_{22}$, and sends $\que_1\circ c_{11}\circ c_{21}$ to $\mathcal S_1$ and $\que_2\circ c_{12}\circ c_{22}$ to $\mathcal S_2$. Each server responds with a string of $2+|\ans_1|+|\ans_2|$ bits. $\mathcal S_1$ sends back $1\circ (c_{11},\ans_1)\circ c_{21}\circ \ans_1$. $\mathcal S_2$ sends back $(c_{22},{\rm ans}_2)\circ 1\circ \ans_{2}\circ c_{12}$. It is easy to see that the dot product of the servers' answers yields $x_i$, and that the procedure above increases the overall communication only by a constant factor. \end{proof} \subsection{Group-based PIR} Finite groups are a natural source of generalized Latin squares. Let $G=\{g_1,\ldots,g_T\}$ be a finite group of size $T$. Let $S=\{s_1,\ldots,s_n\}\subseteq G$ be an ordered subset of $G$ of size $n$. A generalized Latin square $Q_{G,S}$ is a $T$ by $T$ square matrix whose rows and columns are labelled by elements of $G$, and $Q_{g_1,g_2}=i$ if $g_1g_2^{-1}=s_i$, while all other locations contain stars. When a PIR protocol $Q\hookrightarrow A$ uses a generalized Latin square $Q_{G,S}$ we say that it \emph{employs a group-based secret sharing scheme}. Essentially, this means that given an index $i$, $\mathcal U$ maps it to a group element $s_i$, represents $s_i$ as a random product in the group $s_i=g_1g_2^{-1}$, and sends $g_j$ to $\mathcal S_j$. \smallskip The notion of a \emph{group-based} PIR protocol (for which we later prove a lower bound) is more restrictive. Let $M\in [q]^{T\times T}$ and $G$ be finite group. Assume that the rows and columns of $M$ are labelled by $g_1,\ldots,g_T$. We say that $M$ \emph{respects} $G$ if, for every $g_1,g_2,g_3,g_4\in G$ such that $g_1g_2^{-1}=g_3g_4^{-1}$, we have $M_{g_1,g_2}=M_{g_3,g_4}$. \begin{definition}\label{defGBPIR} We say that a PIR protocol $Q\hookrightarrow A$ is \emph{group-based} if it employs a secret sharing scheme based on some group $G$ and, for every $\sigma:[n]\to \mathbb{F}_q$, there exists a completion $C$ such that $C$ reduces to $A$ and $C$ respects $G$. \end{definition} Stated in other words, a PIR scheme is group-based if the servers represent the database by a function on a certain finite group $G$ and the scheme allows the user to retrieve the value of this function at any group element using the natural secret sharing based on $G$. \section{Communication complexity of bilinear group-based PIR} \label{sec:complexityBilinGBPIR} Consider a bilinear group-based PIR scheme $Q\hookrightarrow H_r$ based on a group $G$, with answer length $r$. Clearly, the query length is $\log |G|$. Let $N(q,G,r)$ denote the number of $|G|$ by $|G|$ matrices over $\mathbb{F}_q$ that respect $G$ (for some fixed labelling $\{g_1,\ldots,g_T\}$ or rows and columns) and have rank at most $r$. It is easy to see that \begin{equation}\label{respectToCC} q^n\leq N(q,G,r)\,, \end{equation} since by \expref{Lemma}{subHadamard} every database yields such a matrix and distinct databases yield distinct matrices. In \expref{Section}{secAlgForm} we obtain an equivalent algebraic definition for $N(q,G,r)$, and in \expref{Section}{secMath} we prove an upper bound for $N(q,G,r)$. Our final result is a constraint on the range of possible values of $q$, $|G|$, and $r$. This constraint implies an $\Omega(n^{1/3})$ lower bound for the total communication of any bilinear group-based PIR scheme. \subsection{Algebraic preliminaries}\label{subsec:algBasics} Our proof relies on some basic notions of the representation theory of finite groups. The standard references for this subject are~\cite{Weintraub},~\cite{Isaacs}. For a general algebra background see~\cite{VdWaerden}. Let $G=\{g_1,\ldots,g_T\}$ be a finite (not necessarily abelian) group. The \emph{general linear group} $GL_r(\mathbb{F}_q)$ is the multiplicative group of all non-singular $r$ by $r$ matrices over $\mathbb{F}_q$. \begin{itemize} \item An $\mathbb{F}_q$-\emph{representation} of $G$ of degree $r$ is an homomorphism $\phi:G\to GL_r(\mathbb{F}_q)$. \item The \emph{group algebra} $\mathbb{F}_q[G]$ of $G$ over a field $\mathbb{F}_q$ is the algebra over $\mathbb{F}_q$ consisting of all possible formal linear combinations $\sum\limits_{i=1}^T\alpha_ig_i,$ $\alpha_i\in\mathbb{F}_q$. The algebraic operations in $\mathbb{F}_q[G]$ are defined by: \begin{align*} \sum\limits_{i}\alpha_ig_i+\sum\limits_{i}\beta_ig_i &= \sum\limits_{i}(\alpha_i+\beta_i)g_i\,; \\ \left(\sum\limits_{i}\alpha_ig_i\right) \left(\sum\limits_{i}\beta_ig_i\right) &= \sum\limits_{i,j}(\alpha_i\beta_j)(g_ig_j)\,;\\ \lambda\left(\sum\limits_{i}\alpha_ig_i\right) &= \sum\limits_{i}(\lambda\alpha_i)g_i,\quad \lambda\in\mathbb{F}_q\,. \end{align*} \item A \emph{left (right) ideal} in the group algebra $\mathbb{F}_q[G]$ is an $\mathbb{F}_q$-linear subspace of $\mathbb{F}_q[G]$ that is closed under left (right) multiplications by elements of $\mathbb{F}_q[G]$. \item A \emph{left $\mathbb{F}_q[G]$-module} is an $\mathbb{F}_q$-linear space on which $\mathbb{F}_q[G]$ acts by left multiplication in such a way that for any $m_1,m_2\in M$ and any $\alpha,\beta\in\mathbb{F}_q[G]$: \begin{align*} \alpha(m_1+m_2) &=\alpha m_1 +\alpha m_2\,; \\ (\alpha+\beta)m_1 &= \alpha m_1 + \beta m_1\,; \\ (\alpha\beta)m_1 &= \alpha(\beta m_1)\,. \end{align*} The \emph{dimension} of a module is its dimension as an $\mathbb{F}_q$-linear space. Let $M$ be an $r$-dimensional $\mathbb{F}_q[G]$-module, and let $m=\{m_1,\ldots,m_r\}$ be a basis of $M$. Multiplication by an element $g\in G$ induces a coordinate change in the basis $m$. Such a change can be expressed by an $r$ by $r$ matrix $\phi_{M,m}(g)$. The map $\phi_{M,m} : G\to GL_r(\mathbb{F}_q)$ is an $\mathbb{F}_q$-representation of $G$ of degree $r$. Two $\mathbb{F}_q[G]$-modules $M,M'$ are called \emph{isomorphic} if there exists an isomorphism between them as linear spaces that preserves multiplication by the elements of~$\mathbb{F}_q[G]$. In the matrix form this means that for an arbitrary choice of bases $m,m'$ in $M,M'$ there exists $U\in GL_r(\mathbb{F}_q)$ such that $\phi_{M,m}(g) = U^{-1} \phi_{M',m'}(g)U\ (g\in G)$. In particular, non-isomorphic modules correspond to different representations (again, for any choice of bases) and thus {\bf the number of pairwise non-isomorphic left modules of dimension $r$ does not exceed the number of different $\mathbb{F}_q$-representations $\phi:G\to GL_r(\mathbb{F}_q)$ of degree $r$}. Clearly, every left ideal of $\mathbb{F}_q[G]$ is a left $\mathbb{F}_q[G]$-module. \end{itemize} \subsection{Algebraic formulation}\label{secAlgForm} Let $A=\mathbb{F}_q[G]$. For $\alpha\in A$, let $A\alpha$ denote the \emph{principal left ideal} generated by $\alpha$, that is, the set $\{\beta\alpha \mid \beta\in A\}$. Let ${\rm rk}\;(\alpha)=\dim\:(A\alpha)$, where $\dim\;(A\alpha)$ is the dimension of $A\alpha$ as a linear space over $\mathbb{F}_q$. Consider the \emph{regular representation} $\phi$ of $G$, $\phi:G\to GL_{|G|}(\mathbb{F}_q)$, defined by \begin{equation} (\phi(g))_{g_1,g_2}= \begin{cases} 1, & g_1g_2^{-1}=g, \\ 0, & \mbox{otherwise.} \end{cases} \end{equation} Extend $\phi$ to $A$ by linearity. Note that $\phi$ is an injective algebra homomorphism and that the image of $\phi$ is the $\mathbb{F}_q$-algebra $R$ of all matrices that respect $G$. Observe that for any $M\in R$, \begin{equation}\label{rkDim} \rm{rk }\ M = \dim\;\{M^\prime M\ |\ M^\prime\in R\}\,. \end{equation} To verify formula~\eqref{rkDim} one needs to notice that the first row of a matrix $M^\prime \in R$ can be arbitrary. Therefore products $M^\prime M$ contain all possible linear combinations of rows of $M$ as their first row. Also notice that matrices in $R$ are uniquely determined by their first row. Formula~\eqref{rkDim} follows. Since $\phi$ is injective, it implies that $\rm{rk}(\phi(\alpha))= \rm{rk}(\alpha)\ (\alpha\in A)$, and we arrive at the following alternate definition of $N(q,G,r)$: \begin{equation} N(q,G,r)=\#\{\alpha\in A \mid {\rm rk}(\alpha)\leq r\}\,. \end{equation} \subsection{Low-dimensional principal ideals in group algebras}\label{secMath} Let $V$ be an $\mathbb{F}_q$-linear subspace of $A=\mathbb{F}_q[G]$. The \emph{left annihilator} of $V$ is defined by ${\rm Ann}_L(V)\eqdef \{\beta \in A \mid \beta V =0\}$. Similarly, the \emph{right annihilator} is ${\rm Ann}_R(V)\eqdef \{\beta \in A \mid V \beta =0\}$. Clearly, ${\rm Ann}_L(V)$ is a left ideal in $A$ and ${\rm Ann}_R(V)$ is a right ideal in $A$. Let $M$ be a left $A$-module. The \emph{kernel} of $M$ is defined by ${\rm Ker}\;(M)\eqdef \{\beta \in A \mid \beta M =0\}$. It is straightforward to verify that ${\rm Ker}\;(M)$ is a two-sided ideal that coincides with ${\rm Ann}_L(M)$ if $M$ is a left ideal in $A$. \begin{lemma}\label{numberOfModules} The number of $r$-dimensional left $A$-modules counted up to isomorphism is at most $q^{r^2 \log_2 |G|}$. \end{lemma} \begin{proof} As we remarked in \expref{Section}{subsec:algBasics}, an upper bound on the number of $\mathbb{F}_q$-representations of $G$ of degree $r$ yields an upper bound on the number of non-isomorphic $r$-dimensional $A$-modules. To bound the number of representations, let $g_1,\ldots,g_s$ be a set of generators for $G$, where $s\leq \log_2 |G|$, and note that every representation $\phi: G\to GL_r(\mathbb{F}_q)$ is uniquely specified by $s$ matrices $\phi(g_1),\ldots,\phi(g_s)$ each of size $r$ by $r$. \end{proof} Clearly, isomorphic modules have identical kernels. Now we show that the kernel of a low-dimensional module has high dimension. \begin{lemma}\label{annOfModule} Let $M$ be an $r$-dimensional left $A$-module; then the dimension of ${\rm Ker}\;(M)$ as an $\mathbb{F}_q$-linear space is at least $|G|-r^2$. \end{lemma} \begin{proof} Fix arbitrarily a basis $m=\{m_1,\ldots,m_r\}$ in $M$, consider the representation $\phi_{M,m}$ from \expref{Section}{subsec:algBasics} and extend it by linearity to an algebra homomorphism $\phi_{M,m}: A\to GL_r(\mathbb{F}_q)$ as in \expref{Section}{secAlgForm}. Then ${\rm Ker}\;(M)$ is just the kernel of $\phi_{M,m}$, and the statement follows from basic linear algebra: for any linear mapping $\phi:V\to W$ we have $\dim({\rm Ker}(\phi))\geq \dim(V)-\dim(W)$. \end{proof} \begin{lemma}\label{dimAnnSmall} Suppose $V$ is an $\mathbb{F}_q$-linear subspace of $A$; then $\dim({\rm Ann}_R(V))\leq |G|-\dim(V)$. \end{lemma} \begin{proof} Consider a bilinear map $\ell:A \otimes A\to \mathbb{F}_q$, setting $\ell(x\otimes y)$ equal to the coefficient of $1$ in the expansion of $xy$ in the group basis. Recall from basic linear algebra that given any bilinear map $\ell: U\otimes V\to \mathbb{F}_q$ we can define its \emph{rank} ${\rm rk}(\ell)$ by choosing bases $\{u_1,\ldots,u_m\}$ in $U$ and $\{v_1,\ldots,v_n\}$ in $V$, and letting ${\rm rk}(\ell)$ be the rank of the $m$ by $n$ matrix with the entries $\ell(u_i\otimes v_j)$. ${\rm rk}(\ell)$ does not depend on the choice of the bases. As a consequence, for every subspaces $U'\subseteq U,\ V'\subseteq V'$ such that $\ell(U'\otimes V')=0$ we have the inequality $\dim(U')+\dim(V')\leq m+n-{\rm rk}(\ell)$ (if an $m$ by $n$ matrix of rank $r$ contains an $m'$ by $n'$ zero submatrix, then $m'+n'\leq m+n-r$). In our situation, ${\rm rk}(\ell)=|G|$ (since in the group basis $\ell$ is represented by a permutation matrix). Also, $\ell(V\otimes {\rm Ann}_R(V))=0$. Therefore $\dim({\rm Ann}_R(V))\leq |G|-\dim(V)$ by the above. \end{proof} Our main technical result is given by \begin{theorem}\label{AUpperBound} For an arbitrary finite group $G$ and arbitrary values of $q$ and $r$ $$N(q,G,r)\leq q^{O(r^2 \log |G|)}\,.$$ \end{theorem} \begin{proof} Let $\alpha\in A$ be such that ${\rm rk}\;(\alpha)\leq r$. Consider $A\alpha$ as a left $A$-module. ${\rm Ker}\;(A\alpha)$ is the two-sided ideal $I={\rm Ann}_L(A\alpha)$. Note that $\alpha\in {\rm Ann}_R(I)$. By \expref{Lemma}{numberOfModules}, every $A$-module of dimension up to $r$ has its kernel coming from a family of at most $\sum_{i=1}^r q^{i^2 \log_2 |G|}\leq rq^{r^2 \log_2 |G|}$ ideals. Also by Lemmas~\ref{annOfModule} and~\ref{dimAnnSmall} there are at most $q^{r^2}$ elements in $\textrm{Ann}_R(I)$ for every $I$. \end{proof} Combining Equation~\eqref{respectToCC} with \expref{Theorem}{AUpperBound} we obtain our main result. \begin{theorem}\label{PIRLowerBound} Let $Q\hookrightarrow H_r$ be a bilinear group-based PIR scheme over a group $G$. Let $t=\log |G|$ denote the query length and $r$ denote the answer length; then $$ n \leq O(tr^2)\,. $$ In particular the total communication of any such scheme is $\Omega(n^{1/3})$. \end{theorem} \section{Conclusion}\label{sec:conclusion} We introduced a novel and quite natural combinatorial view of the two-server PIR problem, and obtained a lower bound for the communication complexity of PIR in the corresponding model. Stated informally, our main result is that as long as the servers represent the database by a function on a finite group, the protocol allows the user to retrieve the value of this function at any group element, and the user computes the dot product of the servers' responses to obtain the final answer, the communication complexity has to be $\Omega(n^{1/3})$. Clearly, our result admits two interpretations. On the one hand it can be viewed as a witness in support of the conjecture of Chor et al. from~\cite{CGKS} saying that their PIR protocol with $O(n^{1/3})$ communication is asymptotically optimal. On the other hand, our result exhibits a common shortcoming of the existing upper bound techniques and thus hopefully may provide some directions for future work on upper bounds. We would like to stress the first interpretation of our result by revisiting and discussing all restrictions that we introduced in order to prove the lower bound: \begin{enumerate} \item We restricted ourselves to bilinear protocols, \ie, protocols where $\mathcal U$ computes the dot product of the servers' responses. Bilinearity is a weaker assumption than linearity, therefore if one believes that linear PIRs come close to optimal, then so do bilinear ones. \item We restricted $\mathcal U$ to toss a linear number of coins in the length of his queries. Although this restriction seems a technicality, so far we have not been able to remove %% ToC edit: remove: %go around it. The only justification that we have is that it would seem quite surprising if indeed optimal PIR schemes require a very large amount of randomness. If one accepts restrictions 1-2, then a PIR protocol is just a pair $Q\hookrightarrow H_r$ such that for every $\sigma: [n]\to \mathbb{F}_q$, $Q_\sigma$ can be completed to a matrix of rank at most $r$. \item We further restrict the generalized Latin square $Q$ to be of the form $\textrm{GLS}_{G,S}$ for certain subset $S$ of a finite group $G$. Generalized Latin squares of this form constitute a rich and natural class. In other words, this restriction states that $\mathcal U$ employs a group-based secret sharing scheme to share the index $i$ between the servers. \item Our last restriction is a restriction on the structure of low rank completions of matrices $Q_\sigma$. We require that for every $\sigma$ there exists a completion $C$ of $Q_\sigma$ to a matrix of rank at most $r$ subject to the extra constraint that $C$ respects $G$. Our only evidence for this restriction is that so far we are unaware of examples of matrices $Q_\sigma$ (with parameters suitable for nontrivial PIR) whose minimal rank with respect to locations labelled by stars would be substantially smaller than the minimal rank subject to an extra constraint of respecting $G$. \end{enumerate} We proved that the communication complexity of any PIR scheme that satisfies restrictions 1-4 is $\Omega(n^{1/3})$. We leave it up to the reader to decide whether to accept each of the restrictions 1-4 as reasonable. We hope that ideas and techniques that we introduced may lead to further progress towards understanding the true communication complexity of private information retrieval. In particular the following problem is intriguing: \medskip {\bf Open problem:} Let $Q$ be a $\textrm{GLS}[n,n^\delta]$ of inverse polynomial density. Show that there exists a map $\sigma: [n]\to \mathbb{F}_q$ such that the minimal $\mathbb{F}_q$-rank of $Q_\sigma$ (with respect to locations containing stars in $Q_\sigma$) is $\omega(\log n)$. \smallskip {\bf Comment:} If true this implies an $\omega(\log n)$ lower bound for every bilinear PIR scheme, where $\mathcal U$ tosses a linear number of coins in the length of his queries. If false, this yields a PIR protocol with $c\log n$ communication. It may also be interesting to see if there is any formal connection between this problem and the well-known \emph{matrix rigidity} problem over finite fields. %%\appendix \section{Appendix: Current PIR schemes are bilinear group-based}\label{sec:knownPIRs} A number of two-server PIR schemes are known to date~\cite{CGKS,Amb,BIK,Itoh_upper,BIKR,WY}. The goal of this section is to show that all of them can be easily %% ToC edit: transformed %turned into bilinear group-based schemes. We restrict ourselves to schemes from~\cite{CGKS,BIK,WY} since every other scheme is a variant of one of them. We do not follow the chronological order in which the schemes were proposed. \medskip All known two-server PIR schemes rely on the idea of polynomial interpolation. Specifically, the retrieval of $x_i$, where the servers hold database $x$ and the user holds index $i$, is reduced to an evaluation of a cubic polynomial $F(z_1,\ldots,z_m) \in \mathbb{F}_q[z_1,\ldots,z_m]$, held by the servers, on a point $E(i)$, that the user determines based on $i$. We refer to $E(i)$ as the encoding of $i$. We use the encoding function $E:\ [n]\to \mathbb{F}_q^m$ that has been previously used in~\cite{CGKS,BIK}. Without loss of generality assume that $m^\prime=n^{1/3}$ is an integer. Consider an arbitrary bijection $\gamma: [n]\to [m^\prime]\times [m^\prime]\times [m^\prime]$. Let $e^\prime_l\in \{0,1\}^{m^\prime}$ denote a vector whose unique nonzero coordinate is $\ell$. Set $m=3m^\prime$. Put $$ E(i)=e^\prime_{\gamma(i)_1}\circ e^\prime_{\gamma(i)_2} \circ e^\prime_{\gamma(i)_3}\,. $$ Note that for every $i$, $E(i)$ has three nonzero coordinates. Define $$ F(z_1,\ldots,z_m) = \sum\limits_{i=1}^n x_i \prod\limits_{E(i)_\ell=1} z_{\ell}\,, $$ ($E(i)_l$ is the $\ell$-th coordinate of $E(i)$). Since each $E(i)$ is of weight three, the degree of $F$ is three. Each assignment $E(i)$ to the variables $z_i$ satisfies exactly one monomial in $F$ (whose coefficient is $x_i$); thus, $F(E(i))=x_i$. \subsection{The monomial distribution scheme of~\cite{BIK}} For simplicity we restrict ourselves to the case when the underlying field is $\mathbb{F}_2$. Given a cubic multivariate polynomial $F(z_1,\ldots,z_m)\in \mathbb{F}_2[z_1,\ldots,z_m]$, the servers compute a new polynomial in $2m$ variables $$ \hat F(v_1,\ldots,v_m,w_1,\ldots,w_m) = F(v_1+w_1,\ldots,v_m+w_m)\,. $$ The servers rewrite $\hat F$ as a sum of two polynomials $$ \hat F(v_1,\ldots,v_m,w_1,\ldots,w_m)= \hat F_v(v_1,\ldots,v_m,w_1,\ldots,w_m) + \hat F_w(v_1,\ldots,v_m,w_1,\ldots,w_m)\,, $$ where $\hat F_v$ is the sum of all monomials from $\hat F$ that contain at least two variables $v_j$, and $\hat F_w$ is the sum of all monomials from $\hat F$ that contain at least two variables $w_j$. Note that every monomial of $\hat F$ goes either to $\hat F_v$ or to $\hat F_w$. Servers further rewrite $\hat F_v$ and $\hat F_w$ to obtain \begin{align}\label{clComesIn} \hat F_v(v_1,\ldots,v_m,w_1,\ldots,w_m) &= F(v_1,\ldots,v_m)+\sum\limits_{\ell=1}^m c_\ell(v_1,\ldots,v_m)w_\ell\,, \\ \hat F_w(v_1,\ldots,v_m,w_1,\ldots,w_m) &= F(w_1,\ldots,w_m)+\sum\limits_{\ell=1}^m c_\ell(w_1,\ldots,w_m)v_\ell\,. \end{align} The formal description of the scheme is below. Recall that the user holds $P\in \mathbb{F}_2^m$ and wishes to retrieve $F(P)$. $$ \begin{array}{|lll|} \hline \mathcal U & : & \mbox{Represents $P$ as a random sum\ $P=V+W$ for $V,W\in\mathbb{F}_2^m.$} \\ \mathcal U\to \mathcal S_1 & : & (v_1,\ldots,v_m) \\ \mathcal U\to \mathcal S_2 & : & (w_1,\ldots,w_m) \\ \mathcal U\gets \mathcal S_1 & : & F(V),c_1(V),\ldots,c_m(V) \\ \mathcal U\gets \mathcal S_2 & : & F(W),c_1(W),\ldots,c_m(W) \\ \mathcal U & : & \mbox{Outputs } F(V)+F(W)+(V,(c_1(W),\ldots,c_m(W)))+ (W,(c_1(V),\ldots,c_m(V)))) \\ \hline \end{array} $$ Note that the protocol above is group-based, since the user can retrieve $F(P)$ for any $P\in\mathbb{F}_2^m$, and the user's secret sharing scheme is based on $\mathbb{F}_2^m$. Unfortunately, in the current form, the protocol is not bilinear. It is not hard to modify the protocol to achieve bilinearity. \smallskip {\bf Bilinear group-based form:} $$ \begin{array}{|lll|} \hline \mathcal U & : & \mbox{Represents $P$ as a random sum\ $P=V+W$ for $V,W\in\mathbb{F}_2^m.$} \\ \mathcal U\to \mathcal S_1 & : & (v_1,\ldots,v_m) \\ \mathcal U\to \mathcal S_2 & : & (w_1,\ldots,w_m) \\ \mathcal U\gets \mathcal S_1 & : & F(V)\circ 1\circ c_1(V)\circ\ldots \circ c_m(V)\circ v_1\circ\ldots\circ v_m \\ \mathcal U\gets \mathcal S_2 & : & 1\circ F(W)\circ w_1\circ\ldots\circ w_m\circ c_1(W)\circ\ldots\circ c_m(W) \\ \mathcal U & : & \mbox{Outputs the dot product of the servers' replies} \\ \hline \end{array} $$ \subsection{The combinatorial scheme of~\cite{CGKS}} Unlike the PIR schemes of~\cite{BIK,WY}, the scheme of~\cite{CGKS} does not explicitly mention low degree multivariate polynomials (or any other functions on groups), therefore it is not immediately clear how to make it bilinear group-based. However it was observed in~\cite{BIK} that in fact this scheme can also be cast in terms of polynomial evaluation. We now sketch the description of the scheme and show that it is essentially identical to the scheme of~\cite{BIK}, and therefore can be turned into a bilinear group-based form. \smallskip Recall that $m^\prime=n^{1/3}$ is an integer and $\gamma: [n]\to [m^\prime]\times [m^\prime]\times [m^\prime]$ is a bijection. For $S\subseteq [m^\prime]$ and $j\in [m^\prime]$ let $$ S\oplus j = \begin{cases} S\setminus \{j\}, & \mbox{ if } j\in S, \\ S\cup \{j\}, & \mbox{ otherwise.} \end{cases} $$ For $S_1,S_2,S_3\subseteq [m^\prime]$ let $$ T(S_1,S_2,S_3)=\sum\limits_{\{i \mid \forall j\in [3]:\ \gamma(i)_j\in S_j\}} x_i\,. $$ We say that a triple of sets $S_1^\prime,S_2^\prime,S_3^\prime \subseteq [m^\prime]$ is %% ToC edit: did you mean to emphasize this below? \emph{at distance one} from a triple $S_1,S_2,S_3$ if there exist unique $j\in [3]$ and $k\in [m^\prime]$ such that $S_t=S_t^\prime$ for $t\neq j$ and $S_j=S_j^\prime\oplus k$. Let $B(S_1,S_2,S_3)$ denote the $3m^\prime$ long vector of values of $T(S_1^\prime,S_2^\prime,S_3^\prime)$ at triples $S_1^\prime,S_2^\prime,S_3^\prime$ that are at distance one from $S_1,S_2,S_3$. Below is the formal description of the messages exchanged by the user and the servers: $$ \begin{array}{|lll|} \hline \mathcal U & : & \mbox{Picks $S_1,S_2,S_3\subseteq [m^\prime]$ at random.} \\ \mathcal U\to \mathcal S_1 & : & S_1,S_2,S_3 \\ \mathcal U\to \mathcal S_2 & : & S_1\oplus \gamma(i)_1,S_2\oplus \gamma(i)_2,S_3\oplus \gamma(i)_3 \\ \mathcal U\gets \mathcal S_1 & : & T(S_1,S_2,S_3),B(S_1,S_2,S_3) \\ \mathcal U\gets \mathcal S_2 & : & T(S_1\oplus \gamma(i)_1,S_2\oplus \gamma(i)_2,S_3\oplus \gamma(i)_3), B(S_1\oplus \gamma(i)_1,S_2\oplus \gamma(i)_2,S_3\oplus \gamma(i)_3) \\ \hline \end{array} $$ \medskip Now note that $T(S_1,S_2,S_3)=F(S_1\circ S_2\circ S_3)$. Let $P=E(i)\in\mathbb{F}_2^m$. Recall that $e_\ell\in \{0,1\}^{m}$ denotes a vector whose unique nonzero coordinate is $\ell$. We rewrite the protocol above in a different notation: $$ \begin{array}{|lll|} \hline \mathcal U & : & \mbox{Represents $P$ as a random sum\ $P=V+W$ for $V,W\in\mathbb{F}_2^m.$} \\ \mathcal U\to \mathcal S_1 & : & (v_1,\ldots,v_m) \\ \mathcal U\to \mathcal S_2 & : & (w_1,\ldots,w_m) \\ \mathcal U\gets \mathcal S_1 & : & F(V),F(V+e_1),\ldots,F(V+e_m) \\ \mathcal U\gets \mathcal S_2 & : & F(W),F(W+e_1),\ldots,F(W+e_m) \\ \hline \end{array} $$ Let $c_\ell$ denote the polynomial that has been previously used in formula~\eqref{clComesIn}. It is not hard to verify that \begin{equation}\label{clvsF} c_l(V)=F(V+e_l)+F(V)\,. \end{equation} Taking formula~\eqref{clvsF} into account we conclude that the combinatorial scheme above is essentially identical to the scheme from the previous subsection. Thus it can also be turned into a bilinear group-based form. \subsection{The partial derivatives scheme of~\cite{WY}} An important difference of this scheme is that it requires the field size to be larger than $2$. Fix two distinct nonzero elements $\lambda_1,\lambda_2 \in\mathbb{F}_q$. Let $f(\lambda) \in \mathbb{F}_q[\lambda]$ be a univariate cubic polynomial. Note that $$ f(0)=c_1f(\lambda_1)+c_2f^\prime(\lambda_1)+c_3f(\lambda_2)+ c_4f^\prime(\lambda_2)\,, $$ for some constants $c_i$ that are independent of $f$. \smallskip {\bf Protocol description :} We use standard mathematical notation $\left.\frac{\partial F}{\partial z_\ell}\right|_{W}$ to denote the value of the partial derivative of $F$ with respect to $z_\ell$ at the point $W$. Let $P=E(i)$. The user wishes to retrieve $F(P)$. $$ \begin{array}{|lll|} \hline \mathcal U & : & \mbox{Picks $V\in \mathbb{F}_q^m$ uniformly at random.} \\ \mathcal U\to \mathcal S_1 & : & P+\lambda_1 V \\ \mathcal U\to \mathcal S_2 & : & P+\lambda_2 V \\ \mathcal U\gets \mathcal S_1 & : & F(P+\lambda_1 V), \left.\frac{\partial F}{\partial z_1}\right|_{P+\lambda_1 V}, \ldots, \left.\frac{\partial F}{\partial z_m}\right|_{P+\lambda_1 V} \\ \mathcal U\gets \mathcal S_2 & : & F(P+\lambda_2 V), \left.\frac{\partial F}{\partial z_1}\right|_{P+\lambda_2 V}, \ldots, \left.\frac{\partial F}{\partial z_m}\right|_{P+\lambda_2 V} \\ \mathcal U & : & c_1F(P+\lambda_1 V) + c_2\sum\limits_{\ell=1}^{m} \left.\frac{\partial F}{\partial z_\ell}\right|_{P+\lambda_1 V}V_\ell + c_3F(P+\lambda_2 V) + c_4\sum\limits_{\ell=1}^{m} \left.\frac{\partial F}{\partial z_\ell}\right|_{P+\lambda_2 V}V_\ell \\ \hline \end{array} $$ Note that in the protocol above the servers represent the database by a function $F: \mathbb{F}_q^m\to \mathbb{F}_q$ on a group and the user can retrieve $F(P)$ for arbitrary element $P\in \mathbb{F}_q^m$. However, the protocol is not bilinear group-based, since the user does not secret share according to the group law (\ie, the difference of shares is different from $P$), and the user does not output the dot product of the servers' responses. It is not hard to modify the protocol to achieve the desired properties. \smallskip {\bf Bilinear group-based form:} $$ \begin{array}{|lcl|} \hline \mathcal U & : & \mbox{Picks $V\in \mathbb{F}_q^m$ uniformly at random.} \\ \mathcal U\to \mathcal S_1 & : & (P+\lambda_1 V)\lambda_2/(\lambda_2-\lambda_1) \\ \mathcal U\to \mathcal S_2 & : & (P+\lambda_2 V)\lambda_1/(\lambda_2-\lambda_1) \\ \mathcal U\gets \mathcal S_1 & : & F(P+\lambda_1 V)\circ c_3\circ \left[\frac{c_2}{\lambda_1-\lambda_2}\sum\limits_{\ell=1}^m \left.\frac{\partial F}{\partial z_\ell}\right|_{P+\lambda_1 V} (P+\lambda_1 V)_\ell \right]\circ \left.\frac{\partial F}{\partial z_1}\right|_{P+\lambda_1 V}\circ \ldots \circ \left.\frac{\partial F}{\partial z_m}\right|_{P+\lambda_1 V}\circ \\ & & \\ & & \circ 1 \circ \frac{-c_4}{\lambda_2-\lambda_1}(P+\lambda_1 V)_1\circ\ldots \circ \frac{-c_4}{\lambda_2-\lambda_1}(P+\lambda_1 V)_m \\ & & \\ \mathcal U\gets \mathcal S_2 & : & c_1 \circ F(P+\lambda_2 V)\circ 1 \circ \frac{-c_2}{\lambda_1-\lambda_2}(P+\lambda_2 V)_1\circ\ldots \circ \frac{-c_2}{\lambda_1-\lambda_2}(P+\lambda_2 V)_m\circ \\ & & \\ & & \circ\left[\frac{c_4}{\lambda_2-\lambda_1}\sum\limits_{\ell=1}^m \left.\frac{\partial F}{\partial z_l}\right|_{P+\lambda_2 V} (P+\lambda_2 V)_\ell \right]\circ \left.\frac{\partial F}{\partial z_1}\right|_{P+\lambda_2 V}\circ \ldots \circ \left.\frac{\partial F}{\partial z_m}\right|_{P+\lambda_2 V} \\ \mathcal U & : & \mbox{Outputs the dot product of the servers' replies} \\ \hline \end{array} $$ \section*{Acknowledgement} We would like to thank Noga Alon, Swastik Kopparty, Madhu Sudan and Avi Wigderson for many helpful discussions concerning this work. \bibliographystyle{tocplain} \bibliography{a012} %%\newpage \begin{tocauthors} \begin{tocinfo}[Sasha] Alexander A. Razborov \\ % \tocabout{}\\ Institute for Advanced Study, Steklov Mathematical Institute\\ razborov\tocat{}ias\tocdot{}edu \\ \url{http://www.mi.ras.ru/~razborov/} \end{tocinfo} \begin{tocinfo}[Sergey] Sergey Yekhanin \\ % \tocabout{}\\ Institute for Advanced Study\\ yekhanin\tocat{}ias\tocdot{}edu \\ \url{http://math.ias.edu/~yekhanin/} \end{tocinfo} \end{tocauthors} \begin{tocaboutauthors} \begin{tocabout}[Sasha] \textsc{Alexander Razborov} graduated from the \href{http://www.mi.ras.ru/}{Steklov Mathematical Institute} in 1987 under the supervision of Sergei I. Adian. The title of his dissertation was \href{http://www.mi.ras.ru/~razborov/phd.pdf}{``On systems of equations in a free group''} (in Russian). He is interested in theoretical computer science (especially complexity theory of any kind) and mathematics, more often discrete than not. \end{tocabout} \begin{tocabout}[Sergey] \textsc{Sergey Yekhanin} obtained his doctoral degree from \href{http://www.mit.edu}{MIT} in 2007 under the supervision of \href{http://people.csail.mit.edu/madhu/}{Madhu Sudan}. Sergey is currently a postdoc at the School of Mathematics of the \href{http://www.ias.edu/}{Institute for Advanced Study}. His research interests are in computational complexity theory, cryptography, and the theory of error-correcting codes. \end{tocabout} \end{tocaboutauthors} \end{document}