I. INTRODUCTION

In the Private Information Retrieval (PIR) problem, a database of K messages is replicated at N servers. There is a user who wishes to retrieve a single or multiple messages belonging to the database while protecting the identity of the demanded message(s) from any individual server [1]- [4]. In order to retrieve the desired message(s), the user generates one query for each server. Upon receiving the user's query, each server will return an answer to the user, which depends on the stored messages and the received query. To ensure that each server learns nothing about the identity of the message(s) being retrieved by the user, in an information theoretic sense, each query must be marginally independent of the desired message(s) index.

In a single-server setting or a multi-server setting when all servers can fully collude, the user must download the whole database to achieve privacy in the information-theoretic sense [1]. However, when the user has some side information about the messages in the database [5]- [18] or when the servers do not fully collude [2]- [4], the privacy can be achieved more efficiently in terms of the download cost (i.e., the amount of information downloaded from the server(s)).

For the PIR problem in the presence of side information, two different types of privacy can be considered: (i) Wprivacy, which requires that the identity of the message(s) demanded by the user is protected, and (ii) (W, S)-privacy, which requires that the identities of both the message(s) demanded by user and the message(s) in the user's side information are protected. When the side information is a random subset of messages, the problem is referred to as PIR with Side Information (PIR-SI) or PIR with Private Side Information (PIR-PSI) when W -privacy or (W, S)privacy is required, respectively. The single-server settings of these problems were studied in [5]- [7], and their multiserver settings were studied in [8]- [10]. In [11] and [12], we studied the single-server setting of a related problem in which the side information is a random linear combination of a random subset of messages. This problem is referred to as PIR with Coded Side Information (PIR-CSI) or PIR with Private Coded Side Information (PIR-PCSI) when Wprivacy or (W, S)-privacy is required, respectively. Also, in [13], we recently studied the multi-server setting of the PIR-CSI problem.

In this work, we consider the multi-server setting of the PIR-PCSI problem. In this setting, a database of K messages is replicated across N servers, and a user, who knows a random linear combination of a random subset of M messages in the database, wishes to obtain a message by sending queries to the servers. The goal is to design a scheme that protects the identities of both the message demanded by the user and the messages contributing to the user's side information, and minimizes the download cost. We assume that the servers know the number of messages contributing to the user's side information beforehand. However, the indices and the coefficients of the messages contributing to the user's side information are not known to the servers in advance. The motivation for this type of side information comes from several practical scenarios. For instance, the side information could have been obtained in advance from a trusted server with limited knowledge about the database, or through overhearing in a wireless network, or from the information locally stored in the user's cache.

A. Main Contributions

We consider two settings of the PIR-PCSI problem depending on whether the user's demanded message is one of the messages contributing to the user's side information or not. We characterize (or derive a lower bound on) the capacity of each setting, where the capacity is defined as the supremum of all achievable rates (i.e., the inverse of the normalized download cost). In the first setting, the message demanded by the user is not one of the messages contributing to the user's side information. For this setting, we prove that the capacity is equal to

Interestingly, the capacity in this setting is equal to the capacity of multi-server PIR-PSI problem [8] in which M uncoded messages are available at the user as side information. This result shows that there is no loss in capacity due to restricting the user's side information to one random linear combination of M messages, instead of M uncoded messages.

The converse proof readily follows from the fact that the capacity of this setting is upper-bounded by the capacity of the multi-server setting of the PIR-PSI which is given by

For the achievability proof, we devise a new protocol that builds upon two existing achievability schemes for two different problems: (i) the Private Computation (PC) scheme of [19] for multi-server private computation where a user wishes to privately retrieve one arbitrary linear combination of the messages replicated at multiple servers, and (ii) our Specialized GRS Code scheme proposed in [12] for singleserver PIR-PCSI.

The main ideas of our achievability scheme are as follows. First, the user utilizes the Specialized GRS Code scheme of [12] for single-server PIR-PCSI to construct K -M independent coded messages which are linearly independent combinations of the original messages, to play the role of the original messages in a multi-server private computation problem. Then, the user and the N servers leverage the PC scheme of [19] for the constructed K -M coded messages in such a way that the user can privately download one of K M +1 linear combinations of the K -M coded messages where the support of each linear combination is a distinct subset of [K] of size M + 1.

Additionally, for the setting wherein the demanded message is one of the messages contributing to the user's side information, we show that the capacity is lower-bounded by

The proof is based on a new achievability scheme that leverages the PC scheme of [19] for multi-server private computation, combined with our Modified Specialized GRS Code scheme proposed in [12] for single-server PIR-PCSI.

II. PROBLEM FORMULATION

We denote random variables by bold letters and their realizations by non-bold letters. For a positive integer i, let [i] {1, . . . , i}. Let F q be a finite field for some prime q, and let F × q F q \ {0} be the multiplicative group of F q . Let F q m be an extension field of F q for some integer m ≥ 1.

Consider N non-colluding identical servers, each of which stores K messages X 1 , . . . , X K , where X i is independently and uniformly distributed over F q m , i.e., for all i ∈ [K], it holds that H(X i ) = L m log 2 q, and H(X 1 , . . . , X K ) = KL.

Suppose that there is a user that wishes to retrieve a message X W from the servers for some W ∈ [K], and has a linear combination Y [S,C] i∈S c i X i for some S {i 1 , . . . , i M } ∈ S and some C {c i1 , . . . , c i M } ∈ C, where S is the set of all M -subsets of [K], and C is the set of all length-M sequences with elements from F × q . We refer to W as the demand index, X W as the demand, Y [S,C] as the side information, S as the side information index set, and M as the side information size.

We assume that S is uniformly distributed over S, and that C is uniformly distributed over C. Also, two different models for the conditional distribution of W given S = S are considered:

for Model I and Model II, respectively. Note that for both models it holds that W is uniformly distributed over [K]. We assume that no server knows the realizations of S, C, W in advance. In contrast, we assume that all servers know the considered model (i.e., whether W ∈ S or W ∈ S), the side information size M , the distributions of S and C, and the conditional distribution of W given S.

For any S, C, W , in order to retrieve X W , the user generates N queries Q and the messages in

n forms a Markov chain, and S,C] N from all servers along with the side information Y [S,C] and the queries Q

must enable the user to retrieve the demand X W , i.e.,

and

This condition is referred to as the recoverability condition.

In addition, the queries

must not reveal any information about the user's demand index W and side information index set S to any server,

This condition is referred to as the (W, S)-privacy condition.

For both models (Model I and Model II), we would like to design a protocol for generating queries {Q The rate of a PIR-PCSI-I or PIR-PCSI-II protocol is defined as the ratio of the entropy of a message, i.e., L, to the total entropy of answers from all servers, i.e., H(A [W,S,C] ).

The capacity of the PIR-PCSI-I (PIR-PCSI-II) problem is defined as the supremum of rates over all PIR-PCSI-I (PIR-PCSI-II) protocols. We denote by C (W,S)-I the capacity of the PIR-PCSI-I problem, and denote by C (W,S)-II the capacity of the PIR-PCSI-II problem.

In this work, our goal is to characterize (or derive lower bounds on) C (W,S)-I and C (W,S)-II , and to design PIR-PCSI-I and PIR-PCSI-II protocols that achieve the capacity (or the derived lower bound on the capacity).

III. MAIN RESULTS

In this section, we present our main results. Theorem 1 characterizes the capacity of the PIR-PCSI-I problem C (W,S)-I , and Theorem 2 presents a lower-bound on the capacity of the PIR-PCSI-II problem C (W,S)-II . The proofs of the theorems 1 and 2 are given in sections IV and V, respectively.

Theorem 1. The capacity of the PIR-PCSI-I problem with N servers, K messages, and side information size

Interestingly, this result indicates that the capacity of multi-server PIR-PCSI-I, i.e., C (W,S)-I , is equal to the capacity of the multi-server PIR-PSI [8] where M uncoded messages are available at the user as side information. Note that having only a random linear combination of M messages as side information instead of M uncoded messages, cannot increase the capacity which implies the converse. Thus, to complete the proof of Theorem 1, we only need to prove the achievability which is presented in Section IV. Notably, our results show that having only one random linear combination of messages instead of multiple uncoded messages does not decrease the capacity, either.

Theorem 2. The capacity of the PIR-PCSI-II problem with N servers, K messages, and side information size 2 ≤ M ≤ K is lower-bounded by

This result is interesting because it shows that the lowerbound on the capacity of the multi-server PIR-PCSI-II is the same as the capacity of multi-server PIR-SI when the size of side information is M -1. That is, having a side information which is only a random linear combination of M messages including the demanded message would be at least as effective as knowing M -1 messages separately in terms of minimizing the download cost. For the proof, we construct a PIR-PCSI-II protocol that achieves the capacity lowerbound of Theorem 2. It should be noted that the tightness of this lower bound remains open in general.

IV. THE PIR-PCSI-I PROBLEM

In this section, we complete the proof of Theorem 1 by proposing an achievability scheme for arbitrary N , K ≥ 1 and 0 ≤ M ≤ K -1 that achieves the rate

The proposed protocol, referred to as the Multi-Server PIR-PCSI-I protocol, is a non-trivial combination of the Specialized GRS Code scheme of [12] for single-server PIR-PCSI problem and the Private Computation (PC) scheme of [19] for multi-server private computation problem.

For the proposed protocol, we assume that q ≥ K, and each message X i consists of m = N ( K M +1 ) symbols over F q .

Multi-Server PIR-PCSI-I protocol: The protocol consists of the following five steps:

Step 1: The user utilizes the Specialized GRS Code protocol proposed in [12] to first construct a polynomial

where ω 1 , . . . , ω K are K arbitrarily chosen distinct elements from F q , and then construct r K -M vectors u 1 , . . . , u r , each of length K, such that

, where β j = cj p(ωj ) for j ∈ S, and β j is a randomly chosen element from F × q for j ∈ S.

Each Xi is referred to as a coded message. Note that the vector u i (constructed in Step 1) is the vector of coefficients of the messages {X i } i∈[K] in the coded message Xi . Let F K M +1 , and let J 1 , J 2 , . . . , J F be the collection of all (M + 1)-subsets of [K] in a lexicographical order. The structure of the Specialized GRS Code protocol [12] ensures that for each J f , f ∈ [F ], there exist exactly q -1 linear combinations Z 1 f , Z 2 f , . . . , Z q-1 f of the messages {X i } i∈J f with (non-zero) coefficients from F × q , such that for every k ∈ [q -1], Z k f can be written as a linear combination of the coded messages X1 , . . . ,

are the same up to a scalar multiple, i.e., for each k ∈

(Note that the above procedure dictates a specific choice of the coefficient vectors v f . However, for each f ∈ [F ], the vector v f can be chosen arbitrarily from the set of vectors

Step 3: The user sends to all servers the vectors u 1 , . . . , u r (associated with the coded messages X1 , . . . , Xr ), and the vectors v 1 , . . . , v F (associated with the functions Z 1 , . . . , Z F ). It is noteworthy that the user needs only to send the vectors {u i } i∈[r] to all servers, and each server can construct the vectors {v f } f ∈[F ] by using {u i } i∈[r] (according to the procedure described in Step 2).

Step 4: The user and the servers leverage the PC scheme of [19] with r (independent) messages and F (linear) functions of these messages in order for the user to privately retrieve one of these functions. In particular, the

play the role of the original messages and the functions in the PC scheme, respectively, and the user is interested in retrieving the function Z f * privately, where Z f * is an F × q -linear combination (i.e., a linear combination with nonzero coefficients only) of the messages {X i } i∈W ∪S . (By the construction, there exists one (and only one) function Z f among Z 1 , . . . , Z F such that Z f is an F × q -linear combination of the messages {X i } i∈W ∪S .) To be more specific, each server first constructs the coded messages { Xi } i∈[r] by using the coefficient vectors {u i } i∈[r] (defined in Step 3), and then constructs the functions {Z f } f ∈[F ] by using the coded messages { Xi } i∈[r] and the coefficient vectors

where N is the number of servers. Then, each server sends to the user

. The details of the design of the user's query to each server as well as the linear combinations transmitted by each server (which also depend on the query of the user) can be found in [19,Section 4].

Example 1. (Multi-Server PIR-PCSI-I protocol) Assume that there are N = 2 servers, K = 4 messages from F 5 16 , and M = 2. Note that each message consists of m = N ( K M +1 ) = 16 symbols from F 5 . Suppose that the user demands the message X 1 and has a coded side information Y = X 2 + X 3 , i.e., W = 1, S = {2, 3}, and C = {1, 1} (i.e., c 2 = 1, c 3 = 1).

First, the user picks K = 4 distinct elements ω 1 , . . . , ω 4 from F 5 . Suppose that the user chooses ω 1 = 0, ω 2 = 1, ω 3 = 2, ω 4 = 3. Then, the user constructs the polynomial

The user then computes β j for j ∈ S, i.e., β 2 and β 3 , by setting β 2 = c2 p(ω2) = 2 and β 3 = c3 p(ω3) = 4, and chooses β j for j ∈ S, i.e., β 1 and β 4 , at random (from F × 5 ). Assume that the user chooses β 1 = 1 and β 4 = 2. Then, the user constructs r = K -M = 2 vectors u 1 and u 2 , each of length K = 4, such that

It should be noted that there exists no other vector

Note that the coefficient of the message X i1 = X 1 (i.e., i 1 = min(J 1 ) = 1) in the function Z 1 is equal to 1 when k = 1. Thus, the user constructs the vector

Similarly, the user constructs the vectors

Then, the user sends to all servers the vectors u 1 and u 2 (associated with the coded messages X1 and X2 ), and the vectors v 1 , . . . , v 4 (associated with the functions Z 1 , . . . , Z 4 ). Using the coefficient vectors u 1 and u 2 , each server first constructs the following two coded messages

Then, the user constructs the functions Z 1 , . . . , Z 4 using the coded messages X1 and X2 and the coefficient vectors v 1 , . . . , v 4 as follows:

Finally, the user and the servers apply the PC scheme of [19] for two coded messages X1 , X2 in order for the user to privately retrieve the function Z 1 . (Note that among the functions Z 1 , . . . , Z 4 , only Z 1 is an F × 5 -linear combination of the messages {X i } i∈W ∪S = {X 1 , X 2 , X 3 }.) The details of the PC scheme for this example are as follows. Let π : [16] → [16] be a randomly chosen permutation. Let

for f ∈ [4] and i ∈ [16], where Z f (π(i)) is the π(i)-th F 5 -symbol of Z f , and σ i is a randomly chosen element from {-1, +1}. For simplifying the notation, we define the following: [16]. Then, from each of the two servers (S1 and S2), the user queries 15 carefully designed linear combinations of the symbols {{a i } i∈ [16] , {b i } i∈ [16] , {c i } i∈ [16] , {d i } i∈ [16] }, as given in Table I [19].

As shown in [19], among the 15 symbols queried from S1 (or S2), based on the information obtained from S2 (or S1), 3 symbols are redundant. For instance, consider the 15 symbols queried from S1. (Similar observations can be made regarding the queries from S2.) Among the 4 symbols {a From the answers by the servers, the user obtains all 16 symbols a 1 , . . . , a 16 , and accordingly, all 16 symbols of Z 1 . (Note that a i = u 1 (i) = σ i Z 1 (π(i)) for i ∈ [16].) From Z 1 (= X 1 + 3X 2 + 3X 3 ), the user can decode the desired message X 1 by subtracting off the contribution of their side information X 2 + X 3 .

In order to retrieve X 1 which consists of 16 symbols (over F 5 ), according to the proposed protocol, the user downloads 24 symbols (over F 5 ) from both servers, and hence the rate of the proposed protocol is 16/24 = 2/3.

Note that for every 3-subset {X j1 , X j2 , X j3 } of the messages {X i } i∈ [4] , in the proposed protocol there exists one (and only one) linear combination Z f for some f ∈ [4] of the messages X j1 , X j2 , X j3 . On the other hand, the PC scheme guarantees that no server can obtain any information about the index (f ) of the linear combination Z f being requested by the user. Thus, the proposed scheme satisfies the (W, S)privacy condition, as desired.

Lemma 1. The Multi-Server PIR-PCSI-I protocol satisfies the recoverability and (W,S)-privacy conditions, and achieves the rate C (W,S)-I = 1 + 1/N + • • • + 1/N K-M -1 -1 .

Proof: Since the messages X [K] are uniformly and independently distributed over F q m , and { X1 , . . . , Xr } are linearly independent combinations of the messages in X [K] , thus { X1 , X2 , . . . , Xr } are uniformly and independently distributed over F q m as well, i.e., H( X1 ) = • • • = H( Xr ) = m log q = L. Hence, the rate of the Multi-Server PIR-PCSI-I protocol is the same as the rate of the PC protocol for N servers and K -M messages, which is given by 1 + 1/N + • • • + 1/N K-M -1 -1 (see [19,Theorem 1]).

From the step 4 of the Multi-Server PIR-PCSI-I protocol, it is evident that the recoverability condition is satisfied. The proof of the (W, S)-privacy of the proposed protocol is as follows. The PC protocol protects the privacy of the function (linear combination) requested by the user. That is, given the query, no server can obtain any information about the index of the function requested by the user. Consider an arbitrary server n ∈ [N ], and an arbitrary query Q n to server n, generated by the proposed protocol. Thus, given Q [W,S,C] n = Q n , from the perspective of server n, every function Z f for f ∈ [F ] is equally likely to include the demanded message. We denote the support of Z f by Z f , i.e., Z f is the set of all indices i ∈ [K] such that X i has a non-zero coefficient in the linear combination Z f . Thus, for all f ∈ [F ], we have

noting that F = K M +1 . Note that any given index W ∈ [K] is in the support of exactly