Authors Alexander Razborov, Sergey Yekhanin,
License CC-BY-ND-2.0
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238
http://theoryofcomputing.org
An Ω(n1/3) Lower Bound for Bilinear
Group-Based Private Information Retrieval∗
Alexander A. Razborov† Sergey Yekhanin‡
Received: May 14, 2007; revised: December 19, 2007; published: December 28, 2007.
Abstract: A two-server private information retrieval (PIR) scheme allows a user U to
retrieve the i-th bit of an n-bit string x replicated on two servers while each server indi-
vidually learns no information about i. The main parameter of interest in a PIR scheme is
its communication complexity: the number of bits exchanged by the user and the servers.
Substantial effort has been invested by researchers over the last decade in the search for
efficient PIR schemes. A number of different schemes (Chor et al., 1998, Beimel et al.,
2005, Woodruff and Yekhanin, CCC’05) have been proposed; however, all of them result
in the same communication complexity of O(n1/3 ). The best known lower bound to date is
5 log n by Wehner and de Wolf (ICALP’05). The tremendous gap between upper and lower
bounds is the focus of our paper. We show an Ω(n1/3 ) lower bound in a restricted model
that nevertheless captures all known upper bound techniques.
∗ A preliminary version of this paper appeared in the proceedings of the 47th IEEE Symposium on Foundations of Computer
Science (FOCS’06) [15].
† Supported by the Charles Simonyi Endowment and NSF grant ITR-0324906.
‡ Supported by NSF grant CCR 0219218.
ACM Classification: H.3.3, F.1.3.e, F.1.2.b
AMS Classification: 68P20, 68Q17, 20C20
Key words and phrases: lower bounds, private information retrieval, secret sharing, communication
complexity, group representations, bilinear schemes
Authors retain copyright to their work and grant Theory of Computing unlimited rights
to publish the work electronically and in hard copy. Use of the work is permitted as
long as the author(s) and the journal are properly acknowledged. For the detailed
copyright statement, see http://theoryofcomputing.org/copyright.html.
c 2007 Alexander Razborov and Sergey Yekhanin DOI: 10.4086/toc.2007.v003a012
A. R AZBOROV AND S. Y EKHANIN
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’ re-
sponses 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.
1 Introduction
Private information retrieval (PIR) was introduced in a seminal paper by Chor, Goldreich, Kushilevitz,
and Sudan [5]. In such a scheme a server holds an n-bit string x representing a database, and a user
holds an index i ∈ [n]. At the end of the protocol the user should learn xi 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 [5] 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. [5] obtained a PIR protocol with O(n1/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. [5] had
communication complexity O(n1/3 ). Later Ambainis [1] suggested a scheme with O(n1/5 ) communica-
tion, and Beimel et al. [4] further reduced the communication to O(n1/5.25 ). Finally, in a recent paper
Yekhanin [21] achieved O(n1/32,582,658 ) communication, and showed that communication can be fur-
ther reduced to no(1) under a plausible number-theoretic assumption regarding the density of Mersenne
primes (see also [12]). 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 [4]
log log k
and [21] and is nO( k log k ) .
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 [14]. Later it was improved to 4.4 log n
by Kerenidis and de Wolf [13] using the results of Katz and Trevisan [11]. The current record of 5 log n
is due to Wehner and de Wolf [17]. 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 (i. e., 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 [6, 20].
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 222
L OWER B OUND FOR P RIVATE I NFORMATION R ETRIEVAL
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 communi-
cation 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 [5, 3, 19] all of them have the
same communication complexity of O(n1/3 ). Secondly, the work of [4] implies that a large improvement
in the upper bound for two-server PIR would yield better PIR protocols for all other values of k.
1.1 Our results
Our main result is an Ω(n1/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 induced universal graph for a
family of graphs with a certain property.1 This view allows us to identify two natural models of PIR,
namely, bilinear PIR, and 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 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 Ω(n1/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(n1/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
Fq [G]. Our main technical result is an upper bound for this quantity obtained by an argument relying on
the representation theory of finite groups.
1.2 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 [10, 7, 17]. In par-
ticular, Itoh [10] 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. [7] introduced the notion of linear PIR protocols, i. e., protocols where the servers are
restricted to return linear combinations of the database bits to the user, and also the notion of probe
complexity, i. e., the maximal number of bits the user needs to read from the servers’ answers in order
to compute xi . 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
1 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 F if every graph F ∈ F is an induced subgraph of G.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 223
A. R AZBOROV AND S. Y EKHANIN
by Wehner and de Wolf [17] who showed that the restriction of linearity can in fact be dropped. See
also [2].
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 [10], and do not restrict the user to read only a small number of bits from servers’ answers as
in [7]. We show that our bilinearity restriction is weaker than the linearity restriction of [7], 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).
1.3 Outline
In Section 2 we introduce our notation and provide some necessary definitions. In Section 3 we present
our combinatorial interpretation of two-server PIR, and identify the models of bilinear PIR and bilinear
group-based PIR. Section 4 contains the main technical contribution of the paper. We introduce the
necessary algebraic tools and establish an Ω(n1/3 ) lower bound for communication complexity of any
bilinear group-based PIR scheme. In Section 5 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.
2 Preliminaries
def
Let [s] = {1, . . . , s}. We assume that q is a prime power and use the notation Fq 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 Fq . Throughout log stands for the log
base q. The notation a ◦ b stands for concatenation of strings a and b.
A two-server PIR scheme involves two servers, S1 and S2 , each holding the same n-bit string x (the
database), and a user U who knows n and wishes to retrieve some bit xi , i ∈ [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 [4].
Definition 2.1. A two-server PIR protocol is a triplet of non-uniform algorithms P = (Q, A, C). We
assume that each algorithm is given n as advice. At the beginning of the protocol, the user U tosses
random coins and obtains a random string r. Next, U invokes Q(i, r) to generate a pair of queries
(que1 , que2 ). U sends que1 to S1 and que2 to S2 . Each server S j responds with an answer ans j =
A( j, x, que j ). (We assume without loss of generality that servers are deterministic.) Finally, U computes
its output by applying the reconstruction algorithm C(ans1 , ans2 , i, r). A protocol as above should satisfy
the following requirements:
• Correctness : For any n, x ∈ [q]n , and i ∈ [n], the user outputs the correct value of xi with proba-
bility 1 (where the probability is over the random strings r).
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 224
L OWER B OUND FOR P RIVATE I NFORMATION R ETRIEVAL
• 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 ∈ [n].
The communication complexity of a PIR protocol 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 ∈ [q]n , i ∈ [n],
and random inputs.
Definition 2.2. [7] A linear PIR scheme is a PIR scheme where the answer function 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.
3 A combinatorial view of two-server PIR
Definition 3.1. A generalized Latin square (GLS[n, T ] for short) is a square matrix Q of size T by T
over an alphabet [n] ∪ {∗} such that:
• For every i ∈ [n] and j ∈ [T ], there exists a unique k ∈ [T ] such that Q jk = i;
• For every i ∈ [n] and j ∈ [T ], there exists a unique k ∈ [T ] such that Qk j = i.
In particular, every row (or column) of a GLS[n, T ] contains precisely (T − n) stars. We call the
ratio n/T the 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 GLS[n, T ], and let σ : [n] → [q] be an arbitrary map. By Qσ we denote the matrix of size
T by T over the alphabet [q] ∪ {∗} that is obtained from Q by replacing every non-star entry i in Q by
σ (i). We say that a matrix C ∈ [q]T ×T is a completion of Qσ if Ci j = (Qσ )i j whenever (Qσ )i j ∈ [q].
For matrices C ∈ [q]c×c and A ∈ [q]`×` we say that C reduces to A if there exist two maps π1 : [c] → [`]
and π2 : [c] → [`] such that for any j, k ∈ [c], C jk = Aπ1 ( j),π2 (k) . Note that we do not impose any restrictions
on the maps π1 and π2 ; in particular c can be larger than `.
Definition 3.2. Let Q be a GLS[n, T ] and A ∈ [q]`×` . We say that A covers Q (notation Q ,→ A) if, for
every σ : [n] → [q], there exists a completion C of Qσ such that C reduces to A.
Theorem 3.3. The following two implications are valid:
• A pair Q ,→ A, where Q is a GLS[n, T ] and A ∈ [q]`×` , yields a two-server PIR protocol with
communication log T from U to each S j and communication log ` from the S j ’s back to U.
• A two-server PIR protocol with queries of length t(n) and answers of length
a(n), where the user
tosses at most τ(n) random coins, yields a pair Q ,→ A, where Q is a GLS n, nqt(n)+τ(n) and A is
a q-ary square matrix of size nqt(n)+a(n) .
Proof. We start with the first part. We assume that the matrix A is known to all parties U, S1 , and S2 .
At the preprocessing stage, the servers use the database x ∈ [q]n to define the map σ : [n] → [q], setting
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 225
A. R AZBOROV AND S. Y EKHANIN
def
σ (i) = xi . Also, they find an appropriate completion C, and fix maps π1 : [T ] → [`] and π2 : [T ] → [`],
such that for all j, k: C jk = Aπ1 ( j),π2 (k) . Next, the following protocol is executed.
U : Picks a location j, k in Q such that
Q jk = i uniformly at random.
U → S1 : j
U → S2 : k
U ← S1 : π1 ( j)
U ← S2 : π2 (k)
U : Outputs Aπ1 ( j),π2 (k) .
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 `).
Now we proceed to the second part. Consider a two-server protocol P = (Q, A, C). First we show
that one can modify P to obtain a new PIR protocol P0 = (Q0 , A0 , C0 ) such that C0 depends only on ans01
and ans02 , but not on i or r. The transformation is simple:
• First Q0 obtains a random string r and invokes Q(i, r) to generate (que1 , que2 ). Next Q0 tosses
log n extra random coins to represent i as a random sum i = i1 + i2 mod n, sets que01 = que1 ◦ i1 ,
que02 = que2 ◦ i2 , and sends que01 to S1 and que02 to S2 .
• For j = 1, 2, A0 extracts que j from que0j , runs A on ( j, x, que j ), and returns ans j ◦ que0j .
• Finally, C0 extracts que1 , que2 , ans1 , ans2 , and i from ans01 and ans02 , and performs a brute force
search over all possible random coin tosses of Q to find some random input r0 such that Q(i, r0 ) =
(que1 , que2 ). C0 runs C on (ans1 , ans2 , i, r0 ) and returns the answer (if no such r0 exists, C0 an-
swers arbitrarily). Note that the string r0 may in fact be different from the string r; however the
correctness property of P implies that even in this case C0 outputs the right value.
Now consider the protocol P0 . Let Q0j denote the range of queries to server j, and A0j denote the
range of answers from server j. The variable que0j ranges over Q0j , and the variable ans0j ranges over
A0j . Let R(que0j , i) denote the set of random strings r that lead to the query que0j to server j on input i.
Formally,
R(que01 , i) = r ∈ [q]τ(n) | ∃ que02 : Q(i, r) = (que01 , que02 ) ,
R(que02 , i) = r ∈ [q]τ(n) | ∃ que01 : Q(i, r) = (que01 , que02 ) .
Note that the privacy property of the protocol P0 means that the cardinalities of R(que0j , i) are independent
of i. We denote these cardinalities by r(que0j ). It is easy to see that r(que0j ) is always an integer between
1 and qτ(n) . Now we are ready to define the matrices Q and A.
Rows of Q are labelled by pairs (que01 , s1 ), where s1 ∈ [r(que01 )]. Columns of Q are labelled by
pairs (que02 , s2 ), where s2 ∈ [r(que02 )]. We set Q(que01 ,s1 ),(que02 ,s2 ) = i if there exists a string r ∈ R(que01 , i) ∩
R(que02 , i) such that r is the string number s1 in R(que01 , i) and the string number s2 in R(que02 , i) with
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 226
L OWER B OUND FOR P RIVATE I NFORMATION R ETRIEVAL
respect to lexicographic ordering of these sets; otherwise we set Q(que01 ,s1 ),(que02 ,s2 ) = ∗. The definition
of the protocol P0 easily implies that for every pair (que01 , que02 ) there can be at most one i such that
R(que01 , i) ∩ R(que02 , i) 6= 0, / therefore Q is correctly defined.
Consider now an arbitrary pair (i, (que01 , s1 )), where s1 ∈ [r(que01 )]. Let r be the random string
number s1 in lexicographic ordering of R(que01 , i). Let Q0 (i, r) = (que01 , que02 ), and let s2 be the number
of r in lexicographic ordering of R(que02 , i). The column of Q labelled (que02 , s2 ) is the unique column
such that Q(que01 ,s1 ),(que02 ,s2 ) = 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 ans01 , similarly
columns of A are labelled by possible values of ans02 . We set Aans01 ,ans02 = C0 (ans01 , ans02 ). 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 ,→ A. Given a map σ : [n] → [q] we consider the database x, where
xi = σ (i). We use the protocol P0 to define maps π1 from the row set of Q to the row set of A, and π2
from the column set of Q to the column set of A. We set π1 (que01 , s1 ) = A0 (1, x, que01 ) and π2 (que02 , s2 ) =
A0 (2, x, que02 ). The correctness property of P0 implies that the maps π1 , π2 reduce a certain completion
of Qσ to A.
The theorem above represents our combinatorial view of two-server PIR protocols. A PIR protocol
is just a pair Q ,→ 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.
3.1 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.
Definition 3.4. A Hadamard matrix Hm is a qm by qm matrix where rows and columns are labelled
by elements of Fm
q and matrix cells contain the dot products of corresponding labels. I.e. (Hm )v1 ,v2 =
(v1 , v2 ).
Lemma 3.5. Let M be a square matrix with entries from Fq ; then M reduces to a Hadamard matrix Hm
if and only if the rank of M is at most m.
Proof. Clearly, the rank of Hm is m; therefore the rank of any matrix that reduces to Hm is at most that
large. To prove the converse, observe that M can be written as a sum of m matrices M = M 1 + . . . + M m ,
where each M j is of rank at most one. Let t be the dimension of M. For every i ∈ [m] set the i-th
coordinate of m long vectors v1 , . . . , vt u1 , . . . , ut so that vij uki = M ijk . Now the maps π1 : [t] → [qm ],
π2 : [t] → [qm ] defined by π1 ( j) = v j , π2 (k) = uk embed M into Hm .
The above lemma is important since it allows us to reduce the proof that Q ,→ Hm for some gen-
eralized Latin square Q to showing that for every σ : [n] → Fq , Qσ can be completed to a low rank
matrix.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 227
A. R AZBOROV AND S. Y EKHANIN
Definition 3.6. We say that a two-server PIR scheme Q ,→ A is bilinear if A = Hm for some value of m.
Another way to formulate the above definition is to say that a PIR scheme is bilinear if U computes
the dot product of the servers’ answers to obtain the value of xi . The next lemma shows that the restriction
of bilinearity is weaker than that of linearity.
Lemma 3.7. Every linear PIR protocol can be turned into a bilinear PIR protocol with the same asymp-
totic communication complexity.
Proof. In a linear PIR protocol the user receives two strings ans1 , ans2 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 ans1 and ans2 . The final output of U is a sum
of two dot products (c1 , ans1 ) + (c2 , ans2 ) = xi , for some vectors c1 and c2 that are computed by the user
along with queries (que1 , que2 ). The idea behind turning a linear protocol into a bilinear one is simple.
After generating (que1 , que2 ) along with c1 and c2 , U represents c1 and c2 as sums of random strings
c1 = c11 + c12 , c2 = c21 + c22 , and sends que1 ◦ c11 ◦ c21 to S1 and que2 ◦ c12 ◦ c22 to S2 . Each server
responds with a string of 2 + |ans1 | + |ans2 | bits. S1 sends back 1 ◦ (c11 , ans1 ) ◦ c21 ◦ ans1 . S2 sends back
(c22 , ans2 ) ◦ 1 ◦ ans2 ◦ c12 . It is easy to see that the dot product of the servers’ answers yields xi , and that
the procedure above increases the overall communication only by a constant factor.
3.2 Group-based PIR
Finite groups are a natural source of generalized Latin squares. Let G = {g1 , . . . , gT } be a finite group
of size T . Let S = {s1 , . . . , sn } ⊆ G be an ordered subset of G of size n. A generalized Latin square
QG,S is a T by T square matrix whose rows and columns are labelled by elements of G, and Qg1 ,g2 = i if
g1 g−12 = si , while all other locations contain stars.
When a PIR protocol Q ,→ A uses a generalized Latin square QG,S we say that it employs a group-
based secret sharing scheme. Essentially, this means that given an index i, U maps it to a group element
si , represents si as a random product in the group si = g1 g−1
2 , and sends g j to S j .
The notion of a group-based PIR protocol (for which we later prove a lower bound) is more restric-
tive. Let M ∈ [q]T ×T and G be finite group. Assume that the rows and columns of M are labelled by
g1 , . . . , gT . We say that M respects G if, for every g1 , g2 , g3 , g4 ∈ G such that g1 g−1 −1
2 = g3 g4 , we have
Mg1 ,g2 = Mg3 ,g4 .
Definition 3.8. We say that a PIR protocol Q ,→ A is group-based if it employs a secret sharing scheme
based on some group G and, for every σ : [n] → Fq , there exists a completion C such that C reduces to
A and C respects G.
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.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 228
L OWER B OUND FOR P RIVATE I NFORMATION R ETRIEVAL
4 Communication complexity of bilinear group-based PIR
Consider a bilinear group-based PIR scheme Q ,→ Hr 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 Fq that respect
G (for some fixed labelling {g1 , . . . , gT } or rows and columns) and have rank at most r. It is easy to see
that
qn ≤ N(q, G, r) , (4.1)
since by Lemma 3.5 every database yields such a matrix and distinct databases yield distinct matrices.
In Section 4.2 we obtain an equivalent algebraic definition for N(q, G, r), and in Section 4.3 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 Ω(n1/3 ) lower bound for the total communication of any bilinear group-based
PIR scheme.
4.1 Algebraic preliminaries
Our proof relies on some basic notions of the representation theory of finite groups. The standard
references for this subject are [18], [8]. For a general algebra background see [16].
Let G = {g1 , . . . , gT } be a finite (not necessarily abelian) group. The general linear group GLr (Fq )
is the multiplicative group of all non-singular r by r matrices over Fq .
• An Fq -representation of G of degree r is an homomorphism φ : G → GLr (Fq ).
• The group algebra Fq [G] of G over a field Fq is the algebra over Fq consisting of all possible
T
formal linear combinations ∑ αi gi , αi ∈ Fq . The algebraic operations in Fq [G] are defined by:
i=1
∑ αi gi + ∑ βi gi = ∑(αi + βi )gi ;
i i i
! !
∑ αi gi ∑ βi gi = ∑(αi β j )(gi g j ) ;
i i i, j
!
λ ∑ αi gi = ∑(λ αi )gi , λ ∈ Fq .
i i
• A left (right) ideal in the group algebra Fq [G] is an Fq -linear subspace of Fq [G] that is closed
under left (right) multiplications by elements of Fq [G].
• A left Fq [G]-module is an Fq -linear space on which Fq [G] acts by left multiplication in such a way
that for any m1 , m2 ∈ M and any α, β ∈ Fq [G]:
α(m1 + m2 ) = αm1 + αm2 ;
(α + β )m1 = αm1 + β m1 ;
(αβ )m1 = α(β m1 ) .
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 229
A. R AZBOROV AND S. Y EKHANIN
The dimension of a module is its dimension as an Fq -linear space. Let M be an r-dimensional
Fq [G]-module, and let m = {m1 , . . . , mr } be a basis of M. Multiplication by an element g ∈ G
induces a coordinate change in the basis m. Such a change can be expressed by an r by r ma-
trix φM,m (g). The map φM,m : G → GLr (Fq ) is an Fq -representation of G of degree r. Two
Fq [G]-modules M, M 0 are called isomorphic if there exists an isomorphism between them as
linear spaces that preserves multiplication by the elements of Fq [G]. In the matrix form this
means that for an arbitrary choice of bases m, m0 in M, M 0 there exists U ∈ GLr (Fq ) such that
φM,m (g) = U −1 φM0 ,m0 (g)U (g ∈ G). In particular, non-isomorphic modules correspond to different
representations (again, for any choice of bases) and thus the number of pairwise non-isomorphic
left modules of dimension r does not exceed the number of different Fq -representations
φ : G → GLr (Fq ) of degree r.
Clearly, every left ideal of Fq [G] is a left Fq [G]-module.
4.2 Algebraic formulation
Let A = Fq [G]. For α ∈ A, let Aα denote the principal left ideal generated by α, that is, the set {β α |
β ∈ A}. Let rk (α) = dim (Aα), where dim (Aα) is the dimension of Aα as a linear space over Fq .
Consider the regular representation φ of G, φ : G → GL|G| (Fq ), defined by
(
1, g1 g−1
2 = g,
(φ (g))g1 ,g2 = (4.2)
0, otherwise.
Extend φ to A by linearity. Note that φ is an injective algebra homomorphism and that the image of φ is
the Fq -algebra R of all matrices that respect G. Observe that for any M ∈ R,
rk M = dim {M0 M | M0 ∈ R} . (4.3)
To verify formula (4.3) one needs to notice that the first row of a matrix M 0 ∈ R can be arbitrary. There-
fore products M 0 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 (4.3) follows. Since φ is injec-
tive, it implies that rk(φ (α)) = rk(α) (α ∈ A), and we arrive at the following alternate definition of
N(q, G, r):
N(q, G, r) = #{α ∈ A | rk(α) ≤ r} . (4.4)
4.3 Low-dimensional principal ideals in group algebras
def
Let V be an Fq -linear subspace of A = Fq [G]. The left annihilator of V is defined by AnnL (V ) = {β ∈
def
A | βV = 0}. Similarly, the right annihilator is AnnR (V ) = {β ∈ A | V β = 0}. Clearly, AnnL (V ) is a
left ideal in A and AnnR (V ) is a right ideal in A. Let M be a left A-module. The kernel of M is defined
def
by Ker (M) = {β ∈ A | β M = 0}. It is straightforward to verify that Ker (M) is a two-sided ideal that
coincides with AnnL (M) if M is a left ideal in A.
2
Lemma 4.1. The number of r-dimensional left A-modules counted up to isomorphism is at most qr log2 |G| .
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 230
L OWER B OUND FOR P RIVATE I NFORMATION R ETRIEVAL
Proof. As we remarked in Section 4.1, an upper bound on the number of Fq -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 g1 , . . . , gs be a set of generators for G, where s ≤ log2 |G|,
and note that every representation φ : G → GLr (Fq ) is uniquely specified by s matrices φ (g1 ), . . . , φ (gs )
each of size r by r.
Clearly, isomorphic modules have identical kernels. Now we show that the kernel of a low-dimensional
module has high dimension.
Lemma 4.2. Let M be an r-dimensional left A-module; then the dimension of Ker (M) as an Fq -linear
space is at least |G| − r2 .
Proof. Fix arbitrarily a basis m = {m1 , . . . , mr } in M, consider the representation φM,m from Section 4.1
and extend it by linearity to an algebra homomorphism φM,m : A → GLr (Fq ) as in Section 4.2. Then
Ker (M) is just the kernel of φM,m , and the statement follows from basic linear algebra: for any linear
mapping φ : V → W we have dim(Ker(φ )) ≥ dim(V ) − dim(W ).
Lemma 4.3. Suppose V is an Fq -linear subspace of A; then dim(AnnR (V )) ≤ |G| − dim(V ).
Proof. Consider a bilinear map ` : A ⊗ A → Fq , setting `(x ⊗ 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 ` :
U ⊗V → Fq we can define its rank rk(`) by choosing bases {u1 , . . . , um } in U and {v1 , . . . , vn } in V , and
letting rk(`) be the rank of the m by n matrix with the entries `(ui ⊗ v j ). rk(`) does not depend on the
choice of the bases. As a consequence, for every subspaces U 0 ⊆ U, V 0 ⊆ V 0 such that `(U 0 ⊗ V 0 ) = 0
we have the inequality dim(U 0 ) + dim(V 0 ) ≤ m + n − rk(`) (if an m by n matrix of rank r contains an m0
by n0 zero submatrix, then m0 + n0 ≤ m + n − r).
In our situation, rk(`) = |G| (since in the group basis ` is represented by a permutation matrix). Also,
`(V ⊗ AnnR (V )) = 0. Therefore dim(AnnR (V )) ≤ |G| − dim(V ) by the above.
Our main technical result is given by
Theorem 4.4. For an arbitrary finite group G and arbitrary values of q and r
2
N(q, G, r) ≤ qO(r log |G|) .
Proof. Let α ∈ A be such that rk (α) ≤ r. Consider Aα as a left A-module. Ker (Aα) is the two-sided
ideal I = AnnL (Aα). Note that α ∈ AnnR (I). By Lemma 4.1, every A-module of dimension up to r
2 2
has its kernel coming from a family of at most ∑ri=1 qi log2 |G| ≤ rqr log2 |G| ideals. Also by Lemmas 4.2
2
and 4.3 there are at most qr elements in AnnR (I) for every I.
Combining Equation (4.1) with Theorem 4.4 we obtain our main result.
Theorem 4.5. Let Q ,→ Hr 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 ≤ O(tr2 ) .
In particular the total communication of any such scheme is Ω(n1/3 ).
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 231
A. R AZBOROV AND S. Y EKHANIN
5 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 Ω(n1/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 [5] saying that their PIR protocol with O(n1/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:
1. We restricted ourselves to bilinear protocols, i. e., protocols where 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.
2. We restricted U to toss a linear number of coins in the length of his queries. Although this restric-
tion seems a technicality, so far we have not been able to remove 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 ,→ Hr
such that for every σ : [n] → Fq , Qσ can be completed to a matrix of rank at most r.
3. We further restrict the generalized Latin square Q to be of the form GLSG,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 U employs a group-based secret sharing scheme to share
the index i between the servers.
4. Our last restriction is a restriction on the structure of low rank completions of matrices Qσ . We
require that for every σ there exists a completion C of Qσ 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σ (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.
We proved that the communication complexity of any PIR scheme that satisfies restrictions 1-4
is Ω(n1/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:
Open problem: Let Q be a GLS[n, nδ ] of inverse polynomial density. Show that there exists a map
σ : [n] → Fq such that the minimal Fq -rank of Qσ (with respect to locations containing stars in Qσ ) is
ω(log n).
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 232
L OWER B OUND FOR P RIVATE I NFORMATION R ETRIEVAL
Comment: If true this implies an ω(log n) lower bound for every bilinear PIR scheme, where 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 matrix rigidity problem over finite fields.
6 Appendix: Current PIR schemes are bilinear group-based
A number of two-server PIR schemes are known to date [5, 1, 3, 9, 4, 19]. The goal of this section is to
show that all of them can be easily transformed into bilinear group-based schemes. We restrict ourselves
to schemes from [5, 3, 19] since every other scheme is a variant of one of them. We do not follow the
chronological order in which the schemes were proposed.
All known two-server PIR schemes rely on the idea of polynomial interpolation. Specifically, the
retrieval of xi , where the servers hold database x and the user holds index i, is reduced to an evaluation
of a cubic polynomial F(z1 , . . . , zm ) ∈ Fq [z1 , . . . , zm ], 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] → Fm q that has been previously used in [5, 3]. Without loss of
generality assume that m0 = n1/3 is an integer. Consider an arbitrary bijection γ : [n] → [m0 ] × [m0 ] × [m0 ].
0
Let e0l ∈ {0, 1}m denote a vector whose unique nonzero coordinate is `. Set m = 3m0 . Put
E(i) = e0γ(i)1 ◦ e0γ(i)2 ◦ e0γ(i)3 .
Note that for every i, E(i) has three nonzero coordinates. Define
n
F(z1 , . . . , zm ) = ∑ xi ∏ z` ,
i=1 E(i)` =1
(E(i)l is the `-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 zi satisfies exactly one monomial in F (whose coefficient is xi ); thus,
F(E(i)) = xi .
6.1 The monomial distribution scheme of [3]
For simplicity we restrict ourselves to the case when the underlying field is F2 . Given a cubic multivariate
polynomial F(z1 , . . . , zm ) ∈ F2 [z1 , . . . , zm ], the servers compute a new polynomial in 2m variables
F̂(v1 , . . . , vm , w1 , . . . , wm ) = F(v1 + w1 , . . . , vm + wm ) .
The servers rewrite F̂ as a sum of two polynomials
F̂(v1 , . . . , vm , w1 , . . . , wm ) = F̂v (v1 , . . . , vm , w1 , . . . , wm ) + F̂w (v1 , . . . , vm , w1 , . . . , wm ) ,
where F̂v is the sum of all monomials from F̂ that contain at least two variables v j , and F̂w is the sum of
all monomials from F̂ that contain at least two variables w j . Note that every monomial of F̂ goes either
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 233
A. R AZBOROV AND S. Y EKHANIN
to F̂v or to F̂w . Servers further rewrite F̂v and F̂w to obtain
m
F̂v (v1 , . . . , vm , w1 , . . . , wm ) = F(v1 , . . . , vm ) + ∑ c` (v1 , . . . , vm )w` , (6.1)
`=1
m
F̂w (v1 , . . . , vm , w1 , . . . , wm ) = F(w1 , . . . , wm ) + ∑ c` (w1 , . . . , wm )v` . (6.2)
`=1
The formal description of the scheme is below. Recall that the user holds P ∈ Fm
2 and wishes to
retrieve F(P).
U : Represents P as a random sum P = V +W for V,W ∈ Fm 2.
U → S1 : (v1 , . . . , vm )
U → S2 : (w1 , . . . , wm )
U ← S1 : F(V ), c1 (V ), . . . , cm (V )
U ← S2 : F(W ), c1 (W ), . . . , cm (W )
U : Outputs F(V ) + F(W ) + (V, (c1 (W ), . . . , cm (W ))) + (W, (c1 (V ), . . . , cm (V ))))
Note that the protocol above is group-based, since the user can retrieve F(P) for any P ∈ Fm 2 , and
the user’s secret sharing scheme is based on Fm 2 . Unfortunately, in the current form, the protocol is not
bilinear. It is not hard to modify the protocol to achieve bilinearity.
Bilinear group-based form:
U : Represents P as a random sum P = V +W for V,W ∈ Fm 2.
U → S1 : (v1 , . . . , vm )
U → S2 : (w1 , . . . , wm )
U ← S1 : F(V ) ◦ 1 ◦ c1 (V ) ◦ . . . ◦ cm (V ) ◦ v1 ◦ . . . ◦ vm
U ← S2 : 1 ◦ F(W ) ◦ w1 ◦ . . . ◦ wm ◦ c1 (W ) ◦ . . . ◦ cm (W )
U : Outputs the dot product of the servers’ replies
6.2 The combinatorial scheme of [5]
Unlike the PIR schemes of [3, 19], the scheme of [5] 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 [3] 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 [3], and therefore can be turned into a bilinear group-based form.
Recall that m0 = n1/3 is an integer and γ : [n] → [m0 ] × [m0 ] × [m0 ] is a bijection. For S ⊆ [m0 ] and
j ∈ [m0 ] let (
S \ { j}, if j ∈ S,
S⊕ j =
S ∪ { j}, otherwise.
For S1 , S2 , S3 ⊆ [m0 ] let
T (S1 , S2 , S3 ) = ∑ xi .
{i|∀ j∈[3]: γ(i) j ∈S j }
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 234
L OWER B OUND FOR P RIVATE I NFORMATION R ETRIEVAL
We say that a triple of sets S10 , S20 , S30 ⊆ [m0 ] is at distance one from a triple S1 , S2 , S3 if there exist unique
j ∈ [3] and k ∈ [m0 ] such that St = St0 for t 6= j and S j = S0j ⊕ k. Let B(S1 , S2 , S3 ) denote the 3m0 long
vector of values of T (S10 , S20 , S30 ) at triples S10 , S20 , S30 that are at distance one from S1 , S2 , S3 . Below is the
formal description of the messages exchanged by the user and the servers:
U : Picks S1 , S2 , S3 ⊆ [m0 ] at random.
U → S1 : S1 , S2 , S3
U → S2 : S1 ⊕ γ(i)1 , S2 ⊕ γ(i)2 , S3 ⊕ γ(i)3
U ← S1 : T (S1 , S2 , S3 ), B(S1 , S2 , S3 )
U ← S2 : T (S1 ⊕ γ(i)1 , S2 ⊕ γ(i)2 , S3 ⊕ γ(i)3 ), B(S1 ⊕ γ(i)1 , S2 ⊕ γ(i)2 , S3 ⊕ γ(i)3 )
Now note that T (S1 , S2 , S3 ) = F(S1 ◦ S2 ◦ S3 ). Let P = E(i) ∈ Fm m
2 . Recall that e` ∈ {0, 1} denotes a
vector whose unique nonzero coordinate is `. We rewrite the protocol above in a different notation:
U : Represents P as a random sum P = V +W for V,W ∈ Fm
2.
U → S1 : (v1 , . . . , vm )
U → S2 : (w1 , . . . , wm )
U ← S1 : F(V ), F(V + e1 ), . . . , F(V + em )
U ← S2 : F(W ), F(W + e1 ), . . . , F(W + em )
Let c` denote the polynomial that has been previously used in formula (6.1). It is not hard to verify
that
cl (V ) = F(V + el ) + F(V ) . (6.3)
Taking formula (6.3) into account we conclude that the combinatorial scheme above is essentially iden-
tical to the scheme from the previous subsection. Thus it can also be turned into a bilinear group-based
form.
6.3 The partial derivatives scheme of [19]
An important difference of this scheme is that it requires the field size to be larger than 2. Fix two
distinct nonzero elements λ1 , λ2 ∈ Fq . Let f (λ ) ∈ Fq [λ ] be a univariate cubic polynomial. Note that
f (0) = c1 f (λ1 ) + c2 f 0 (λ1 ) + c3 f (λ2 ) + c4 f 0 (λ2 ) ,
for some constants ci that are independent of f .
Protocol description : We use standard mathematical notation ∂∂ zF` to denote the value of the
W
partial derivative of F with respect to z` at the point W . Let P = E(i). The user wishes to retrieve F(P).
U : Picks V ∈ Fm
q uniformly at random.
U → S1 : P + λ1V
U → S2 : P + λ2V
U ← S1 : F(P + λ1V ), ∂∂ zF1 , . . . , ∂∂zFm
P+λ1V P+λ1V
U ← S2 : F(P + λ2V ), ∂∂ zF1 , . . . , ∂∂zFm
P+λ2V P+λ2V
m m
U : c1 F(P + λ1V ) + c2 ∑ ∂ z`
∂F
V` + c3 F(P + λ2V ) + c4 ∑ ∂∂ zF` V`
`=1 P+λ1V `=1 P+λ2V
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 235
A. R AZBOROV AND S. Y EKHANIN
Note that in the protocol above the servers represent the database by a function F : Fm q → Fq on a
group and the user can retrieve F(P) for arbitrary element P ∈ Fmq . However, the protocol is not bilinear
group-based, since the user does not secret share according to the group law (i. e., 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.
Bilinear group-based form:
U : Picks V ∈ Fmq uniformly at random.
U → S1 : (P + λ1V )λ2 /(λ2 − λ1 )
U → S2 : (P + λ2V )λ1 /(λ2 −
λ1 )
m
U ← S1 : F(P + λ1V ) ◦ c3 ◦ c2
λ1 −λ2 ∑ ∂F
∂ z` P+λ V (P + λ1V )` ◦ ∂∂ zF1 ◦ . . . ◦ ∂∂zFm ◦
`=1 1 P+λ1V P+λ1V
◦1 ◦ λ−c 4
2 −λ1
(P + λ1V )1 ◦ . . . ◦ λ−c 4
2 −λ1
(P + λ1V )m
U ← S2 : c1 ◦ F(P + λ2V ) ◦ 1 ◦ λ−c 2
1 −λ2
(P + λ2V )1 ◦ . . . ◦ λ−c 2
1 −λ2
(P + λ2V )m ◦
m
◦ c4
λ2 −λ1 ∑ ∂F
∂ zl P+λ V (P + λ2V )` ◦ ∂∂ zF1 ◦ . . . ◦ ∂∂zFm
`=1 2 P+λ2V P+λ2V
U : Outputs the dot product of the servers’ replies
Acknowledgement
We would like to thank Noga Alon, Swastik Kopparty, Madhu Sudan and Avi Wigderson for many
helpful discussions concerning this work.
References
[1] * A NDRIS A MBAINIS: Upper bound on the communication complexity of private informa-
tion retrieval. In Proc. 32nd Intern. Colloquium on Automata, Languages and Programming
(ICALP’97), volume 1256 of Lecture Notes in Computer Science, pp. 401–407. Springer, 1997.
[ICALP:j210805656376051]. 1, 6
[2] * R ICHARD B EIGEL , L ANCE F ORTNOW, AND W ILLIAM G ASARCH: A tight lower bound for
restricted PIR protocols. Computational Complexity, 15:82–91, 2006. [10.1007s00037-006-0208-
3]. 1.2
[3] * A MOS B EIMEL , Y UVAL I SHAI , AND E YAL K USHILEVITZ: General constructions for
information-theoretic private information retrieval. J. Computer and System Sciences, 71:213–247,
2005. [JCSS:10.1016/j.jcss.2005.03.002]. 1, 6, 6.1, 6.2
[4] * A MOS B EIMEL , Y UVAL I SHAI, E YAL K USHILEVITZ , AND J EAN -F RANCIOS R AY-
MOND : Breaking the O n1/(2k−1) barrier for information-theoretic private information
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 236
L OWER B OUND FOR P RIVATE I NFORMATION R ETRIEVAL
retrieval. In Proc. 43rd FOCS, pp. 261–270. IEEE Computer Society Press, 2002.
[FOCS:10.1109/SFCS.2002.1181949]. 1, 2, 6
[5] * B ENNY C HOR , O DED G OLDREICH , E YAL K USHILEVITZ , AND M ADHU S UDAN: Private in-
formation retrieval. J. ACM, 45:965–981, 1998. [JACM:10.1145/293347.293350]. 1, 5, 6, 6.2
[6] * W ILLIAM G ASARCH: A survey on private information retrieval. The Bulletin of the EATCS,
82:72–107, 2004. 1
[7] * O DED G OLDREICH , H OWARD K ARLOFF , L EONARD S CHULMAN , AND L UCA T REVISAN:
Lower bounds for linear locally decodable codes and private information retrieval. In Proc. 17th
Computational Complexity Conf. (CCC’02), pp. 175–183. IEEE Computer Society Press, 2002.
[CCC:10.1109/CCC.2002.1004353]. 1.2, 2.2
[8] * I. M ARTIN I SAACS: Character theory of finite groups. Academic Press, 1976. 4.1
[9] * T OSHIYA I TOH: Efficient private information retrieval. IEICE Trans. Fund. of Electronics,
Commun. and Comp. Sci., E82-A:11–20, 1999. 6
[10] * T OSHIYA I TOH: On lower bounds for the communication complexity of private information
retrieval. IEICE Trans. Fund. of Electronics, Commun. and Comp. Sci., E82-A:157–164, 2001.
1.2
[11] * J ONATHAN K ATZ AND L UCA T REVISAN: On the efficiency of local decoding proce-
dures for error-correcting codes. In Proc. 32nd STOC, pp. 80–86. ACM Press, 2000.
[STOC:10.1145/335305.335315]. 1
[12] * K IRAN S. K EDLAYA AND S ERGEY Y EKHANIN: Locally decodable codes from nice subsets of
finite fields and prime factors of Mersenne numbers. Electronic Colloquium on Computational
Complexity (ECCC) TR07-040, 2007. [ECCC:TR07-040]. 1
[13] * I ORDANIS K ERENIDIS AND RONALD DE W OLF: Exponential lower bound for 2-query locally
decodable codes via a quantum argument. J. of Computer and System Sciences, 69:395–420, 2004.
[JCSS:10.1016/j.jcss.2004.04.007]. 1
[14] * E RAN M ANN: Private access to distributed information. Master’s thesis, Technion - Israel Insti-
tute of Technology, Haifa, 1998. 1
[15] * A LEXANDER R AZBOROV AND S ERGEY Y EKHANIN: An Ω(n1/3 ) lower bound for bilinear
group based private information retrieval. In Proc. 47th FOCS, pp. 739–748. IEEE Computer
Society Press, 2006. [FOCS:10.1109/FOCS.2006.10]. ∗
[16] * B. L. VAN DER WAERDEN: Algebra. Springer, 2003. 4.1
[17] * S TEPHANIE W EHNER AND RONALD DE W OLF: Improved lower bounds for locally decodable
codes and private information retrieval. In Proc. 32nd Intern. Colloquium on Automata, Languages
and Programming (ICALP’05), volume 3580 of Lecture Notes in Computer Science, pp. 1424–
1436. Springer, 2005. [ICALP:1utwmhj4me3lr582]. 1, 1.2
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 237
A. R AZBOROV AND S. Y EKHANIN
[18] * S TEVEN H. W EINTRAUB: Representation theory of finite groups: algebra and arithmetic. vol-
ume 59 of Graduate Studies in Mathematics. AMS, 2003. 4.1
[19] * DAVID W OODRUFF AND S ERGEY Y EKHANIN: A geometric approach to information-theoretic
private information retrieval. In Proc. 20th IEEE Computational Complexity Conf. (CCC’05), pp.
275–284. IEEE Computer Society Press, 2005. [CCC:10.1109/CCC.2005.2]. 1, 6, 6.2, 6.3
[20] * S ERGEY Y EKHANIN: Locally decodable codes and private information retrieval schemes. PhD
thesis, Massachusetts Institute of Technology, 2007. 1
[21] * S ERGEY Y EKHANIN: Towards 3-query locally decodable codes of subexponential length. In
Proc. 39th STOC, pp. 266–274. ACM Press, 2007. [STOC:10.1145/1250790.1250830]. 1
AUTHORS
Alexander A. Razborov
Institute for Advanced Study, Steklov Mathematical Institute
razborov ias edu
http://www.mi.ras.ru/~razborov/
Sergey Yekhanin
Institute for Advanced Study
yekhanin ias edu
http://math.ias.edu/~yekhanin/
ABOUT THE AUTHORS
A LEXANDER R AZBOROV graduated from the Steklov Mathematical Institute in 1987 under
the supervision of Sergei I. Adian. The title of his dissertation was “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.
S ERGEY Y EKHANIN obtained his doctoral degree from MIT in 2007 under the supervision
of Madhu Sudan. Sergey is currently a postdoc at the School of Mathematics of the
Institute for Advanced Study. His research interests are in computational complexity
theory, cryptography, and the theory of error-correcting codes.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 221–238 238