In the information-theoretic Private Information Retrieval (PIR) problem (see, e.g., [1], [2]), there is a user that wishes to download a single or multiple messages belonging to a database stored on a single or multiple (non-colluding or colluding) servers. The goal of the user is to minimize the download cost (i.e., the amount of information downloaded from the server(s)), while hiding the identity of its demanded message(s) from the server(s). This setup was recently extended in [3]- [12] to the settings wherein the user has some side information about the messages in the database, and the side information is unknown to the server(s).
For the single-server setting of the PIR problem in the presence of some side information, we studied the cases in which the side information is a random subset of messages (a.k.a. PIR with Side Information (PIR-SI)) and a random linear combination of a random subset of messages (a.k.a. PIR with Coded Side Information (PIR-CSI)) in [3], [11] and [9], respectively. The multi-server setting of the PIR-SI problem was also studied in [7], [8], [10]. For the PIR-SI problem, two different types of privacy, known as W -privacy (i.e., only the identities of the demand messages must be protected) and (W, S)-privacy (i.e., the identities of both the demand and side information messages must be protected
The authors are with the Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77843 USA (E-mail: {anoosheh, fatemeh.kazemi, spalex}@tamu.edu).
This material is based upon work supported by the National Science Foundation under Grants No. 1718658 and 1642983. jointly) have been considered, whereas the problem of PIR-CSI has only been studied when W -privacy is required.
In this work, we study the single-server single-message PIR-CSI problem where (W, S)-privacy is required. In this problem, referred to as PIR with Private Coded Side Information (PIR-PCSI), there is a single server storing a database of K messages, and there is a user who knows a random linear combination of a random subset of M messages in the database. The user is interested in downloading a single message from the server while preserving the privacy of both the demand message and the messages contributing to the side information. This problem setting can be motivated by several practical scenarios. For instance, the user may have obtained their side information via overhearing in a wireless network; or from a trusted server with limited knowledge about the database; or from the information locally stored in the user's cache of limited size.
We define the (scalar-linear) capacity of the PIR-PCSI problem as the supremum of all achievable rates (i.e., the ratio of the entropy of a message to the entropy of the download cost) over all (scalar-linear) PIR-PCSI protocols. Depending on whether the user's demanded message itself contributes to the user's coded side information or not, we consider two different models of the problem.
For the model in which the demanded message is not part of the side information, we characterize the capacity and the scalar-linear capacity. In particular, we show that for this model the capacity and the scalar-linear capacity are both equal to (K -M ) -1 for any 0 ≤ M ≤ K -1. This is interesting because, as shown in [3,Theorem 2], even when the user knows M randomly chosen (uncoded) messages as their side information, in order to guarantee (W, S)-privacy, the capacity is equal to
For the model wherein the user's demanded message contributes to their side information, we show that the scalar-linear capacity is equal to (K -M + 1) -1 for any 2 ≤ M ≤ K. Interestingly, this result shows that when the user knows M -1 randomly chosen messages (different from the demand), achieving (W, S)-privacy is as costly as that when the user knows only one random linear combination of their demanded message and M -1 other random messages.
The converse proofs are based on new informationtheoretic arguments, and the proofs of achievability rely on novel PIR protocols based on the Generalized Reed-Solomon (GRS) codes that contain a specific codeword which depends on the coefficients and the indices of messages in the side information and the index of the demanded message.
Throughout, we denote random variables and their realizations by bold-face letters and regular letters, respectively.
Let F q be a finite field for some prime q, and let F q l be an extension field of F q for some integer l ≥ 1, and let L l log 2 q. For an integer i ≥ 1, let [i] {1, . . . , i}. Let K ≥ 1 and 0 ≤ M ≤ K be two integers. We denote by S the set of all M -subsets of [K], and denote by C the set of all length-M sequences with elements from F × q F q \ {0}. Assume that there is a server that stores a set of K messages, denoted by X {X 1 , . . . , X K }, where each message X i is independently and uniformly distributed over F q l , i.e., H(X i ) = L for i ∈ [K] and H(X) = KL, where X {X 1 , . . . , X K }. Also assume that there is a user that wishes to retrieve a message X W from the server for some W ∈ [K], and knows a linear combination Y [S,C] i∈S c i X i for some S {i 1 , . . . , i M } ∈ S and C {c i1 , . . . , c iM } ∈ C. We refer to W as the demand index, X W as the demand, S as the side information index set, Y [S,C] as the side information, and M as the side information size.
We assume that S is uniformly distributed over S, and C is uniformly distributed over C. Also, we consider two different models as follows for the conditional distribution of W given S = S:
Model II: W is uniformly distributed over S. To avoid the degenerate cases, we assume 0 ≤ M ≤ K -1 and 2 ≤ M ≤ K for the models I and II, respectively. Note that Pr(W = W, S = S|W ∈ S) is equal to
S ∈ S such that W ∈ S, and it is zero otherwise; and Pr(W = W , S = S|W ∈ S) is equal to (M K M ) -1 for all W ∈ [K], S ∈ S such that W ∈ S, and it is zero otherwise.
We assume that a priori the server knows the underlying problem model (i.e., W ∈ S or W ∈ S), the side information size (M ), the distributions of S and C, and the conditional distribution of W given S; whereas the realizations S, C, and W are unknown to the server a priori.
For any S, C, W , in order to retrieve X W , the user sends to the server a query Q [W,S,C] , which is a (potentially stochastic) function of W, S, C. We denote Q [W,S,C] by Q. The query must protect the privacy of both the user's demand index and side information index set from the server. That is, for any θ ∈ {0, 1}, it must hold that
for all W ∈ [K], S ∈ S. We refer to this condition as the (W, S)-privacy condition. Note that (W, S)-privacy is a stronger condition than W -privacy considered in [9], where the query must protect only the privacy of the user's demand index from the server. Upon receiving Q [W,S,C] , the server sends to the user an answer A [W,S,C] , which is a (deterministic) function of the query Q [W,S,C] , the indicator variable 1 {W ∈S} , and the messages in X. We denote C] , and W, S, C must enable the user to retrieve the demand X W . That is, it must hold that
We refer to this condition as the recoverability condition.
The following lemma, which follows from a simple contradiction and hence appears without proof, gives a necessary condition for (W, S)-privacy and recoverability.
For each model (I or II), the problem is to design a protocol for generating a query Q [W,S,C] (and the corresponding answer A [W,S,C] , given Q [W,S,C] , 1 {W ∈S} , and X) for any given W, S, C, such that both the privacy and recoverability conditions are satisfied. We refer to this problem as singleserver Private Information Retrieval (PIR) with Private Coded Side Information (PCSI), or PIR-PCSI for short. The PIR-PCSI problem under the model I or model II is referred to as PIR-PCSI-I or PIR-PCSI-II, respectively.
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 conditional entropy of the answer A [W,S,C] given that W ∈ S (or W ∈ S). The capacity of PIR-PCSI-I (or PIR-PCSI-II) problem is defined as the supremum of rates over all PIR-PCSI-I (or PIR-PCSI-II) protocols. The supremum of rates over all scalar-linear PIR-PCSI-I (or PIR-PCSI-II) protocols, i.e., where the answer contains only scalar-linear combinations of the messages in X, is defined as the scalarlinear capacity of PIR-PCSI-I (or PIR-PCSI-II) problem.
In this work, our goal is to characterize the capacity and the scalar-linear capacity of the PIR-PCSI-I and PIR-PCSI-II problems, and to design PIR-PCSI-I and PIR-PCSI-II protocols that are capacity-achieving.
We present our main results in this section. The capacity and the scalar-linear capacity of PIR-CSI-I problem are characterized in Theorem 1, and the scalar-linear capacity of PIR-CSI-II problem is characterized in Theorem 2. The proofs are given in Sections IV and V.
Theorem 1. The capacity and the scalar-linear capacity of PIR-PCSI-I problem with K messages and side information size 0 ≤ M ≤ K -1 are given by (K -M ) -1 .
The converse follows directly from the result of [3, Theorem 2], which was proven using an index coding argument, for single-server single-message PIR with (uncoded) side information when (W, S)-privacy is required. In this work, we provide an alternative proof by upper bounding the rate of any PIR-PCSI-I protocol using information-theoretic arguments (see Section IV-A). The key component of the proof is the necessary condition presented in Lemma 1.
The achievability proof relies on a new PIR-PCSI-I protocol, termed the Specialized GRS Code protocol, which achieves the rate (K -M ) -1 (see Section IV-B). This protocol is based on the Generalized Reed-Solomon (GRS) codes that contain a specific codeword depending on W, S, C. Remark 1. As shown in [3], when there is a single server storing K independent and identically distributed messages, and there is a user that knows M randomly chosen (uncoded) messages as their side information and demands a single message not in their side information, in order to guarantee (W, S)-privacy, the minimum download cost is (K -M )L, where L is the entropy of a message. Surprisingly, this result matches the result of Theorem 1. This shows that, when compared to having M random messages separately as side information, for achieving (W, S)-privacy there will be no additional loss in capacity even if only one random linear combination of M random messages is known to the user.
Remark 2. When W -privacy is required, the result of [9, Theorem 1] shows that the capacity of single-server singlemessage PIR with a coded side information that does not include the demand (known as the PIR-CSI-I problem in [9]) is equal to
the capacity of PIR-PCSI-I is strictly smaller than that of PIR-CSI-I. This is expected because W -privacy is a weaker notion of privacy when compared to (W, S)-privacy. However, for the two extremal cases of M = 0 and M = K -1, it follows that (W, S)-privacy comes at no extra cost than W -privacy.
Theorem 2. The scalar-linear capacity of PIR-PCSI-II problem with K messages and side information size 2 ≤ M ≤ K is given by (K -M + 1) -1 .
The converse proof is based on a mix of algebraic and information-theoretic arguments (see Section V-A), and the proof of achievability is based on a modified version of the Specialized GRS Code protocol which achieves the rate (K -M + 1) -1 (see Section V-B).
Remark 3. Interestingly, comparing the results of [3, Theorem 2] and Theorem 2, one can see that when the side information is composed of M -1 randomly chosen messages (different from the demand message), (W, S)-privacy cannot be achieved more efficiently than the case in which the side information is only one random linear combination of M random messages including the demand.
Remark 4. As shown in [9, Theorem 2], when W -privacy is required, the capacity of single-server single-message PIR with a coded side information to which the demand message contributes (known as the PIR-CSI-II problem in [9]) is equal to 1 for M = 2 and M = K, and is equal to 1 2 for all 3 ≤ M ≤ K -1. The result of Theorem 2 matches this result for the cases of M = K and M = K -1, and thereby, (W, S)-privacy and W -privacy are attainable at the same cost. For other cases of M , as expected, achieving (W, S)-privacy is more costly than achieving W -privacy.
As shown in [3] using an index-coding argument, when (W, S)-privacy is required, the capacity of PIR with M uncoded messages as side information is given by (K -M ) -1 . Obviously, the capacity of PIR-PCSI-I is upper bounded by this quantity. This proves the converse for Theorem 1. We present an alternative information-theoretic proof here. ) such that W ∈ S. Let E denote the event that W ∈ S. We need to show that H(A|E) ≥ (K -M )L. Similar to the proof of [9, Theorem 1], it can be shown that
(1)
where (2) holds because H(X i |A, Q, E, Y i ) = 0 for all j ∈ I (by assumption); and (3) holds since X I is independent of (Q, E, Y, X W , Y I ) (noting that I and W ∪ S are disjoint). Note also that, by the maximality of I, for any j ∈ J [K] \ (W ∪ S ∪ I), there exists
where (4) holds since H(X j |A, Q, E, Y I ) = 0 for all j ∈ J (by assumption); and (5) holds because X J and (Q, E, Y, X W , Y I , X I ) are independent (noting that J and W ∪ S ∪ I are disjoint). Putting ( 1), (3), and ( 5) together, it follows that H(A|E) ≥ H(X W ) + H(X I ) + H(X J ) = (K -M )L, as was to be shown.
In this section, we propose a PIR-PCSI-I protocol that achieves the rate (K -M ) -1 . Throughout, we assume that q ≥ K. It is noteworthy that for q < K the achievability of the rate (K -M ) -1 is not necessarily feasible, and it is conditional upon the existence of a (K, K -M ) maximumdistance-seperable (MDS) code over F q that includes a codeword such that the ith codeword symbol is zero for any i ∈ W ∪ S, it is equal to c i for any i ∈ S (where c i is the coefficient of X i in Y [S,C] ), and is non-zero for i = W .
Specialized GRS Code Protocol: This protocol consists of four steps as follows:
Step 1: First, the user arbitrarily chooses K distinct elements ω 1 , . . . , ω K from F q , and constructs a polynomial
where the choice of v i 's is specified as follows. For any i ∈ S, v i = ci p(ωi) where c i is the coefficient of X i in Y [S,C] ; and for any i ∈ S, v i is chosen at random from F × q . For any i ∈ [K -M ] and any j ∈ [K], the jth element in the sequence Q i can be thought of as the entry (i, j)
is the generator matrix of a (K, K -M ) GRS code with distinct parameters ω 1 , . . . , ω K and non-zero multipliers v 1 , . . . , v K [13]. The above construction ensures that such a GRS code has a specific codeword with support S ∪ W , namely K-M i=1 p i-1 g i , where the ith codeword symbol is equal to c i for i ∈ S, and is non-zero for i = W .
Step 2: The user sends the query Q [W,S,C] = {Q 1 , . . . , Q K-M } to the server.
Step 3: By using Q i , the server computes
and it sends the answer A [W,S,C] = {A 1 , . . . , A K-M } to the user.
Note that A i 's are the parity check equations of a (K, M ) GRS code which is the dual code of the GRS code generated by the matrix G defined earlier.
Step 4: Upon receiving the answer, the user retrieves X W by subtracting off the contribution of their side information
Consider a scenario where the server has K = 4 messages X 1 , . . . , X 4 ∈ F 5 , and the user demands the message X 1 and has a coded side information of size
First, the user chooses K = 4 distinct elements ω 1 , . . . , ω 4 from F 5 , say (ω 1 , ω 2 , ω 3 , ω 4 ) = (0, 1, 2, 3). Then, the user constructs the polynomial p
The user then computes v j for j ∈ S, i.e., v 2 and v 3 , by setting v 2 = c2 p(ω2) = 2 and v 3 = c3 p(ω3) = 4, and chooses v j for j ∈ S, i.e., v 1 and v 4 , at random (from F × 5 ). Suppose that the user chooses v 1 = 1 and v 4 = 2. Then, the user constructs
and sends the answer A = {A 1 , A 2 } back to the user. Then, the user computes
and recovers X 1 by subtracting off the side information X 2 +X 3 . For this example, the rate of the proposed protocol is 1/2. Lemma 3. The Specialized GRS Code protocol is a PIR-PCSI-I protocol, and achieves the rate (K -M ) -1 .
Proof: Since the matrix G, defined in Step 1 of the protocol, generates a (K, K -M ) GRS code which is an MDS code, the rows of G are linearly independent, and accordingly, A 1 , . . . , A K-M are linearly independent combinations of X 1 , . . . , X K , which are themselves independently and uniformly distributed over F q l . Thus, A 1 , . . . , A K-M are independently and uniformly distributed over F q l . Since H(X i ) = L for all i, then H(A i ) = L for all i, and
S ∈ S such that W ∈ S, and C ∈ C. Since W and S are jointly distributed uniformly (given that W ∈ S) and C is uniformly distributed, then
From the construction, it should be obvious that the recoverability condition is satisfied. The (W, S)-privacy condition is also satisfied because: (i) the (K, K -M ) GRS code, generated by the matrix G, is an MDS code, and thereby, the minimum (Hamming) weight of a codeword is K -(K -M ) + 1 = M + 1; and (ii) there exist the same number of minimum-weight codewords for any support of size M + 1 [13]. Thus, for any W ∈ [K], S ∈ S such that W ∈ S, the dual code, defined by the parity check matrix G, contains the same number of parity check equations (with support W ∪ S) from each of which the candidate demand message X W can be recovered, given a potential side information Y [S,C] for some C ∈ C.
In this section, we give an information-theoretic proof of converse for Theorem 2. ) such that W ∈ S. Let E denote the event that W ∈ S. We need to show that H(A|E) ≥ (K -M + 1)L. Let I be the set of all
There are two cases: (i) I = ∅, and (ii) I = ∅.
Case (i): Since X I and (Q, E) are independent, and H(X I |A, Q, E) = 0 (by assumption), then
, and S j {N + 1, N + j + 1, . . . , N + j + M -1} for j ∈ J. By Lemma 1, for any j ∈ J, there exists C j ∈ C (and
where c j is the coefficient of X N +1 in Y j . For any scalar-linear protocol (i.e., the answer A consists only of scalar-linear combinations of messages in X), it is easy to see that either H(Z j |A, Q) = 0 or H(Z j + cX N +1 |A, Q) = 0 for some c ∈ F × q \ {c j }. (Otherwise, the server learns that W and S cannot be N + 1 and S j , respectively. This obviously violates the (W, S)privacy condition.) Thus, H(Z j |A, Q, X N +1 ) = 0. Let Z J {Z j } j∈J . Then, we have
where (7) holds since H(Z j |A, Q, X N +1 ) = 0 for all j ∈ J (by assumption); and (8) follows because Z J is independent of (Q, E, X I , X N +1 ), noting that Z J , X I , and X N +1 are linearly independent (by construction). By the linear independence of Z j 's for all j ∈ J, it follows that H(Z J ) = (K -M -N + 1)L. By ( 6) and ( 8 [K -M ], and S j {1, j + 2, . . . , j + M } for j ∈ J. Similarly as in the case (i), we define Y j (and Z j ) for all j ∈ J, where X N +1 is replaced by X 1 everywhere.
For any scalar-linear protocol, by a similar argument as before, it can be shown that H(Z j |A, Q, X 1 ) = 0 for all j ∈ J. Let Z J {Z j } j∈J . Then, we can write
= H(X 1 |Q, E, Y) + H(A|Q, E, Y, X 1 ) = H(X 1 ) + H(A|Q, E, Y, X 1 )
= H(X 1 ) + H(Z J |Q, E, Y, X 1 )
+ H(A|Q, E, Y, X 1 , Z J ) ≥ H(X 1 ) + H(Z J ) (11) where (9) follows because H(X 1 |A, Q, E, Y) = 0 (by the recoverability condition); (10) holds since H(Z j |A, Q, X 1 ) = 0, and subsequently, H(Z j |A, Q, E, Y, X 1 ) = 0, for all j ∈ J; and (11) follows because Z J is independent of (Q, E, Y, X 1 ) (due to the linear independence of Z J , Y, and X 1 ). Since |J|= K -M , we have H(Z J ) = (K -M )L (noting that Z j 's are linearly independent), and thereby, H(A|E) ≥ L + (K -M )L = (K -M + 1)L.
In this section, we propose a PIR-PCSI-II protocol, which is a slightly modified version of the Specialized GRS Code protocol, that achieves the rate (K -M + 1) -1 .
Modified Specialized GRS Code Protocol: This protocol consists of four steps, where the steps 2-4 are the same as Steps 2-4 in the Specialized GRS Code protocol (Section IV-B), except that M is replaced with M -1 everywhere. The step 1 of the proposed protocol is as follows:
Step 1: The user first constructs a polynomial p(x) = K-M i=0 p i x i i ∈S (x -ω i ), and then constructs K -M + 1 sequences Q 1 , . . . , Q K-M +1 , each of length K, defined as
where v i 's are chosen as follows. For any i ∈ S \ W , v i = ci p(ωi) where c i is the coefficient of X i in Y [S,C] ; v W = c p(ωW ) for a randomly chosen element c from F × q \ {c W } where c W is the coefficient of X W in Y [S,C] ; and for any i ∈ S, v i is chosen at random from F × q . Lemma 5. The Modified Specialized GRS Code protocol is a PIR-PCSI-II protocol, and achieves the rate (K -M +1) -1 .
Proof: The proof, omitted to avoid repetition, follows from the same lines as in the proof of Lemma 3 where M is replaced by M -1, and W ∈ S is replaced by W ∈ S.