Private Information Retrieval from MDS Coded Data with Colluding Servers: Settling a Conjecture by Freij-Hollanti et al.
Hua Sun Syed A. Jafar










Private Information Retrieval
 
from MDS Coded Data with Colluding Servers: 

Settling a Conjecture by Freij-Hollanti et al.


     Hua Sun and Syed A. Jafar 





    
==============================================================================================================================



Hua Sun (email: huas2@uci.edu) and Syed A. Jafar (email: syed@uci.edu) are with the Center of Pervasive Communications and Computing (CPCC) in the Department of Electrical Engineering and Computer Science (EECS) at the University of California Irvine. 


Private Information Retrieval
 
from MDS Coded Data with Colluding Servers: 

Settling a Conjecture by Freij-Hollanti et al.


     Hua Sun and Syed A. Jafar 





    
==============================================================================================================================





A (K, N, T, K_c) instance of the MDS-TPIR problem is comprised of K messages and N distributed servers. Each message is separately encoded through a (K_c, N) MDS storage code. A user wishes to retrieve one message, as efficiently as possible,  while revealing no information about the desired message index to any colluding set of up to  T servers. The fundamental limit on the efficiency of retrieval, i.e., the capacity of MDS-TPIR is known only at the extremes where either T or K_c belongs to {1,N}. The focus of this work is a recent conjecture by Freij-Hollanti, Gnilke, Hollanti and Karpuk which offers a general capacity expression for MDS-TPIR. We prove that the conjecture is false by presenting as a counterexample a PIR scheme for the setting (K, N, T, K_c) = (2,4,2,2), which achieves the rate 3/5, exceeding the conjectured capacity, 4/7. Insights from the counterexample lead us to capacity characterizations for various instances of MDS-TPIR including all cases with (K, N, T, K_c) = (2,N,T,N-1), where N and T can be arbitrary. 





§ INTRODUCTION

Private Information Retrieval (PIR) is the problem of retrieving one out of K messages from N distributed servers (each stores all K messages) in such a way that any individual server learns no information about which message is being retrieved. The rate of a PIR scheme is the ratio of the number of bits of the desired message to the total number of bits downloaded from all servers. The supremum of achievable rates is the capacity of PIR. The capacity of PIR was shown in <cit.> to be 

    C_   =   (1+1/N+1/N^2+⋯+1/N^K-1)^-1

The capacity of several variants of PIR has also since been characterized in <cit.>. 


The focus of this work is on a recent conjecture by Freij-Hollanti, Gnilke, Hollanti and Karpuk (FGHK conjecture, in short) in <cit.> which offers a  capacity expression for a generalized form of PIR, called MDS-TPIR. MDS-TPIR involves two additional parameters: K_c and T, which generalize the storage and privacy constraints, respectively. Instead of replication, each message is  encoded through a (K_c, N) MDS storage code, so that the information stored at any K_c servers is exactly enough to recover all K messages. Privacy must be preserved not just from each individual server, but from any colluding set of up to  T servers. MDS-TPIR is a generalization of PIR, because setting both T=1 and K_c=1 reduces MDS-TPIR to the original PIR problem for which the capacity is already known (see (<ref>)). 


The capacity of MDS-TPIR is known only at the degenerate extremes – when either T or K_c takes the value 1 or N. If either T or K_c is equal to N then by analogy to the single server setting it follows immediately that the user must download all messages, i.e., the capacity is 1/K. If K_c=1 or T=1, then the problem specializes to TPIR, and  MDS-PIR, respectively.  The capacity of TPIR (K_c=1) was shown in <cit.> to be

    C_   =   (1+T/N+T^2/N^2+⋯+T^K-1/N^K-1)^-1

The capacity of MDS-PIR (T=1) was characterized by Banawan and Ulukus in <cit.>,  as

    C_   =   (1+K_c/N+K_c^2/N^2+⋯+K_c^K-1/N^K-1)^-1

It is notable that K_c and T  play similar roles in the two capacity expressions.

The capacity achieving scheme of Banawan and Ulukus <cit.> improved upon a scheme proposed earlier by Tajeddine and Rouayheb in <cit.>. 
Tajeddine and Rouayheb also proposed an achievable scheme for  MDS-TPIR for  the T=2 setting. The scheme was generalized by Freij-Hollanti et al. <cit.> to the  (K, N, T, K_c) setting, T+K_c≤ N, where it achieves the rate 1 - T+K_c -1/N. Remarkably, the rate achieved by this scheme does not depend on the number of messages, K. In support of the plausible asymptotic (K→∞) optimality of their scheme, and based on the intuition from existing capacity expressions for PIR, MDS-PIR and TPIR, Freij-Hollanti et al. conjecture that if T+K_c≤ N, then the capacity of MDS-TPIR is given by the following expression.




FGHK Conjecture <cit.>:

    C^_ =( 1 + T+K_c -1/N + ⋯ + (T+K_c -1)^K-1/N^K-1)^-1

The conjecture is appealing for its generality and elegance as it captures all four parameters, K, N, T, K_c in a compact form. T and K_c appear as interchangeable terms,  and the capacity expression appears to be a natural extension of the  capacity expressions for TPIR and MDS-PIR. Indeed, the conjectured capacity recovers the known capacity of TPIR if we set K_c=1 and that of MDS-PIR if we set T=1. However, in all non-degenerate cases where T,K_c∉{1,N}, the capacity of MDS-TPIR, and therefore the validity of the conjecture is unknown. In fact, in all these cases the problem is open on both sides, i.e., the conjectured capacity expression is neither known to be achievable, nor known to be an outer bound. The lack of any non-trivial outer bounds for MDS-TPIR is also recently highlighted in <cit.>. This intriguing combination of plausibility, uncertainty and generality of the FGHK conjecture motivates our work. Our  contribution is summarized next.



  §.§.§ Summary of Contribution

As the main outcome of this work, we disprove the FGHK conjecture. For our counterexample, we consider the setting (K, N, T, K_c) = (2, 4, 2, 2) where the data is stored using the (2,4)  MDS code (x,y)→ (x,y,x+y,x+2y). The conjectured capacity for this setting is 4/7. We show that the rate 3/5 > 4/7 is achievable, thus disproving the conjecture. As a converse argument, we show that no  (scalar or vector) linear PIR scheme can achieve a rate higher than 3/5 for this MDS storage code subject to T=2 privacy. 



The insights from the counterexample lead us to characterize the exact capacity of various instances of MDS-TPIR. This includes all cases with (K,N,T,K_c)=(2,N,T,N-1), where N and T can be arbitrary. The capacity for these cases turns out to be 

    C   =   N^2-N/2N^2-3N+T

Note that this is the information theoretic capacity, i.e., for K=2 messages, no (N-1,N) MDS storage code and no PIR scheme (linear or non-linear) can beat this rate, which is achievable with the simple MDS storage code (x_1, x_2,⋯, x_N-1)→ (x_1, x_2, ⋯, x_N-1, ∑_i=1^N-1 x_i) and a linear PIR scheme. 

The general capacity expression for MDS-TPIR remains unknown. However, we are able to show that  it cannot be symmetric in K_c and T, i.e., the two parameters are not interchangeable in general. Also, between K_c and T the capacity expression does not consistently favor one over the other. These findings are illustrated by the following four cases for which the capacity is settled.

    [               4c(K,N,T,K_c);           2-5     (2,4,2,3)     (2,4,3,2)     (2,4,1,3)     (2,4,3,1);                        6/11           4/7           4/7           4/7;                                                  <cit.>        <cit.>;               ]

The first two columns show that the capacity is not symmetric in K_c and T, since switching their values changes the capacity. The first two columns also suggest that increasing K_c hurts capacity more than increasing T. However, considering columns 3 and 4 as the baseline where the capacities are equal, and comparing the drop in capacity from column 3 to column 1 when T is increased, versus no change in capacity from column 4 to column 2 when K_c is increased shows the opposite trend. Therefore, neither T nor K_c is consistently dominant in terms of the sensitivity of capacity to these two parameters. 

Finally,  taking an asymptotic view of capacity of MDS-TPIR, we show that  if T+K_c>N, then the capacity collapses to 0 as the number of messages K→∞. This is consistent with the restriction of T+K_c≤ N  that is required by the achievable scheme of Freij-Hollanti et al. whose  rate does not depend on K. 


Notation: For n_1, n_2 ∈ℤ, define the notation [n_1: n_2] as the set {n_1, n_1+1,⋯, n_2}, A_n_1:n_2 as the vector (A_n_1, A_n_1+1, ⋯, A_n_2), and  S(n_1 : n_2,:) as the submatrix of a matrix S formed by retaining only the n_1^th to the n_2^th rows. The notation X ∼ Y is used to indicate that X and Y are identically distributed. The cardinality of a set ℐ is denoted as |ℐ|. The determinant of a matrix S is denoted as |S|. For an index set ℐ = {i_1, ⋯, i_n} such that i_1 < ⋯ < i_n, the notation A_ℐ represents the vector (A_i_1, ⋯, A_i_n). (V_1; V_2; ⋯; V_n) refers to a matrix whose i^th row vector is V_i, i ∈ [1:n].



§ PROBLEM STATEMENT

Consider[While the problem statement is presented in its general form, we will primarily consider cases with K=2 messages in this paper (outer bounds for larger K are presented in Section <ref>).] K independent messages W_1, ⋯, W_K∈𝔽_p^L× 1, each represented as an L× 1 vector comprised of  L i.i.d. uniform symbols from a finite field 𝔽_p for a prime p. In p-ary units,

    H(W_1)    =   ⋯ = H(W_K) = L 
    
    H(W_1, ⋯, W_K)    =    H(W_1) + ⋯ + H(W_K)

There are N servers. The n^th server stores (W_1n, W_2n, ⋯, W_Kn), where W_kn∈𝔽^L/K_c× 1 represents L/K_c symbols from W_k, k ∈ [1:K]. 

    H(W_kn | W_k) = 0,  H(W_kn) = L/K_c

We require the storage system to satisfy the MDS property, i.e., from the information stored in any K_c servers, we can recover each message, i.e.,

    []   H(W_k | W_k 𝒦_c) = 0, ∀𝒦_c ⊂ [1:N], |𝒦_c| = K_c

Let us use ℱ to denote a random variable privately generated by the user, whose realization is not available to the servers. ℱ represents the randomness in the strategies followed by the user. Similarly, 𝒢 is a random variable that determines the random strategies followed by the servers, and whose realizations are assumed to be known to all the servers and to the user. The user privately generates θ uniformly from [1:K] and wishes to retrieve W_θ while keeping θ a secret from each server. ℱ and 𝒢 are generated independently and before the realizations of the messages or the desired message index are known, so that

    H(θ, ℱ, 𝒢, W_1, ⋯, W_K)  = H(θ) + H(ℱ) + H(𝒢) + H(W_1) + ⋯ + H(W_K)

Suppose θ = k. In order to retrieve W_k, k ∈ [1:K] privately, the user privately generates N random queries, Q_1^[k], ⋯, Q_N^[k].

    H(Q_1^[k], ⋯, Q_N^[k] | ℱ) = 0, ∀ k ∈ [1:K]

The user sends query Q_n^[k] to the n^th server, n ∈ [1:N]. Upon receiving Q_n^[k], the n^th server generates an answering string A_n^[k], which is a function of the received query Q_n^[k], the stored information W_1n, ⋯, W_Kn and 𝒢,

    H(A_n^[k] | Q_n^[k], W_1n, ⋯, W_Kn, 𝒢) = 0

Each server returns to the user its answer A_n^[k].[If the A_n^[k] are obtained as inner products of query vectors and stored message vectors, then such a PIR scheme is called a linear PIR scheme.]

From all the information that is now available at the user (A_1:N^[k], Q_1:N^[k], ℱ,𝒢), the user decodes the desired message W_k according to a decoding rule that is specified by the PIR scheme. Let P_e denote the probability of error achieved with the specified decoding rule.

To protect the user's privacy, the K strategies must be indistinguishable (identically distributed) from the perspective of any subset 𝒯⊂ [1:N] of at most T colluding servers, i.e., the following privacy constraint must be satisfied.

    []  
    (Q_𝒯^[k], A_𝒯^[k], 𝒢, W_1𝒯, ⋯, W_K𝒯) ∼ (Q_𝒯^[k'], A_𝒯^[k'], 𝒢, W_1𝒯, ⋯, W_K𝒯), 
    ∀ k, k' ∈ [1:K], ∀𝒯⊂ [1:N], |𝒯| = T


The PIR rate characterizes how many bits of desired information are retrieved per downloaded bit and is defined as follows.

    R = L/D

where D is the expected value of the total number of bits downloaded by the user from all the servers. 

A rate R is said to be ϵ-error achievable if there exists a sequence of PIR schemes, indexed by L, each of rate greater than or equal to R, for which P_e → 0 as L →∞. Note that for such a sequence of PIR schemes, from Fano's inequality, we must have

    [] 
     o(L)    =   1/L H(W_k|A_1:N^[k], Q_1:N^[k], ℱ, 𝒢)  
       (<ref>)=   1/L H(W_k|A_1:N^[k], ℱ, 𝒢)

where o(L) represents a term whose value approaches zero as L approaches infinity. The supremum of ϵ-error achievable rates is called the capacity C.[Alternatively, the capacity may be defined with respect to zero error criterion, i.e., the supreme of zero error achievable rates where a rate R is said to be zero error achievable if there exists (for some L) a PIR scheme of rate greater than or equal to R for which P_e = 0. ]



§ SETTLING THE CONJECTURE

Our main result, which settles the FGHK conjecture, is stated in the following theorem.

For the MDS-TPIR problem with K = 2 messages, N = 4 servers, T = 2 privacy and the (K_c, N) = (2,4) MDS storage code  (x,y)→ (x,y,x+y,x+2y), a rate of 3/5 is achievable. Since the achievable rate exceeds the conjectured capacity of 4/7 for this setting, the FGHK conjecture is false.


Proof: We present a scheme that achieves rate 3/5. We assume that each message is comprised of L=12  symbols from 𝔽_p for a  sufficiently[ It suffices to choose p=349 for Theorem <ref>. In general, the appeal to large field size, analogous to the random coding argument in information theory, is made to prove the existence of a scheme, but may not be essential to the construction of the PIR scheme. To underscore this point, Section <ref> includes some examples of MDS-TPIR capacity achieving schemes over small fields.  ] large prime p. Define a∈𝔽_p^6×1 as the 6× 1 vector (a_1;a_2;⋯; a_6) comprised of i.i.d. uniform symbols a_i∈𝔽_p. Vectors b,  c,  d are defined similarly. Messages W_1, W_2 are defined in terms of these vectors as follows.

    W_1 = ( a;  b)        W_2 = ( c;  d)



 §.§ Storage Code

The storage is specified as

    (W_11,W_12, W_13, W_14)    =    ( a,  b,  a +b,  a+2b)
    
    (W_21,W_22, W_23, W_24)    =    ( c,  d,  c +d,  c+2d)

Recall that W_kn is the information about message W_k that is stored at Server n. Thus, Server 1 stores ( a,c), Server 2 stores ( b,d), Server 3 stores ( a+b, c+d), and Server 4 stores ( a+2b, c+2d). In particular, each server stores 6 symbols for each message, for a total of 12 symbols per server. Any two servers store just enough information to recover both messages, thus the MDS storage criterion is satisfied.



 §.§ Construction of Queries

The query to each server Q_n^[k] is comprised of two parts,  denoted as Q_n^[k](W_1), Q_n^[k](W_2). Each part contains 3 row vectors, also called query vectors, along which the server should project its corresponding stored message symbols.

    Q_n^[k] = (Q_n^[k](W_1), Q_n^[k](W_2))

In preparation for the construction of the queries, let us denote the set of all full rank 6 × 6 matrices over 𝔽_p as 𝒮. The user privately chooses two matrices, S and S', independently and uniformly from 𝒮. Label the rows of S as V_1, V_2, V_3, V_4, V_5, V_6, and the rows of S' as U_0, U_1, U_2, U_3, U_4, U_5. Define

    𝒱_1={V_1, V_2, V_3},      𝒰_1={U_0, U_6, U_8}
    𝒱_2={V_1, V_4, V_5},      𝒰_2={U_0, U_7, U_9}
    𝒱_3={V_2, V_4, V_6},      𝒰_3={U_0, U_1, U_3}
    𝒱_4={V_3, V_5, V_6},      𝒰_4={U_0, U_2, U_4}

 U_6, U_7, U_8, U_9 are obtained as follows.

    U_6 = U_1 + U_2,       U_7 = U_1 + 2U_2 
    
    U_8 = U_3 + U_4,       U_9 = U_3 + 2U_4



As a preview of what we are trying to accomplish, we note that for Server n∈[1:4],   𝒱_n will be used as the query vectors for desired message symbols, while 𝒰_n will be used as query vectors for undesired message symbols. Since K_c=2, the same query vector V_i sent to two different servers will recover 2 independent desired symbols.  Each V_i, i∈[1:6], is used exactly twice, so all queries for desired symbols will return independent information for a total of 12 independent desired symbols. On the other hand, for undesired symbols note that U_0 is used as the query vector to all 4 servers, but because K_c=2, it can only produce 2 independent symbols, i.e., 2 of the 4 symbols are redundant. The dependencies introduced via (<ref>),(<ref>) are carefully chosen to  ensure that the queries along U_1, U_2, U_6, U_7 will produce only  3 independent symbols. Similarly, the queries along U_3,U_4, U_8,U_9 will produce only 3 independent symbols. Thus, all the queries for the undesired message will produce a total of only 8 independent symbols. The 12 independent desired symbols and 8 independent undesired symbols will be resolved from a total of 12+8=20 downloaded symbols, to achieve the rate 12/20=3/5. To ensure T=2 privacy, the 𝒰_i and 𝒱_i queries will be made indistinguishable from the perspective of any 2 colluding servers. The key to the T=2 privacy is that any 𝒱_n, 𝒱_n', n≠ n' have one element in common. Similarly,  any 𝒰_n, 𝒰_n', n≠ n' also have one element in common. This is a critical aspect of the construction. 



Next we provide a detailed description of the queries and downloads  for message W_k, k ∈ [1:2], both when W_k is desired and when it is not desired. To simplify the notation, we will denote W_k = ( x;  y). Note that when k = 1, ( x;  y) = ( a;  b) and when k = 2, ( x;  y) = ( c;  d).



  §.§.§ Case 1. W_k is Desired

The query sent to Server n is a 3× 6 matrix whose rows are the 3 vectors in 𝒱_n. The ordering of the rows is uniformly random, i.e.,

    : Q_n^[k](W_k) = π_n (𝒱_n),       n∈[1:4]

For a set 𝒱={V_i_1,V_i_2,V_i_3}, π_n (𝒱) is equally likely to return any one of the 6 possibilities: (V_i_1; V_i_2; V_i_3), (V_i_1; V_i_3; V_i_2), (V_i_2; V_i_1; V_i_3), (V_i_2; V_i_3; V_i_1), (V_i_3; V_i_1; V_i_2) and (V_i_3; V_i_2; V_i_1). The π_n are independently chosen for each n∈[1:4].


After receiving the 3 query vectors Q_n^[k](W_k),  Server n projects its stored W_kn symbols along these vectors.  
This creates three linear combinations of W_kn symbols (denoted as A_n^[k](W_k)).

    A_n^[k](W_k) = Q_n^[k](W_k) W_kn

Define k^c=3-k as the complement of k, i.e., k^c=1 if k=2 and vice versa. The answers A_n^[k] to be sent to the user will be constructed eventually by combining A_n^[k](W_k) and A_n^[k](W_k^c), since separately sending these answers will be too inefficient. The details of this combining process will be specified later. Next we note an important property of the construction.

Desired Symbols Are Independent: We show that if the user can recover A_1:4^[k](W_k) from the downloads, then he can recover all 12 symbols of W_k. From A_1:4^[k](W_k) the user recovers the 12 symbols V_1 x, V_2 x, V_3 x, V_1 y, V_4 y, V_5 y, V_2( x+y), V_4( x+y), V_6( x+y), V_3( x+2y), V_5( x+2y), V_6( x+2y). From these 12 symbols, he recovers V_i x and V_i y for all i∈[1:6].
Since S = (V_1; V_2; V_3; V_4; V_5; V_6) has full rank (invertible)  and the user knows V_1:6, he recovers all symbols in x and y (thus W_k).



  §.§.§ Case 2. W_k is Undesired

Similarly, the query sent to Server n is a 3× 6 matrix whose rows are the 3 vectors in 𝒰_n.  The ordering of the rows is uniformly random for each n, and independent across all n∈[1:4].

    : Q_n^[k^c](W_k) = π_n'(𝒰_n),       n∈[1:4]

Each server projects its stored W_kn symbols along the 3 query vectors to obtain,

    A_n^[k^c](W_k) = Q_n^[k^c](W_k) W_kn

Interfering Symbols Have Dimension 8:
 A_1:4^[k^c](W_k) is comprised of  U_0 x, U_6 x, U_8 x, U_0 y, U_7 y, U_9 y, U_0( x+y), U_1( x+y), U_3( x+y), U_0( x+2y), U_2( x+2y), U_4( x+2y). We now show that these 12 symbols are dependent and have dimension only 8.[Equivalently, the joint entropy of these 12 variables, conditioned on U_0:9 is only 8 p-ary units.] Because of (<ref>) and (<ref>), we have

    U_0  x + U_0  y   =    U_0 ( x+ y) 
    
    U_0  x + 2U_0  y   =    U_0  ( x+2 y) 
    
    U_6  x + U_7  y - U_1 ( x+ y)    =    U_2  ( x+2 y) 
    
    U_8  x + U_9  y - U_3  ( x+ y)    =    U_4  ( x+2 y)

Thus, of the 12 symbols recovered from A_1:4^[k^c](W_k), at least 4 are linear combinations of the remaining 8. It follows that A_1:4^[k^c](W_k) contains no more than 8 dimensions. The number of dimensions is also not less than 8 because, the following 8 undesired symbols (two symbols from each server) are  independent, 

    :        U_0  x, U_6  x = (U_1+U_2)  x
    :        U_0  y, U_9  y = (U_3 + 2U_4)  y
    :        U_1 ( x +  y), U_3 ( x +  y) 
    :        U_2 ( x + 2 y), U_4 ( x + 2 y)

To see that the 8 symbols are  independent, we add 4 new symbols (U_1  x, U_3  y, U_5 x, U_5 y) such that from the 12 symbols, we can recover all 12 undesired symbols (S'  x, S'  y). Since the 4 new symbols cannot contribute more than 4 dimensions, the original 8 symbols must occupy at least 8 dimensions.






 §.§ Combining Answers for Efficient Download

Based on the queries, each server has 3 linear combinations of symbols of W_1 in  A_n^[k](W_1) and 3 linear combinations of symbols of W_2 in A_n^[k](W_2) for a total of 12 linear combinations of desired symbols and 12 linear combinations of undesired symbols across all servers. However, recall that there are only 8 independent linear combinations of undesired symbols. This is a fact that can be exploited to improve the efficiency of download. Specifically, we will combine the 6 queried symbols (i.e., the 6 linear combinations) from each server into 5  symbols to be downloaded by the user. Intuitively, 5 symbols from each server will give the user a total of 20 symbols, from which he can resolve the 12 desired and 8 undesired symbols. 
 
The following function maps 6 queried symbols to 5 downloaded symbols.

    ℒ(X_1, X_2, X_3, Y_1, Y_2, Y_3)    = (X_1, X_2, Y_1, Y_2, X_3 + Y_3)

Note that the first four symbols are directly downloaded and only the last symbol is mixed. The desired and undesired symbols are combined to produce the answers as follows.

    A_n^[k] = ℒ(C_n A_n^[k](W_1), C_n A_n^[k](W_2))

where C_n are deterministic 3× 3 matrices, that are required to satisfy the following two properties. Denote the first 2 rows of C_n as C_n.


  P1. All C_n must have full rank.

  P2.  For all (3!)^4 distinct realizations of π_n', n ∈ [1:4], the 8  linear combinations of the undesired message symbols that are directly downloaded (2 from each server), C_1 A_1^[k](W_k^c), C_2 A_2^[k](W_k^c), C_3 A_3^[k](W_k^c), C_4 A_4^[k](W_k^c) are  independent. 

As we will prove in the sequel, it is not difficult to find matrices that satisfy these properties. In fact, these properties are `generic', i.e., uniformly random choices of C_n  matrices will satisfy these properties with probability approaching 1 as the field size approaches infinity. The appeal to generic property will be particularly useful as we consider larger classes of MDS-TPIR settings. Those (weaker) proofs apply here as well. However, for the particular setting of Theorem <ref>, based on a brute force search we are able to strengthen the proof by presenting the following explicit choice of C_n, n∈[1:4] which satisfies both properties over 𝔽_349.


    C_1 = (
    [ 1 2 3; 6 5 4; 0 0 1 ]), 
    C_2 = (
    [  1  7  3; 11  9  8;  0  0  1 ]), 
    C_3 = (
    [  1 10  8;  7  5  4;  0  0  1 ]), 
    C_4 = (
    [  1  3  5; 12  9  3;  0  0  1 ])

Property P1 is trivially verified. Property P2 is  verified by considering one by one, all of the 6^4 distinct realizations of π_n', n∈[1:4]. To show how this is done, let us consider one case here. Suppose the realization of the permutations is such that

    π_1'(𝒰_1)    =    (U_0, U_6, U_8)
    π_2'(𝒰_2)    =    (U_0, U_9, U_7)
    π_3'(𝒰_3)    =    (U_1, U_3, U_0)
    π_4'(𝒰_4)    =    (U_2, U_4, U_0)

then we have

    (C_1 A_1^[k](W_k^c); ⋯; C_4 A_4^[k](W_k^c)) = 
    ([  1  2  0 -3  0  3  0  3;  6  5  0 -4  0  4  0  4;  0 -3  1  7  3  0  3  0;  0 -8 11  9  8  0  8  0;  8  0  8  0  1 10  0  0;  4  0  4  0  7  5  0  0;  5  0 10  0  0  0  1  3;  3  0  6  0  0  0 12  9 ])_≜𝒞( [        U_0  x;        U_6  x;        U_0  y;        U_9  y;  U_1  ( x+ y);  U_3  ( x+ y); U_2  ( x+2 y); U_4  ( x+2 y) ])

The determinant of 𝒞  over 𝔽_349 is 321. Since the determinant is non-zero, all of its 8 rows are linearly independent.  Note that the test for property P2 does not depend on the realizations of U_i vectors. To see why this is true, note that the 8 linear combinations of ( x, y) in the rightmost column vector of (<ref>) are linearly independent. Therefore, if 𝒞 is an invertible matrix then the 8 directly downloaded linear combinations on the LHS of (<ref>) are also  independent (have joint entropy 8 p-ary units, conditioned on U_0:9).

At this point the construction of the scheme is complete. All that remains now is to prove that the  scheme is correct, i.e., it retrieves the desired message,  and that it is T=2 private.



 §.§ The Scheme is Correct (Retrieves Desired Message)

As noted previously, the first 4 variables in the output of the ℒ function are obtained directly, i.e., C_1 A_1^[k](W_1), C_2 A_2^[k](W_1), C_3 A_3^[k](W_1), C_4 A_4^[k](W_1) and C_1 A_1^[k](W_2), C_2 A_2^[k](W_2), C_3 A_3^[k](W_2), C_4 A_4^[k](W_2) are all directly recovered. By property P2 of C_n, C_1 A_1^[k](W_k^c), C_2 A_2^[k](W_k^c), C_3 A_3^[k](W_k^c), C_4 A_4^[k](W_k^c) are linearly independent. Since the user  has recovered 8 independent dimensions of interference, and interference only spans 8 dimensions, all interference is recovered and eliminated. Once the interference is eliminated, since C_n matrices have full rank, the user is left with 12 independent linear combinations of desired symbols, from which he is able to recover the 12 desired message symbols. Therefore the scheme is correct.




 §.§ The Scheme is Private (to any T=2 Colluding Servers)

To prove that the scheme is T = 2 private (refer to (<ref>)), it suffices to show that the queries for any 2 servers are identically distributed, regardless of which message is desired. Since each query is made up of two independently generated parts, one for each message, it suffices to prove that the query vectors for a message (say W_k) are identically distributed, regardless of whether the message is desired or undesired,

    (Q_n_1^[k](W_k), Q_n_2^[k](W_k)) ∼(Q_n_1^[k^c](W_k), Q_n_2^[k^c] (W_k)), 
     ∀ n_1, n_2  ∈ [1:4], n_1 < n_2

Note that  

    (Q_n_1^[k](W_k), Q_n_2^[k](W_k)) = (π_n_1(𝒱_n_1), π_n_2(𝒱_n_2) ) 
    (Q_n_1^[k^c](W_k), Q_n_2^[k^c](W_k)) = (π_n_1' (𝒰_n_1), π_n_2' (𝒰_n_2) )

Therefore, to prove (<ref>) it suffices to show the following.

    ( V_i_1, V_i_2, V_i_3, V_i_4, V_i_5) ∼( U_0, U_j_1, U_j_2, U_j_3, U_j_4)

where 𝒱_n_1 = {V_i_1, V_i_2, V_i_3}, 𝒱_n_2 = {V_i_1,V_i_4,V_i_5}, 𝒰_n_1 = {U_0, U_j_1, U_j_2}, 𝒰_n_2 = {U_0, U_j_3,U_j_4}.
Because S is uniformly chosen from the set of all full rank matrices, we have

    (V_i_1, V_i_2, V_i_3, V_i_4, V_i_5) ∼ (V_1, V_2, V_3, V_4, V_5)

Next we note that there is a bijection between 

    (U_0, U_j_1, U_j_2, U_j_3, U_j_4)   ↔   (U_0, U_1, U_2, U_3, U_4)

This is because (U_0, U_j_1, U_j_2, U_j_3, U_j_4) always includes U_0, two terms out of U_1, U_2, U_6, U_7 and two terms out of U_3, U_4, U_8, U_9.  But from any two terms of U_1, U_2, U_6, U_7 there is a bijection to U_1, U_2, and from any two terms of U_3,U_4,U_8, U_9 there is a bijection to U_3, U_4. Now since S' = (U_0; U_1; U_2; U_3; U_4; U_5) is picked uniformly from 𝒮, conditioned on any feasible value of U_5, (U_0, U_1, U_2, U_3, U_4) is uniformly distributed over all possible values that preserve full rank for S'. Since (U_0, U_j_1, U_j_2, U_j_3, U_j_4) spans the same space as (U_0, U_1, U_2, U_3, U_4), they have the same set of feasible values. The bijection between them then means that (U_0, U_j_1, U_j_2, U_j_3, U_j_4) is also uniformly distributed over all possibilities that preserve full rank for S', conditioned on any feasible U_5. That means

    (U_0, U_j_1, U_j_2, U_j_3, U_j_4) ∼ (U_0, U_1, U_2, U_3, U_4)

Finally, we note that S and S' are identically distributed, so we have

    (V_1, V_2, V_3, V_4, V_5) ∼ (U_0, U_1, U_2, U_3, U_4)

Combining (<ref>), (<ref>) and (<ref>), we arrive at (<ref>) and (<ref>).




 §.§ Rate achieved is 3/5

The rate achieved is 12/20 = 3/5, because we download 20 symbols in total (5 from each server) and the desired message size is 12 symbols. 



§ OPTIMALITY OF RATE 3/5

We  presented a scheme that achieves the rate 3/5 for the setting (K, N, T, K_c) = (2, 4, 2, 2) with the MDS storage code (x,y)→(x,y,x+y,x+2y). But is the scheme optimal? i.e., is the rate 3/5 the highest rate possible for this setting? To settle this question we need an upper bound. So far the best information theoretic upper bound that we are able to prove is 8/13[Remarkably, 8/13 can be shown to be the capacity if the colluding sets of servers are restricted to servers {1,2},{2,3}, {3,4},{4,1} (see Section <ref>).] (see Section <ref>), which leaves the information theoretic capacity open for this setting. However, let us define the notion of “linear capacity" as the highest rate that can be achieved by any (scalar or vector) linear PIR scheme. It turns out that we are  able to settle the linear capacity.

For the MDS-TPIR problem with (K, N, T, K_c) = (2, 4, 2, 2) and the MDS storage code (x,y)→(x,y,x+y,x+2y), the linear capacity is 3/5.

Proof: Since the achievability of 3/5 has already been shown, we are left to prove the converse, i.e., the upper bound.

Let a, b, c, d∈𝔽_p^L/2× 1 be i.i.d. uniform L/2× 1 vectors over 𝔽_p. Without loss of generality, the MDS storage code for message W_k is represented as follows. 

    W_1 = ( a;  b)        W_2 = ( c;  d)

and the storage is specified as

    (W_11,W_12, W_13, W_14)    =    ( a,  b,  a +b,  a+2b) 
    
    (W_21,W_22, W_23, W_24)    =    ( c,  d,  c +d,  c+2d)

The scheme is linear so that the download from each server consists of linear combinations of the stored symbols of both messages. Furthermore, without loss of generality, we assume that the scheme is symmetric[Any scheme can be made symmetric, e.g., by repeating the original scheme for each of the N! permutations of the servers to retrieve a correspondingly expanded message of length L'=N! L.] and  the download from each server is comprised of d≤ L/2 independent symbols from each message. Therefore, the downloads can be expressed as

    A_n^[k]   =   V_1n^[k] W_1n+V_2n^[k] W_2n, ∀ n ∈ [1:4], k∈[1:2]
    (V_1n^[k])   =   (V_2n^[k])=d

where V_in^[k] are D/4× L/2  matrices that may be chosen randomly by the user (functions of ℱ). Clearly we must have 4d≥ L otherwise the L symbols of the desired message cannot be recovered.
Define ϵ≥ 0 such that 

    4d    =    L(1+ϵ)

Without loss of generality, let us assume henceforth that W_2 is the desired message. For the next set of arguments, we focus only on the downloads corresponding to W_2, i.e., set all W_1 symbols to 0. Further, let us use the notation 𝖵 to represent the row span of the matrix V. The symbols downloaded from Server n along 𝖵⊂𝖵^[2]_2n, are called redundant if they can be expressed as linear combinations of symbols downloaded from other servers, i.e., they contribute no new information.

    H(V W_2n|V^[2]_2n_1 W_2n_1, V^[2]_2n_2 W_2 n_2, V^[2]_2n_3W_2n_3,ℱ, V) =0

where n, n_1, n_2, n_3 are distinct indices in [1:4].  Note that we download no more than a total of L(1+ϵ) (possibly dependent) symbols of W_2 from all 4 servers, from which we must be able to decode all L independent symbols of W_2. Therefore, we cannot have more than ϵ L redundant symbols. Therefore, for any V that satisfies (<ref>) we must have 

    (𝖵)    ≤   ϵ L


Next, let us consider the pairwise overlap between 𝖵^[2]_2i and 𝖵^[2]_2j, i < j, i, j ∈ [1:4]. By the symmetry of the scheme, there exist V_ij, ∀ i,j∈[1:4], i≠ j, and α≥ 0 such that

    𝖵_ij = 𝖵^[2]_2i∩𝖵^[2]_2j,  (𝖵_ij) = α d


The following lemma formalizes the intuition that the overlaps α must be small enough to ensure that we have enough independent symbols to recover W_2.


    3α d    ≤    d + 2ϵ L 
    α   ≤   1/3 + 8/3( ϵ/1+ϵ)


Proof: 
First, we show that 

    (𝖵_12∩𝖵_13) ≤ϵ L

For any vector v ∈𝖵_12∩𝖵_13 (note that v belongs simultaneously to 𝖵_21^[2], 𝖵_22^[2], 𝖵_23^[2]), the symbol v W_23 (downloaded from Server 3) is redundant because it is a linear combination of downloads from servers 1 and 2,

    v( c+d)    =    v c+v d
    ∴ v W_23   =    v W_21 + v W_22
       ⇒    H(v W_23|V^[2]_21 W_21, V^[2]_22 W_2 2,ℱ,v) = 0

From (<ref>) and (<ref>), we have (<ref>).

Second, we show that 

    ((𝖵_12∪𝖵_13) ∩𝖵_14) ≤ϵ L
 
Consider any vector v ∈𝖵_12. Because v belongs to both 𝖵_21^[2] and 𝖵_22^[2], we have downloaded v W_21=v c and v W_22=v d from servers 1 and 2. Similarly, for any vector v' ∈𝖵_13, we have downloaded v' W_21=v' c and v' W_23 = v'( c+d)=v' W_21 + v' W_22 (from servers 1 and 3), from which we can recover v' W_21=v' c and v' W_22=v' d. Consider now any vector v^* ∈ (𝖵_12∪𝖵_13) ∩𝖵_14. Suppose v^* = h_1 v + h_2 v', v ∈𝖵_12, v' ∈𝖵_13 for constants h_1, h_2. The symbol v^* W_24=v^*( c+2d) (downloaded from Server 4) is redundant because it is a linear combination of downloads from servers 1, 2 and 3,

    v^* W_24   =    (h_1 v + h_2 v')( c+2d)
       =    h_1 v c + 2h_1 v  d + h_2 v'  c + 2h_2 v'  d
       =    h_1 v W_21 + 2h_1 v W_22 + h_2 v' W_21 + 2h_2 v' W_22
       ⇒     H(v^* W_24 |V^[2]_21 W_21, V^[2]_22 W_2 2, V^[2]_23 W_23,ℱ, v^*) = 0

From (<ref>) and (<ref>), we have (<ref>). Next, consider (𝖵_12∪𝖵_13).

    (𝖵_12∪𝖵_13) 
         =   (𝖵_12) + (𝖵_13) - (𝖵_12∩𝖵_13) 
       ≥    2α d - ϵ L   ( (<ref>)(<ref>))

Finally, consider (𝖵_12∪𝖵_13∪𝖵_14). 

    d    =   (𝖵_21^[2]) ≥(𝖵_12∪𝖵_13∪𝖵_14) 
       =   (𝖵_12∪𝖵_13) + (𝖵_14) -  ( (𝖵_12∪𝖵_13) ∩𝖵_14)  
       ≥    2α d- ϵ L + α d - ϵ L     ( (<ref>)(<ref>)(<ref>))
    
       ⇒     3α d ≤ d + 2ϵ L



We now proceed to complete the converse.

    D +o(L)L ≥ H(A_1:4^[1] | ℱ, 𝒢) + o(L)L 
       (<ref>)=    H(A_1:4^[1], W_1 | ℱ, 𝒢) 
       (<ref>)=    H(W_1) + H(A_1^[1] | W_1, ℱ, 𝒢) 
    + H(A_2:4^[1] | W_1, A_1^[1]ℱ, 𝒢)   
       ≥    H(W_1) + H(A_1^[1] | W_1, ℱ, 𝒢) + H(A_3:4^[1] | W_1, W_21, A_1^[1], ℱ, 𝒢)  
       (<ref>)(<ref>)(<ref>)=    H(W_1) + H(A_1^[1] | W_1, ℱ, 𝒢) 
    + H(A_3:4^[1] | W_1, W_21, ℱ, 𝒢)  
       (<ref>)(<ref>)=    H(W_1) + H(A_1^[2] | W_1, ℱ, 𝒢) 
    + H(A_3:4^[2] | W_1, W_21, ℱ, 𝒢)   
       (<ref>)(<ref>)=   H( a,b) + H(V_21^[2] c| ℱ) + H(V_23^[2]( c+d),V_24^[2]( c+2d) |  c, ℱ)  
       =   H( a,b) + H(V_21^[2] c| ℱ) 
    + H(V_23^[2] d,2V_24^[2] d | ℱ)   
       (<ref>)=    L + (𝖵_21^[2]) + (𝖵_23^[2]∪𝖵_24^[2]) 
       (<ref>)(<ref>)=    L + d + 2d - α d  
       (<ref>)≥    L + (3- 1/3 - 8/3( ϵ/1+ϵ))(1+ϵ)L/4
       =     5L/3

Letting L→∞, we have R = L/D ≤ 3/5.





§ CAPACITY OF A CLASS OF MDS-TPIR INSTANCES

Building upon the insights from the achievable scheme and linear converse presented in the previous sections, we are able  to settle the information theoretic capacity of a non-trivial class of MDS-TPIR instances.

For the class of MDS-TPIR instances with (K,N, T, K_c)=(2,N,T,N-1), with arbitrary T,N, the capacity is C = N^2 - N/2N^2 - 3N + T.


The case T=N is trivial because if all servers collude then the situation is equivalent to the single database scenario, i.e., it is optimal to download everything, and the capacity is 1/K=1/2.  For the remaining cases,  T<N, and the proof of converse is presented in Section <ref>. The proof of achievability for T=2 setting appears in Section <ref> where we present a scheme with zero error. The proof of achievability for T>2 settings appears in Section <ref> where we present a scheme with vanishing probability of error. The remainder of this section presents two examples (one with T=2 and one with T=3) to illustrate the key ideas.



 §.§ Example: Capacity achieving scheme for (K, N, T, K_c)=(2, 4, 2,3)

Let us present a scheme that achieves the rate 6/11, which is the capacity for this setting according to Theorem <ref>. As evident from the description below, the scheme builds upon the ideas that were introduced for  Theorem <ref>. 



  §.§.§ Message and Storage Code

Let each message be comprised of L=N(N-1) = 12 independent symbols from a sufficiently large finite field 𝔽_p. Define a∈𝔽_p^4 × 1 as the vector (a_1; a_2; a_3; a_4) comprised of i.i.d. uniform symbols a_i ∈𝔽_p. Vectors b, c, d, e, f are defined similarly. Messages W_1, W_2 are defined in terms of these vectors as follows.

    W_1 = ( a;  b;  c)     W_2 = ( d;  e;  f)

The (N-1,N) = (3,4) MDS storage code is specified as follows. 

    (W_11, W_12, W_13, W_14)    =    ( a,  b,  c,  a+b+c) 
    
    (W_21, W_22, W_23, W_24)    =    ( d,  e,  f,  d+e+f)

Note that each server stores 4 symbols for each message and any three serves store just enough information to recover both messages (MDS property is satisfied).



  §.§.§ Construction of Queries

 The query to each server consists of 6 vectors, the first three for W_1 (denoted as Q_n^[k](W_1)) and the last three for W_2 (denoted as Q_n^[k](W_2)). The queries and downloads for W_k, k ∈ [1:2] are described next. We denote W_k = ( x;  y;  z). When k = 1, ( x;  y;  z) = ( a;  b;  c) and when k = 2, ( x;  y;  z) = ( d;  e;  f).

Denote the set of all full rank 4 × 4 matrices over 𝔽_p as 𝒮_4. The user privately chooses two matrices S, S', independently and uniformly from 𝒮_4. Label the rows of S as V_1, V_2, V_3, V_4, and the rows of S' as U_1, U_2, U_1, U_2. Define the following sets 

    [   𝒱_1     =     {  V_2,  V_3, V_4},;   𝒱_2     = {V_1,        V_3, V_4},;   𝒱_3     = {V_1,  V_2,       V_4},;   𝒱_4     = {V_1,  V_2,   V_3    }, ]      [             𝒰_1               = {U_1, U_2, U_1};             𝒰_2               = {U_1, U_2, U_2};             𝒰_3               = {U_1, U_2, U_3};             𝒰_4               = {U_1, U_2, U_4};                 ]

where U_3, U_4 are obtained as follows.

    U_3    =    U_1 + U_2, 
    
    U_4    =    U_1 + 2U_2

A preview of the scheme is as follows. For Server n ∈ [1:4], the vectors in 𝒱_n are for the desired message and the vectors in 𝒰_n are for the undesired message. Since K_c = N-1 = 3, and each query vector V_i is used no more than three times, all queries for the desired message will return  independent symbols for a total of 12 desired symbols. For the undesired message, the same query vector U_1 is used 4 times such that only 3 independent symbols are produced. Similarly the 4 uses of U_2 produce only 3 independent symbols. Thus all queries for the undesired message will produce at most 6 + 4 = 10 independent undesired symbols. The 12 independent desired symbols and 10 undesired symbols will be resolved from a total of 12 + 10 = 22 downloaded symbols, to achieve the rate 12/22 = 6/11. Privacy is ensured by the observation that any 𝒱_n, 𝒱_n', n≠ n' have two elements in common and similarly any 𝒰_n, 𝒰_n', n≠ n' have two elements in common. We now proceed to the details.


When W_k is desired, we have ∀ n ∈ [1:4],


    n:      
    Q_n^[k](W_k)    = π_n (𝒱_n),    A_n^[k](W_k)    = Q_n^[k](W_k) W_kn.


Desired Symbols Are Independent: From A_1:4^[k](W_k), the user can recover the 12 symbols V_2 x, V_3 x, V_4 x, V_1 y, V_3 y, V_4 y, V_1 z, V_2 z, V_4 z, V_1( x+ y+ z), V_2( x+ y+ z), V_3( x+ y+ z) and therefore all 12 symbols (x; y; z) of W_k, since S = (V_1;V_2;V_3;V_4) has full rank. 


When W_k is undesired, we have ∀ n ∈ [1:4],


    n:       Q_n^[k^c](W_k)    = π_n' (𝒰_n),    A_n^[k^c](W_k)    = Q_n^[k^c](W_k) W_kn.

Interfering Symbols Are Dependent and Have Dimension at most 10:
Consider the interfering symbols along the common vectors U_1, U_2. Note that 

    U_1  x + U_1  y + U_1  z = U_1 ( x +  y +  z)
    U_2  x + U_2  y + U_2  z = U_2 ( x +  y +  z)

Since at least 2 interfering symbols are linear combinations of the rest, the 12 interfering symbols cannot have more than 10 dimensions, i.e., their joint entropy is no more than 10 in p-ary units. 



  §.§.§ Combining Answers, Correctness and Rate


The combining process and correctness proof are similar to that in Theorem <ref>. The difference is that in Theorem <ref>, we find the explicit choice of combining matrices, here we will only prove the existence of combining matrices over a sufficiently large field. The details are deferred to the general proof in Section <ref>. We repeat the above query construction two times independently such that each server has 6 × 2 = 12 symbols (6 in W_1 and 6 in W_2).
These 12 symbols at each server are combined to 11 downloaded symbols, A_n^[k] and it is ensured that we can decode all interfering symbols and then extract the desired symbols. 

Thus, the rate achieved is 6/11. 



  §.§.§ Privacy Proof

The privacy proof is virtually identical to that in Theorem <ref>, so the details are deferred to the general proof in Section <ref>. 





 §.§ Example: Capacity achieving scheme for (K, N, T, K_c)=(2, 4,3,3)

Let us present a scheme that achieves the rate 12/23, which is the capacity for this setting according to Theorem <ref>.  The key distinction of this T = 3 case with the T=2 case presented in the previous section is that permutations of the query vectors are no longer enough to ensure the privacy. So we will resort to sending the space spanned by the query vectors instead of the query vectors themselves. Furthermore, instead of guaranteeing zero-error, we will only show that the probability of error can be made arbitrarily small by choosing a sufficiently large message size.



  §.§.§ Message and Storage Code

The message construction and storage code are the same as  when T=2.
Let each message be comprised of L=N(N-1) = 12 independent symbols from a sufficiently large finite field 𝔽_p. Define a∈𝔽_p^4 × 1 as the vector (a_1; a_2; a_3; a_4) comprised of i.i.d. uniform symbols a_i ∈𝔽_p. Vectors b, c, d, e, f are defined similarly. Messages W_1, W_2 are defined in terms of these vectors as follows.

    W_1 = ( a;  b;  c)     W_2 = ( d;  e;  f)

The (N-1,N) = (3,4) MDS storage code is specified as follows. 

    (W_11, W_12, W_13, W_14)    =    ( a,  b,  c,  a+b+c) 
    
    (W_21, W_22, W_23, W_24)    =    ( d,  e,  f,  d+e+f)




  §.§.§ Construction of Queries

The query to each server consists of two vector spaces, one for W_1 (span of the rows of Q_n^[k](W_1)) and one for W_2 (span of the rows of  Q_n^[k](W_2)). The queries and downloads for W_k, k ∈ [1:2] are described next. We denote W_k = ( x;  y;  z). When k = 1, ( x;  y;  z) = ( a;  b;  c) and when k = 2, ( x;  y;  z) = ( d;  e;  f).

Denote the set of all full rank 4 × 4 matrices over 𝔽_p as 𝒮_4. The user privately chooses two matrices S, S', independently and uniformly from 𝒮_4. Label the rows of S as V_1, V_2, V_3, V_4, and the rows of S' as U_1, U_1, U_2, U_3. Define the following sets 
    [   𝒱_1     =     {  V_2,  V_3, V_4},;   𝒱_2     = {V_1,        V_3, V_4},;   𝒱_3     = {V_1,  V_2,       V_4},;   𝒱_4     = {V_1,  V_2,   V_3    }, ]      [                                                  𝒰_1                                                    =                   {U_1, U_1, U_2} = {U_1, U_1, U_2 };                                                  𝒰_2                                                    =               {U_1, U_3, U_4} = {U_1, U_3, U_1+U_2 };                                                  𝒰_3                                                    =           {U_1, U_5, U_6} = {U_1, U_1+U_3, U_2+U_3 };                                                  𝒰_4                                                    = {U_1, U_7, U_8} = {U_1, U_1+U_2+U_3, U_1+2U_2+2U_3 } ]








where U_1, ⋯, U_8 are the rows of U, obtained as follows.

    U   =   P (U_1; U_2; U_3) 
    ([ U_1; U_2; U_3; U_4; U_5; U_6; U_7; U_8 ])    =   (
    [ 1 0 0; 0 1 0; 0 0 1; 1 1 0; 1 0 1; 0 1 1; 1 1 1; 1 2 2 ])([ U_1; U_2; U_3 ])

A preview of the scheme is as follows. For Server n ∈ [1:4], the span of 𝒱_n is the query space for the desired message and the span of 𝒰_n is the query space for the undesired message. Since K_c = N-1 = 3, and each query vector V_i is used no more than three times, all queries for the desired message will return  independent symbols for a total of 12 desired symbols. For the undesired message, the same query vector U_1 is used 4 times such that only 3 independent symbols will be produced. Thus all queries for the undesired message will produce at most 3 + 8 = 11 independent undesired symbols. The 12 independent desired symbols and 11 undesired symbols will be resolved from a total of 12 + 11 = 23 downloaded symbols, to achieve the rate 12/23. Privacy is ensured by choosing P in such a way that it allows a bijective mapping between the 𝒰_n or 𝒱_n spaces that may be observed by any set of up to T = 3 colluding servers. The bijection shows that the queries for both desired and undesired messages are uniformly distributed, and therefore indistinguishable. While a specific P is chosen for this example, there are many choices of P that will work. In fact, P only needs to be sufficiently generic, so as the field size grows, almost all choices of P will work. We now proceed to the details.


When W_k is desired, we have ∀ n ∈ [1:4],


    n:      
    Q_n^[k](W_k)    = 𝔹 (𝒱_n),    A_n^[k](W_k)    = Q_n^[k](W_k) W_kn.

where 𝔹(𝒱) represents the reduced row echelon form of a matrix whose rows are the elements of  𝒱. The reduced row echelon form ensures that the queries reveal only the space spanned by the corresponding V_i vectors to each server, and not  directly the V_i vectors themselves.


Desired Symbols Are Independent: From A_1:4^[k](W_k), we can recover the 12 symbols of W_k. 
Note that because the user knows V_1:4, from A_1:4^[k](W_k) he can recover the projections along V_i. For example, the row reduced echelon form for 𝒱_1 is a change of basis operation that can be represented as 𝔹(𝒱_1)=B_1(V_2;V_3;V_4) for some invertible matrix B_1. Since the user knows B_1, he can multiply A_1^[k](W_k) with (B_1)^-1 as follows

    B_1^-1A_1^[k](W_k)   =   B_1^-1Q_n^[k](W_k) W_k1
       =   B_1^-1B_1(V_2;V_3;V_4) x
       =   (V_2 x; V_3 x; V_4 x)

Thus, from A_1:4^[k](W_k) the user recovers the 12 symbols V_2 x, V_3 x, V_4 x, V_1 y, V_3 y, V_4 y, V_1 z, V_2 z, V_4 z, V_1( x+ y+ z), V_2( x+ y+ z), V_3( x+ y+ z) and therefore all 12 symbols (x; y; z) of W_k, since S = (V_1;V_2;V_3;V_4) has full rank. 


When W_k is undesired, we have ∀ n ∈ [1:4],


    n:       Q_n^[k^c](W_k)    = 𝔹 (𝒰_n),    A_n^[k^c](W_k)    = Q_n^[k^c](W_k) W_kn.

Interfering Symbols Are Dependent and Have Dimension at most 11:
Consider the interfering symbols along the common vector U_1. Note that 

    U_1  x + U_1  y + U_1  z = U_1 ( x +  y +  z)

Since at least 1 interfering symbol is a linear combination of the rest, the 12 interfering symbols cannot have more than 11 dimensions, i.e., their joint entropy is no more than 11 in p-ary units. 



  §.§.§ Combining Answers, Correctness and Rate

The combining process and correctness proof are similar to that in Theorem 1 except that the combining matrices C_n are chosen in a uniformly random manner now (so the matrices are no longer deterministic). We will show in Section <ref> that independent and uniformly random choices of C_n are enough to guarantee that as the field size approaches infinity, i.e., p→∞, the probability of error, P_e→ 0. The reasoning for the rate calculation is as follows. We repeat the above query construction four times independently such that each server has 6 × 4 = 24 symbols (12 in W_1 and 12 in W_2). These 24 symbols at each server are combined to 23 downloaded symbols, A_n^[k] and it is ensured that we can almost surely decode all interfering symbols and then extract the desired symbols.  Thus, the rate achieved is 12/23. 



  §.§.§ Privacy Proof

Since the privacy proof is a bit more involved now, let us use this example to introduce the key ideas.
To show that the scheme is private to any T = 3 colluding servers, it suffices to show that the queries for W_k for any T = 3 servers are identically distributed, regardless of which message is desired. Consider 3 distinct indices i , j , l, i < j <l in [1:4], we require 

    (Q_i^[k](W_k), Q_j^[k](W_k), Q_l^[k](W_k) )    ∼   (Q_i^[k^c](W_k), Q_j^[k^c](W_k), Q_l^[k^c](W_k) ) 
    ⟺    (𝔹(𝒱_i), 𝔹(𝒱_j), 𝔹(𝒱_l) )    ∼   ( 𝔹(𝒰_i), 𝔹(𝒰_j), 𝔹(𝒰_l)  )

Note that 

    (𝔹(𝒱_i), 𝔹(𝒱_j), 𝔹(𝒱_l) ) = (𝔹({V_m, V_j, V_l}), 𝔹({V_m, V_i, V_l}), 𝔹({V_m, V_i, V_j}) )

where m ∉{i,j,l}, m ∈ [1:4]. 
To prove (<ref>), we wish to transform the spaces on the RHS to the form that is the same as (<ref>). 
To this end, we first compute the vectors that lie in the span of both 𝔹(𝒰_i) and 𝔹(𝒰_j), i < j. Note that the matrix P is designed such that except U_1, we have only one such vector (up to scaling), denoted as U_{i,j}. U_{i,j} are computed explicitly as follows. Further, we fix the scaling factor such that the U_{i,j} vector is unique.

    U_{1,2}   =    U_1 + U_2 
    
    U_{1,3}   =    U_1 - U_2 
    
    U_{1,4}   =    U_1 
    
    U_{2,3}   =    U_1 + U_2 + 2U_3 
    
    U_{2,4}   =    U_1 + U_2 + U_3 
    
    U_{3,4}   =    U_2 + U_3

It is easy to verify that U_{i,j}, U_{i,l}, U_{j,l}, i,j,l ∈ [1:4], i < j < l, are linearly independent, i.e.,

    (i,j,l) = (1,2,3)       (U_{1,2}; U_{1,3} ; U_{2,3}) = (U_1 + U_2; U_1 - U_2; U_1 + U_2 + 2U_3) = 3 
    
    (i,j,l) = (1,2,4)       (U_{1,2}; U_{1,4}; U_{2,4}) = (U_1 + U_2; U_1; U_1 + U_2 + U_3) = 3 
    
    (i,j,l) = (1,3,4)       (U_{1,3}; U_{1,4}; U_{3,4}) = (U_1 - U_2; U_1; U_2 + U_3) = 3 
    
    (i,j,l) = (2,3,4)       (U_{2,3}; U_{2,4}; U_{3,4}) = (U_1 + U_2 + 2U_3; U_1 + U_2 + U_3; U_2 + U_3) = 3

As a result, we may equivalently represent Q_i^[k^c](W_k) as

    Q_i^[k^c](W_k) =  𝔹(𝒰_i) = 𝔹({U_1, U_{i,j}, U_{i,l}}), ∀  i,j,l ∈ [1:4], i ≠ j, i≠ l, j ≠ l

Note that equipped with this representation, ( 𝔹(𝒰_i), 𝔹(𝒰_j), 𝔹(𝒰_l)  ) is now of the same form as (𝔹(𝒱_i), 𝔹(𝒱_j), 𝔹(𝒱_l) )   and we are now ready to prove the privacy condition (<ref>). 

    (<ref>) ⟺      (𝔹({V_m, V_j, V_l}), 𝔹({V_m, V_i, V_l}), 𝔹({V_m, V_i, V_j}) ) 
       ∼   ( 𝔹({U_1, U_{i,j}, U_{i,l}}), 𝔹({U_1, U_{i,j}, U_{j,l}}), 𝔹({U_1, U_{i,l}, U_{j,l}})  )

Therefore, it suffices to show the following.

    (V_m, V_i, V_j, V_l) ∼ (U_1, U_{j,l}, U_{i,l}, U_{i,j})

Because S is uniformly chosen from the set of all full rank matrices, we have

    (V_m, V_i, V_j, V_l) ∼ (V_1, V_2, V_3, V_4)

Based on  (<ref>),  there is a bijection between 

    (U_1, U_{j,l}, U_{i,l}, U_{i,j}) ↔  (U_1, U_1, U_2, U_3)

Now since S' = (U_1; U_1; U_2; U_3) is uniform in all full rank matrices, the above bijection then means that (U_1; U_{j,l}; U_{i,l}; U_{i,j}) is also uniform in all full rank matrices, i.e.,

    (U_1, U_{j,l}, U_{i,l}, U_{i,j}) ∼  (U_1, U_1, U_2, U_3)

Finally, note that S and S' have the same distribution, so we have

    (V_1, V_2, V_3, V_4) ∼  (U_1, U_1, U_2, U_3)

Therefore, from (<ref>), (<ref>) and (<ref>), we have proved (<ref>) and (<ref>).






§ CONCLUSION
 
We settle a conjecture on the capacity of MDS-TPIR by Freij-Hollanti et al.  <cit.> by constructing a scheme that  beats the conjectured capacity for one particular instance of MDS-TPIR. The rate achieved by the new scheme is shown to be the best possible rate that can be achieved by any linear scheme for the same MDS storage code. The insights from the achievability and converse arguments allow us to characterize the capacity of a class of MDS-TPIR instances. Through another counterexample, we are also able to prove that the  capacity expression cannot be symmetric in T and K_c parameters, i.e., these parameters cannot be interchangeable in general. Nevertheless, the general capacity expression for MDS-TPIR remains unknown.




§ APPENDIX



 §.§ Examples of Optimal Schemes over Small Fields

To highlight that the assumption of large field size (which was made convenience) may not be essential, in this section, we provide two examples of explicit MDS-TPIR capacity achieving schemes over small fields. 



  §.§.§ Example 1

Consider the MDS-TPIR instance with (K,N,T,K_c) = (2,3,2,2). Note that the capacity of this setting is 6/11, as established in Theorem <ref>. We provide an alternative achievable scheme for rate 6/11. In particular, the scheme operates over the binary field and the upload is 4 bits per server (the query to each server takes values in a set with cardinality 2^4 = 16). 

We assume that each message is L = 6 bits. Denote a_1, ⋯, a_6, b_1, ⋯, b_6 as 12 i.i.d. uniform bits, a_i, b_i ∈𝔽_2. Messages W_1, W_2 are defined in terms of these bits as follows.


    W_1 = (a_1; a_2; a_3; a_4; a_5; a_6), W_2 = (b_1; b_2; b_3; b_4; b_5; b_6)

The storage is specified as

    :      W_11 = (a_1; a_2; a_3), W_21 = (b_1; b_2; b_3) 
    :      W_12 = (a_4; a_5; a_6), W_22 = (b_4; b_5; b_6) 
    :      W_13 = (α_1; α_2; α_3), W_23 = (β_1; β_2; β_3)

where α_1, α_2, α_3, β_1, β_2, β_3 are obtained as follows.

    α_1 = a_1 + a_2 + a_5,       β_1 = b_1 + b_2 + b_5 
    α_2 = a_1 + a_3 + a_6,       β_2 = b_1 + b_3 + b_6 
    α_3 = a_2 + a_4 + a_6,       β_3 = b_2 + b_4 + b_6

Further define

    α_4    =   α_1 + α_2 + α_3 = a_3 + a_4 + a_5 
    β_4    =   β_1 + β_2 + β_3 = b_3 + b_4 + b_5

Note that each server stores 3 bits of each message and the storage at any 2 servers is just enough to recover both messages (MDS storage property is satisfied).

Define a function that maps 4 input bits to 3 output bits as follows.

    ℒ_3 (X_1, X_2, Y_1, Y_2) = (X_1+Y_2, X_2+Y_2, Y_1+Y_2)


We now describe the PIR scheme. ℱ is a uniform random variable in [1:16]. Depending on the value of ℱ and the desired message index θ∈ [1:2], the user's query is specified by Table 1. The double-quotes notation around a random variable represents the query about its realization. Note that the queries to Server 1 and Server 2 are the same, regardless of the value of θ and the query to Server 3 is a deterministic function of that to Server 1 and Server 2.



We show that the scheme is both correct and private. The schemes is correct because our scheme satisfies the important property (P1) that from the answers A_1^[k], A_2^[k], we always know one undesired bit in A_3^[k] and then we can extract the 2 desired bits in A_3^[k] (because if any 1 of the 4 input bits of the ℒ_3 function is known, the remaining 3 input bits can be solved from the 3 output bits). Combining these 2 desired bits with the other 4 desired bits (2 from Server 1 and 2 from Server 2), we obtain the desired message (easy to verify that these 6 bits are independent).
The property (P1) is easy to verify. For example, consider k=1 and ℱ = 8. From A_1^[1], A_2^[1], we obtain b_1, b_3, b_4, b_5, from which we further obtain β_4 = b_3 + b_4 + b_5 and β_4 appears in A_3^[1]. The scheme is private because it is easy to verify that for any 2 servers, the queries are identically distributed no matter which message is desired and then the privacy condition (<ref>) is satisfied.

The scheme downloads 4 bits from Server 1, 4 bits from Server 2 and 3 bits from Serve 3. It retrieves 6 desired message bits. Therefore the rate is 6/11.



  §.§.§ Example 2
 Consider the MDS-TPIR instance with (K,N,T,K_c) = (2,4,3,2).
The capacity of this setting turns out to be 4/7. The rate can not be more than 4/7 because the capacity of TPIR with (K,N,T) = (2,4,3) is 4/7 <cit.> and reducing K_c from 2 to 1 can not hurt. We provide an achievable scheme for rate 4/7. In particular, the scheme operates over the finite field 𝔽_13 and the upload is 6 bits per server (the query to each server takes values in a set with cardinality 2^6 = 64). 

We assume that each message is L = 4 symbols. Denote a_1, a_2, a_3, a_4, b_1, b_2, b_3, b_4 as 8 i.i.d. uniform symbols, a_i, b_i ∈𝔽_13. Messages W_1, W_2 are defined in terms of these symbols as follows.


    W_1 = (a_1; a_2; a_3; a_4), W_2 = (b_1; b_2; b_3; b_4)

The storage is specified as

    :      W_11 = (a_1; a_2), W_21 = (b_1; b_2) 
    :      W_12 = (a_3; a_4), W_22 = (b_3; b_4) 
    :      W_13 = (α_1; α_2), W_23 = (β_1; β_2) 
    :      W_14 = (α_3; α_4), W_24 = (β_3; β_4)

where α_1, α_2, α_3, α_4, β_1, β_2, β_3, β_4 are obtained as follows.

    α_1 = 3a_1 + 2a_2 + 4a_3 + a_4,       β_1 = 3b_1 + 2b_2 + 4b_3 + b_4 
    α_2 = 2a_1 +3a_2 + a_3 + 4a_4,       β_2 = 2b_1 +3b_2 + b_3 + 4b_4 
    α_3 = 3a_1 + 12a_2 + 4a_3 + 6a_4,       β_3 = 3b_1 + 12b_2 + 4b_3 + 6b_4 
    α_4 = 12a_1 + 3a_2 + 6a_3 + 4a_4,       β_4 = 12b_1 + 3b_2 + 6b_3 + 4b_4

Note that each server stores 2 symbols of each message and the storage at any 2 servers is just enough to recover both messages (MDS storage property is satisfied).

We now describe the PIR scheme. ℱ is a uniform random variable in [1:64]. The user's query is uniform over 64 choices and is specified by Table 2. Note that the queries to servers 1, 2 and 3 are the same, regardless of the value of θ and the query to Server 4 is a deterministic function of that to servers 1, 2 and 3.





The key to the scheme is that the undesired symbol downloaded from Server 4 is known from that downloaded from servers 1, 2 and 3, while desired symbols are all independent. This observation is formalized in the following lemma.

For all values of i_1, i_2, i_3, i_4, i_4', j_1, j_2, j_3, j_4, j_4' in Table 2, we have

    (a_i_1, a_i_2, α_i_3, α_i_4) = 4,      (a_i_1, a_i_2, α_i_3, α_i_4') = 3
    (b_j_1, b_j_2, β_j_3, β_j_4) = 3,      (b_j_1, b_j_2, β_j_3, β_j_4') = 4


Lemma <ref> is proved by brute force, i.e., verifying (<ref>) and (<ref>) hold for each case.

We show that the scheme is both correct and private.
The schemes is correct because as Lemma <ref> has proved, the 4 undesired symbols only have dimension 3 and it is easy to see that the 3 undesired symbols in answers from the first 3 servers have dimension 3. Therefore, from the answers A_1^[k], A_2^[k], A_3^[k], we always know the undesired symbol in A_4^[k]. Subtracting the undesired symbol out from A_4^[k], we obtain the desired symbol interference freely. Lemma <ref> has proved that the 4 desired symbols are independent such that we can recover the desired message.
The scheme is private because it is easy to verify that for any 3 servers, the queries are identically distributed no matter which message is desired and then the privacy condition (<ref>) is satisfied.

The scheme downloads 2 symbols from Server 1, Server 2 and Server 3 each, and 1 symbol from Server 4. It retrieves 4 desired message symbols. Therefore the rate is 4/7.

Let us conclude this example with the observation that this MDS-TPIR instance with (K,N,T,K_c) = (2,4,3,2) is not covered by Theorem <ref>,  but we were still able to find its capacity. Let us also note that we are able to cast this example into a similar framework as Theorem <ref> and prove the existence of  PIR schemes that achieve the same capacity for the (x,y)→(x,y,x+y,x+2y) MDS storage code, subject to the assumption of a sufficiently large finite field. The details are repetitive, and therefore omitted. However, we believe this example may provide useful insights for further generalizations.


 

 §.§ Achievability Proof for Theorem <ref> when T = 2

The proof for the general setting (arbitrary N) follows the same route as the N = 4 example presented earlier.
We assume that each message is comprised of L=N(N-1) independent symbols from a sufficiently large finite field 𝔽_p. 



  §.§.§ Storage Code

The (N-1,N) MDS storage code is as follows. 

    W_kn   ∈   𝔽_p^N × 1, k ∈ [1:2], n∈[1:N]
    
    W_k    =    (W_k1; W_k2; ⋯; W_k(N-1)) ∈𝔽_p^L × 1
    
    W_kN   =    W_k1 + W_k2 + ⋯ + W_k(N-1)




  §.§.§ Construction of Queries

The query to each server consists of 2(N-1) vectors, the first N-1 vectors for W_1 (Q_n^[k](W_1)) and the last N-1 vectors for W_2 (Q_n^[k](W_2)). The queries and downloads for W_k, k ∈ [1:2] are described next.


Denote the set of all full rank N × N matrices over 𝔽_p as 𝒮_N. The user privately chooses two matrices S, S', independently and uniformly from 𝒮_N. Label the rows of S as V_1, ⋯, V_N, and the rows of S' as U_1, ⋯, U_N-2, U_1, U_2. Define ∀ n ∈ [1:N]

    𝒱_n    =   {V_1, ⋯, V_n-1, V_n+1, ⋯, V_N}
    𝒰_n    =   {U_1, ⋯, U_N-2, U_n}

where U_n, n ∈ [1:N] are the rows of U, obtained as follows.

    U = _N × 2 (U_1; U_2)

where _N × 2 is an N× 2 matrix such that any two of its rows are linearly independent. 

When W_k is desired, we have ∀ n,


    n:
    Q_n^[k](W_k)    = π_n (𝒱_n),    A_n^[k](W_k)    = Q_n^[k](W_k) W_kn.



Desired Symbols Are Independent: From A_1:N^[k](W_k), we can recover all N(N-1) symbols of W_k. This is easily seen because the storage is an (N-1, N) MDS code, no query dimension is repeated more than N-1 times and the matrix S has full rank.

When W_k is undesired, we have ∀ n,


    n: Q_n^[k^c](W_k)    = π_n' (𝒰_n),    A_n^[k^c](W_k)    = Q_n^[k^c](W_k) W_kn.

Interfering Symbols Are Dependent and Have Dimension at most N(N-1) - (N-2):
Consider the interfering symbols along the common vectors U_i, i ∈ [1:N-2]. Note that 

    U_i W_k1 + ⋯ + U_i W_k(N-1) = U_i W_kN

Therefore (N-2) interfering symbols are linear combinations of the other N^2 - 2N + 2 symbols. 




  §.§.§ Combining Answers for Efficient Download

Based on the queries, each server has 2(N-1) symbols, N-1 in W_1, A_n^[k](W_1) and N-1 in W_2, A_n^[k](W_2) for a total of L = N(N-1) desired symbols and L = N(N-1) undesired symbols. Note that there are at most N^2 - 2N + 2 ≜ I independent undesired symbols. Exploiting this fact, we will combine the 2(N-1) queried symbols from each server into (I+L)/N  symbols to be downloaded by the user. Intuitively, (L+I)/N symbols from each server will give the user a total of L+I symbols, from which he can resolve the L desired and I undesired symbols.

Define the following function that maps 2L/N ∈ℤ_+ input symbols to (L+I)/N ∈ℤ_+ output symbols.

    ℒ^*(X_1, X_2, ⋯, X_L/N, Y_1, Y_2, ⋯, Y_L/N) 
       =    (X_1, ⋯, X_I/N, Y_1, ⋯, Y_I/N, X_I/N+1 + Y_I/N+1, ⋯, X_L/N + Y_L/N)



We formalize the combining process in the following lemma.

Suppose each server has L/N desired symbols and L/N undesired symbols. Across all servers, the L desired symbols are independent, while the L undesired symbols have dimension at most I, i.e., all L undesired symbols can be expressed as linear combinations of symbols in s, where s is a set of I symbols. Further, each server contains I/N distinct symbols in s.

The desired and undesired symbols are combined to produce the answers as follows.

    A_n^[k] = ℒ^*(C_n A_n^[k](W_1), C_n A_n^[k](W_2))

where C_n are  deterministic L/N × L/N matrices, that are required to satisfy the following two properties. Denote the first I/N rows of C_n as C_n.


  P1. All C_n have full rank.

  P2. For all (N-1)!^N distinct realizations of π_n', n ∈ [1:N], the I  symbols of the undesired message that are directly downloaded (I/N from each server), C_1 A_1^[k](W_k^c), C_2 A_2^[k](W_k^c), ⋯, C_N A_N^[k](W_k^c) are independent in variables in s. 


Then we have the following claim.

Claim. The C_n satisfying the two required properties exist over 𝔽_p for a sufficiently large prime p.[In fact, the properties are generic, i.e., they are satisfied by almost all matrices over large fields.]


This proof of existence will use Schwartz-Zippel lemma <cit.> about the roots of a polynomial. The variables for the polynomial are the coefficients of the C_n matrices. Let us start with an arbitrary choice of π_n', n ∈ [1:N].
Since all A_n^[k](W_k^c) can be expressed in terms of the I symbols in 
the vector s with constant coefficients, 
we can express

    (C_1 A_1^[k](W_k^c); ⋯; C_N A_N^[k](W_k^c)) = 𝒞_I× I s

Now consider the polynomial given by the determinant of 𝒞. This is not the zero polynomial[A polynomial is a zero polynomial if all its coefficients are zero.] because we can easily assign values to C_n  to make 𝒞 = I, the identity matrix. This is  because the queried symbols from each server include I/N distinct symbols in s. 

Next do the same for every realization of π_n', n ∈ [1:N]. As there are N permutations involved, and each can take (N-1)! different values, so we have a total of (N-1)!^N different possibilities. We will consider each of them separately. Each time we find a different 𝒞, which gives us a different non-zero polynomial.

Next consider the determinant of each C_n. This gives us another N non-zero polynomials.

For each of these (N-1)!^N + N polynomials, Schwartz-Zippel lemma guarantees that a uniformly random choice of C_n produces a non-zero evaluation with high probability over a large field (probability approaching 1 as p →∞). Since the intersection of finite number of high probability events is also a high probability event, there must exist a realization of C_n over a large field for which all (N-1)!^N + N polynomials simultaneously evaluate to non-zero values, i.e., a realization that satisfies both properties. Hence, the claim is true.





Next we prove that the  scheme retrieves the desired message,  and that it is T private.




  §.§.§ The Scheme is Correct (Retrieves Desired Message)

Note that from (<ref>), independent undesired message symbols distribute evenly across the databases, such that Lemma <ref> applies. 
Note that the first 2I/N variables in the output of the ℒ^* function are obtained directly, i.e., C_1 A_1^[k](W_1), C_2 A_2^[k](W_1), ⋯, C_N A_N^[k](W_1) and C_1 A_1^[k](W_2), C_2 A_2^[k](W_2), ⋯, C_N A_N^[k](W_2) are all directly recovered. By property P2 of C_n, C_1 A_1^[k](W_k^c), C_2 A_2^[k](W_k^c), ⋯, C_N A_N^[k](W_k^c) are linearly independent. Since we have recovered I independent dimensions of interference, and interference only spans at most I dimensions, all interference is recovered and eliminated. Further, since the L desired symbols are independent and since the C_n matrices have full rank, the user is able to recover the L desired message symbols after the interference symbols are recovered and subtracted from the downloaded equations. Therefore the scheme is correct  with zero error.





  §.§.§ The Scheme is Private (to any T=2 Colluding Servers)

To prove that the scheme is T = 2 private (refer to (<ref>)), it suffices to show that the queries for any 2 servers are identically distributed, regardless of which message is desired. Since each query is made up of 2(N-1) vectors, N-1 for each message and the vectors for W_1 and the vectors for W_2 are generated independently, it suffices to prove that the vectors for one message (say W_k) are identically distributed, i.e.,


    (Q_n_1^[k](W_k), Q_n_2^[k](W_k)) ∼(Q_n_1^[k^c](W_k), Q_n_2^[k^c] (W_k)), 
     ∀ n_1, n_2  ∈ [1:4], n_1 < n_2

Note that  
 
    (Q_n_1^[k](W_k), Q_n_2^[k](W_k)) = (π_n_1(𝒱_n_1), π_n_2(𝒱_n_2) ) 
    (Q_n_1^[k^c](W_k), Q_n_2^[k^c](W_k)) = (π_n_1' (𝒰_n_1), π_n_2' (𝒰_n_2) )

Therefore, to prove (<ref>) it suffices to show the following.

    ( V_1, ⋯, V_i_n_1-1, V_i_n_1+1, ⋯, V_i_n_2-1, V_i_n_2 +1, ⋯, V_N, V_i_n_2, V_i_n_1) ∼( U_1, ⋯, U_N-2, U_n_1, U_n_2)

Because S is uniformly chosen from the set of all full rank matrices, we have

    ( V_1, ⋯, V_i_n_1-1, V_i_n_1+1, ⋯, V_i_n_2-1, V_i_n_2 +1, ⋯, V_N, V_i_n_2, V_i_n_1)  ∼  S

Recall that S = (V_1, ⋯, V_N).
Next we note that there is a bijection between 

    ( U_1, ⋯, U_N-2, U_n_1, U_n_2)    ↔    S'

because of (<ref>) so that there is a bijection between U_n_1, U_n_2 and U_1, U_2. Recall that S' =  ( U_1, ⋯, U_N-2, U_1, U_2 ).
Now as S' is uniform over all full rank matrices, ( U_1, ⋯, U_N-2, U_n_1, U_n_2) is also uniform over all full rank matrices,

    ( U_1, ⋯, U_N-2, U_n_1, U_n_2)    ∼    S'

Finally, we note that S and S' are identically distributed, so we have

    S ∼ S'

Combining (<ref>), (<ref>) and (<ref>), we arrive at (<ref>) and (<ref>).



  §.§.§ Rate Achieved is (N^2 - N)/(2N^2 - 3N + 2)

The rate achieved is (N^2 - N)/(2N^2 - 3N + 2), because we download 2N^2 - 3N + 2 symbols in total and the desired message size is N(N-1) symbols. 





 §.§ Achievability Proof of Theorem <ref> when T >2

The proof for the general setting follows the same route as the N = 4, T = 3 example presented earlier.
We assume that each message is comprised of L=N(N-1) independent symbols from a sufficiently large finite field 𝔽_p. 



  §.§.§ Storage Code

The (N-1,N) MDS storage code is as follows. 

    W_kn   ∈   𝔽_p^N × 1, k ∈ [1:2], n∈[1:N]
    
    W_k    =    (W_k1; W_k2; ⋯; W_k(N-1)) ∈𝔽_p^L × 1
    
    W_kN   =    W_k1 + W_k2 + ⋯ + W_k(N-1)




  §.§.§ Construction of Queries

The query to each server consists of two vector spaces, one for W_1 (span of the rows of Q_n^[k](W_1)) and one for W_2 (span of the rows of  Q_n^[k](W_2)). The queries and downloads for W_k, k ∈ [1:2] are described next.

Denote the set of all full rank N × N matrices over 𝔽_p as 𝒮_N. The user privately chooses two matrices S, S', independently and uniformly from 𝒮_N. Label the rows of S as V_1, ⋯, V_N, and the rows of S' as U_1, ⋯, U_N-T, U_1, ⋯, U_T. Define ∀ n ∈ [1:N]

    𝒱_n    =   {V_1, ⋯, V_n-1, V_n+1, ⋯, V_N}
    𝒰_n    =   {U_1, ⋯, U_N-T, U_(n-1)(T-1)+1, ⋯, U_n(T-1)}

where U_1, ⋯, U_N(T-1) are the rows of U, obtained as follows.

    U = P (U_1; ⋯; U_T)

P is a deterministic N(T-1) × T matrix that is chosen in such a way that it allows a bijective mapping between the 𝒰_n or 𝒱_n spaces that may be observed by any set of up to T colluding servers. 

Intuitively, the only requirement on this matrix is that it is sufficiently `generic', so that almost all N(T-1) × T matrices over large finite fields are acceptable. Here unlike the previous example where we explicitly construct the matrix P, we will specify (later) the properties of this matrix and prove that such a matrix exists.

When W_k is desired, we have ∀ n,


    n:
    Q_n^[k](W_k)    = 𝔹 (𝒱_n), A_n^[k](W_k) = Q_n^[k](W_k) W_kn.


Desired Symbols Are Independent: From A_1:N^[k](W_k), we can recover all N(N-1) symbols of W_k. This is easily seen because the storage is an (N-1, N) MDS code and the matrix S has full rank.

When W_k is undesired, we have ∀ n,


    n: Q_n^[k^c](W_k)    = 𝔹 (𝒰_n), A_n^[k^c](W_k) = Q_n^[k^c](W_k) W_kn.

Interfering Symbols Are Dependent and Have Dimension at most N(N-1) - (N-T):
Consider the interfering symbols along the common vectors U_i, i ∈ [1:N-T]. Note that 

    U_i W_k1 + ⋯ + U_i W_k(N-1) = U_i W_kN

Therefore (N-T) interfering symbols are linear combinations of the other N^2 - 2N + T symbols. 



  §.§.§ Combining Answers for Efficient Download

The idea of combining is the same as the T = 2 setting. That is, we will combine the 2(N-1) queried symbols from each server into (2N^2-3N+T)/N = (L+I)/N symbols to be downloaded by the user. We will use the same combining function ℒ^* defined in (<ref>). The difference lies in the combining matrices C_n. For T = 2, C_n are deterministic and the scheme has zero-error, while here C_n are random and the scheme has ϵ-error, with ϵ approaching zero as the message size approaches infinity. The combining process is described in the following lemma, which corresponds to Lemma <ref> (with differences brought by random C_n accounted).












Suppose each server has L/N desired symbols and L/N undesired symbols from 𝔽_p. Across all servers, the L desired symbols are independent, while the L undesired symbols have dimension at most I, i.e., all L undesired symbols can be expressed as linear combinations of symbols in s, where s is a set of I symbols. Further, each server contains I/N distinct symbols in s.

The desired and undesired symbols are combined to produce the answers as follows.

    A_n^[k] = ℒ^*(C_n A_n^[k](W_1), C_n A_n^[k](W_2))

where C_n are  random L/N × L/N matrices, that are required to satisfy the following two properties. Denote the first I/N rows of C_n as C_n.


  P1. All C_n are full rank.

  P2. The I  symbols of the undesired message that are directly downloaded (I/N from each server), C_1 A_1^[k](W_k^c), C_2 A_2^[k](W_k^c), ⋯, C_N A_N^[k](W_k^c) are independent in variables in s. 


Then the following claim must be true.



Claim. The probability that C_n, n∈[1:N] with each element chosen independently and uniformly over 𝔽_p, satisfy the two required properties, approaches 1 as p→∞. 




Proof:
Without loss of generality, we assume that I/N is an integer. There is no loss of generality because if I/N is not an integer, we may repeat the scheme a number of times (say M) such that IM/N becomes an integer.

The proof relies on Schwartz-Zippel lemma <cit.> about the roots of a polynomial. The variables for the polynomial are the coefficients of the C_n matrices. 
Consider an arbitrary realization of the query spaces 𝒰_n. Generate uniformly random C_n, independent of 𝒰_n.


Given 𝒰_n, n∈[1:N], since all A_n^[k](W_k^c) can be expressed in terms of the I symbols of the vector s with constant coefficients, we can express

    (C_1 A_1^[k](W_k^c); ⋯; C_N A_N^[k](W_k^c)) = 𝒞_I × I s

Now consider the polynomial given by the determinant of 𝒞. This is not the zero polynomial because we can easily assign values to C_n  to make 𝒞 = I, the identity matrix. This is  because each server contains I/N distinct symbols in s. By the Schwartz-Zippel lemma, a non-zero polynomial evaluates to a non-zero value with probability approaching 1 as the field size p increases and C_n are chosen uniformly over 𝔽_p. Therefore Property P2 is satisfied with high probability.


Next consider the determinant of each C_n. This gives us another N non-zero polynomials.  When we choose C_n uniformly, the determinant of C_n is not zero almost surely for large p, so that C_n have full rank and Property P1 is satisfied with high probability.

Now, because Property P1 and P2 are each satisfied with probability approaching 1, the probability that the two are simultaneously satisfied also approaches 1 (union bound). 
Since this is true conditioned on every possible realization of 𝒰_n, n∈[1:N],  it is also true  unconditionally.









Next we prove that the  scheme retrieves the desired message,  and that it is T private.




  §.§.§ The Scheme is Correct (Retrieves Desired Message)

Note that from (<ref>), independent undesired message symbols distribute evenly across the databases, such that Lemma <ref> applies. 
Note that the first 2I/N variables in the output of the ℒ^* function are obtained directly, i.e., C_1 A_1^[k](W_1), C_2 A_2^[k](W_1), ⋯, C_N A_N^[k](W_1) and C_1 A_1^[k](W_2), C_2 A_2^[k](W_2), ⋯, C_N A_N^[k](W_2) are all directly recovered. By property P2 of C_n, C_1 A_1^[k](W_k^c), C_2 A_2^[k](W_k^c), ⋯, C_N A_N^[k](W_k^c) are linearly independent  with probability approaching 1 as p→∞. Since we have recovered I independent dimensions of interference, and interference only spans at most I dimensions, all interference is recovered and eliminated. Further, since the L desired symbols are independent and since the C_n matrices have full rank, the user is able to recover the L desired message symbols after the interference symbols are recovered and subtracted from the downloaded equations. Therefore the scheme is correct  with a probability of error ϵ that approaches 0 as the field size p approaches infinity. Note that since each message is comprised of L independent and uniformly random symbols in 𝔽_p, as p approaches infinity, the size of each message also approaches infinity. So, given any ϵ>0, we can find a sufficiently large p, and a correspondingly large message size value such that the probability of error of the scheme described above, is less than ϵ.





  §.§.§ The Scheme is Private (to any T Colluding Servers)


To prove that the scheme is T private (refer to (<ref>)), it suffices to show that the queries for any T servers are identically distributed, regardless of which message is desired. Since each query is made up of two vector spaces, one for each message and the two vector spaces are generated independently, it suffices to prove that the query spaces for one message (say W_k) are identically distributed whether it is desired or undesired. Consider an index set 𝒯 = {i_1, i_2, ⋯, i_T}⊂ [1:N] such that i_1 < i_2 < ⋯ < i_T. For all 𝒯, we require 

    (Q_i_1^[k](W_k), ⋯, Q_i_T^[k](W_k) )    ∼   (Q_i_1^[k^c](W_k), ⋯, Q_i_T^[k^c](W_k) ) 
    ⟺    (𝔹(𝒱_i_1), ⋯, 𝔹(𝒱_i_T) )    ∼   ( 𝔹(𝒰_i_1), ⋯, 𝔹(𝒰_i_T)  )

Note that 

    (𝔹(𝒱_i_1), 𝔹(𝒱_i_2), ⋯, 𝔹(𝒱_i_T) ) 
       =   (𝔹({V_𝒯^c, V_i_2, ⋯, V_i_T}), 𝔹({V_𝒯^c, V_i_1, V_i_3, ⋯, V_i_T}), 𝔹({V_𝒯^c, V_i_1, ⋯, V_i_T-1}) )

Next we transform the spaces on the RHS of (<ref>) to the form that is the same as (<ref>). 
To do this, we require the matrix P to satisfy the following properties.


  P1. For all 𝒯^* ={j_1,j_2,⋯,j_T-1}⊂ [1:N], |𝒯^*| = T-1, j_1<j_2<⋯ <j_T-1, there exists a function m_𝒯^*(P) that returns a non-zero vector which lies simultaneously in the spans of each of P_j_t≜ P((j_t-1)(T-1)+1:j_t(T-1),:), t∈[1:T-1]. 
Note that m_𝒯^*(P) is a 1 × T row vector that only depends on P (it does not depend on U).


  P2. For each 𝒯 = {i_1, i_2, ⋯, i_T}⊂ [1:N], the vectors m_𝒯^*(P), ∀𝒯^* ⊂𝒯, |𝒯^*| = T-1 (found in P1) are linearly independent. Equivalently, we require the following T × T matrix to have full rank.

    P_𝒯≜ (m_{i_[1:T]/{T}}(P); m_{i_[1:T]/{T-1}}(P); ⋯; m_{i_[1:T]/{1}}(P))



Claim. The P satisfying the two required properties exists over 𝔽_p for a sufficiently large p.

Similar to the proof of existence of C_n matrices presented earlier, this proof of existence will use Schwartz-Zippel lemma <cit.> about the roots of a polynomial. The variables for the polynomial are the coefficients of the P matrix. Since P is a N(T-1) × T matrix,  we have a total of NT(T-1) variables. Define a set 𝒫 that is comprised of all non-zero polynomials with NT(T-1) variables of P as its variables, and coefficients from 𝔽_p.

We first consider Property P1. Recall that there are  NT-1 choices for 𝒯^*. Let us start with an arbitrary choice of 𝒯^* = {j_1, j_2, ⋯, j_T-1} such that j_1 < j_2 < ⋯ < j_T-1.  The required non-zero vector m_𝒯^*(P) is found as follows.

    m_𝒯^*(P) = H_1 P_j_1 = H_2 P_j_1 = ⋯ = H_T-1 P_j_T-1
       ⇒   [
    [   H_1   H_2     ⋯ H_T-1 ]]
    [
    [    P_j_1    P_j_1        ⋯    P_j_1;   -P_j_2        0        ⋯        0;        ⋮   -P_j_3        ⋱        0;        0        0        0 -P_j_T-1 ]]_≜ P_𝒥
     =
    [
    [ 0 0 ⋯ 0 ]]

where P_j_t, t ∈ [1:T-1] are (T-1) × T matrices, 0 is the (T-1) × T matrix with all elements equal to 0 and P_𝒥 is a (T-1)^2 × T(T-2) matrix.
Note that the left null space of P_𝒥 is exactly of one dimension if P_𝒥 has full rank. Consider the matrix P_𝒥^*, which is a square matrix formed by the last T(T-2) rows of P_𝒥. We claim that the determinant of P_𝒥^* is a non-zero polynomial, i.e., |P_𝒥^*|∈𝒫. This is because we can identify a specific choice of P_j_t such that |P_𝒥^*| is not zero, as follows. We set P_j_t to be the matrix obtained by inserting an all zero column as the (T+1- t)^th column of the (T-1) × (T-1) identity matrix I_T-1. Equivalently, this means that

    P_j_t U    =    (U_1; ⋯; U_T-t; U_T+2-t; ⋯; U_T), t ∈ [1:T-1]

Since U_1, ⋯, U_T are independent,  m_𝒯^*(P) U can only be some scaled version of the U_1 vector.
This means that P_𝒥^* has full rank (which is also easily verified by plugging the vaules of P_j_t in P_𝒥^*). Therefore, |P_𝒥^*|∈𝒫.
To make m_𝒯^*(P) a function, i.e., to remove ambiguity due to scaling factors,   let us normalize the vector [H_1, ⋯, H_T-1] by its first element, h, such that this vector is unique (scaling is fixed). Note that h∈𝒫 because if we use the same special choice of P_j_t as above, we find that h = 1 (non-zero). With normalized [H_1, ⋯, H_T-1], we obtain m_𝒯^*(P). Note that each element of m_𝒯^*(P) also belongs to 𝒫. 

Now do the same for every possible choice of 𝒯^*. There are NT-1 possibilities. We will consider each of them separately. Each time we obtain different |P_𝒥^*|, h ∈𝒫 and find a different m_𝒯^*(P). Putting all of these together, we have a set of 2 NT-1 non-zero polynomials. 

Next consider Property P2. Similarly, we consider all choices of 𝒯 separately. For each choice of 𝒯 = {i_1, i_2, ⋯, i_T} such that i_1 < i_2 ⋯ < i_T, we consider the determinant of P_𝒯.
This determinant polynomial is non-zero because we may set P_i_t, t ∈ [1:T] to be the matrix obtained by inserting an all zero column as the (T+1- t)^th column of I_T-1, such that the common vector m_𝒯^*(P), ∀𝒯^* ∈𝒯, |𝒯^*| = T-1 can be computed explicitly

    P_i_t U    =    (U_1; ⋯, U_T-t; U_T+2-t⋯; U_T)
    
    
    m_{i_[1:T]/{t}}(P)    =     e_T+1 - t,  ∀ t ∈ [1:T]

where e_i represents the 1 × T unit row vector with a 1 in the i^th location and 0 at all other locations.
Therefore, P_𝒯 is an identity matrix and the determinant is 1 (non-zero). With all choices of 𝒯, we have another NT non-zero polynomials.

By Schwartz-Zippel lemma, as the field size grows, for each of the polynomials mentioned above, a uniform choice of P produces a  non-zero evaluation with probability approaching 1. By the union bound, the probability that all polynomials simultaneously produce a non-zero value also approaches 1. In particular, for a sufficiently large field this probability is not zero, so there must exist a P matrix that satisfies both properties.


Because of the two properties, we may equivalently represent Q_i_t^[k^c](W_k), t ∈ [1:T] as

    Q_i_t^[k^c](W_k) =  𝔹(𝒰_i) = 𝔹({U, U_{i_[1:T]/{1}}, ⋯, U_{i_[1:T]/{t-1}}, U_{i_[1:T]/{t+1}}, ⋯, U_{ i_[1:T]/{T}}}),


We are now ready to prove the privacy condition (<ref>). 

    (<ref>) ⟺      (𝔹({V_𝒯^c, V_i_2, ⋯, V_i_T}), 𝔹({V_𝒯^c, V_i_1, V_i_3, ⋯, V_i_T}), 𝔹({V_𝒯^c, V_i_1, ⋯, V_i_T-1}) ) 
       ∼   ( 𝔹({U, U_{i_[1:T]/{2}}, ⋯, U_{i_[1:T]/{T}}}), 𝔹({U, U_{i_[1:T]/{1}}, U_{i_[1:T]/{3}}, ⋯, U_{i_[1:T]/{T}}}), 
           ⋯, 𝔹({U, U_{i_[1:T]/{1}}, ⋯, U_{ i_[1:T]/{T-1}}})  )

Therefore, it suffices to show the following.

    (V_𝒯^c, V_i_1, V_i_2, ⋯, V_i_T) ∼ (U, U_{i_[1:T]/{1}}, U_{i_[1:T]/{2}}, ⋯, U_{i_[1:T]/{T}})

Because S is uniformly chosen from the set of all full rank matrices, we have

    (V_𝒯^c, V_i_1, V_i_2, ⋯, V_i_T) ∼ (V_1, V_2, ⋯, V_N)

Because of  Property P2, there is a bijection between 

    (U, U_{i_[1:T]/{1}}, U_{i_[1:T]/{2}}, ⋯, U_{i_[1:T]/{T}}) ↔  (U, U)

Now since S' = (U; U) is uniform in all full rank matrices, the  bijection implies that  (U, U_{i_[1:T]/{1}}, U_{i_[1:T]/{2}}, ⋯, U_{i_[1:T]/{T}}) is also uniform in all full rank matrices, i.e.,

    (U, U_{i_[1:T]/{1}}, U_{i_[1:T]/{2}}, ⋯, U_{i_[1:T]/{T}}) ∼  (U, U)

Finally, note that S and S' have the same distribution, so we have

    (V_1, V_2, ⋯, V_N) ∼ (U, U)

Therefore, from (<ref>), (<ref>) and (<ref>), we have proved (<ref>) and (<ref>).


  §.§.§ Rate Achieved is (N^2 - N)/(2N^2 - 3N + T)

The rate achieved is (N^2 - N)/(2N^2 - 3N + T), because we download 2N^2 - 3N + T symbols in total and the desired message size is N(N-1) symbols. 




 §.§ Converse for Arbitrary K

In this section, we consider the information theoretic converse of MDS-TPIR, for two scenarios, 
one with (K, N, T, K_c) = (K, 4, 2, 2) and the other with (K, N, T, K_c) such that N < T + K_c. For both scenarios, we provide outer bounds that hold for arbitrary K. 

Let us start with two useful lemmas that hold for arbitrary K, N, T, K_c.

For all 𝒯⊂ [1:N], |𝒯| = T and k, k' ∈ [1:K],

    (A_𝒯^[k], W_1, ⋯, W_K, ℱ, 𝒢) ∼ (A_𝒯^[k'], W_1, ⋯, W_K, ℱ, 𝒢)



Proof: From (<ref>), we know that Q_𝒯^[k]∼ Q_𝒯^[k']. Combining with (<ref>), we have

    H(Q_𝒯^[θ] | ℱ) = 0

From (<ref>), we have

    I(θ; W_1, ⋯, W_K, ℱ, 𝒢) = 0 
       (<ref>)⟹    I(θ; W_1, ⋯, W_K, ℱ, 𝒢, Q_𝒯^[θ]) = 0 
       (<ref>)(<ref>)(<ref>)⟹    I(θ; W_1, ⋯, W_K, ℱ, 𝒢, A_𝒯^[θ]) = 0 
       ⟹    (A_𝒯^[k], W_1, ⋯, W_K, ℱ, 𝒢) ∼ (A_𝒯^[k'], W_1, ⋯, W_K, ℱ, 𝒢)




For all 𝒦_c = {n_1, n_2, ⋯, n_K_c}⊂ [1:N],

    H(A_𝒦_c^[1] | W_1, ℱ, 𝒢) = ∑_n ∈𝒦_c H(A_n^[1] | W_1, ℱ, 𝒢)


Proof: From (<ref>) and (<ref>), we know that for any K_c servers, the stored information is independent. 

    H(W_k𝒦_c) = ∑_n ∈𝒦_c H(W_k n), ∀ k ∈ [1:K] 
       (<ref>)⟹    H(W_2𝒦_c, ⋯, W_K𝒦_c | W_1, ℱ, 𝒢)
    = ∑_n ∈𝒦_c∑_k=2^K H(W_k n | W_1, ℱ, 𝒢)

As answers are functions of the storage, the answers from any K_c servers are independent as well. Consider two arbitrary  subsets of 𝒦_c that have no overlap, 𝒦_1, 𝒦_2 ⊂𝒦_c, 𝒦_1 ∩𝒦_2 = ∅.

    I(A_𝒦_1^[1]; A_𝒦_2^[1] | W_1, ℱ, 𝒢) 
       ≤    I(A_𝒦_1^[1]; A_𝒦_2^[1], W_2𝒦_2, ⋯, W_K𝒦_2 | W_1, ℱ, 𝒢) 
       (<ref>)(<ref>)=    I(A_𝒦_1^[1]; W_2𝒦_2, ⋯, W_K𝒦_2 | W_1, ℱ, 𝒢) 
       (<ref>)(<ref>)≤    I(W_2𝒦_1, ⋯, W_K𝒦_1 ; W_2𝒦_2, ⋯, W_K𝒦_2 | W_1, ℱ, 𝒢) 
       (<ref>)=    0

Using (<ref>) repeatedly, we obtain (<ref>).


Next we proceed to the two scenarios.
To highlight the parameter K, in this section, the capacity C and the download cost D are denoted as C(K) and D(K), respectively.


  §.§.§ (K, N, T, K_c) = (K, 4, 2, 2)

For the setting with (K, N, T, K_c) = (K, 4, 2, 2), we obtain a recursive upper bound that holds for arbitrary K. This result is stated in the following theorem.

For the class of MDS-TPIR instances with (K,N, T, K_c)=(K,4,2,2), with arbitrary K, the following recursive relation on the capacity outer bound C(K) ≥ C(K) holds. 

    C(K)    ≤   ( 1 + 3/8( 1/C(K-1))  + (1 - (2/3)^K-1) 3/4)^-1, ∀ K ≥ 2 
    C(1)   =    1


Consider an MDS-TPIR instance with (K,N, T, K_c)=(K,4,2,2). When K = 1, C(1) = 1 is a trivial bound on C(1). Next we consider K ≥ 2. Define

    C(K)    =    L/H(A_1:4^[1] | ℱ, 𝒢) 
    C(K-1)    =    L/H(A_1:4^[2] | W_1, ℱ, 𝒢)

C(K) is a valid outer bound on C(K), since

    C(K) = L/H(A_1:4^[1] | ℱ, 𝒢) ≥ L/D(K) = C(K)

Similarly, C(K-1) is a valid outer bound on C(K-1).
Now, substituting (<ref>) and (<ref>) to (<ref>), we have

    H(A_1:4^[1] | ℱ, 𝒢)/L ≥ 1 + 3/8  H(A_1:4^[2] | W_1, ℱ, 𝒢)/L + (1 - (2/3)^K-1) 3/4


We proceed to prove (<ref>). To simplify the notation, we define (W_1i, W_2i, ⋯, W_Ki) = W_*i, i ∈ [1:N].

    H(A_1:4^[1] | ℱ, 𝒢) 
       (<ref>)=    H(A_1:4^[1], W_1 | ℱ, 𝒢) + o(L) L 
       (<ref>)=    H(W_1) + H(A_1^[1] | W_1, ℱ, 𝒢) + H(A_2:4^[1] | W_1, A_1^[1], ℱ, 𝒢)  + o(L) L
       ≥    H(W_1) + H(A_1^[1] | W_1, ℱ, 𝒢) + H(A_3:4^[1] | W_1, W_*1, A_1^[1], ℱ, 𝒢) + o(L) L
       (<ref>)(<ref>)(<ref>)=    L + H(A_1^[1] | W_1, ℱ, 𝒢) + H(A_3:4^[1] | W_1, W_*1, ℱ, 𝒢) + o(L) L
       (<ref>)(<ref>)=    L + H(A_1^[2] | W_1, ℱ, 𝒢) + H(A_3:4^[2] | W_1, W_*1, ℱ, 𝒢)  + o(L) L

Advancing the databases indices, from (<ref>), we have

    H(A_1:4^[1] | ℱ, 𝒢)  
       ≥    L + H(A_1^[2] | W_1, ℱ, 𝒢) + H(A_2:3^[2] | W_1, W_*1, ℱ, 𝒢) + o(L) L

Adding (<ref>) and (<ref>), we have

    H(A_1:4^[1] | ℱ, 𝒢) + o(L) L 
       ≥    L + H(A_1^[2] | W_1, ℱ, 𝒢) + 1/2( H(A_3:4^[2] | W_1, W_*1, ℱ, 𝒢) + H(A_2:3^[2] | W_1, W_*1, ℱ, 𝒢) ) 
       ≥    L + H(A_1^[2] | W_1, ℱ, 𝒢) + 1/2( H(A_2:4^[2] | W_1, W_*1, ℱ, 𝒢) + H(A_3^[2] |  W_1, W_*1, ℱ, 𝒢) ) 
       (<ref>)(<ref>)(<ref>)=    L + H(A_1^[2] | W_1, ℱ, 𝒢) + 1/2 H(A_3^[2] | W_1, ℱ, 𝒢) + 1/2 H(A_2:4^[2] | W_1, W_*1, ℱ, 𝒢)

where we use the sub-modular property of entropy functions to obtain (<ref>).
Now consider the term H(A_2:4^[2] | W_1, W_*1, ℱ, 𝒢). This corresponds to the total download for the setting where we have 3 servers (servers 2, 3 and 4), K-1 messages (W_2, W_3, ⋯, W_K), each message is of length L/2 and the MDS code is fully replicated (conditioning on W_*1, each other server contains the other half information of entropy L/2 about each message), i.e., the TPIR setting. W_2 is the desired message. As the capacity of this TPIR setting is 1/3(1 - (2/3)^K-1)^-1 <cit.>, we have

    H(A_2:4^[2] | W_1, W_*1, ℱ, 𝒢) ≥ 3(1 - (2/3)^K-1) L/2

Substituting back to (<ref>) and advancing database indices, we have ∀ i, j ∈ [1:4], i ≠ j,

    H(A_1:4^[1] | ℱ, 𝒢) + o(L) L 
       ≥    L + H(A_i^[2] | W_1, ℱ, 𝒢) + 1/2 H(A_j^[2] | W_1, ℱ, 𝒢) + (1 - (2/3)^K-1) 3L/4

Adding (<ref>) for all i, j ∈ [1:4], we have

    H(A_1:4^[1] | ℱ, 𝒢) + o(L) L 
       ≥    L + 1/4∑_i=1^4 H(A_i^[2] | W_1, ℱ, 𝒢) + 1/8∑_j=1^4 H(A_j^[2] | W_1, ℱ, 𝒢) + (1 - (2/3)^K-1) 3L/4
       ≥    L + 3/8  H(A_1:4^[2] | W_1, ℱ, 𝒢) + (1 - (2/3)^K-1) 3L/4

Normalizing both sides by L, we arrive at (<ref>).


Two observations from the converse argument are listed below.


  * When we set K=2, we obtain the information theoretic bound 8/13.

    C(2)    ≤   C(2) 
       (<ref>)≤    (1 + 3/8 × 1/C(1) +  (1-2/3) × 3/4)^-1
       (<ref>)=    (1 + 3/8 × 1 +  (1-2/3) × 3/4)^-1 = 8/13



  * As K→∞, the capacity upper bound converges to 5/14.
Since the MDS-TPIR scheme of Freij-Hollanti et al. <cit.> achieves the rate 1/4 for this setting as K→∞, we note that the asymptotic optimality of the scheme remains open.




  §.§.§ (K, N, T, K_c) with N < T + K_c

For the setting with (K, N, T, K_c) and N < T + K_c, we obtain a recursive upper bound that holds for arbitrary K. This result is stated in the following theorem.

For the class of MDS-TPIR instances (K,N, T, K_c) such that N < T + K_c, with arbitrary K, N, T, K_c, the following recursive relation on the capacity outer bound C(K) ≥ C(K) holds. 

    C(K)    ≤   ( 1 + N-T/N( 1/C(K-1)) + (K-1)(1-N-T/K_c) )^-1, ∀ K ≥ 2
    C(1)   =    1

Therefore, for constant N, T, K_c, when K →∞, C(K) decreases linearly with K such that downloading everything (rate 1/K) is order optimal.

Consider an MDS-TPIR instance (K,N, T, K_c) such that N < T + K_c. When K = 1, C(1) = 1 is a trivial bound on C(1). Next we consider K ≥ 2. Define

    C(K)    =    L/H(A_1:N^[1] | ℱ, 𝒢) 
    C(K-1)    =    L/H(A_1:N^[2] | W_1, ℱ, 𝒢)

C(K) is a valid outer bound on C(K), since

    C(K) = L/H(A_1:N^[1] | ℱ, 𝒢) ≥ L/D(K) = C(K)

Similarly, C(K-1) is a valid outer bound on C(K-1).
Now, substituting (<ref>) and (<ref>) to (<ref>), we have

    H(A_1:N^[1] | ℱ, 𝒢)/L≥ 1 + N-T/NH(A_1:N^[2] | W_1, ℱ, 𝒢)/L + (K-1)(1-N-T/K_c)


We proceed to prove (<ref>). 
Consider an index set 𝒩⊂ [1:N] with cardinality |𝒩| = N-T  < K_c. Denote the complement of 𝒩 as 𝒩^c.

    H(A_1:N^[1] | ℱ, 𝒢) 
       (<ref>)=    H(A_1:N^[1], W_1 | ℱ, 𝒢) +o(L) L 
       (<ref>)=    H(W_1) + H(A_𝒩^[1] | W_1, ℱ, 𝒢) + H(A_𝒩^c^[1] | W_1, A_𝒩^[1], ℱ, 𝒢) +o(L) L 
       (<ref>)(<ref>)≥    L + ∑_n ∈𝒩 H(A_n^[1] | W_1, ℱ, 𝒢) 
    + H(A_𝒩^c^[1] | W_1, W_*𝒩, A_𝒩^[1], ℱ, 𝒢) +o(L) L
       (<ref>)(<ref>)(<ref>)=    L + ∑_n ∈𝒩 H(A_n^[1] | W_1, ℱ, 𝒢)  + H(A_𝒩^c^[1] | W_1, W_*𝒩, ℱ, 𝒢) +o(L) L 
       (<ref>)(<ref>)=    L + ∑_n ∈𝒩 H(A_n^[2] | W_1, ℱ, 𝒢)  + H(A_𝒩^c^[2] | W_1, W_*𝒩, ℱ, 𝒢) +o(L) L 
       (<ref>)(<ref>)(<ref>)=    L + ∑_n ∈𝒩 H(A_n^[2] | W_1, ℱ, 𝒢) + H(A_1:N^[2] | W_1, W_*𝒩, ℱ, 𝒢) +o(L) L 
       (<ref>)≥    L + ∑_n ∈𝒩 H(A_n^[2] | W_1, ℱ, 𝒢) + H(A_1:N^[2], W_2 | W_1, W_*𝒩, ℱ, 𝒢)  + o(L) L 
       ≥    L + ∑_n ∈𝒩 H(A_n^[2] | W_1, ℱ, 𝒢) + H(W_2 | W_1, W_*𝒩, ℱ, 𝒢) +  H(A_1:N^[2] | W_1, W_2, W_*𝒩, ℱ, 𝒢) + o(L) L
          
       (<ref>)(<ref>)(<ref>)=    L + ∑_n ∈𝒩 H(A_n^[2] | W_1, ℱ, 𝒢) + L(K_c - |𝒩|)/K_c + H(A_1:N^[2] | W_1, W_2, W_*𝒩, ℱ, 𝒢)+ o(L) L 
       (<ref>)(<ref>)(<ref>)=    L + ∑_n ∈𝒩 H(A_n^[2] | W_1, ℱ, 𝒢) + L(K_c - N + T)/K_c + H(A_𝒩^c^[2] | W_1, W_2, W_*𝒩, ℱ, 𝒢) + o(L) L

To bound the term H(A_𝒩^c^[2] | W_1, W_2, W_*𝒩, ℱ, 𝒢), we repeat (<ref>) to (<ref>) for messages W_3, ⋯, W_K. This gives us

    H(A_1:N^[1] | ℱ, 𝒢) 
       ≥    L + ∑_n ∈𝒩 H(A_n^[2] | W_1, ℱ, 𝒢) + L(K-1)(1-N-T/K_c) + o(L) L

Consider (<ref>) for all subsets of [1:N] that have exactly N-T elements and average over all such subsets. We have

    H(A_1:N^[1] | ℱ, 𝒢) 
       ≥    L + 1/NN-T∑_𝒩: |𝒩| = N -T∑_n ∈𝒩 H(A_n^[2] | W_1, ℱ, 𝒢) + L(K-1)(1-N-T/K_c) + o(L) L 
       ≥    L + N-T/N H(A_1:N^[2] | W_1, ℱ, 𝒢) + L(K-1)(1-N-T/K_c) + o(L) L

Letting L →∞ and normalizing by L, we have proved (<ref>) and (<ref>). 

Based on Theorem <ref> the following observations are relevant.


  * When we set K=2, K_c = N-1, we obtain the information theoretic bound for Theorem <ref>, i.e., (N^2 - N)/(2N^2 - 3N + T).

    C(2)    ≤   C(2) 
       (<ref>)≤   (1 + N-T/N×1/C(1) +  (2-1)(1-N-T/N-1) )^-1
       (<ref>)=   (1 + N-T/N× 1 +  T-1/N-1)^-1 = N^2 - N/2N^2 - 3N + T


  * As K→∞, Theorem <ref> shows that the capacity decays as 1/K, so that it converges to 0. As a sanity check, we note that indeed, the MDS-TPIR scheme of Freij-Hollanti et al. <cit.>, which does not depend on the number of messages K, does not apply when N<T+K_c. Thus, in this case the asymptotic optimality as K→∞ is trivially settled.





 §.§ Restricted Colluding Sets

Recall that for the setting of our counterexample, i.e., (K, N, T, K_c)=(2,4,2,2), while the linear capacity is settled, the information theoretic capacity remains open. In particular, the best information theoretic capacity upper bound that we were able to obtain is 8/13. To gain  insights into the potential tightness of this bound, here we look into the capacity of this setting with restricted colluding sets, a line of inquiry recently initiated by Tajeddine et al. in <cit.>. Our motivation for studying restricted colluding sets comes from the following observation.

Consider TPIR, for which the capacity is known <cit.>. The TPIR formulation allows the possibility that any set of up to T servers may collude. However, suppose we relax the privacy constraint, by allowing only collusions between cyclically contiguous servers, i.e., the colluding servers must belong to the set of servers indexed {n, n+1, ⋯, n+T-1} for some n∈[1:N], with the indices interpreted modulo N. Because of the symmetry that is still maintained across servers, it is readily verified that the converse proof for TPIR in <cit.> still goes through unchanged. Thus, even though the restriction on colluding sets to cyclically contiguous servers relaxes the privacy constraint, it does not affect the capacity of TPIR.



 
This  leads us to question if a similar property might hold for MDS-TPIR. If so, then we could gain insights into the capacity of MDS-TPIR by imposing similar restrictions on the colluding sets. This line of thought leads us to two somewhat contrasting observations, that are presented in the following two subsections.





  §.§.§ (K, N, T,K_c) = (2,4,2,2) with Cyclically Adjacent Colluding Sets

Our first observation is in favor of the tightness of the upper bound 8/13. Indeed, if colluding sets were restricted to cyclically contiguous sets then 8/13 is the capacity for the MDS-TPIR setting (K, N, T, K_c)=(2,4,2,2). This observation is summarized in a bit more detail next.


For our counterexample we  considered the MDS-TPIR setting (K, N, T, K_c) = (2,4,2,2) where any 2 servers may collude. Suppose, now we restrict the colluding sets of servers to cyclically adjacent pairs, i.e., any one of {1,2}, {2,3}, {3,4}, {4,1}.  Essentially we have relaxed the privacy constraint by eliminating the possibilities that Server 1 might collude with Server 3, or that Server 2 might collude with Server 4. For this setting, we show that the capacity is 8/13.



The converse is similar to that with T = 2, presented in Section <ref>. (<ref>) holds with restricted colluding sets when K = 2, because we are left with only K - 1 = 1 message. All other steps follow similarly because the assumption of symmetry across servers  holds under cyclically adjacent colluding sets. As a result, the capacity upper bound of 8/13 (refer to (<ref>)) holds here.

Next, we summarize the achievable scheme. The message construction and the storage code are specified as follows. 

    W_kn∈𝔽_p^4× 1, k ∈ [1:2], n ∈ [1:4] 
          W_k = (W_k1; W_k2) ∈𝔽_p^8 × 1
          W_k3 = W_k1 + W_k2, W_k4 = W_k1 + 2W_k2

The construction of queries is similar to that with T= 2 in Section <ref>. The query to each server Q_n^[k] is comprised of two parts, Q_n^[k](W_1), Q_n^[k](W_2). Each part contains 2 row vectors, along which the server should project its corresponding stored message symbols. To generate the query vectors, the user privately chooses two matrices, S = (V_1;V_2; V_3; V_4) and S' = (U_0; U_1; U_2; U_3), independently and uniformly from 𝒮_4, the set of all full rank 4 × 4 matrices over 𝔽_p. Define

    𝒱_1={V_1, V_2},      𝒰_1={U_0, U_1+U_2}
    𝒱_2={V_2, V_3},      𝒰_2={U_0, U_1+2U_2}
    𝒱_3={V_3, V_4},      𝒰_3={U_0, U_1}
    𝒱_4={V_4, V_1},      𝒰_4={U_0, U_2}

Independent random orderings of the rows in 𝒱_n are the queries to Server n for the desired message and independent random orderings of the rows in 𝒰_n are the queries to Server n for the undesired message. The rate achieved is 8/13 because the 8 desired symbols along the V_i vectors are all independent and the 8 undesired symbols occupy only 5 dimensions (the 4 symbols along U_0 contribute only 2 independent dimensions and the remaining 4 symbols contribute only 3 independent dimensions). Privacy follows from the observation that for each cyclically adjacent colluding set of servers, say Server 1 and Server 2, the sets 𝒱_1,𝒱_2 intersect in one of their elements, as do the sets 𝒰_1,𝒰_2, and both are otherwise uniformly random, thus making the distinction of 𝒰,𝒱 invisible to the colluding servers. Note that this scheme is not private to the non-adjacent colluding servers, say Server 1 and Server 3, because, 𝒱_1,𝒱_3 contain no common vectors, while 𝒰_1,𝒰_3 do share a common vector. The remaining details are virtually identical to the settings already covered in Section <ref> and Section <ref> and are omitted. 











  §.§.§ Disjoint Colluding Sets of T Servers Each

Our second observation provides a counterpoint to the first observation. The first observation favored the tightness of 8/13 bound based on the insight originating from TPIR, that certain restrictions on colluding sets may not affect capacity. The second observation challenges this viewpoint by showing that insights from TPIR do not carry over to MDS-TPIR. 


Consider again the TPIR problem. Suppose T divides N, i.e., mT=N for some m∈ℤ_+, and we partition the N servers into the m disjoint sets of T elements each: 𝒯_1={1,2,⋯, T}, 𝒯_2={T+1,T+2,⋯, 2T}, ⋯, 𝒯_m={(m-1)T+1, (m-1)T+2, ⋯, N}. Further, suppose we relax the privacy constraint and allow collusions between only those servers that belong to the same 𝒯_i, i∈[1:m]. Then, note that the TPIR problem with restricted colluding sets becomes equivalent to the PIR problem with N/T=m servers.[This is because storage is fully replicated, so that each disjoint set of T colluding servers may be equivalently replaced with 1 server.] However, the capacity of PIR with N/T servers is the same as the capacity of TPIR with N servers. Therefore, relaxing the privacy constraint by restricting the colluding sets to disjoint sets of cardinality T each, in the manner described above, does not affect the capacity of TPIR. However, as we will show next, the same is not true for MDS-TPIR.


Consider MDS-TPIR with (K, N, T, K_c)=(2,4,3,2), where any T=2 of the N=4 servers may collude. From Theorem <ref> we know that the capacity of this setting is 6/11. 
However, now suppose we partition the servers into disjoint sets 𝒯_1={1,2}, 𝒯_2={3,4}, each of cardinality T=2. Now we allow collusions only between servers in the same 𝒯_i set, i.e., Server 1 can only collude with Server 2, while Server 3 can only collude with Server 4. Then, in contrast to TPIR where such a restriction on colluding sets does not affect the capacity, we now show that with these restricted colluding sets, the capacity of MDS-TPIR changes — it increases from 6/11 to 4/7.


The converse for rate 4/7 is trivial, because the rate can not be higher than that of MDS-PIR with (K, N, K_c) = (2,4,3), where privacy needs to be ensured only to each individual server. From <cit.>, we know that the capacity of MDS-PIR with (K, N, K_c) = (2,4,3) is 4/7. Therefore, the upper bound follows.

Next, we consider the achievable scheme. Each message consists of 12 symbols. The storage code is specified as follows. 

    W_kn∈𝔽_p^4× 1, k ∈ [1:2], n ∈ [1:4] 
          W_k = (W_k1; W_k2; W_k3) ∈𝔽_p^12 × 1
          W_k4 = W_k1 + W_k2 + W_k3

The query to each server Q_n^[k] is comprised of vectors in 𝒱_n and 𝒰_n, given as follows. 

    𝒱_1={V_1, V_3, V_5},      𝒰_1={U_0, U_1, U_2}
    𝒱_2={V_1, V_3, V_5},      𝒰_2={U_0, U_1, U_2}
    𝒱_3={V_2, V_4, V_6},      𝒰_3={U_0, U_1, U_2}
    𝒱_4={V_2, V_4, V_6},      𝒰_4={U_0, U_1,U_2}

where S = (V_1;V_2; V_3; V_4; V_5; V_6) and S' = (U_0; U_1; U_2; U_3; U_4; U_5) are independent and uniform from the set of all full rank 6 × 6 matrices. 
The rate achieved is 12/(12+9) = 4/7 because the 12 desired symbols along the V_i vectors are all independent and the 12 undesired symbols occupy only 9 dimensions (the symbols along each U_i, i∈{0,1,2}, occupy only K_c = 3 dimensions). Privacy follows from the observation that for either colluding set {1,2} or {3,4}, the vectors in 𝒱 and 𝒰 are both the same. The remaining details can be filled in based on Section <ref> and Section <ref> and are omitted. 

In light of the two contrasting observations, the tightness of the 8/13 upper bound, as well as the general impact of restricted colluding sets on the capacity of MDS-TPIR remain intriguing open problems for future work. For readers interested in the latter problem, we conclude this section with two simple examples of such capacity characterizations. 



  §.§.§ Examples of Capacity of MDS-TPIR under Restricted Colluding Sets

As usual in this section, we will omit details of achievability arguments that follow directly from Section <ref> and Section <ref>.



  
Example 1
Consider the setting (K, N, K_c)=(2,4,2) and let the restricted colluding sets be {1,2}, {3,4}. Alternatively, let the restricted colluding sets be {1,2}, {3}, {4}. In either case, the capacity is 2/3, same as that of MDS-PIR with (K, N, K_c) = (2, 4, 2) <cit.> so that the converse is implied. The scheme that achieves rate 4/6= 2/3 is as follows.

    W_kn∈𝔽_p^2× 1, k ∈ [1:2], n ∈ [1:4] 
          W_k = (W_k1; W_k2) ∈𝔽_p^4 × 1
          W_k3 = W_k1 + W_k2, W_k4 = W_k1 + 2W_k2
          𝒱_1={V_1}, 𝒰_1={U_0}
          𝒱_2={V_1}, 𝒰_2={U_0}
          𝒱_3={V_2}, 𝒰_3={U_0}
          𝒱_4={V_2}, 𝒰_4={U_0}

where S = (V_1;V_2) and S' = (U_0; U_1) are independently and uniformly chosen from the set of all full rank 2 × 2 matrices. 



  
Example 2
Suppose (K, N, K_c) = (2, 3, 2) and the colluding sets are either {1,2},{2,3}.
Alternatively, suppose the colluding sets are {1,2}, {3}. In both cases, the capacity is 4/7. The scheme that achieves rate 4/7 is as follows.

    W_kn∈𝔽_p^2× 1, k ∈ [1:2], n ∈ [1:3] 
          W_k = (W_k1; W_k2) ∈𝔽_p^4 × 1
          W_k3 = W_k1 + W_k2
          𝒱_1={V_1}, 𝒰_1={U_0}
          𝒱_2={V_1, V_2}, 𝒰_2={U_0, U_1}
          𝒱_3={V_2}, 𝒰_3={U_0}

where S = (V_1;V_2) and S' = (U_0; U_1) are independent and uniformly chosen from the set of all full rank 2 × 2 matrices over 𝔽_p. 

For the converse, consider (<ref>). Plugging in K = 2, K_c = 2, 𝒩 = {3}, N = 3, we have

    D ≥ H(A_1:3^[1] | ℱ, 𝒢) ≥ L + H(A_3^[2] | W_1, ℱ, 𝒢) + L/2 + o(L) L

Note that (<ref>) still holds when |𝒩| = K_c. Plugging in K = 2, K_c = 2, 𝒩 = {1,2}, N = 3, we have

    D ≥ H(A_1:3^[1] | ℱ, 𝒢) ≥ L + H(A_1^[2] | W_1, ℱ, 𝒢) + H(A_2^[2] | W_1, ℱ, 𝒢) + o(L) L

Adding the two inequalities above, we have

    2D    ≥    5L/2 +  H(A_1^[2], A_2^[2],A_3^[2] | W_1, ℱ, 𝒢) + L/2 + o(L) L  
       (<ref>)≥    5L/2 +  H(W_2 | W_1, ℱ, 𝒢) + L/2 + o(L) L  
       (<ref>)(<ref>)=    7L/2 + o(L) L

Normalizing by L and taking limits as L approaches infinity, gives us the upper bound on the rate L/D as 4/7, which completes the converse.


IEEEtran


