Theory of Computing, Volume 3 (2007), pp. 221–238 http://theoryofcomputing.org

An Ω(n^{1/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 𝒰 to retrieve the i-th bit of an n-bit string x replicated on two servers while each server individually learns no information about i. The main parameter of interest in a PIR scheme is its communication complexity: the number of bits exchanged by the user and the servers. Substantial effort has been invested by researchers over the last decade in the search for efficient PIR schemes. A number of different schemes (Chor et al., 1998, Beimel et al., 2005, Woodruff and Yekhanin, CCC’05) have been proposed; however, all of them result in the same communication complexity of O(n^{1/3}). The best known lower bound to date is 5logn by Wehner and de Wolf (ICALP’05). The tremendous gap between upper and lower bounds is the focus of our paper. We show an Ω(n^{1/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 papers and grant “Theory of Computing” unlimited rights to publish the paper electronically and in hard copy. Use of the article 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.

\begin{matrix}c \\ ◯ \end{matrix} 2007 Alexander Razborov and Sergey Yekhanin

A. Razborov and S. Yekhanin

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.

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 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 logn + 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(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. [5] had communication complexity O(n^{1/3}). Later Ambainis [1] suggested a scheme with O(n^{1/5}) communication, and Beimel et al. [4] further reduced the communication to O(n^{1/5.25}). Finally, in a recent paper Yekhanin [21] 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 [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] and [21] and is n^{O(\frac{loglogk}{klogk})}.

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 4logn is due to Mann [14]. Later it was improved to 4.4logn by Kerenidis and de Wolf [13] using the results of Katz and Trevisan [11]. The current record of 5logn 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].

Lower Bound for Private Information Retrieval

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 [5, 3, 19] all of them have the same communication complexity of O(n^{1/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 Ω(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 twoserver 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 Ω(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 𝔽_{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.

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 particular, 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 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 [17] who showed that the restriction of linearity can in fact be dropped. See also [2].

1We 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 ℱ if every graph F ∈ ℱ is an induced subgraph of G.

Theory of Computing, Volume 3 (2007), pp. 221–238 223

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 Ω(n^{1/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

Let [s] =^{def}{1,...,s}. We assume that q is a prime power and use the notation 𝔽_{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 𝔽_{q}. 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, 𝒮_{1} and 𝒮_{2}, each holding the same n-bit string x (the database), and a user 𝒰 who knows n and wishes to retrieve some bit x_{i}, 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 𝒫 = (𝒬,𝒜,𝒞). We assume that each algorithm is given n as advice. At the beginning of the protocol, the user 𝒰 tosses random coins and obtains a random string r. Next, 𝒰 invokes 𝒬(i,r) to generate a pair of queries (que_{1},que_{2}). 𝒰 sends que_{1} to 𝒮_{1} and que_{2} to 𝒮_{2}. Each server 𝒮_{j} responds with an answer ans_{j} = 𝒜(j,x,que_{j}). (We assume without loss of generality that servers are deterministic.) Finally, 𝒰 computes its output by applying the reconstruction algorithm 𝒞(ans_{1},ans_{2},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 x_{i} with probability 1 (where the probability is over the random strings r).

• 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 𝒫 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 𝒜(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 Q_{kj} = 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 C_{ij} = (Q_{σ})_{ij} whenever (Q_{σ})_{ij} ∈ [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 logT from 𝒰 to each 𝒮_{j} and communication logℓ from the 𝒮_{j}’s back to 𝒰.

• 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,nq^{t(n)+τ(n)}]and A is a q-ary square matrix of size nq^{t(n)+a(n)}.

Proof. We start with the first part. We assume that the matrix A is known to all parties 𝒰, 𝒮_{1}, and 𝒮_{2}. At the preprocessing stage, the servers use the database x ∈ [q]^{n} to define the map σ : [n] → [q], setting σ(i) =^{def}x_{i}. 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.

𝒰 : Picks a location j,k in Q such that

Q_{jk} = i uniformly at random.

𝒰 → 𝒮_{1} : j
𝒰 → 𝒮_{2} : k
𝒰 ← 𝒮_{1} : π_{1}(j)
𝒰 ← 𝒮_{2} : π_{2}(k)
𝒰  : 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(logT + logℓ).

Now we proceed to the second part. Consider a two-server protocol 𝒫 = (𝒬,𝒜,𝒞). First we show that one can modify 𝒫 to obtain a new PIR protocol 𝒫′= (𝒬′,𝒜′,𝒞′) such that 𝒞′depends only on ans′_{1} and ans′_{2}, but not on i or r. The transformation is simple:

• First 𝒬′ obtains a random string r and invokes 𝒬(i,r) to generate (que_{1},que_{2}). Next 𝒬′ tosses logn extra random coins to represent i as a random sum i = i_{1}+ i_{2} modn, sets que′_{1} = que_{1}∘ i_{1}, que′_{2} = que_{2}∘ i_{2}, and sends que′_{1} to 𝒮_{1} and que′_{2} to 𝒮_{2}.

• For j = 1,2, 𝒜′extracts que_{j} from que′_{j}, runs 𝒜 on (j,x,que_{j}), and returns ans_{j} ∘ que′_{j}.

• Finally, 𝒞′ extracts que_{1},que_{2},ans_{1},ans_{2}, and i from ans′_{1} and ans′_{2}, and performs a brute force search over all possible random coin tosses of 𝒬 to find some random input r′such that 𝒬(i,r′) = (que_{1},que_{2}). 𝒞′ runs 𝒞 on (ans_{1},ans_{2},i,r′) and returns the answer (if no such r′ exists, 𝒞′ answers arbitrarily). Note that the string r′may in fact be different from the string r; however the correctness property of 𝒫 implies that even in this case 𝒞′outputs the right value.

Now consider the protocol 𝒫′. Let Q′_{j} denote the range of queries to server j, and A′_{j} denote the range of answers from server j. The variable que′_{j} ranges over Q′_{j}, and the variable ans′_{j} ranges over A′_{j}. Let R(que′_{j},i) denote the set of random strings r that lead to the query que′_{j} to server j on input i. Formally,

R(que′_{1},i)= {r ∈ [q]^{τ(n)}| ∃ que′_{2} : Q(i,r) = (que′_{1},que′_{2})},
R(que′_{2},i)= {r ∈ [q]^{τ(n)}| ∃ que′_{1} : Q(i,r) = (que′_{1},que′_{2})}.

Note that the privacy property of the protocol 𝒫′means that the cardinalities of R(que′_{j},i) are independent of i. We denote these cardinalities by r(que′_{j}). It is easy to see that r(que′_{j}) 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 (que′_{1},s_{1}), where s_{1} ∈ [r(que′_{1})]. Columns of Q are labelled by pairs (que′_{2},s_{2}), where s_{2} ∈ [r(que′_{2})]. We set Q_{(que′_{1},s_{1}),(que′_{2},s_{2})} = i if there exists a string r ∈ R(que′_{1},i) ∩ R(que′_{2},i) such that r is the string number s_{1} in R(que′_{1},i) and the string number s_{2} in R(que′_{2},i) with respect to lexicographic ordering of these sets; otherwise we set Q_{(que′_{1},s_{1}),(que′_{2},s_{2})} = ∗. The definition of the protocol 𝒫′ easily implies that for every pair (que′_{1},que′_{2}) there can be at most one i such that R(que′_{1},i) ∩ R(que′_{2},i) ≠ ∅, therefore Q is correctly defined.

Consider now an arbitrary pair (i,(que′_{1},s_{1})), where s_{1} ∈ [r(que′_{1})]. Let r be the random string number s_{1} in lexicographic ordering of R(que′_{1},i). Let 𝒬′(i,r) = (que′_{1},que′_{2}), and let s_{2} be the number of r in lexicographic ordering of R(que′_{2},i). The column of Q labelled (que′_{2},s_{2}) is the unique column such that Q_{(que′_{1},s_{1}),(que′_{2},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}, similarly columns of A are labelled by possible values of ans′_{2}. We set A_{ans′_{1},ans′_{2}} = 𝒞′(ans′_{1},ans′_{2}). 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 x_{i} = σ(i). We use the protocol 𝒫′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}(que′_{1},s_{1}) = 𝒜′(1,x,que′_{1}) and π_{2}(que′_{2},s_{2}) = 𝒜′(2,x,que′_{2}). The correctness property of 𝒫′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 H_{m} is a q^{m} by q^{m} matrix where rows and columns are labelled by elements of 𝔽_{q}^{m} and matrix cells contain the dot products of corresponding labels. I.e. (H_{m})_{v_{1},v_{2}} = (v_{1},v_{2}).

Lemma 3.5. Let M be a square matrix with entries from 𝔽_{q}; then M reduces to a Hadamard matrix H_{m} if and only if the rank of M is at most m.

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}+ ...+ 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 v^{1},...,v^{t} u^{1},...,u^{t} so that v_{i}^{j}u_{i}^{k} = M_{jk}^{i}. Now the maps π_{1} : [t] → [q^{m}], π_{2} : [t] → [q^{m}] defined by π_{1}(j) = v^{j}, π_{2}(k) = u^{k} embed M into H_{m}.

The above lemma is important since it allows us to reduce the proof that Q ↪ H_{m} for some generalized Latin square Q to showing that for every σ : [n] → 𝔽_{q}, Q_{σ} can be completed to a low rank matrix.

Definition 3.6. We say that a two-server PIR scheme Q ↪ A is bilinear if A = H_{m} for some value of m.

Another way to formulate the above definition is to say that a PIR scheme is bilinear if 𝒰 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.

Lemma 3.7. Every linear PIR protocol can be turned into a bilinear PIR protocol with the same asymptotic communication complexity.

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 𝒰 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}, 𝒰 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} ∘ c_{11} ∘ c_{21} to 𝒮_{1} and que_{2} ∘ c_{12} ∘ c_{22} to 𝒮_{2}. Each server responds with a string of 2 + |ans_{1}| + |ans_{2}| bits. 𝒮_{1} sends back 1 ∘ (c_{11},ans_{1}) ∘ c_{21}∘ ans_{1}. 𝒮_{2} sends back (c_{22},ans_{2}) ∘ 1 ∘ ans_{2}∘ 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.

3.2 Group-based PIR

Finite groups are a natural source of generalized Latin squares. Let G = {g_{1},...,g_{T}} be a finite group of size T. Let S = {s_{1},...,s_{n}} ⊆ 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_{1}g_{2}^{−1} = s_{i}, while all other locations contain stars.

When a PIR protocol Q ↪ A uses a generalized Latin square Q_{G,S} we say that it employs a groupbased secret sharing scheme. Essentially, this means that given an index i, 𝒰 maps it to a group element s_{i}, represents s_{i} as a random product in the group s_{i} = g_{1}g_{2}^{−1} , and sends g_{j} to 𝒮_{j}.

The notion of a group-based PIR protocol (for which we later prove a lower bound) is more restrictive. Let M ∈ [q]^{T ×T} and G be finite group. Assume that the rows and columns of M are labelled by g_{1},...,g_{T}. We say that M respects G if, for every g_{1},g_{2},g_{3},g_{4} ∈ G such that g_{1}g_{2}^{−1} = g_{3}g_{4}^{−1} , we have M_{g_{1},g_{2}} = M_{g_{3},g_{4}}.

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] → 𝔽_{q}, 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.

4 Communication complexity of bilinear group-based PIR

Consider a bilinear group-based PIR scheme Q ↪ 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 𝔽_{q} that respect G (for some fixed labelling {g_{1},...,g_{T}} or rows and columns) and have rank at most r. It is easy to see that

q^{n} ≤ 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 Ω(n^{1/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 = {g_{1},...,g_{T}} be a finite (not necessarily abelian) group. The general linear group GL_{r}(𝔽_{q}) is the multiplicative group of all non-singular r by r matrices over 𝔽_{q}.

• An 𝔽_{q}-representation of G of degree r is an homomorphism ϕ : G → GL_{r}(𝔽_{q}).

• The group algebra 𝔽_{q}[G] of G over a field 𝔽_{q} is the algebra over 𝔽_{q} consisting of all possible

formal linear combinations ∑_{i=1}^{T} α_{i}g_{i}, α_{i} ∈ 𝔽_{q}. The algebraic operations in 𝔽_{q}[G] are defined by:

∑_{i} α_{i}g_{i}+ ∑_{i} β_{i}g_{i} = ∑_{i} (α_{i}+ β_{i})g_{i};

( ∑_{i} α_{i}g_{i}) ( ∑_{i} β_{i}g_{i}) = ∑_{i,j} (α_{i}β_{j})(g_{i}g_{j});

λ ( ∑_{i} α_{i}g_{i}) = ∑_{i} (λα_{i})g_{i}, λ ∈ 𝔽_{q}.

• A left (right) ideal in the group algebra 𝔽_{q}[G] is an 𝔽_{q}-linear subspace of 𝔽_{q}[G] that is closed under left (right) multiplications by elements of 𝔽_{q}[G].

• A left 𝔽_{q}[G]-module is an 𝔽_{q}-linear space on which 𝔽_{q}[G] acts by left multiplication in such a way that for any m_{1},m_{2} ∈ M and any α,β ∈ 𝔽_{q}[G]:

α(m_{1}+ m_{2}) = αm_{1}+ αm_{2};
(α + β)m_{1} = αm_{1}+ βm_{1};
(αβ)m_{1} = α(βm_{1}).

The dimension of a module is its dimension as an 𝔽_{q}-linear space. Let M be an r-dimensional 𝔽_{q}[G]-module, and let m = {m_{1},...,m_{r}} 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 matrix ϕ_{M,m}(g). The map ϕ_{M,m}: G → GL_{r}(𝔽_{q}) is an 𝔽_{q}-representation of G of degree r. Two 𝔽_{q}[G]-modules M,M′ are called isomorphic if there exists an isomorphism between them as linear spaces that preserves multiplication by the elements of 𝔽_{q}[G]. In the matrix form this means that for an arbitrary choice of bases m,m′ in M,M′ there exists U ∈ GL_{r}(𝔽_{q}) such that ϕ_{M,m}(g) = U^{−1} ϕ_{M′,m′}(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 𝔽_{q}-representations ϕ : G → GL_{r}(𝔽_{q}) of degree r.

Clearly, every left ideal of 𝔽_{q}[G] is a left 𝔽_{q}[G]-module.

4.2 Algebraic formulation

Let A = 𝔽_{q}[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 𝔽_{q}. Consider the regular representation ϕ of G, ϕ : G → GL_{|G|}(𝔽_{q}), defined by

(ϕ(g))_{g_{1},g_{2}} = \{ \begin{matrix}1, & g_{1}g_{2}^{−1} = g, \\ 0, & otherwise. \end{matrix}  (4.2)

Extend ϕ to A by linearity. Note that ϕ is an injective algebra homomorphism and that the image of ϕ is the 𝔽_{q}-algebra R of all matrices that respect G. Observe that for any M ∈ R,

rkM = dim{M′M | M′∈ R}.  (4.3)

To verify formula (4.3) one needs to notice that the first row of a matrix M′∈ R can be arbitrary. Therefore products M′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 injective, 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

Let V be an 𝔽_{q}-linear subspace of A = 𝔽_{q}[G]. The left annihilator of V is defined by Ann_{L}(V) =^{def}{β ∈ A | βV = 0}. Similarly, the right annihilator is Ann_{R}(V) =^{def}{β ∈ A | V β = 0}. Clearly, Ann_{L}(V) is a left ideal in A and Ann_{R}(V) is a right ideal in A. Let M be a left A-module. The kernel of M is defined by Ker(M) =^{def}{β ∈ A | βM = 0}. It is straightforward to verify that Ker(M) is a two-sided ideal that coincides with Ann_{L}(M) if M is a left ideal in A.

Lemma 4.1. The number of r-dimensional left A-modules counted up to isomorphism is at most q^{r^{2}log_{2}|G|}.

Proof. As we remarked in Section 4.1, an upper bound on the number of 𝔽_{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},...,g_{s} be a set of generators for G, where s ≤ log_{2}|G|, and note that every representation ϕ : G → GL_{r}(𝔽_{q}) is uniquely specified by s matrices ϕ(g_{1}),...,ϕ(g_{s}) 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 𝔽_{q}-linear space is at least |G| − r^{2}.

Proof. Fix arbitrarily a basis m = {m_{1},...,m_{r}} in M, consider the representation ϕ_{M,m}from Section 4.1 and extend it by linearity to an algebra homomorphism ϕ_{M,m}: A → GL_{r}(𝔽_{q}) 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 𝔽_{q}-linear subspace of A; then dim(Ann_{R}(V)) ≤ |G| − dim(V).

Proof. Consider a bilinear map ℓ : A ⊗ A → 𝔽_{q}, 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 → 𝔽_{q} we can define its rank rk(ℓ) by choosing bases {u_{1},...,u_{m}} in U and {v_{1},...,v_{n}} in V, and letting rk(ℓ) be the rank of the m by n matrix with the entries ℓ(u_{i}⊗ v_{j}). rk(ℓ) does not depend on the choice of the bases. As a consequence, for every subspaces U′⊆ U, V′⊆ V′such that ℓ(U′⊗ V′) = 0 we have the inequality dim(U′) + dim(V′) ≤ m + n − rk(ℓ) (if an m by n matrix of rank r contains an m′ by n′zero submatrix, then m′+ n′≤ m + n − r).

In our situation, rk(ℓ) = |G| (since in the group basis ℓ is represented by a permutation matrix). Also, ℓ(V ⊗ Ann_{R}(V)) = 0. Therefore dim(Ann_{R}(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

N(q,G,r) ≤ q^{O(r^{2}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 = Ann_{L}(Aα). Note that α ∈ Ann_{R}(I). By Lemma 4.1, every A-module of dimension up to r has its kernel coming from a family of at most ∑ _{i=1}^{r} q^{i^{2}log_{2}|G|} ≤ rq^{r^{2}log_{2}|G|} ideals. Also by Lemmas 4.2 and 4.3 there are at most q^{r^{2}} elements in Ann_{R}(I) for every I.

Combining Equation (4.1) with Theorem 4.4 we obtain our main result.

Theorem 4.5. Let Q ↪ 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 ≤ O(tr^{2}).

In particular the total communication of any such scheme is Ω(n^{1/3}).

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 Ω(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 [5] 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:

1. We restricted ourselves to bilinear protocols, i. e., protocols where 𝒰 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 𝒰 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 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 ↪ H_{r} such that for every σ : [n] → 𝔽_{q}, 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 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 𝒰 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 Ω(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:

Open problem: Let Q be a GLS[n,n^{δ}] of inverse polynomial density. Show that there exists a map σ : [n] → 𝔽_{q} such that the minimal 𝔽_{q}-rank of Q_{σ} (with respect to locations containing stars in Q_{σ}) is ω(logn).

Comment: If true this implies an ω(logn) lower bound for every bilinear PIR scheme, where 𝒰 tosses a linear number of coins in the length of his queries. If false, this yields a PIR protocol with clogn 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 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},...,z_{m}) ∈ 𝔽_{q}[z_{1},...,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] → 𝔽_{q}^{m} that has been previously used in [5, 3]. Without loss of generality assume that m′= n^{1/3} is an integer. Consider an arbitrary bijection γ : [n] → [m′]×[m′]×[m′]. Let e′_{l}∈ {0,1}^{m′}denote a vector whose unique nonzero coordinate is ℓ. Set m = 3m′. Put

E(i) = e′_{γ(i)_{1}}∘ e′_{γ(i)_{2}}∘ e′_{γ(i)_{3}}.

Note that for every i, E(i) has three nonzero coordinates. Define

F (z_{1},...,z_{m}) = ∑_{i=1}^{n} x_{i} ∏_{E(i)_{ℓ}=1} z_{ℓ},

(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 z_{i} satisfies exactly one monomial in F (whose coefficient is x_{i}); thus, F (E(i)) = x_{i}.

6.1 The monomial distribution scheme of [3]

For simplicity we restrict ourselves to the case when the underlying field is 𝔽_{2}. Given a cubic multivariate polynomial F (z_{1},...,z_{m}) ∈ 𝔽_{2}[z_{1},...,z_{m}], the servers compute a new polynomial in 2m variables

F̂(v_{1},...,v_{m},w_{1},...,w_{m}) = F (v_{1}+ w_{1},...,v_{m}+ w_{m}).

The servers rewrite F̂ as a sum of two polynomials

F̂(v_{1},...,v_{m},w_{1},...,w_{m}) = F̂_{v}(v_{1},...,v_{m},w_{1},...,w_{m}) + F̂_{w}(v_{1},...,v_{m},w_{1},...,w_{m}),

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 to F̂_{v}or to F̂_{w}. Servers further rewrite F̂_{v}and F̂_{w}to obtain

F̂_{v}(v_{1},...,v_{m},w_{1},...,w_{m})= F (v_{1},...,v_{m}) + ∑_{ℓ=1}^{m} c_{ℓ}(v_{1},...,v_{m})w_{ℓ},  (6.1)
F̂_{w}(v_{1},...,v_{m},w_{1},...,w_{m})= F (w_{1},...,w_{m}) + ∑_{ℓ=1}^{m} c_{ℓ}(w_{1},...,w_{m})v_{ℓ}.  (6.2)

The formal description of the scheme is below. Recall that the user holds P ∈ 𝔽_{2}^{m} and wishes to retrieve F (P).

𝒰 : Represents P as a random sum P = V + W for V,W ∈ 𝔽_{2}^{m}.

𝒰 → 𝒮_{1} : (v_{1},...,v_{m})
𝒰 → 𝒮_{2} : (w_{1},...,w_{m})
𝒰 ← 𝒮_{1} : F (V),c_{1}(V),...,c_{m}(V)
𝒰 ← 𝒮_{2} : F (W),c_{1}(W),...,c_{m}(W)
𝒰  : Outputs F (V) + F (W) + (V,(c_{1}(W),...,c_{m}(W))) + (W,(c_{1}(V),...,c_{m}(V))))

Note that the protocol above is group-based, since the user can retrieve F (P) for any P ∈ 𝔽_{2}^{m}, and the user’s secret sharing scheme is based on 𝔽_{2}^{m}. 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:

𝒰 : Represents P as a random sum P = V + W for V,W ∈ 𝔽_{2}^{m}.

𝒰 → 𝒮_{1} : (v_{1},...,v_{m})
𝒰 → 𝒮_{2} : (w_{1},...,w_{m})
𝒰 ← 𝒮_{1} : F (V) ∘ 1 ∘ c_{1}(V) ∘ ...∘ c_{m}(V) ∘ v_{1}∘ ...∘ v_{m}
𝒰 ← 𝒮_{2} : 1 ∘ F (W) ∘ w_{1}∘ ...∘ w_{m}∘ c_{1}(W) ∘ ...∘ c_{m}(W)

𝒰 : 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 m′= n^{1/3} is an integer and γ : [n] → [m′] × [m′] × [m′] is a bijection. For S ⊆ [m′] and j ∈ [m′] let

S ⊕ j = \{ \begin{matrix}S \ \{j\}, & if j ∈ S, \\ S ∪ \{j\}, & otherwise. \end{matrix}

For S_{1},S_{2},S_{3} ⊆ [m′] let

T (S_{1},S_{2},S_{3}) = ∑_{{i|∀j∈[3]: γ(i)_{j}∈S_{j}}} x_{i}.

We say that a triple of sets S′_{1},S′_{2},S′_{3} ⊆ [m′] is at distance one from a triple S_{1},S_{2},S_{3} if there exist unique j ∈ [3] and k ∈ [m′] such that S_{t} = S′_{t} for t ≠ j and S_{j} = S′_{j}⊕ k. Let B(S_{1},S_{2},S_{3}) denote the 3m′long vector of values of T (S′_{1},S′_{2},S′_{3}) at triples S′_{1},S′_{2},S′_{3} 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:

𝒰 : Picks S_{1},S_{2},S_{3} ⊆ [m′] at random.
𝒰 → 𝒮_{1} : S_{1},S_{2},S_{3}
𝒰 → 𝒮_{2} : S_{1}⊕ γ(i)_{1},S_{2}⊕ γ(i)_{2},S_{3}⊕ γ(i)_{3}
𝒰 ← 𝒮_{1} : T (S_{1},S_{2},S_{3}),B(S_{1},S_{2},S_{3})
𝒰 ← 𝒮_{2} : T (S_{1}⊕ γ(i)_{1},S_{2}⊕ γ(i)_{2},S_{3}⊕ γ(i)_{3}),B(S_{1}⊕ γ(i)_{1},S_{2}⊕ γ(i)_{2},S_{3}⊕ γ(i)_{3})

Now note that T (S_{1},S_{2},S_{3}) = F (S_{1}∘ S_{2}∘ S_{3}). Let P = E(i) ∈ 𝔽_{2}^{m}. Recall that e_{ℓ} ∈ {0,1}^{m} denotes a vector whose unique nonzero coordinate is ℓ. We rewrite the protocol above in a different notation:

𝒰 : Represents P as a random sum P = V + W for V,W ∈ 𝔽_{2}^{m}.
𝒰 → 𝒮_{1} : (v_{1},...,v_{m})
𝒰 → 𝒮_{2} : (w_{1},...,w_{m})
𝒰 ← 𝒮_{1} : F (V),F (V + e_{1}),...,F (V + e_{m})
𝒰 ← 𝒮_{2} : F (W),F (W + e_{1}),...,F (W + e_{m})

Let c_{ℓ} denote the polynomial that has been previously used in formula (6.1). It is not hard to verify that

c_{l}(V) = F (V + e_{l}) + F (V).  (6.3)

Taking formula (6.3) 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.

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} ∈ 𝔽_{q}. Let f(λ) ∈ 𝔽_{q}[λ] be a univariate cubic polynomial. Note that

f(0) = c_{1}f(λ_{1}) + c_{2}f′(λ_{1}) + c_{3}f(λ_{2}) + c_{4}f′(λ_{2}),

for some constants c_{i} that are independent of f.

Protocol description : We use standard mathematical notation \frac{∂F}{∂z_{ℓ}}|_{W} to denote the value of the partial derivative of F with respect to z_{ℓ} at the point W. Let P = E(i). The user wishes to retrieve F (P).

𝒰 : Picks V ∈ 𝔽_{q}^{m} uniformly at random.
𝒰 → 𝒮_{1} : P + λ_{1}V
𝒰 → 𝒮_{2} : P + λ_{2}V
𝒰 ← 𝒮_{1} : F (P + λ_{1}V), \frac{∂F}{∂z_{1}} |_{P+λ_{1}V} ,..., \frac{∂F}{∂z_{m}}|_{P+λ_{1}V}
𝒰 ← 𝒮_{2} : F (P + λ_{2}V), \frac{∂F}{∂z_{1}} |_{P+λ_{2}V} ,..., \frac{∂F}{∂z_{m}}|_{P+λ_{2}V}
𝒰  : c_{1}F (P + λ_{1}V) + c_{2} ∑_{ℓ=1}^{m} \frac{∂F}{∂z_{ℓ}}|_{P+λ_{1}V} V_{ℓ}+ c_{3}F (P + λ_{2}V) + c_{4} ∑_{ℓ=1}^{m} \frac{∂F}{∂z_{ℓ}}|_{P+λ_{2}V} V_{ℓ}

Note that in the protocol above the servers represent the database by a function F : 𝔽_{q}^{m} → 𝔽_{q} on a group and the user can retrieve F (P) for arbitrary element P ∈ 𝔽_{q}^{m}. 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:

𝒰 : Picks V ∈ 𝔽_{q}^{m} uniformly at random.

𝒰 → 𝒮_{1} : (P + λ_{1}V)λ_{2}/(λ_{2}− λ_{1})
𝒰 → 𝒮_{2} : (P + λ_{2}V)λ_{1}/(λ_{2}− λ_{1})
𝒰 ← 𝒮_{1} : F (P + λ_{1}V) ∘ c_{3}∘ [ \frac{c_{2}}{λ_{1}−λ_{2}} ∑_{ℓ=1}^{m} \frac{∂F}{∂z_{ℓ}}|_{P+λ_{1}V} (P + λ_{1}V)_{ℓ}]∘ \frac{∂F}{∂z_{1}} |_{P+λ_{1}V} ∘ ...∘ \frac{∂F}{∂z_{m}}|_{P+λ_{1}V} ∘

∘1 ∘ \frac{−c_{4}}{λ_{2}−λ_{1}} (P + λ_{1}V)_{1}∘ ...∘ \frac{−c_{4}}{λ_{2}−λ_{1}} (P + λ_{1}V)_{m}

𝒰 ← 𝒮_{2} : c_{1}∘ F (P + λ_{2}V) ∘ 1 ∘ \frac{−c_{2}}{λ_{1}−λ_{2}} (P + λ_{2}V)_{1}∘ ...∘ \frac{−c_{2}}{λ_{1}−λ_{2}} (P + λ_{2}V)_{m}∘

∘[ \frac{c_{4}}{λ_{2}−λ_{1}} ∑_{ℓ=1}^{m} \frac{∂F}{∂z_{l}} |_{P+λ_{2}V} (P + λ_{2}V)_{ℓ}]∘ \frac{∂F}{∂z_{1}} |_{P+λ_{2}V} ∘ ...∘ \frac{∂F}{∂z_{m}}|_{P+λ_{2}V}

𝒰 : 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] * Andris Ambainis: Upper bound on the communication complexity of private information 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] * Richard Beigel, Lance Fortnow, and William Gasarch: A tight lower bound for restricted PIR protocols. Computational Complexity, 15:82–91, 2006. [10.1007s00037-006-0208-3]. 1.2

[3] * Amos Beimel, Yuval Ishai, and Eyal Kushilevitz: 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] * Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Jean-Francios Ray-

mond: Breaking the O(n^{1/(2k−1)}) barrier for information-theoretic private information retrieval. In Proc. 43rd FOCS, pp. 261–270. IEEE Computer Society Press, 2002. [FOCS:10.1109/SFCS.2002.1181949]. 1, 2, 6

[5] * Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan: Private information retrieval. J. ACM, 45:965–981, 1998. [JACM:10.1145/293347.293350]. 1, 5, 6, 6.2

[6] * William Gasarch: A survey on private information retrieval. The Bulletin of the EATCS, 82:72–107, 2004. 1

[7] * Oded Goldreich, Howard Karloff, Leonard Schulman, and Luca Trevisan:

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. Martin Isaacs: Character theory of finite groups. Academic Press, 1976. 4.1

[9] * Toshiya Itoh: Efficient private information retrieval. IEICE Trans. Fund. of Electronics, Commun. and Comp. Sci., E82-A:11–20, 1999. 6

[10] * Toshiya Itoh: 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] * Jonathan Katz and Luca Trevisan: On the efficiency of local decoding procedures for error-correcting codes. In Proc. 32nd STOC, pp. 80–86. ACM Press, 2000. [STOC:10.1145/335305.335315]. 1

[12] * Kiran S. Kedlaya and Sergey Yekhanin: 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] * Iordanis Kerenidis and Ronald de Wolf: 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] * Eran Mann: Private access to distributed information. Master’s thesis, Technion - Israel Institute of Technology, Haifa, 1998. 1

[15] * Alexander Razborov and Sergey Yekhanin: An Ω(n^{1/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] * Stephanie Wehner and Ronald de Wolf: 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

[18] * Steven H. Weintraub: Representation theory of finite groups: algebra and arithmetic. volume 59 of Graduate Studies in Mathematics. AMS, 2003. 4.1

[19] * David Woodruff and Sergey Yekhanin: 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] * Sergey Yekhanin: Locally decodable codes and private information retrieval schemes. PhD thesis, Massachusetts Institute of Technology, 2007. 1

[21] * Sergey Yekhanin: 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

Alexander Razborov 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.

Sergey Yekhanin 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.