%% 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}
