I. INTRODUCTION

Private Information Retrieval (PIR) is a fundamental problem in information security and privacy. The goal of the PIR is to retrieve data from one or more remote servers while protecting the identity of the retrieved data items. The problem has attracted significant attention within the computer science community since the 1990s (see, e.g., [1]) and more recently has become a very active research topic in the information theory community (see, e.g., [2]- [6] and references therein). This research has produced many interesting results on several important variations of the PIR problem, including PIR in the presence of colluding servers [6]- [12], PIR from coded data [13]- [15], as well as multi-message PIR [16], [17].

This paper presents new approaches for the design of multiserver PIR schemes that leverage prior side information. The problem is inspired by PIR scenarios where a user has prior Ningze Wang and Alex Sprintson are with the Department of Electrical and Computer Engineering, Texas A&M University (E-mail: {ningzewang, spalex}@tamu.edu). Anoosheh Heidarzadeh is with the Department of Electrical and Computer Engineering, Santa Clara University, (E-mail: aheidarzadeh@scu.edu).

information about the data stored on the servers and would like to leverage it to maximize the download rate.

The PIR setting with side information was initially studied in single-server scenarios (refer to, e.g., [18]- [30]). This line of work has been extended to multi-server settings, including cache-aided PIR [31]- [33], PIR with side information [34]- [36], PIR with private side information [37]- [39], PIR with private coded side information [40], and multi-message PIR with private side information [41]. In PIR problems with private side information, it is required to prevent any server from identifying the side information messages. This requirement results in a lower rate than in scenarios where the side information messages do not need to be kept private.

The most relevant to our work are the papers by Kadhe et al. [35] and Li and Gastpar [36]. In particular, [35] extends the PIR scheme developed for the single-server PIR problem for the more general multi-server setting. Later, [36] claimed a converse bound on the maximum achievable download rate for the multi-server PIR in the presence of side information.

In this work, we make the following contributions. First, we revisit the PIR problem with side information and present a new technique to leverage side information for the construction of more efficient multi-server PIR schemes. Our approach generalizes the probabilistic method due to Tian et al. [4] for settings with side information. The key idea is that since the identity of the side information messages does not need to be kept private, the information retrieval scheme does not need to be symmetric. In particular, the information requested from a server does not need to have an equal probability across different sets of demand and side information. This offers more flexibility in designing the retrieval scheme, enabling us to achieve higher rates compared to symmetric schemes.

Second, we use this approach to construct an efficient randomized algorithm that determines the linear combinations of sub-packets that need to be recovered from each server. Our scheme achieves the highest known download rate for this problem. In particular, the rate of our scheme is higher than that of the scheme in [35] when M + 1 does not divide K, where M is the number of side information messages and K is the total number of messages stored at the servers. In addition, our scheme requires a much lower sub-packetization level of N -1, compared to the sub-packetization level of N K required by the existing solutions, where N is the number of servers. A lower degree of sub-packetization has many practical advantages, including reduced complexity. Moreover, the rate achieved by our scheme invalidates the converse bound on the maximum achievable download rate claimed in [36].

II. PROBLEM SETUP

We use bold-face symbols to represent random variables and regular symbols for their realizations. For an integer i ≥ 1, we denote the set {1, . . . , i} by [i], and denote the set {0} ∪ [i] by [0 : i]. For any set, we refer to its subsets of size k as k-subsets. We denote the ith component of a vector v by v(i), and denote its support, which refers to the index set of its nonzero components, by supp(v).

In this work, we revisit the problem of Private Information Retrieval with Side Information (PIR-SI), which was initially introduced in [35] and subsequently studied in [36]. For completeness, the problem formulation is presented below.

For a prime power q and an integer L ≥ 1, let F q be a finite field of order q, and F L q be the L-dimensional vector space over F q .

Consider N > 1 non-colluding servers each of which stores an identical copy of K > 1 messages X 1 , . . . , X K , where each message X i is a vector in F L q . That is, each message X i consists of L sub-packets X i,1 , . . . , X i,L , where each sub-packet X i, j is a symbol from F q . We refer to L as the sub-packetization level and q as the field size. Consider a scenario where a user wants to retrieve the message X W for some W ∈ [K], and the user has prior knowledge of M messages X S := {X i : i ∈ S} for some M-subset S ⊆ [K] \ {W}. We refer to X W as the user's demand and W as the demand's index. In addition, we refer to X S as the user's side information, S as the side information's index set, and M as the number of side information messages.

In line with prior work, we make the following assumptions in this work: (i) X 1 , . . . , X K are independent uniform random variables over F L q ; (ii) W is a uniform random variable over [K], and S is a uniform random variable over all M-subsets of [K] \ {W} given W = W; (iii) The random variables (W, S) and (X 1 , . . . , X K ) are independent; (iv) The distribution of (W, S) is known in advance to all servers; and (v) The realization (W, S) is not initially known to any server.

For each n ∈ [N], the user generates a query Q

, which is a (deterministic or stochastic) function of (W, S), and sends the query

does not reveal any information about the demand's index W to server n. That is, for all n ∈ [N], it must hold that

We refer to this requirement as the privacy condition. It should be noted that the privacy condition does not imply the privacy of the side information's index set S. That is, the query Q [W,S] n may leak some information about S to server n, while satisfying the privacy condition. This differs from the Private Information Retrieval with Private Side Information (PIR-PSI) setting considered in [37]- [39], where both the demand's index W and the side information's index set S must be kept private from each server.

Upon receiving the query

, and sends it back to the user. The answer A

The user must be able to recover their demand X W given the collection of answers A

}, the side information X S , and the realizations W and S. That is,

We refer to this requirement as the recoverability condition.

The PIR-SI problem is to design a protocol for generating a collection of queries Q [W,S] and the corresponding collection of answers A [W,S] for any given (W, S) such that both the privacy and recoverability conditions are satisfied.

We define the rate of a PIR-SI scheme as the ratio of the number of bits required by the user, i.e., H(X W ) = B := L log 2 q, to the total number of bits downloaded from all servers, i.e., ∑ N n=1 H(A

). Note that the number of bits downloaded from each server n, i.e., H(A

), is given by

where the summation is over all query realizations Q

It is important to highlight that we define rate based on the conditional entropy of each server's answer given the user's query sent to that server, i.e., H(A

). This metric accurately captures the expected number of bits downloaded from server n, because the user's query sent to server n is known to both the user and server n. In contrast, the (unconditional) entropy of the answer from each server, i.e.,

H(A [W,S] n

), which was used in previous works, e.g., in [2] and [3], for rate calculation, takes also into account the randomness of the query. This can potentially introduce excessive uncertainty, which is irrelevant to the expected number of downloaded bits. It should be noted that, regardless of which rate definition is used, the rate of the PIR-SI scheme presented in [35] remains unchanged. This is because, in this scheme, the length of the answer (i.e., the number of bits downloaded) from each server is the same for all query realizations. As a consequence, the entropy of the answer and the conditional entropy of the answer given the query are equal. However, this equivalence may not hold for PIR-SI schemes in which the answer length varies across different query realizations.

In this work, our goal is to characterize the capacity of PIR-SI, defined as the maximum achievable rate among all PIR-SI schemes, in terms of the number of servers N, the number of messages K, the number of side information messages M, the sub-packetization level L, and the field size q. We consider all values of N > 1, K > 1, 1 ≤ M ≤ K -1, and q ≥ 2. Additionally, we focus on cases with 1 ≤ L ≤ N -1. Such small values of L are particularly interesting when considering schemes that utilize linear operations at the sub-packet level and require a low sub-packetization level.

III. MAIN RESULTS

In this section, we present our main results and discuss the existing bounds on the capacity of PIR-SI for all admissible values of N, K, M, L, and q.

To simplify the notation, we define g := ⌈ K M+1 ⌉, and

.

Theorem 1. The capacity of PIR-SI with N servers, K messages, M side information messages, the sub-packetization level L = N -1, and the field size q, is lower bounded by

.

To establish this result, we present a novel PIR-SI scheme that achieves the rate R defined in (1). The retrieval process in our scheme relies on linear operations at the sub-packet level, and requires recovering no more than one linear combination of message sub-packets from each server. The distinctive aspect of our scheme lies in its randomized strategy to identify the message sub-packets to be combined and determine the specific linear combination to be recovered from each server. This strategy is carefully designed to ensure both the privacy and recoverability conditions, while taking advantage of the fact that the side information messages do not require privacy.

Theorem 2. With R defined in (1) and R * defined as

it follows that R ≥ R * for all values of N, K, and M. In particular, we have R = R * when K is divisible by M + 1, and R > R * when K is not divisible by M + 1.

Theorem 3. The capacity of PIR-SI with the same parameters as in Theorem 1, except when L < N -1, is lower bounded by R L defined as in (1), except when N is replaced by L + 1.

The proof follows from a simple two-step application of our PIR-SI scheme, and is omitted for brevity. Here, we outline the key steps of the proof. First, the user chooses L + 1 servers arbitrarily. Then, the user employs the proposed scheme designed for the case with L + 1 servers, K messages, M side information messages, and the sub-packetization level L, to privately retrieve the demand message with the help of the side information messages. This achieves the rate R L defined similarly to R as in (1) when N is replaced by L + 1.

Remark 1. Our PIR-SI scheme serves as a nontrivial extension of the PIR scheme presented in [4] to incorporate side information. In the PIR scheme of [4], the space of query realizations includes a linear combination of any subset of messages, or more generally, a linear combination of their respective subpackets with one sub-packet per message. However, in the PIR-SI setting, not all of these query realizations are necessary, and excluding certain query realizations can potentially increase the rate. Specifically, it is unnecessary to retrieve any side information message or any linear combination of any subset of side information messages. However, excluding only these query realizations can compromise privacy. This implies the need to exclude additional query realizations beyond those specifically related to side information messages. Moreover, in the PIR scheme of [4], privacy is ensured by employing a uniform probability distribution over all query realizations. However, when some query realizations are excluded, it may be necessary to introduce a non-uniform probability distribution over the remaining ones to maintain privacy. Our PIR-SI scheme maximizes the rate while ensuring privacy by identifying query realizations to exclude and optimizing the probability distribution over the remaining ones.

Remark 2. The best previously-known achievable rate for PIR-SI was reported in [35]. The PIR-SI scheme presented in [35] is based on the following approach: (i) forming g linear combinations of messages, referred to as the coded messages, each of which is the sum of a distinct subset of messages, where one of these subsets contains only the demand message and a subset of the side information messages, and (ii) privately retrieving one of these g coded messages, namely, the one containing the demand message, through the application of a capacity-achieving PIR scheme. As shown in [35], this scheme achieves the rate R * defined in (2). As evident from the result of Theorem 2, our scheme and the one in [35] achieve the same rate when M + 1 divides K, yet remarkably, our scheme achieves a higher rate when M + 1 does not divide K. The main difference between these schemes lies in determining which sub-packets of which messages must be combined in each query realization. In the scheme of [35], the query realizations are linear combinations of only g coded messages, each corresponding to a specific subset of messages. This is while our scheme incorporates many more subsets of messages to construct query realizations. Moreover, the scheme of [35] operates exclusively on the sub-packets of the underlying coded messages, where the lth sub-packet of each coded message is the sum of the lth sub-packet of the corresponding messages. In contrast, our scheme goes beyond this limitation by allowing the combination of sub-packets with different indices for any subset of messages. While this flexibility does not result in a rate increase when K is divisible by M + 1, its advantage becomes apparent when K is not divisible by M + 1. Specifically, this flexibility allows for utilizing a more efficient probability distribution over query realizations, leading to an improved rate performance.

Remark 3. The capacity of PIR-SI is obviously upper bounded by 1, which coincides with the achievable rate R when M = K -1. However, a nontrivial upper bound remains unknown for cases where 1 ≤ M ≤ K -2. It was reported in [36] that the capacity is upper bounded by R * . While R * matches R when K is divisible by M + 1, R * is strictly less than R when K is not divisible by M + 1. This shows that R * is not a valid upper bound on the capacity in non-divisible cases. Moreover, it remains unknown whether R * is indeed the capacity in divisible cases or there exists a scheme that can achieve a rate higher than R * in such cases.

IV. PROOF OF THEOREM 1

In this section, we present a new PIR-SI scheme that achieves the rate R defined in (1) for any admissible set of values of N, K, M, and q, when L = N -1.

The proposed scheme consists of two steps as outlined below.

Step 1: Given the demand's index W and the side information's index set S, the user generates N queries Q

, and sends the query Q [W,S] n to server n. The user's query to each server must specify which subpackets of which messages are to be combined and what specific combination coefficients are to be used to generate the corresponding answer. In the proposed scheme, each server's answer is either null, meaning that the server does not send an answer back to the user, or composed of a sum that includes exactly one sub-packet of every message within a designated subset of messages. Thus, the user's query to each server can be represented by a vector v ∈ [0 : N -1] K , where an allzero vector corresponds to a null answer, and any nonzero vector corresponds to a specific sum. Specifically, if v(i) is zero, it means that none of the sub-packets X i,1 , . . . , X i,N-1 contributes to the sum that forms the server's answer, and if v(i) is equal to j ̸ = 0, it means that the sub-packet X i, j contributes to the sum forming the answer of the server.

To generate the queries Q

, the user employs a randomized algorithm-which depends on W and Sto construct N vectors v 1 , . . . , v N ∈ [0 : N -1] K , and sends the vector ṽn := v π(n) to server n as the query Q , where the probability of selecting each k ∈ [0 : g -1] is equal to P k , where

. Given the value of I, the user then proceeds as follows:

1) I ̸ = g -1: First, the user randomly selects a vector a ∈ [0 : N -1] K with supp(a) ⊂ [K] \ {W} ∪ S and |supp(a)|= I(M + 1). If I = 0, the vector a is all-zero. Otherwise, if I ̸ = 0, the vector a corresponds to a sum of I(M + 1) sub-packets, each belonging to one message from the set of interference messages, i.e., messages that are neither demand nor side information.

Next, the user randomly selects a vector b ∈ [0 : N -1] K with supp(b) = S. The vector b corresponds to a sum of M sub-packets, each belonging to one side information message. Then, the user forms the vectors v 1 , . . . , v N by setting

where c j ∈ [0 : N -1] K represents the vector corresponding to the jth sub-packet of the demand message X W . That is, c j (i) = 0 for i ∈ [K] \ {W}, and c j (W) = j.

2) I = g -1: First, the user randomly selects a vector a ∈ [0 : N -1] K with supp(a) = [K] \ {W} ∪ S. The vector a corresponds to a sum of K -M -1 sub-packets, each belonging to one interference message.

Next, the user randomly selects a vector b 1 ∈ [0 : N -1] K with supp(b 1 ) ⊆ S and |supp(b 1 )|= g(M + 1) -K. The user then randomly selects a vector b 2 ∈ [0

The vectors b 1 and b 2 respectively correspond to a sum of g(M + 1) -K and K -(g -1)(M + 1) -1 sub-packets, each belonging to one side information message. Then, the user forms the vectors v 1 , . . . , v N by setting

where c 1 , . . . , c N-1 are defined as before.

Step 2: Upon receiving the query Q

if the vector ṽn is nonzero, server n computes the sum

and sends back Ỹn to the user as the answer A [W,S] n . Otherwise, if the vector ṽn is all-zero, server n does not send back any answer to the user, and the user sets Ỹn = 0. Lemma 1. The proposed scheme satisfies both the privacy and recoverability conditions and achieves the rate R in (1).

Proof: The proof can be found in the extended version of this work, [42].

V. PROOF OF THEOREM 2

We need to show that (i) R = R * when K is divisible by M + 1, and (ii) R > R * when K is not divisible by M + 1, where R and R * are defined in (1) and (2), respectively.

First, consider the case (i). In this case, g = K/(M + 1).

Now, consider the case (ii). In this case, g > K/(M + 1).

, and consequently,

VI. AN ILLUSTRATIVE EXAMPLE

Consider N = 3 servers, each storing K = 3 messages X 1 , X 2 , X 3 , where each message X i consists of L = N -1 = 2 sub-packets X i,1 and X i,2 . Suppose that a user wants to retrieve one message, say, X 1 , and the user knows M = 1 other message, say, X 2 . That is, W = 1 and S = {2}.

To generate the N = 3 queries, one for each server, the user proceeds as follows to construct N

Noting that g = ⌈K/(M + 1)⌉ = 2, the user begins by randomly selecting I ∈ [0 : g -1] = {0, 1}, where the probability of I = 0 (or I = 1) is P 0 (or P 1 ). In this example, Given the vectors a and b (or b 1 and b 2 ) and the N -1 = 2 vectors c 1 = [1, 0, 0] and c 2 = [2, 0, 0] with supp(c 1 ) = supp(c 2 ) = {W} = {1}, the user constructs the vectors v 1 , v 2 , v 3 by using the algorithm described in Step 1. In this example, there are six feasible sets of vectors {v 1 , v 2 , v 3 } in total, with two sets for I = 0 and the remaining four sets for I = 1. The table presented below enumerates all six sets of vectors {v 1 , v 2 , v 3 } along with their corresponding probabilities P {v 1 ,v 2 ,v 3 } , where the first two rows correspond to I = 0, and the last four rows correspond to I = 1. 1 v 2 v 3 P {v 1 ,v 2 ,v 3 } [0, 0, 0] [1, 1, 0] [2, 1, 0] P 0 /2 [0, 0, 0] [1, 2, 0] [2, 2, 0] P 0 /2 [0, 1, 1] [1, 1, 1] [2, 1, 1] P 1 /4 [0, 2, 1] [1, 2, 1] [2, 2, 1] P 1 /4 [0, 1, 2] [1, 1, 2] [2, 1, 2] P 1 /4 [0, 2, 2] [1, 2, 2] [2, 2, 2] P 1 /4

Followed by constructing v 1 , v 2 , v 3 , the user randomly selects a permutation π : [3] → [3], and sends the query vector v π(n) to server n. Upon receiving v π(n) , if v π (n) is nonzero, server n sends back the answer sum Y π(n) = ∑ i∈supp(v π(n) ) X i,v π(n) (i) ; otherwise, if v π(n) is all-zero, no answer is sent back, and Y π(n) = 0. In this example, there are six feasible sets of sums {Y 1 , Y 2 , Y 3 }, one for each set of vectors {v 1 , v 2 , v 3 }.

Table I lists all six sets of sums {Y 1 , Y 2 , Y 3 } and their probabilities P {Y 1 ,Y 2 ,Y 3 } . For completeness, we also present Table II which lists all six sets of sums {Y 1 , Y 2 , Y 3 } and their probabilities P {Y 1 ,Y

2 ,Y 3 } , for the general case of W = i, S = { j}, and [K] \ {W} ∪ S = [3] \ {i, j} = {k}, where {i, j, k} is an arbitrary permutation of [3].