Private Information Retrieval with Private Coded Side Information: The Multi-Server Case
Fatemeh Kazemi Esmaeil Karimi Anoosheh Heidarzadeh Alex Sprintson



















3.75

plain






2028Private Information Retrieval with Private Coded Side Information: The Multi-Server Case
    Fatemeh Kazemi, Esmaeil Karimi, Anoosheh Heidarzadeh, and Alex SprintsonThe authors are with the Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77843 USA (E-mail: {fatemeh.kazemi, esmaeil.karimi, anoosheh, spalex}@tamu.edu).
    December 30, 2023
==================================================================================================================================================================================================================================================================================



plain



In this paper, we consider the multi-server setting of Private Information Retrieval with Private Coded Side Information (PIR-PCSI) problem. In this problem, there is a database of K messages whose copies are replicated across N servers, and there is a user who knows a random linear combination of a random subset of M messages in the database as side information. The user wishes to download one message from the servers, while protecting the identities of both the demand message and the messages forming the side information. We assume that the servers know the number of messages forming the user's side information in advance, whereas the indices of these messages and their coefficients in the side information are not known to any of the servers a priori. 

Our goal is to characterize (or derive a lower bound on) the capacity, i.e., the maximum achievable download rate, for the  two settings. In the first setting, the set of messages forming the linear combination available to the user as side information, does not include the user's demanded message. For this setting, we show that the capacity is equal to (1+1/N+…+1/N^K-M-1)^-1. In the second setting, the demand message contributes to the linear combination available to the user as side information, i.e., the demand message is one of the  that form the user's side information. For this setting, we show that the capacity is lower-bounded by (1+1/N+…+1/N^K-M)^-1. The proposed achievability schemes and proof techniques leverage ideas from both our recent methods proposed for the single-server PIR-PCSI problem as well as the techniques proposed by Sun and Jafar for multi-server private computation problem.







§ INTRODUCTION

In the Private Information Retrieval (PIR) problem, a database of K messages are 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 <cit.>. 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 <cit.>. However, when the user has some side information about the messages in the database <cit.> or when the servers do not fully collude <cit.>, the privacy can be achieved in a more efficient manner in terms of minimizing 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) W-privacy, which requires that the identity of the user's demanded message(s) be protected, and (ii) (W,S)-privacy, which requires that  the identities of both the user's demanded message(s) and the message(s) in the user's side information be 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) where W-privacy or (W,S)-privacy is required, respectively. The single-server settings of these problems were studied in <cit.>, and their multi-server settings were studied in <cit.>. In <cit.> and <cit.>, 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 W-privacy or (W,S)-privacy is required, respectively. Also,  in <cit.>, 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 user's demanded message and the messages forming the user's side information, while minimizes the download cost. The servers are assumed to know the number of messages contributing to the user's side information beforehand. However, the indices and the coefficients of the messages in 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. 



 §.§ Main Contributions




We consider two settings of the PIR-PCSI problem depending on whether the user's demanded message is one of the messages forming 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 forming the user's side information. For this setting, we prove that the capacity is equal to (1+1/N+…+1/N^K-M-1)^-1. Interestingly, the capacity in this setting is equal to the capacity of multi-server PIR-PSI problem <cit.> 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 PIR-PSI which is given by (1+1/N+…+1/N^K-M-1)^-1 (see <cit.>). 

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 <cit.> 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 <cit.> for single-server PIR-PCSI. 

The main ideas of our achievability scheme are as follows. First, the user utilizes the Specialized GRS Code scheme of <cit.> for single-server PIR-PCSI to construct K-M independent super-messages which are some 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 <cit.> for the constructed K-M super-messages in such a way that the user can privately download one of KM+1 linear combinations of the K-M super-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 forming the user's side information, we show that the capacity is lower-bounded by (1+1/N+…+1/N^K-M)^-1. The proof is based on a new achievability scheme that leverages the PC scheme of <cit.> for multi-server private computation, combined with our Modified Specialized GRS Code scheme proposed in <cit.> for single-server PIR-PCSI. 








  







§ 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 𝔽_q be a finite field for some prime q, and let 𝔽_q^×≜𝔽_q∖{0} be the multiplicative group of 𝔽_q. Let 𝔽_q^m be an extension field of 𝔽_q for some integer m≥ 1. 



Consider N non-colluding identical servers, each of which stores K messages X_1,…,X_K, where 𝐗_i is independently and uniformly distributed over 𝔽_q^m, i.e., for all i∈ [K], it holds that 
    H(𝐗_i) = L≜ mlog_2 q,   and  H(𝐗_1,…,𝐗_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}∈𝒮 and some C ≜{c_i_1,…,c_i_M}∈𝒞, where 𝒮 is the set of all M-subsets of [K], and 𝒞 is the set of all length-M sequences with elements from 𝔽^×_q. We call W the demand index, X_W the demand, Y^[S,C] the side information, S the side information index set, and M the side information size. 


We assume that 𝐒 is uniformly distributed over 𝒮, and that 𝐂 is uniformly distributed over 𝒞. Also, two different models for the conditional distribution of 𝐖 given 𝐒=S are considered: 

    
  * Model I: 𝐖 is uniformly distributed over [K]∖ S;
    
  * Model II: 𝐖 is uniformly distributed over S.






    p_𝐖|𝐒(W|S) = 
    {[     1/K-M,       W∉S,;         0, otherwise. ].
 




    p_𝐖|𝐒(W|S) = 
    {[       1/M,      W∈ S,;         0, otherwise; ].
 


It is assumed that 1≤ M ≤ K-1 and 2≤ M≤ K for Model I and Model II, respectively. Note that for both models it holds that 𝐖 is uniformly distributed over [K]. 


We assume that no server knows the realizations of 𝐒,𝐂,𝐖 in advance. In contrast, we assume that all servers know the considered model (i.e., whether 𝐖∉𝐒 or 𝐖∈𝐒), the side information size M,  the distributions of 𝐒 and 𝐂, and the conditional distribution of 𝐖 given 𝐒. 





For any S, C, W, in order to retrieve X_W, the user generates N queries Q_1^[W,S,C],…, Q_N^[W,S,C], and sends to the n-th server the query Q_n^[W,S,C]. Each query Q_n^[W,S,C] is assumed to be a (potentially stochastic) function of W, S, C, and Y^[S,C]. Upon receiving the query Q_n^[W,S,C], the n-th server responds to the user with an answer A_n^[W,S,C]. The answer A_n^[W,S,C] is a (deterministic) function of the query Q_n^[W,S,C] and the messages in X_[K]≜{X_1,…,X_K}. Note that for all n∈ [N], it holds that


    (𝐖,𝐒) → (𝐐_n^[𝐖,𝐒,𝐂],𝐗_[K]) →𝐀_n^[𝐖,𝐒,𝐂]
 forms a Markov chain, and 
    H(𝐀_n^[𝐖,𝐒,𝐂]| 𝐐_n^[𝐖,𝐒,𝐂],𝐗_[K]) = 0.
 


The answers A_1^[W,S,C],…,A_N^[W,S,C] from all servers along with the side information Y^[S,C] and the queries Q_1^[W,S,C],…,Q_N^[W,S,C] must enable the user to retrieve the demand X_W, i.e.,

    H(𝐗_𝐖| 𝐀^[𝐖,𝐒,𝐂],𝐐^[𝐖,𝐒,𝐂], 𝐘^[𝐒,𝐂],𝐖,𝐒,𝐂)=0,

where A^[W,S,C]≜{A_1^[W,S,C],…,A_N^[W,S,C]}, and Q^[W,S,C]≜{Q_1^[W,S,C],…,Q_N^[W,S,C]}. This condition is referred to as the recoverability condition.

In addition, the queries Q_1^[W,S,C], …,Q_N^[W,S,C] must not reveal any information about the user's demand index W and side information index set S to any server,

    I(𝐖,𝐒; 𝐐_n^[𝐖,𝐒,𝐂],𝐀_n^[𝐖,𝐒,𝐂],𝐗_[K])=0  ∀ n ∈ [N].
 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_1^[W,S,C],…,Q_N^[W,S,C]} for any given W,S,C. The protocol also prescribes, for all n ∈ [N], how the n-th server generates the answer A_n^[W,S,C], given Q_n^[W,S,C] and X_[K]. 

A protocol that satisfies both the (W,S)-privacy and recoverability conditions for all W,S,C with W∉S (or W∈ S), is referred to as a PIR-PCSI–I (or PIR-PCSI–II) protocol. The problem of designing a PIR-PCSI–I (or PIR-PCSI–II) protocol is referred to as the PIR-PCSI–I (or PIR-PCSI–II) problem. 






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(𝐀^[𝐖,𝐒,𝐂]).  



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). 



§ MAIN RESULTS


In this section, we present our main results. Theorem <ref> characterizes the capacity of the PIR-PCSI–I problem C_(W,S)- I, and Theorem <ref> presents a lower-bound on the capacity of the PIR-PCSI–II problem C_(W,S)- II. The proofs of theorems <ref> and <ref> are given in sections <ref> and <ref>, respectively.


The capacity of the PIR-PCSI–I problem with N servers, K messages, and side information size 1≤ M ≤ K-1 is given by

    C_(W,S)- I= (1+1/N+…+1/N^K-M-1)^-1.




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 <cit.> 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 <ref>, we only need to prove the achievability which is presented in Section <ref>.
Notably, our results show that having only one random linear combination of messages instead of multiple uncoded messages does not decrease the capacity, either. 






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

    C_(W,S)- II≥(1+1/N+…+1/N^K-M)^-1.




This result is interesting because it shows that the lower-bound 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 lower-bound of Theorem <ref>. It should be noted that the tightness of this lower bound remains open in general. 










§ THE  PIR-PCSI-I  PROBLEM


In this section, we complete the proof of Theorem <ref> by proposing an achievability scheme for arbitrary N, K≥ 1 and 0≤ M≤ K-1 that achieves the rate (1+1/N+…+1/N^K-M-1)^-1. 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 <cit.> for single-server PIR-PCSI problem and the Private Computation (PC) scheme of <cit.> for multi-server private computation problem. 

For the proposed protocol, we assume that q≥ K, and each message X_i consists of m= N^KM+1 symbols over 𝔽_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 <cit.> to first construct a polynomial p(x) = ∑_i=0^K-M-1 p_i x^i ≜∏_i∉S∪ W (x-ω_i) where ω_1,…,ω_K are K arbitrarily chosen distinct elements from 𝔽_q, and then construct r ≜ K-M vectors u_1,…,u_r, each of length K, such that u_i = [β_1ω_1^i-1 ,…,β_Kω_K^i-1] for i∈ [r], where β_j=c_j/p(ω_j) for j∈ S, and β_j is a randomly chosen element from 𝔽_q^× for j∉S. 






Step 2: Let X̂_i≜∑_j=1^Kβ_jω_j^i-1 X_j for i∈ [r]. Each X̂_i is referred to as a super-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 super-message X̂_i. Let F≜KM+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 <cit.> 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 𝔽^×_q, such that for every k∈ [q-1], Z^k_f can be written as a linear combination of the super-messages X̂_1,…,X̂_r. Let v^k_f≜ [v^k_f,1,…,v^k_f,r] be a vector of length r such that Z^k_f = ∑_i=1^r v^k_f,iX̂_i. Note that, for each f ∈ [F], Z^1_f,Z^2_f,…,Z^q-1_f are the same up to a scalar multiple, i.e., for each k∈ [q-1], Z^k_f = α_k Z^1_f, or equivalently, v^k_f = α_k v^1_f, for some distinct α_k∈𝔽^×_q. 
For each f∈ [F], let i_f≜min(J_f). Note also that for every f∈ [F], there exists a unique k_f∈ [q-1] such that the coefficient of the message X_i_f in the linear combination Z^k_f_f is equal to 1. The user then constructs F vectors v_1,…,v_F, each of length r, such that v_f = v^k_f_f. (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 {v^k_f}_k∈ [q-1].) Let Z_f≜ Z^k_f_f for f∈ [F]. Each Z_f is referred to as a (linear) function. Note that v_f is the vector of coefficients of the super-messages {X̂_i}_i∈ [r] in the function Z_f. 



Step 3: The user sends to all servers the vectors u_1,…,u_r (associated with the super-messages X̂_1,…,X̂_r), 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 <cit.> 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 r=K-M super-messages {X̂_i}_i∈ [r] and the F functions {Z_f}_f∈ [F] 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 𝔽^×_q-linear combination (i.e., a linear combination with non-zero 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 𝔽_q^×-linear combination of the messages {X_i}_i ∈ W∪ S.) To be more specific, each server first constructs the super-messages {X̂_i}_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 super-messages {X̂_i}_i∈ [r] and the coefficient vectors {v_f}_f∈ [F] (defined in Step 3). Note that each function Z_f for f∈ [F] consists of m=N^F 𝔽_q-symbols where N is the number of servers. Then, each server sends to the user m(1/N+1/N^2+…+1/N^K-M) carefully designed linear combinations of all 𝔽_q-symbols associated with all functions {Z_f}_f∈ [F]. 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 <cit.>.   


The user and the N servers leverage the PC protocol for r independent super-messages in such a way that the user can download one of F=KM+1 linear combinations {W_f}_f∈ [F] of the r independent super-messages, defined as W_f=∑_k=1^rα_f,kX̂_k for f ∈ [F], where the support of each linear combination W_f for f ∈ [F] is a distinct subset of [K] of size M+1. How the values of  α_f,k are defined? It should be noted that the construction by the Specialized GRS Code Protocol <cit.> ensures that there exists a set of coefficients α_f,k for all f ∈ [F] and k ∈ [r] such that the set of the supports of the functions W_f for all f ∈ [F] created based on these coefficients, be equal to the set of all subsets of [K] of size M+1. Specifically, the construction by the Specialized GRS Code Protocol guarantees that there exists a specific set of coefficients {α_f,1,α_f,2,…,α_f,r} for some f ∈ [F], say f=g, where α_g,k=0 for k ∉(S∪ W), α_g,k=c_k for k ∈ S, and α_g,k≠ 0 for k=W. I do not understand this sentence - it requires more clarifications. The user retrieves X_W by subtracting off the contribution of its side information Y^[S,C] from W_g=∑_k=1^rα_g,kX̂_k.











(PC Protocol <cit.>) Suppose there are N = 2 servers and K = 2 messages. Suppose the user wishes to privately compute one of the following F = 4 functions.


[ W_1=2X_1+X_2,   W_2=X_1+2X_2;      W_3=X_1+4X_2,   W_4=X_2;                              ]


Suppose the user is interested in retrieving W_1. The protocol assumes that each of the messages consists of L = N^F= 16 bits. Let π represents a permutation over [L]. Let u_f(i)=σ_i W_f(π(i)) for all f ∈ [F], i ∈ [L], where W_f(π(i)) are the bits from message W_f, permuted by π, and u_f(i) are the corresponding signed versions obtained by scaling with σ_i ∈{+1,-1}. For this example, let (a_i,b_i,c_i,d_i)=(u_1(i),u_2(i),u_3(i),u_4(i)) for all i ∈ [L]. It should be noted that unlike the Sun-Jafar Protocol presented in <cit.> where independent random permutations are applied to the bits of each message, in PC Protocol, the same permutation π is applied to the bits of all messages. Also, the same sign variable σ_i is applied to the bits from different messages that have the same index. Both π and σ_i are generated privately, independently and uniformly by the user such that they are not known to the
servers. The user will start with the query structure of the Sun-Jafar Protocol, and then modifies the query according to the Index assignment and Sign assignment processes, which are both elaborated in <cit.>. Then, it requests the bits from the first server (S_1) and the second server (S_2) as given in Table <ref>.


 


As can be seen, 15 symbols are queried from each server. However, based on the information obtained from the other server, 3 symbols are redundant. Thus, the user can download 12 generic combinations of these 15 symbols. The PC Protocol satisfies both the recoverability and W-Privacy conditions. Because, the user can decode the 16 bits of W_1 by downloading 24 bits (12 bits per server), and each of the two servers cannot distinguish which function is requested by the user.



Example 1. (Multi-Server PIR-PCSI–I protocol) Assume that there are N = 2 servers, K=4 messages from 𝔽_5^16, and M=2. Note that each message consists of m= N^KM+1= 16 symbols from 𝔽_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 𝔽_5. Suppose that the user chooses ω_1=0, ω_2=1, ω_3=2, ω_4=3. Then, the user constructs the polynomial p(x) = ∏_i∉S∪ W (x-ω_i)=x-ω_4=x-3. The user then computes β_j for j∈ S, i.e., β_2 and β_3, by setting β_2=c_2/p(ω_2)=2 and β_3=c_3/p(ω_3)=4, and chooses β_j for j∉S, i.e., β_1 and β_4, at random (from 𝔽^×_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 u_i=[β_1ω_1^i-1,…,β_Kω_K^i-1] for i∈{1,2}. That is, the user constructs u_1=[1,2,4,2] and u_2=[0,2,3,1]. For set J_1={1,2,3}, there exist exactly q-1=4 vectors v^k_1 = [k,3k] for k∈{1,…,4} such that ku_1+3ku_2=k[1,3,3,0].

It should be noted that there exists no other vector v=[v_1,v_2] such that the support of the vector v_1u_1 + v_2u_2 is J_1 = {1,2,3}. Note that the coefficient of the message X_i_1=X_1 (i.e., i_1=min(J_1)=1) in the  Z_1 is equal to 1 when k=1. Thus, the user constructs the vector v_1=v^1_1=[1,3]. Similarly, the user  the vectors v_2=[1,2], v_3=[1,4] and v_4=[0,3]. Then, the user sends to all servers the vectors u_1 and u_2 (associated with the super-messages X̂_1 and X̂_2), 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 two super-messages X̂_1=X_1+2X_2+4X_3+2X_4 and X̂_2=2X_2+3X_3+X_4. Then, it constructs the functions Z_1,…,Z_4 using the super-messages X̂_1 and X̂_2 and the coefficient vectors v_1,…,v_4 as follows: 

    [ Z_1=X̂_1+3X̂_2=X_1+3X_2+3X_3;  Z_2=X̂_1+2X̂_2=X_1+X_2+4X_4;   Z_3=X̂_1+4X̂_2=X_1+X_3+X_4;      Z_4=3X̂_2=X_2+4X_3+3X_4;                              ]



Finally, the user and the servers apply the PC scheme of <cit.> for two super-messages X̂_1, X̂_2 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 𝔽^×_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 u_f(i)≜σ_i Z_f(π(i)) for f ∈ [4] and i ∈ [16], where Z_f(π(i)) is the π(i)-th 𝔽_5-symbol of Z_f, and σ_i is a randomly chosen element from {-1,+1}. 
For simplifying the notation, let (a_i,b_i,c_i,d_i)=(u_1(i),u_2(i),u_3(i),u_4(i)) for all i ∈ [16]. The user then 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 <ref> <cit.>, from each of the servers (S1 and S2). 

As shown in <cit.>, 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_1,b_1,c_1,d_1}, any 2 symbols suffice to recover the other 2 symbols. For example, c_1 and d_1 can be obtained from a_1 and b_1. (Note that Z_3 and Z_4 can be written as a linear combination of Z_1 and Z_2.) Thus, the server S1 needs to send two arbitrary symbols from {a_1,b_1,c_1,d_1}. In addition, given any 2 symbols from {a_2,b_2,c_2,d_2}, any 5 symbols among the 6 symbols {a_3-b_2,a_4-c_2,a_5-d_2,b_4-c_3,b_5-d_3,c_5-d_4} queried from S1 would suffice to recover the remaining symbol. For example, c_5-d_4 can be obtained from the symbols {a_3-b_2,a_4-c_2,a_5-d_2,b_4-c_3,b_5-d_3,b_2,d_2} (for details, see <cit.>). 
Thus, each of the servers S1 and S2 needs to send to the user only 12 symbols. In particular, S1 transmits 2 arbitrary symbols from {a_1,b_1,c_1,d_1}, 5 arbitrary symbols from {a_3-b_2,a_4-c_2,a_5-d_2,b_4-c_3,b_5-d_3,c_5-d_4}, and the 4 symbols {a_9-b_7+c_6,a_10-b_8+d_6,a_11-c_8+d_7,b_11-c_10+d_9}, and the symbol {a_15-b_14+c_13-d_12}; and S2 transmits 2 arbitrary symbols from {a_2,b_2,c_2,d_2}, 5 arbitrary symbols from {a_6-b_1,a_7-c_1,a_8-d_1,b_7-c_6,b_8-d_6,c_8-d_7}, and the 4 symbols {a_12-b_4+c_3,a_13-b_5+d_3,a_14-c_5+d_4,b_14-c_13+d_12}, and the symbol {a_16-b_11+c_10-d_9}. 











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 𝔽_5), according to the proposed protocol, the user downloads 24 symbols (over 𝔽_5) from both servers, and hence the rate of the proposed protocol is 16/24=2/3. 


Note that for every 3-subset {X_j_1,X_j_2,X_j_3} 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_j_1,X_j_2,X_j_3. 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.  




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.




Since the messages 𝐗_[K] are uniformly and independently distributed over 𝔽_q^m, and
{X̂_1,…,X̂_r} are linearly independent combinations of the messages in X_[K], thus {𝐗̂_1,…,𝐗̂_r} are uniformly and independently distributed over 𝔽_q^m as well, i.e., H(𝐗̂_1) = … = H(𝐗̂_r) = mlog 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 <cit.>).

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 𝐐^[𝐖,𝐒,𝐂]_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 𝒵_f, i.e., 𝒵_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 

    (𝐖∈𝒵_f|𝐐^[𝐖,𝐒,𝐂]_n = Q_n) = 1/KM+1,
 noting that F=KM+1. 
Note that any given index W'∈ [K] is in the support of exactly K-1M functions Z_f, f∈ [F]. 
For any given f∈ [F], given 𝐐^[𝐖,𝐒,𝐂]_n = Q_n and 𝐖∈𝒵_f, from the perspective of server n, every index W'∈𝒵_f is equally likely to be the demand index. That is, for all f∈ [F], we have 

    (𝐖=W'|𝐐^[𝐖,𝐒,𝐂]_n = Q_n,𝐖∈𝒵_f) = 1/M+1,     W'∈𝒵_f,
     0,    otherwise.
 Furthermore, for any given f∈ [F] and W'∈𝒵_f, we have 

    (𝐒=S'|𝐐^[𝐖,𝐒,𝐂]_n = Q_n,𝐖∈𝒵_f,𝐖 = W') =  1,     S'= 𝒵_f∖{W'},
     0,    otherwise.
 Consider arbitrary W'∈ [K] and S'⊂ [K]∖{W'}, |S'| = M. Let f'∈ [F] be the (unique) index such that 𝒵_f' = W'∪ S'. It is easy to see that (𝐖=W',𝐒=S',𝐖∈𝒵_f|𝐐^[𝐖,𝐒,𝐂]_n = Q_n) = 0 for all f∈ [F], f≠ f'. Thus, by using (<ref>)-(<ref>), we can write 

    (𝐖=W',𝐒=S'|𝐐^[𝐖,𝐒,𝐂]_n = Q_n)
        = ∑_f∈ [F](𝐖=W',𝐒=S',𝐖∈𝒵_f|𝐐^[𝐖,𝐒,𝐂]_n = Q_n)
        = (𝐖=W',𝐒=S',𝐖∈𝒵_f'|𝐐^[𝐖,𝐒,𝐂]_n = Q_n)
        = (𝐖∈𝒵_f'|𝐐^[𝐖,𝐒,𝐂]_n = Q_n)×(𝐖 = W'|𝐐^[𝐖,𝐒,𝐂]_n = Q_n, 𝐖∈𝒵_f')
         ×(𝐒 = S'|𝐐^[𝐖,𝐒,𝐂]_n = Q_n, 𝐖∈𝒵_f',𝐖 = W')
        = 1/KM+1×1/M+1× 1 
        = M! (K-M-1)!/K!
 On the other hand, we have 

    (𝐖= W',𝐒= S')
    
       = (𝐖= W') ×(𝐒= S'| 𝐖= W') 
        =1/K×1/K-1M
        = M! (K-M-1)!/K!.
 From (<ref>) and (<ref>), for any W'∈ [K] and S'⊂ [K]∖{W'}, |S'|=M, we have 
    (𝐖= W',𝐒= S'| 𝐐^[𝐖,𝐒,𝐂]_n=Q_n) = (𝐖= W',𝐒= S').
 This completes the proof of (W,S)-privacy of the proposed protocol.




§ THE  PIR-PCSI-II  PROBLEM


In this section, we prove the result of Theorem <ref> 

by constructing a PIR-PCSI–II protocol, referred to as the Multi-Server PIR-PCSI–II protocol, for arbitrary N, K≥ 2 and 2 ≤ M≤ K that achieves the rate (1+1/N+…+1/N^K-M)^-1. 

For the proposed protocol, we assume that q≥ K, and each message is comprised of m = N^KM symbols over 𝔽_q.
 



Multi-Server PIR-CSI–II protocol: The protocol consists of four steps, where the steps 2-4 are the same as the steps 2-4 in the Multi-Server PIR-PCSI–I protocol, except that M is replaced with M-1 everywhere. The step 1 of the proposed protocol is as follows: 

Step 1: The user utilizes the Modified Specialized GRS Code protocol proposed in <cit.> to first construct a polynomial  p(x) = ∑_i=0^K-M p_i x^i ≜∏_i∉S (x-ω_i) where ω_1,…,ω_K are K arbitrarily chosen distinct elements from 𝔽_q, and then construct r ≜ K-M+1 vectors u_1,…,u_r, each of length K, such that u_i = [β_1ω_1^i-1 ,…,β_Kω_K^i-1] for i∈ [r], where β_j=c_j/p(ω_j) for j∈ S∖ W, β_W=c/p(ω_W) where c is chosen uniformly at random from 𝔽^×_q∖{c_W}, and β_j is a randomly chosen element from 𝔽_q^× for j∉S. 


Example 2. (Multi-Server PIR-CSI–II protocol) Assume that there are N = 2 servers, K=4 messages from 𝔽_5^16, and M=3. Note that each message consists of m= N^KM= 16 symbols from a finite field 𝔽_5. Suppose the user demands the message X_1 and has a coded message X_S=X_1+2X_2+3X_3 as side information, i.e., W = 1, S= {1,2,3} and C = {1,2,3} (c_1=1,c_2=2, c_3=3). 

In the first step, the user picks K=4 distinct elements ω_1,…,ω_4 from 𝔽_5. Let assume the user has chosen ω_1=0,ω_2=1,ω_3=2,ω_4=3. Then, the user constructs a polynomial p(x) = ∏_i∉S (x-ω_i)=x-ω_4=x-3. Next, the user computes β_j for j∈ S∖ W, i.e., β_2 and β_3, by setting β_2=c_2/p(ω_2)=4 and β_3=c_3/p(ω_3)=2, and computes β_W, i.e., β_1, by choosing c=2 uniformly at random from 𝔽^×_5∖{1} and setting β_1=c/p(ω_W)=1. Also, the user chooses β_j for j ∉S, i.e., β_4 at random (from 𝔽^×_5). Suppose the user has chosen β_4=3. Then, the user constructs r=K-M+1=2 vectors 𝐮_1 and 𝐮_2, each of length K=4, such that 𝐮_i=[β_1ω_1^i-1,…,β_Kω_K^i-1] for i∈{1,2}. That is, the user constructs 𝐮_1=[1,4,2,3] and 𝐮_2=[0,4,4,4]. According to the similar procedure explained in example 1, the user constructs the vectors 𝐯_1=[1,3], 𝐯_2=[1,2], 𝐯_3=[1,4] and 𝐯_4=[0,4]. The user sends to all servers the vectors 𝐮_1,𝐮_2 (associated with the super-messages X̂_1,X̂_2), and the vectors 𝐯_1,…,𝐯_4 (associated with the functions Z_1,…,Z_4). Using the coefficient vectors 𝐮_1,𝐮_2, each server first constructs 2 super-messages X̂_1=X_1+4X_2+2X_3+3X_4 and X̂_2=4X_2+4X_3+4X_4. Then, each server constructs the functions Z_1,…,Z_4 using the super-messages X̂_1,X̂_2 and the coefficient vectors 𝐯_1,…,𝐯_4, as follows:  


[  Z_1=X̂_1+3X̂_2=X_1+X_2+4X_3;  Z_2=X̂_1+2X̂_2=X_1+2X_2+X_4; Z_3=X̂_1+4X̂_2=X_1+3X_3+4X_4;        Z_4=4X̂_2=X_2+X_3+X_4;                              ]


The last step is that the user and the servers apply the PC scheme of <cit.> for two super-messages X̂_1, X̂_2 in such a way that the user can privately download Z_1. The form of the queries of the PC scheme is given in Table <ref>. Among the 15 symbols queried from each server, it can be shown that 3 symbols are redundant based on the information obtained from the other server. Thus, the user can download only 12 generic combinations of these 15 symbols from each server. In order to retrieve X_1 which has 16 symbols, the proposed scheme requires to download 24 symbols, achieving the rate of 2/3. Based on the same reasoning as discussed in Example 1, the scheme is (W,S)-private. 





The Multi-Server PIR-PCSI–II protocol satisfies the recoverability and (W,S)-privacy conditions, and achieves the rate (1+1/N+…+1/N^K-M)^-1.



The proof is similar to the proof of Lemma <ref>, and hence omitted to avoid repetition.




§ CONCLUSION

In this paper, we studied the multi-server setting of the Private Information Retrieval with Private Coded Side Information (PIR-PCSI) problem. In this problem, there is a database of K messages replicated across N servers, and there is a user who initially has a random linear combination of a random subset of M messages in the database as side information. The goal of the user is to retrieve one message from the servers, while protecting the  of both the demand message and the side information messages jointly. We considered two different models for this problem depending on whether the side information is a function of the demand message or not. First, we focused on the setting in which the side information is not a function of the demand message. For this setting, we proved that the capacity is given by (1+1/N+…+1/N^K-M-1)^-1. Then, we considered the setting in which the side information is a function of the demand message. For this setting, we show that the capacity is lower-bounded by (1+1/N+…+1/N^K-M)^-1. Our proposed achievability schemes are inspired by our recently proposed scheme for the single-server PIR-PCSI problem in conjunction with the scheme proposed by Sun and Jafar for multi-server private computation problem. 



IEEEtran

