1

Private Information Retrieval from MDS Coded
Databases with Colluding Servers under Several
Variant Models
Yiwei Zhang and Gennian Ge

arXiv:1705.03186v2 [] 11 Oct 2017

Abstract
Private information retrieval (PIR) gets renewed attentions due to its information-theoretic reformulation and its application in
distributed storage system (DSS). The general PIR model considers a coded database containing N servers storing M files. Each
file is stored independently via the same arbitrary (N, K)-MDS code. A user wants to retrieve a specific file from the database
privately against an arbitrary set of T colluding servers. A key problem is to analyze the PIR capacity, defined as the maximal
number of bits privately retrieved per one downloaded bit. Several extensions for the general model appear by bringing in various
additional constraints. In this paper, we propose a general PIR scheme for several variant PIR models including: PIR with robust
servers, PIR with Byzantine servers, the multi-file PIR model and PIR with arbitrary collusion patterns.
Index Terms
Private information retrieval, distributed storage system, PIR capacity, PIR with robust servers, PIR with Byzantine servers,
multi-file PIR, PIR with arbitrary collusion patterns

I. I NTRODUCTION
The concept of private information retrieval is first introduced by Chor et al. [9], [10]. In a system consisting of several
servers each storing the same n-bit database, a classic PIR scheme will allow a user to retrieve a single bit of the database
without revealing the identity of the desired bit to any single server. PIR has received a lot of attention from the computer
science community and cryptography community. The main research objective is to minimize the total communication cost,
including both the upload cost (the queries sent to the servers) and the download cost (the feedbacks from the servers). A
series of works have managed to reduce the communication cost, see for example, [5], [11], [12], [31], [32] and the references
therein.
Recently, the PIR problem is reformulated from an information-theoretic point of view. Instead of retrieving a single bit
from an n-bit database, the information-theoretic PIR problem considers retrieving a single file from an n-file database, where
the length of each file could be arbitrarily large. In this sense, the objective turns into minimizing the total communication
cost per unit of retrieved data. It is further noticed in [7] that in this information-theoretic model the upload cost could be
neglected with respect to the download cost. Meanwhile, with the development of distributed storage system (DSS), it is natural
to consider designing PIR schemes for coded databases instead of the replicated-based databases [1], [6], [7], [16].
The general model for the information-theoretic, DSS-oriented PIR problem is as follows. Assume we have a coded database
containing N servers storing M files. Each file is stored independently via the same arbitrary (N, K)-MDS code. A user wants
to retrieve a specific file from the database. Any T out of the N servers may collude in attacking on the privacy of the user.
We call the PIR scheme for such a system as an (N, K, T ; M )-scheme. PIR rate is defined as the number of bits of messages
that could be privately retrieved per one bit of downloaded message. The supremum of all achievable rates is called the PIR
capacity, denoted by C = C(N, K, T ; M ). Starting from the pioneering work [19] by Sun and Jafar, a series of works have
attempted to analyze the fundamental limits on the PIR capacity. The exact value of the PIR capacity for the degenerating
cases, i.e., either K = 1 or T = 1, has been completely solved [4], [20]. For MDS coded databases with colluding servers
(K ≥ 2 and T ≥ 2), determining the capacity still remains an open problem and several PIR schemes for the general model
can be found in [13], [18], [22], [23], [33].
Several extensions for the general PIR model gradually appear by bringing in various additional constraints. For example,
the symmetric PIR problem is considered in [21], [27] and [28], where a further constraint is that the user should learn nothing
about any undesired file. [17] discusses multi-round PIR schemes, where the queries and feedbacks are made in several rounds
and the user may adjust his queries according to the feedbacks from previous rounds. [15] considers the model replacing the
underlying MDS storage code by some non-MDS code. Recent months have witnessed a new trend of researches on PIR with
The research of Y. Zhang was supported by the Post-Doctoral Science Foundation of China under Grant No. 2017M610942 and Beijing Postdoctoral
Research Foundation.
The research of G. Ge was supported by the National Natural Science Foundation of China under Grant Nos.11431003 and 61571310, Beijing Scholars
Program, Beijing Hundreds of Leading Talents Training Project of Science and Technology, and Beijing Municipal Natural Science Foundation.
Y. Zhang is with the School of Mathematical Sciences, Capital Normal University, Beijing 100048, China (email: rexzyw@163.com).
G. Ge is with the School of Mathematical Sciences, Capital Normal University, Beijing 100048, China (e-mail: gnge@zju.edu.cn).

2

side information [8], [14], [26], [29], [30]. It is expected that more variant models of PIR will arise according to different
practical scenarios.
In this paper, we will mainly consider the following four PIR variant models:
• 1. PIR with robust servers. In this model, some S out of the N servers are robust servers and they fail to respond to the
user’s queries. Thus this can be thought of as an erasure-correcting PIR model. PIR with robust servers has been studied by
Sun and Jafar in [20] for the degenerating case K = 1 and then by Tajeddine and Rouayheb in [24] for the degenerating case
T = 1.
• 2. PIR with Byzantine servers. In this model, among the N servers we have B Byzantine servers, which respond with
incorrect answers due to their outdated contents or even adversary motivations. Thus this can be thought of as an error-correcting
PIR model. For the degenerating case K = 1, PIR with Byzantine servers has been studied by Banawan and Ulukus in [3].
• 3. Multi-file PIR. This model assumes that a user wants to retrieve several files simultaneously. Multi-file PIR is first
considered by Banawan and Ulukus [2] for the case K = T = 1. They show that in order to retrieve P ≥ 2 files, one can do
better than the trivial approach of executing P independent (single-file) PIR schemes.
• 4. PIR with arbitrary collusion patterns. Instead of the original “any-T -out-of-the-N -servers-may-collude” setting, in this
model we are given a collusion pattern, which is a family of subsets of the servers closed under inclusion. A subset in the
family indicates that this set of servers may collude in attacking on the privacy. This model is first proposed in [25], which
mainly analyzes the effectiveness of the general PIR scheme proposed in [13] in the new scenario.
In this paper, we will consider the first three models above in MDS-coded databases with colluding servers, i.e., we study
these models for non-degenerated parameters K ≥ 2 and T ≥ 2. The main approach is to adapt the general PIR scheme we
presented in [33] according to the additional constraints in different models. Also we will investigate the effectiveness of our
previous strategy for the model with arbitrary collusion patterns. A summary of the results for each independent model are
listed as follows.



−S
N
−T
• 1. PIR with robust servers. When T + K ≤ N and NK
> K
− NK
, we have an (N, K, T ; M )-PIR scheme
−S−1
(NK−1
)
(N )−(N −T )
with S robust servers whose rate is N −1 (1 + R + R2 + · · · + RM−1 )−1 , where R = K N −SK . This result contains the
(K−1)
( K )
degenerating case K = 1 presented in [20] as a special case.




−B
N
−T
• 2. PIR with Byzantine servers. When T + K ≤ N and 2 NK
− K
> N
− NK
, we have an (N, K, T ; M )-PIR
K
N
−B
2(NK
(N )−(N −T )
)
)−(K
2
M−1 −1
(1 + R + R + · · · + R
) , where R = 2 KN −B −K N . This result
scheme with B robust servers whose rate is
N
( K ) (K )
(K )
contains the degenerating case K = 1 presented in [3] as a special case.
• 3. Multi-file PIR. In this part, we first present an upper bound of the multi-file PIR capacity for the degenerating cases,
P
i.e., one of the parameters K and T equals one. We then present a multi-file PIR scheme for the case M
≥ 21 , which works
for general parameters K and T and is of optimal PIR rate for the degenerating cases.
• 4. PIR with arbitrary patterns. We adapt our PIR scheme in this model and its PIR rate depends on an optimization
problem related to combinatorial design theory.
The rest of the paper is organized as follows. In Section II, we introduce the general model of the PIR problem alongside
with the different settings with respect to each variant model. In Section III we briefly recall the general PIR scheme we
presented in [33], which is the prototype of all the upcoming schemes for the variant models. Sections IV, V, VI and VII
present the main results of the paper, analyzing the four models respectively. Finally Section VIII concludes the paper.
II. P ROBLEM S TATEMENT
In this section we introduce the general model of the PIR problem alongside with the different settings with respect to each
variant model. Basically the statement follows the same way as shown in [2], [4], [18]–[20], [33].
The general model considers a distributed storage system consisting of N servers. The system stores M files, denoted as
W [1] , W [2] , . . . , W [M] ∈ FqL×K , i.e., each file is of length LK and represented in a matrix of size L × K. The files are
independent and identically distributed with
H(W [i] ) = LK,
H(W

[1]

,W

[2]

,...,W

[M]

i ∈ {1, 2, . . . , M },

) = M LK.

(1)
(2)

[i]

Denote the jth row of the file W [i] as wj ∈ FK
q , 1 ≤ j ≤ L. Each file is stored in the system via the same given
(N, K)-MDS code. The generator matrix G ∈ FK×N
of the MDS code is denoted as
q
i
h
,
(3)
G = g1 g2 · · · gN
K×N

3

[i]

and the MDS property means that any K columns of G are linearly independent. For each wj , the nth server stores the
[i]
stored on the nth server are the concatenated projections of all the files
coded bit wj gn . Thus, the whole contents yn ∈ FML
q
{W [1] , W [2] , . . . , W [M] } on the encoding vector gn , i.e.,


W [1]


..
yn = 
(4)
 gn
.
W [M]
iT
h
[M]
[2]
[M]
[1]
[2]
[1]
= w1 g n · · · wL g n w1 g n · · · wL g n · · · w1 g n · · · wL g n .

(5)

Now assume that a user wants to retrieve an arbitrary file W [i] . The retrieval is done by sending some queries to the servers
and then analyzing the feedbacks. Let F denote a random variable generated by the user and unknown to any server. F
represents the randomness of the user’s strategy to generate the queries. Let G denote a random variable generated by the
servers and also known to the user. G represents the randomness of the server’s strategy to produce the feedbacks1. Both F
and G are generated independently of the files and the index i of the desired file, i.e.,
H(F , G, i, W [1] , W [2] , . . . , W [M] ) = H(F ) + H(G) + H(i) + H(W [1] ) + · · · + H(W [M] ).

(6)

[i]

Using his strategy F , the user generates a set of queries Qn to the nth server, 1 ≤ n ≤ N . The queries are independent of
the files, i.e.,
[i]
[i]
[i]
(7)
[Query] I(Q1 , Q2 , . . . , QN ; W [1] , W [2] , . . . , W [M] ) = 0.
[i]

[i]

Upon receiving the query, the n-th server responds a feedback An , which is a deterministic function of the query Qn ,
[i]
the strategy G and the data yn (and therefore a deterministic function of the query Qn , the strategy G and the files
[1]
[2]
[M]
{W , W , . . . , W }), i.e.,
[i]
[i]
[i]
[1]
[2]
[M]
[Feedback] H(A[i]
) = 0.
n |Qn , G, yn ) = H(An |Qn , G, W , W , . . . , W

(8)

[i]

The user retrieves his desired file W based on all the queries and feedbacks, plus the knowledge of the strategies F and
G, i.e.,
[i]
[i]
[i]
[i]
[i]
[i]
(9)
[Correctness] H(W [i] |Q1 , Q2 , . . . , QN , A1 , A2 , . . . , AN , F , G) = 0.
[i]

[i]

[i]

For any subset T of the servers, |T | = T , let QT represent {Qn , n ∈ T }. Similarly we have the notation AT . The privacy
constraint requires that this set of servers learns nothing about the identity of the retrieved file, i.e.,
[i]

[i]

[Privacy] I(i; QT ) = I(i; AT ) = 0, ∀T ⊆ {1, 2, . . . , N }, |T | = T.

(10)

The rate for the PIR scheme is defined as the ratio of the size of the retrieved file to the total download cost, i.e.,
H(W [i] )
,
PN
[i]
n=1 H(An )

(11)

and the PIR capacity C is the supremum of all achievable rates.
For each variant model, the statement above requires slight modifications.
A. Problem Statement for PIR with robust servers
In this model, some S out of the N servers may fail to respond. Under this assumption, in order to successfully retrieve a
file, the correctness constraint (9) should be modified as
[i]

[i]

[i]

[i]

[i]

[i]

[Correctness with robust servers] H(W [i] |Q1 , Q2 , . . . , QN , Aj1 , Aj2 , . . . , AjN −S , F , G) = 0,

(12)

where J = {j1 , j2 , . . . , jN −S } is an arbitrary subset of [N ]. The complement set J represents those S robust servers that fail
to respond. Note that a robust server can also collude in attacking on the privacy.
1 The role of G is first proposed by Sun and Jafar in [18]. Such a strategy allows the server to perform some coding procedures before responding and thus
may reduce the download cost. For more details please refer to [18]. In almost all the other works on PIR schemes, including the current draft, we follow a
question-and-answer format. That is, for any query vector the server responds the corresponding projection of his contents onto the query. For this kind of
schemes G is a deterministic strategy and thus can be neglected.

4

B. Problem Statement for PIR with Byzantine servers
In this model, there exists a set B of Byzantine servers unknown to the user. |B| = B. These servers will respond incorrect
answers due to outdated contents or even adversary motivations. That is, for a Byzantine server, the feedback (8) should be
modified as
[i]
[i]
[i]
[1]
[2]
[M]
) ≥ 0, n ∈ B.
[Feedback from Byzantine servers] H(A[i]
n |Qn , G, yn ) = H(An |Qn , G, W , W , . . . , W

(13)

Note that as remarked in [3], we should differentiate the actions of T servers colluding in attacking on the privacy and B
servers coordinating in introducing errors. No specific relation between these two actions are assumed.
C. Problem Statement for multi-file PIR
In this model, a user wants to retrieve an arbitrary set of P ≥ 2 files simultaneously and the set of indices of these files is
P = {i1 , i2 , . . . , iP } ⊂ {1, 2, . . . , M }. Denote W [P] = {W [i] , i ∈ P}. To retrieve W [P] , the queries and feedbacks are then
[P]
[P]
denoted as Qn and An , n ∈ [N ]. The general statement should be adjusted to a multi-file version as follows.
[P]

[P]

[P]

[Multi-file Query] I(Q1 , Q2 , . . . , QN ; W [1] , W [2] , . . . , W [M] ) = 0.

(14)

[P]
[P]
[P]
[1]
[2]
[M]
[Multi-file Feedback] H(A[P]
) = 0.
n |Qn , G, yn ) = H(An |Qn , G, W , W , . . . , W

(15)

[P]

[P]

[P]

[P]

[P]

[P]

[Multi-file Correctness] H(W [P] |Q1 , Q2 , . . . , QN , A1 , A2 , . . . , AN , F , G) = 0.
[P]

[P]

[Multi-file Privacy] I(P; QT ) = I(P; AT ) = 0, ∀T ⊆ {1, 2, . . . , N }, |T | = T.
Correspondingly, the multi-file version PIR rate is defined as
P

[i]
i∈P H(W )
,
PN
[P]
n=1 H(An )

(16)
(17)

(18)

and the multi-file PIR capacity C P is the supremum of all achievable rates.
D. Problem Statement for PIR with arbitrary collusion patterns
In this model, we have a collusion pattern T, which is a family of subsets of [N ] closed under inclusion. A subset T ∈ T
indicates that this set of servers may collude in attacking on the identity of the desired file. So the privacy constraint (10)
should be modified as
[i]

[i]

[Privacy against collusion pattern T] I(i; QT ) = I(i; AT ) = 0, ∀T ∈ T.
III. T HE PROTOTYPE :

A

PIR

(19)

SCHEME FOR THE GENERAL MODEL

In this section we recall the general PIR scheme we proposed in [33]. It is the prototype of the upcoming PIR schemes
for all the variant models. The scheme suits the general model with T + K ≤ N and achieves the best rate up to now for a
certain range of parameters. For a detailed comparison of several PIR schemes for the general PIR model, please refer to [33,
Section IV].
Theorem 1: [33, Theorem 1] When T + K ≤ N , there exists an (N, K, T ; M )-PIR scheme with rate

N −T
(1 + R + R2 + · · · + RM−1 )−1 , where R = 1 −

A. The general scheme

K

N
K

.

We repeat the notations again as shown in the problem setting and these notations will be used throughout the draft. Denote
the files as W [1] , W [2] , . . . , W [M] and without loss of generality we let W [1] be the desired file. Each file is of length LK
and represented in a matrix of size L × K over Fq , where L is a constant to be determined later. Fq is a sufficiently large
finite field that allows the existence of several MDS codes used in the scheme (in Step 2). Each file, say W [m] , consists
[m]
[m]
[m]
of L rows, w1 , w2 , . . . , wL . For each file W [m] we will build a list of “atoms”. Each atom is a linear combination of
[m]
[m]
[m]
{w1 , w2 , . . . , wL }, represented in the form of sW [m] , where s is a vector in FL
q . A query to a server can be written as a
[m]
linear combination of atoms towards different files and therefore a linear combination of {wl : 1 ≤ m ≤ M, 1 ≤ l ≤ L}. Upon
[m]
receiving a query, the server responds the corresponding coded bit based on its storage {wl gn : 1 ≤ m ≤ M, 1 ≤ l ≤ L}.
Constructing the PIR scheme contains the following steps.

5

• Step 1: Let α and β be the smallest positive integers satisfying
 
  
!
N
N
N −T
α
= (α + β)
−
.
(20)
K
K
K


N
Assume the existence of an (α+β) N
N .
K , α K -MDS code. The transpose of its generator matrix is denoted as MDS(α+β)(N
K )×α(K )

N
M−1
• Step 2: Let L = K (α + β)
. Independently choose M random matrices, S1 , . . . , SM , uniformly from all the L × L
full rank matrices over Fq .


−1
N
• Step 3: Build an assisting array of size N
K−1 × N consisting of K symbols. Each symbol appears K times and every
K columns share a common symbol.
• Step 4: [Building basic blocks of the query structure] The query structure is divided into several blocks, where each block
is labelled by a nonempty subset of files D ⊆ {W [1] , W [2] , . . . , W [M] }. In a block labelled by D, every query is a mixture of
|D| atoms related to the files in D. We set each block in an “isomorphic” form with the assisting array, i.e., every K servers
share a common query. We further call a block labelled by D a d-block if |D| = d. For any D ⊆ {W [1] , W [2] , . . . , W [M] },
|D| = d, we require that the number of d-blocks labelled by D is αM−d β d−1 .
• Step 5: [Constructing the atoms for the desired file in each block] The atoms for the desired file W [1] are just built by
S1 W [1] and then distributed to different blocks.
• Step 6: [Dividing the query structure into groups] Now let D denote a nonempty set of files not containing
the desired
S
file W [1] . There are totally αM−|D| β |D|−1 blocks labelled by D and αM−|D|−1 β |D| blocks labelled by D {W [1] }. Partition
M−|D|−1 |D|−1
these blocks into αM−|D|−1 β |D|−1 groups, S
denoted by ΓD
β
, where each group consists of α blocks
λ, 1 ≤λ ≤α
[1]
labelled by D and β blocks labelled by D {W }. Repeat this process for every nonempty set D not containing W [1] and
thus the whole query structure is partitioned into groups.
• Step 7: [Constructing the atoms for undesired files in each group] For each group constructed withrespect to D and any
N
file W [m] ∈ D, m 6= 1, the number of atoms towards W [m] within the blocks in this group is (α + β) N
α K
K , among which
S
[1]
atoms appear in blocks
D and the other β N
K atoms appear as interferences in blocks labelled byD {W }.
 labelled by [m]
N
N
′
[m]
′
Let these (α + β) K atoms for W
be built by MDS(α+β)(N )×α(N ) Sm W , where Sm denotes some α K rows in the
K
K
matrix Sm .

M−2
Repeat this process for all the groups. Note that we shall come across the same file W [M] several times. We have |D|−1
choices for a subset D of size |D|, containing W [M] but without W [1] . With respect to any such D we have αM−|D|−1 β |D|−1
groups. So the exact number of times we come across W [M] can be computed as


M−1
X
M −2
= (α + β)M−2 .
(21)
αM−|D|−1 β |D|−1
|D| − 1
|D|=1

Every time we come across the same file W [M] , we have to ensure that the rows we select from Sm are non-intersecting.
N
This can be satisfied since (α + β)M−2 α K
≤ L.
B. An example: N = 4, K = 2, T = 2 and M = 3
We illustrate the scheme via an example: N = 4, K = 2, T = 2 and M = 3. The parameters throughout the construction
can be calculated as α = 5, β = 1 and L = 216. The assisting array could be of the form
( 1 1 2 2 )
3 4
5 6

3
6

4
5

.

Now we have three files U , V and W . Let each file be of length 432 and represented in a matrix of size 216 × 2, i.e.,
U=

u1 !
..
.

u216

V =

v1 !
..
.

W =

v216

w1 !
..
.

(22)

w216

where ui , vi , wi ∈ F2q , 1 ≤ i ≤ 216. Here Fq is a sufficiently large finite field. Let U be the desired file. We shall construct
three lists of atoms a[1:216] , b[1:216] and c[1:216] , corresponding to each of the files accordingly. Following Step 4, the query
structure is divided into several blocks as follows. In each block we set the queries in an “isomorphic” form with the assisting
array.

ΛUV W :

(

Server I
a1 + b 1 + c1
a3 + b 3 + c3
a5 + b 5 + c5

Server II
a1 + b 1 + c1
a4 + b 4 + c4
a6 + b 6 + c6

Server III
a2 + b 2 + c2
a3 + b 3 + c3
a6 + b 6 + c6

Server IV )
a2 + b 2 + c2
,
a4 + b 4 + c4
a5 + b 5 + c5

6

ΛVλ W

ΛUV
:
λ

ΛUW
:
λ

:

(

(

(

Server I
b6λ+1 + c6λ+1
b6λ+3 + c6λ+3
b6λ+5 + c6λ+5

Server I
a6λ+1 + b6λ+31
a6λ+3 + b6λ+33
a6λ+5 + b6λ+35

Server I
a6λ+31 + c6λ+31
a6λ+33 + c6λ+33
a6λ+35 + c6λ+35

Server II
b6λ+1 + c6λ+1
b6λ+4 + c6λ+4
b6λ+6 + c6λ+6

Server III
b6λ+2 + c6λ+2
b6λ+3 + c6λ+3
b6λ+6 + c6λ+6

Server II
a6λ+1 + b6λ+31
a6λ+4 + b6λ+34
a6λ+6 + b6λ+36

Server III
a6λ+2 + b6λ+32
a6λ+3 + b6λ+33
a6λ+6 + b6λ+36

Server II
a6λ+31 + c6λ+31
a6λ+34 + c6λ+34
a6λ+36 + c6λ+36

Server III
a6λ+32 + c6λ+32
a6λ+33 + c6λ+33
a6λ+36 + c6λ+36

Server IV )
b6λ+2 + c6λ+2
for λ ∈ {1, 2, 3, 4, 5},
b6λ+4 + c6λ+4
b6λ+5 + c6λ+5
Server IV
)
a6λ+2 + b6λ+32
for λ ∈ {1, 2, 3, 4, 5},
a6λ+4 + b6λ+34
a6λ+5 + b6λ+35
Server IV
)
a6λ+32 + c6λ+32
for λ ∈ {1, 2, 3, 4, 5},
a6λ+34 + c6λ+34
a6λ+35 + c6λ+35

and finally
ΛX
η

( Server I
x6η+61
:
x6η+63
x6η+65

Server II
x6η+61
x6η+64
x6η+66

Server III Server IV )
x6η+62
x6η+62
for (x, X) ∈ {(a, U ), (b, V ), (c, W )} and η ∈ {1, · · · , 25}.
x6η+63
x6η+64
x6η+66
x6η+65

The remaining task is then to determine the atoms. Independently choose three random matrices S1 , S2 , S3 ∈ F216×216
,
q
uniformly from all the 216 × 216 full rank matrices over Fq . The atoms a[1:216] are built just by setting a[1:216] = S1 U .
In Step 2 we have a (36, 30)-MDS code and the transpose of its generator matrix is denoted as MDS36×30 . Select the first
30 rows of S2 , denoted as S2 [(1 : 30), :]. Then b[1:36] are built by setting b[1:36] = MDS36×30 S2 [(1 : 30), :]V . Similarly
c[1:36] = MDS36×30 S3 [(1 : 30), :]W . This is exactly what we do in Step 7 by choosing D = {V, W }. We pause here to explain
the motivations of the atoms defined so far. Notice that {bi + ci : 7 ≤ i ≤ 36} could be retrieved since each appears as a query
in two different servers. Then due to the property of MDS36×30 , we can solve {bi +ci : 1 ≤ i ≤ 6} from {bi +ci : 7 ≤ i ≤ 36}.
Therefore the interferences can be eliminated in the block ΛUV W and thus a[1:6] could be retrieved. This is exactly how we
make use of the side information provided by {ΛVλ W : 1 ≤ λ ≤ 5} to retrieve some messages of the desired file U hidden in
ΛUV W .
The motivations of the other atoms follow the same idea, i.e., we want to make use of the side information provided by
{ΛVη : 1 ≤ η ≤ 25} (respectively, provided by {ΛW
η : 1 ≤ η ≤ 25}) to retrieve some messages of the desired file U hidden in
UW
{ΛUV
:
1
≤
λ
≤
5}
(respectively,
hidden
in
{Λ
: 1 ≤ λ ≤ 5}). This is done in separate parallel steps. Divide the query
λ
λ
UW
X
structure {ΛUV
:
1
≤
λ
≤
5},
{Λ
:
1
≤
λ
≤
5},
{Λ
η : X ∈ {V, W }, 1 ≤ η ≤ 25} into the following separate groups:
λ
λ

UX
X
ΓX
λ = Λλ , {Λη : 5λ − 4 ≤ η ≤ 5λ} , X ∈ {V, W }, 1 ≤ λ ≤ 5.
In each ΓX
λ we can select the atoms as

b[6λ+31:6λ+36] S[30λ+37:30λ+66] = MDS36×30 S2 [(30λ + 1 : 30λ + 30), :]V,
or similarly

c[6λ+31:6λ+36] S[30λ+37:30λ+66] = MDS36×30 S3 [(30λ + 1 : 30λ + 30), :]W.

Retrieving the file U is equivalent to retrieving a[1:216] since S1 is a full rank matrix. Retrieving a[67:216] is straightforward
from the blocks labelled by U and we have explained how to retrieve a[1:6] . Then in each ΓVλ or ΓW
λ we have the atoms
a[6λ+1:6λ+6] or a[6λ+31:6λ+36] accompanied by the interferences b[6λ+31:6λ+36] or c[6λ+31:6λ+36] . Due to the MDS property
we can solve these interferences via b[30λ+37:30λ+66] or c[30λ+37:30λ+66] . Once eliminating these interferences, we are able to
retrieve a[7:66] .
The scheme is private against any two colluding servers. The query structure is completely symmetric with respect to all
the files. From the perspective of any two colluding servers, altogether the number of atoms towards each of the three files is
125 + 25 × 2 + 5 = 180. Extract the coefficients of each atom as a vector in F216
q . Recall how we select the random matrices
S1 , S2 , S3 and the (36, 30)-MDS code. It turns out that the 180 vectors with respect to each file form a random subspace
of dimension 180 in F216
q , so the two servers cannot tell any difference among the atoms towards different files and thus the
identity of the retrieved file is disguised.
216×2
36
The rate of the scheme above is then 12×25×3+12×5×3+12
= 91
.

7

C. Analysis of the general model
To verify the correctness and privacy of the general scheme and to compute its rate as shown in Theorem 1, please refer
to [33]. Here we briefly analyze some key ingredients in the scheme, which will shed light on how to adjust the scheme for
other variant models.
First, we should guarantee the correctness of the scheme, i.e., the user should succeed in retrieving his desired file. In the
scheme above, all the atoms towards the desired file are independent and the redundancy of the atoms towards undesired files
only exists within groups. In such a way we can fully use the side information and retrieve as many bits of the desired files as
possible. However, in the model with robust or Byzantine servers, since some feedbacks are either erased or in error, then it is
natural to bring in more redundancy among the atoms for both the desired and undesired files. Moreover, note that a robust or
Byzantine server not only affects its own feedbacks, it also results in a waste of some other feedbacks from well-functioned
servers. For example, if Server I in the previous example is robust, then the user does not know the coded bit (a1 + b1 + c1 )g1 .
As a result, the coded bit (a1 + b1 + c1 )g2 from Server II will be of no use, but it still accounts for one bit in the total
download size.
Second, we should guarantee the privacy of the scheme. We should carefully adjust the ratio of the number of different
blocks and this is exactly what the parameters α and β computed in Step 2 are aimed for. What we do in the general scheme
is to guarantee that from the perspective of any T colluding servers, the subspaces derived from the atoms towards each file
are indistinguishable. For the variant models, since we have to bring in more redundancy among the atoms for each file, then
we should readjust the ratio correspondingly to guarantee the privacy.
Besides these two major aspects mainly concentrated on modifying the atoms and ratio of blocks, the scheme could be
modified through other ways, such as modifying the assisting array or modifying the query structure. We will encounter all
kinds of such modifications by analyzing the variant models case-by-case later.
IV. PIR WITH

ROBUST SERVERS

In this section, we deal with the first variant model, PIR with robust servers. In this model we have a database with N
servers storing M files. Each file is stored independently via an arbitrary (N, K)-MDS code. A set of S servers do not respond
and are therefore called robust servers. A user wants to retrieve a certain file from the database. At first he does not know
which set of S servers are robust and thus he makes queries to every server. Of course he will then know which servers are
robust since he does not receive feedbacks from these servers. Any set of T servers may collude in attacking on the privacy
of the user. Note that a robust server, although providing no feedbacks, may also participate in attacking the privacy of the
user. This model can be regarded as an erasure-correcting PIR model.
A. PIR scheme with robust servers
Constructing the PIR scheme with robust servers contains the following steps.
• Step 1: Let α and β be the smallest positive integers satisfying


  
!
N −S
N
N −T
α
= (α + β)
−
.
(23)
K
K
K


N −S
Assume the existence of an (α+β) N
-MDS code. The transpose of its generator matrix is denoted as MDS(α+β)(N )×α(N −S) .
K ,α K
K
K
 N −S 
N
Assume the existence of an K , K
-MDS code. The transpose of its generator matrix is denoted as MDS(N )×(N −S) .
K
K

−S
• Step 2: Let L = NK
(α + β)M−1 . Independently choose M random matrices, S1 , . . . , SM , uniformly from all the L × L
full rank matrices over Fq .


−1
N
• Step 3: Build an assisting array of size N
K−1 × N consisting of K symbols. Each symbol appears K times and every
K columns share a common symbol.
• Step 4: [Building basic blocks of the query structure] The query structure is divided into several blocks, where each block
is labelled by a subset of files D ⊆ {W [1] , W [2] , . . . , W [M] }. In a block labelled by D, every query is a mixture of |D| atoms
related to the files in D. We set each block in an “isomorphic” form with the assisting array, i.e., every K servers share a
common query. We further call a block labelled by D a d-block if |D| = d. For any D ⊆ {W [1] , W [2] , . . . , W [M] }, |D| = d,
we require that the number of d-blocks labelled by D is αM−d β d−1 .
• Step 5: [Constructing the atoms
labelled
 for the desired file in each block] As indicated by the assisting array, in a block
′
[1]
by D with W [1] ∈ D, we have N
, where
N −S S1 W
atoms
towards
the
desired
file.
Let
these
atoms
be
built
by
MDS
N
K
(K )×( K )

N −S
′
[1]
S1 denotes some K rows in the matrix S1 . Repeat this process for all the blocks labelled by D with W ∈ D, totally
the number of such blocks is
M
X

|D|=1

M−|D| |D|−1

α

β




M −1
= (α + β)M−1 .
|D| − 1

(24)

8


−S
We have to ensure that the rows we select from S1 are non-intersecting. This can be satisfied since (α + β)M−1 NK
= L.
• Step 6: [Dividing the query structure into groups] Now let D denote a nonempty set of files not containing
the
desired
S
file W [1] . There are totally αM−|D| β |D|−1 blocks labelled by D and αM−|D|−1 β |D| blocks labelled by D {W [1] }. Partition
M−|D|−1 |D|−1
these blocks into αM−|D|−1 β |D|−1 groups, S
denoted by ΓD
β
, where each group consists of α blocks
λ, 1 ≤λ ≤α
[1]
labelled by D and β blocks labelled by D {W }. Repeat this process for every nonempty set D not containing W [1] and
thus the whole query structure is partitioned into groups.
• Step 7: [Constructing the atoms for undesired files in each group] For each group constructed
 with respect to DN and
 any
N
file W [m] ∈ D, the number of atoms towards W [m]
within
the
blocks
in
this
group
is
(α
+
β)
,
among
which
α
atoms
K
K

S
N
[1]
appear in blocks
labelled
by
D
and
the
other
β
atoms
appear
as
interferences
in
blocks
labelled
by
D
{W
}.
Let
these
K


N −S
′
[m]
′
[m]
,
where
S
denotes
some
α
(α + β) N
N −S Sm W
N
rows
in
the
matrix
atoms
for
W
be
built
by
MDS
m
(α+β)(K )×α( K )
K
K
Sm .

M−2
Repeat this process for all the groups. Note that we shall come across the same file W [M] several times. We have |D|−1
choices for a subset D of size |D|, containing W [M] but without W [1] . With respect to any such D we have αM−|D|−1 β |D|−1
groups. So the exact number of times we come across W [M] can be computed as


M−1
X
M −2
= (α + β)M−2 .
(25)
αM−|D|−1 β |D|−1
|D| − 1
|D|=1

Every time we come across the same file W[M] , we have to ensure that the rows we select from Sm are non-intersecting.
−S
This can be satisfied since (α + β)M−2 α NK
≤ L.
The construction of the PIR scheme with robust servers is finished. Comparing the scheme with the prototype, one can see
that the main adaptation is changing the redundancy in atoms and then adjusting the ratio of different blocks (i.e. determining
the value of parameters α and β).
B. An example: N = 6, S = 1, K = 2, T = 2 and M = 2
The parameters throughout the construction can be calculated as α = 9, β = 1 and L = 100. The assisting array could be
of the form
1 1 2 3 4 5
(
)
2 6 6 7 8 9
3 7 10 10 11 12 .
4 8 11 13 13 14
5 9 12 14 15 15
Now we have two files U and V . Let each file be of length 200 and represented in a matrix of size 100 × 2, i.e.,
U=

u1 !
..
.

u100

V =

v1 !
..
.

(26)

v100

where ui , vi ∈ F2q , 1 ≤ i ≤ 100. Here Fq is a sufficiently large finite field. Let U be the desired file. We shall construct two
lists of atoms a[1:150] and b[1:150] corresponding to each file accordingly. Following Step 4, the query structure is divided into
several blocks as follows. In each block we set the queries in an “isomorphic” form with the assisting array.

ΛUV

ΛX
η

Server I
( x15η+1
x15η+2
:
x15η+3
x15η+4
x15η+5

Server I
( a1 + b 1
a2 + b 2
:
a3 + b 3
a4 + b 4
a5 + b 5

Server II Server III Server IV
a1 + b 1
a2 + b 2
a3 + b 3
a6 + b 6
a6 + b 6
a7 + b 7
a7 + b7 a10 + b10 a10 + b10
a8 + b8 a11 + b11 a13 + b13
a9 + b9 a12 + b12 a14 + b14

Server II Server III Server IV
x15η+1
x15η+2
x15η+3
x15η+6
x15η+6
x15η+7
x15η+7
x15η+10
x15η+10
x15η+8
x15η+11
x15η+13
x15η+9
x15η+12
x15η+14

Server V
x15η+4
x15η+8
x15η+11
x15η+13
x15η+15

Server V
a4 + b 4
a8 + b 8
a11 + b11
a13 + b13
a15 + b15

Server VI
a5 + b 5 )
a9 + b 9
,
a12 + b12
a14 + b14
a15 + b15

Server VI
x15η+5 )
x15η+9
for (x, X) ∈ {(a, U ), (b, V )} and η ∈ {1, · · · , 9}.
x15η+12
x15η+14
x15η+15

The remaining task is then to determine the atoms. In Step 2 we have a (150, 90)-MDS code and the transpose of its
generator matrix is denoted as MDS150×90 . We also have a (15, 10)-MDS code and the transpose of its generator matrix is

9

, uniformly from all the 100 × 100 full
denoted as MDS15×10 . Independently choose two random matrices S1 , S2 ∈ F100×100
q
rank matrices over Fq . By Step 5, the atoms a[15η+1:15η+15] , 0 ≤ η ≤ 9 are built by MDS15×10 S1 [(10η + 1 : 10η + 10), :]U ,
where S1 [(10η + 1 : 10η + 10), :] means the ten rows indexed from 10η + 1 to 10η + 10 from S1 . By Step 7, the atoms b[1:150]
are built by MDS150×90 S2 [(1 : 90), :]V .
Without loss of generality, suppose Server I is the robust server. Then the user can retrieve {ai + bi : 6 ≤ i ≤ 15},
{x15η+i : x ∈ {a, b}, 1 ≤ η ≤ 9, 6 ≤ i ≤ 15}. By the property of MDS150×90 , the user can use the 90 known atoms towards
V to solve the remaining atoms towards V . Particularly, he can solve {bi : 6 ≤ i ≤ 15}. Eliminating the interferences, the user
now retrieves {ai : 6 ≤ i ≤ 15}. Now that the user knows {a15η+i : 0 ≤ η ≤ 9, 6 ≤ i ≤ 15}. By the property of MDS15×10
and the singularity of S1 , the user retrieves the whole file U .
The scheme is private against any two colluding servers. From the perspective of any two colluding servers, the number
of atoms towards each file is 90. Extract the coefficients of each atom as a vector in F100
q . Recall how we select the random
matrices S1 , S2 and those two MDS codes. It turns out that the 90 vectors with respect to each file form a random subspace
of dimension 90 in F100
q , so the two servers cannot tell any difference between the atoms towards different files and thus the
identity of the retrieved file is disguised.
100×2
8
The rate of the scheme above is then 5×5×19
= 19
. Note that the denominator is not 6 × 5 × 19 since the robust server will
produce no download cost at all.
C. Analysis of the PIR scheme with robust servers
Each query in the scheme appears in K distinct servers. If all these K servers are not robust, then this query can be
−S
−S
successfully retrieved. For each group constructed with respect to D, α NK
queries in the blocks labelled by
and 
β NK
 DN
S
N
−S
[1]
queries in the blocks
-MDS
 labelled by D {W } could be retrieved. Based on the property of the (α + β) K ,Nα−S K
−S
code, these α NK
queries in the blocks labelled by D
will
help
us
eliminate
the
interferences
of
the
β
queries
in
K

S
N −S
[1]
[1]
the blocks labelled
 by F {W
 }, and thus the β [1]K atoms towards W are retrieved. As a result, in each block related
−S
to W [1] , NK
out of the N
are successfully retrieved. By the property of MDS(N )×(N −S) and the
K atoms towards W
K
K
singularity of S1 , the desired file is successfully retrieved.
The scheme is private against
any T colluding servers. From the perspective of any T colluding servers, they shall receive

N −T
(α + β)M−1 ( N
−
)
atoms
towards each file. Extract the coefficients of each atom as a vector in FL
q . Recall how we
K
K
build the atoms by using the full rank matrices S1 , . . . , Sm and the two MDS codes.
One
can
see
that
the
vectors of all the


N
−T
atoms towards any file will form a random subspace of dimension (α + β)M−1 ( K
− NK
) in FL
.
So
these
T colluding
q
servers cannot tell any difference among the atoms towards different files and thus the identity of the retrieved file is disguised.
Finally we compute
rate of the PIR scheme with robust servers. The retrieved file is of length LK. The download cost
 Nthe
−S
in any block is K N
N . So the rate can be computed as
K

N −S−1
1
L
LK
K−1
 = N −1 ·
.
 = N  N −S −1

α
α
M
N N −S PM
M
M
M−|D|
|D|−1
1 + α+β + · · · + ( α+β
)M−1
(α + β) − α
β
K K N
K
K−1
N β
|D|=1 α
|D|



−S
N
−T
A final remark is that our scheme only works for the case T + K ≤ N and NK
> K
− NK
since otherwise the
equality (23) does not make sense. To sum up, we have the following theorem.
−S
N −T
Theorem 2: When T + K ≤ N and NK
> N
, there exists an (N, K, T ; M )-PIR scheme with S robust servers
K −
K
N −S−1
(N )−(N −T )
( K−1 )
whose rate is N −1 (1 + R + R2 + · · · + RM−1 )−1 , where R = K N −SK .
(K−1)
( K )
Particularly, for the degenerating case K = 1, the PIR rate of the scheme is (1 + R + R2 + · · · + RM−1 )−1 with R = NT−S ,
which is exactly the result presented in [20].
V. PIR WITH B YZANTINE SERVERS
In this section, we deal with the second variant model, PIR with Byzantine servers. In this model we have a database with
N servers storing M files. Each file is stored independently via an arbitrary (N, K)-MDS code. A set of B servers are called
Byzantine servers. They will produce incorrect feedbacks due to their outdated contents or even adversary motivations. A user
wants to retrieve a certain file from the database and he does not know which set of B servers are Byzantine. Any set of
T servers may collude in attacking on the privacy of the user. We should differentiate the actions of T servers colluding in
attacking on the privacy and B servers coordinating in introducing errors. No specific relation between these two actions are
assumed. This model can be regarded as an error-correcting PIR model. Recall the fact from classic coding theory: the maximum
number of errors that can be corrected by a linear code with minimum distance d is τ ≤ ⌊ d−1
2 ⌋. As for an [n, k, d]-linear
n−k
MDS code, τ ≤ ⌊ d−1
⌋
=
⌊
⌋.
2
2

10

A. PIR scheme with Byzantine servers
Constructing the PIR scheme with robust servers contains the following steps.
• Step 1: Let α and β be the smallest positive integers satisfying

  !
  
!
N −B
N
N
N −T
α 2
−
= (α + β)
−
.
(27)
K
K
K
K



N
−B
Assume the existence of an (α + β) K
, α(2 NK
− N
of its generator matrix is denoted as
K ) -MDS
 code.
The Ntranspose

N
N −B

.
Assume
the
existence
of
an
MDS
,
2
−
-MDS
code. The transpose of its generator
N −B
N
K
K
K
(α+β)(N
K )×α 2( K )−(K )

.
matrix is denoted as MDS N
N
N −B
(K )×
 2( NK)−(K ) M−1
N −B
• Step 2: Let L = 2 K − K (α + β)
. Independently choose M random matrices, S1 , . . . , SM , uniformly from
all the L × L full rank matrices over Fq .


−1
N
• Step 3: Build an assisting array of size N
K−1 × N consisting of K symbols. Each symbol appears K times and every
K columns share a common symbol.
• Step 4: [Building basic blocks of the query structure] The query structure is divided into several blocks, where each block
is labelled by a subset of files D ⊆ {W [1] , W [2] , . . . , W [M] }. In a block labelled by D, every query is a mixture of |D| atoms
related to the files in D. We set each block in an “isomorphic” form with the assisting array, i.e., every K servers share a
common query. We further call a block labelled by D a d-block if |D| = d. For any D ⊆ {W [1] , W [2] , . . . , W [M] }, |D| = d,
we require that the number of d-blocks labelled by D is αM−d β d−1 .
• Step 5: [Constructing the atoms
for the desired file in each block] As indicated by the assisting array, in a block labelled by

N
 S ′ W [1] ,
D with W [1] ∈ D, we have K
atoms towards the desired file. Let these atoms be built by MDS N
−B
1
× 2(NK
−(N
)
)
)
(
K
K


N −B
N
′
where S1 denotes some 2 K − K rows in the matrix S1 . Repeat this process for all the blocks labelled by D with
W [1] ∈ D, totally the number of such blocks is
M
X

|D|=1

αM−|D| β |D|−1




M −1
= (α + β)M−1 .
|D| − 1

(28)


−B
We
have to ensure that the rows we select from S1 are non-intersecting. This can be satisfied since (α+β)M−1 × 2 NK
−

N
=
L.
K
• Step 6: [Dividing the query structure into groups] Now let D denote a nonempty set of files not containing
the desired
S
file W [1] . There are totally αM−|D| β |D|−1 blocks labelled by D and αM−|D|−1 β |D| blocks labelled by D {W [1] }. Partition
M−|D|−1 |D|−1
these blocks into αM−|D|−1 β |D|−1 groups, S
denoted by ΓD
β
, where each group consists of α blocks
λ, 1 ≤λ ≤α
[1]
labelled by D and β blocks labelled by D {W }. Repeat this process for every nonempty set D not containing W [1] and
thus the whole query structure is partitioned into groups.
• Step 7: [Constructing the atoms for undesired files in each group] For each group constructed
 with respect to DN and
 any
N
file W [m] ∈ D, the number of atoms towards W [m]
within
the
blocks
in
this
group
is
(α
+
β)
,
among
which
α
K
K atoms

S
N
[1]
appear in blocks
labelled
by
D
and
the
other
β
atoms
appear
as
interferences
in
blocks
labelled
by
D
{W
}.
Let
K
 these


N −B
N
N
[m]
′
′
[m]

Sm W , where Sm denotes some α 2 K − K
(α + β) K atoms for W
be built by MDS
N
(α+β)(K
)×α 2(NK−B)−(N
K)
rows in the matrix Sm .

M−2
Repeat this process for all the groups. Note that we shall come across the same file W [M] several times. We have |D|−1
choices for a subset D of size |D|, containing W [M] but without W [1] . With respect to any such D we have αM−|D|−1 β |D|−1
groups. So the exact number of times we come across W [M] can be computed as


M−1
X
M−|D|−1 |D|−1 M − 2
= (α + β)M−2 .
(29)
α
β
|D| − 1
|D|=1

Every time we come across the same file W [M] , we have to ensure that the rows we select from Sm are non-intersecting.
This can be satisfied since

  !
N −B
N
M−2
(α + β)
α 2
−
≤ L.
(30)
K
K
The construction of the PIR scheme with Byzantine servers is finished. Comparing the scheme with the prototype, one
can see that the main adaptation is changing the redundancy in atoms and then adjusting the ratio of different blocks (i.e.
determining the value of parameters α and β).

11

B. An example: N = 8, B = 1, K = 2, T = 2 and M = 2
The parameters throughout the construction can be calculated as
of the form
1 1 2 3 4
2 8 8 9 10
( 3 9 14 14 15
4 10 15 19 19
5 11 16 20 23
6 12 17 21 24
7 13 18 22 25

α = 13, β = 1 and L = 196. The assisting array could be
5
11
16
20
23
26
27

6
12
17
21
24
26
28

7
13
18 )
22 .
25
27
28

Now we have two files U and V . Let each file be of length 392 and represented in a matrix of size 196 × 2, i.e.,
U=

u1 !
..
.

V =

u196

v1 !
..
.

(31)

v196

F2q ,

where ui , vi ∈
1 ≤ i ≤ 196. Here Fq is a sufficiently large finite field. Let U be the desired file. We shall construct two
lists of atoms a[1:392] and b[1:392] corresponding to each file accordingly. Following Step 4, the query structure is divided into
several blocks as follows. In each block we set the queries in an “isomorphic” form with the assisting array.

ΛUV

Server I
a1 + b 1
a
( 2 + b2
a3 + b 3
:
a4 + b 4
a5 + b 5
a6 + b 6
a7 + b 7

Server II
a1 + b 1
a8 + b 8
a9 + b 9
a10 + b10
a11 + b11
a12 + b12
a13 + b13

Server III Server IV
a2 + b 2
a3 + b 3
a8 + b 8
a9 + b 9
a14 + b14 a14 + b14
a15 + b15 a19 + b19
a16 + b16 a20 + b20
a17 + b17 a21 + b21
a18 + b18 a22 + b22

Server V
a4 + b 4
a10 + b10
a15 + b15
a19 + b19
a23 + b23
a24 + b24
a25 + b25

ΛX
η

Server I
x28η+1
( x28η+2
x28η+3
:
x28η+4
x28η+5
x28η+6
x28η+7

Server II Server III Server IV Server V
x28η+1
x28η+2
x28η+3
x28η+4
x28η+8
x28η+8
x28η+9
x28η+10
x28η+9
x28η+14
x28η+14
x28η+15
x28η+10
x28η+15
x28η+19
x28η+19
x28η+11
x28η+16
x28η+20
x28η+23
x28η+12
x28η+17
x28η+21
x28η+24
x28η+13
x28η+18
x28η+22
x28η+25

Server VI Server VII Server VIII
a5 + b 5
a6 + b 6
a7 + b 7
a11 + b11 a12 + b12
a13 + b13 )
a16 + b16 a17 + b17
a18 + b18
,
a20 + b20 a21 + b21
a22 + b22
a23 + b23 a24 + b24
a25 + b25
a26 + b26 a26 + b26
a27 + b27
a27 + b27 a28 + b28
a28 + b28
Server VI
x28η+5
x28η+11
x28η+16
x28η+20
x28η+23
x28η+26
x28η+27

Server VII
x28η+6
x28η+12
x28η+17
x28η+21
x28η+24
x28η+26
x28η+28

Server VIII
x28η+7
x28η+13 )
x28η+18
x28η+22
x28η+25
x28η+27
x28η+28

for (x, X) ∈ {(a, U ), (b, V )} and η ∈ {1, · · · , 13}.
The remaining task is then to determine the atoms. In Step 2 we have a (392, 182)-MDS code and the transpose of its
generator matrix is denoted as MDS392×182 . We also have a (28, 14)-MDS code and the transpose of its generator matrix is
denoted as MDS28×14 . Independently choose two random matrices S1 , S2 ∈ F196×196
, uniformly from all the 196×196 full rank
q
matrices over Fq . By Step 5, the atoms a[28η+1:28η+28] , 0 ≤ η ≤ 13 are built by setting MDS28×14 S1 [(14η + 1 : 14η + 14), :]U ,
where S1 [(14η + 1 : 14η + 14), :] means the fourteen rows indexed from 14η + 1 to 14η + 14 from S1 . By Step 7, the atoms
b[1:392] are built by MDS392×182 S2 [(1 : 182), :]V .
The user can retrieve all queries since each appears in k = 2 servers. However, due to the existence of a Byzantine server,
there will be errors and the number of errors in b[29:392] is at most 91 (at most seven errors from each ΛVη ). Due to the property
of MDS392×182 , these errors can be corrected and therefore the user retrieves the correct value of b[1:28] . Now the user has
a[28η+1:28η+28] , 0 ≤ η ≤ 13. Due to the property of MDS28×14 , each subset a[28η+1:28η+28] can correct its possible seven (at
most) errors and thus the file U is successfully retrieved.
The scheme is private against any two colluding servers. From the perspective of any two colluding servers, the number of
atoms towards each file is 182. Extract the coefficients of each atom as a vector in F196
q . Recall how we select the random
matrices S1 , S2 and the two MDS codes. It turns out that the 182 vectors with respect to each file form a random subspace
of dimension 182 in F196
q , so the two servers cannot tell any difference between the atoms towards different files and thus the
identity of the retrieved file is disguised.
7
196×2
= 27
.
The rate of the scheme above is then 8×7×27

12

C. Analysis of the PIR scheme with Byzantine servers
Each query in the scheme appears in K distinct servers and is thus retrieved. However, due
 to the existence of a Byzantine
N
server, there will be errors. For
each
group
constructed
with
respect
to
D,
among
the
α
in the blocks labelled by
K queries



N
N −B
N
D there will be at most α K − K
errors.
errors
 The
 can be corrected since these α K queries arise from a punctured
N
N −B
MDS code
with
minimum
distance
1
+
2α
−
. Therefore the user can correctly eliminate the interferences in those
KS
K

−S
β NK
queries in the blocks labelled by D {W [1] } and retrieve the atoms towards W [1] . Now every atom towards W [1] is
 and the singularity of S1 , the desired file is successfully retrieved.
retrieved. Then by the property of MDS N
−B
)−(N
(K )× 2(NK
K)
The scheme is private against
any T colluding servers. From the perspective of any T colluding servers, they shall receive

N −T
(α + β)M−1 ( N
−
)
atoms
towards each file. Extract the coefficients of each atom as a vector in FL
q . Recall how we
K
K
build the atoms by using the full rank matrices S1 , . . . , Sm and the two MDS codes.
One
can
see
that
the
vectors of all the


N
−T
atoms towards any file will form a random subspace of dimension (α + β)M−1 ( K
− NK
) in FL
q . So these T colluding
servers cannot tell any difference among the atoms towards different files and thus the identity of the retrieved file is disguised.
Finally we compute
 the rate of the PIR scheme with robust servers. The retrieved file is of length LK. The download cost
in any block is K N
K . So the rate can be computed as


−B
N
2 NK
− K
L
LK
1
.
·
=

 = N  −1

α
α
N
M
N PM
M
M
M−|F
|
|F
|−1
1
+
+
·
·
· + ( α+β
)M−1
(α
+
β)
−
α
β
K K
β
α+β
K
K
|F |=1 α
|F |




−B
N
N −T
A final remark is that our scheme only works for the case T + K ≤ N and 2 NK
− N
since otherwise
K > K −
K
the equality (27) does not make sense. To sum up, we have the
following
theorem.


−B
N
N
−T
Theorem 3: When T + K ≤ N and 2 NK
− K
> K
− NK
, there exists an (N, K, T ; M )-PIR scheme with B
N −B
N
2( K )−(K )
(N )−(N −T )
2
M−1 −1
(1 + R + R + · · · + R
) , where R = 2 KN −B −K N .
robust servers whose rate is
N
(K )
( K ) (K )
2
M−1 −1
) with
Particularly, for the degenerating case K = 1, the PIR rate of the scheme is N −2B
N (1 + R + R + · · · + R
T
R = N −2B , which is exactly the result presented in [3].
VI. M ULTI - FILE PIR
In this section, we deal with the multi-file PIR problem. Again we have a database with N servers storing M files and each
file is stored independently via an arbitrary (N, K)-MDS code. Now a user wants to retrieve several files simultaneously. A
naive approach to retrieve P ≥ 2 files simultaneously is to execute P independent single-file PIR schemes. It should be noted
that in a scheme designed for retrieving a certain file, the user may have additional knowledge of some other desired files.
However, even taking these benefits into consideration, it is still possible to do better than the naive approach. The multi-file
model is a little more complex in the sense that we may have different strategies according to whether the ratio P/M is larger
2
or smaller than 1/2, as shown in [2] for the degenerating case K = T = 1. In this draft we only deal with the case P ≥ M
2 .
The rest of this section is further divided into two subsections. The first subsection contains the analysis of the upper bound
of the multi-file PIR capacity based on information inequalities. The next subsection discusses the multi-file PIR scheme for
P ≥ M
2 .
A. Upper bound of the multi-file PIR capacity for the degenerating cases
In this subsection we shall analyze the upper bound of the multi-file PIR capacity based on information inequalities. The
case K = T = 1 has been presented in [2]. We shall only consider the degenerating cases K = 1 or T = 1 here. As for the
non-degenerating case (i.e., K ≥ 2 and T ≥ 2), analyzing the upper bound of the capacity is a rather difficult problem, even
for the general single-file PIR model. Given the parameters P, N, K, T , the minimal download cost is then a function of the
number of files M , denoted as ΩM . For simplicity we need the following notations as in [2].

Q , Qn[P] : P ⊂ {1, 2, . . . , M }, |P| = P, n ∈ {1, 2, . . . , N } .
(32)
 [P] [P]
[P]
A[P]
for n1 ≤ n2 , n1 , n2 ∈ {1, 2, . . . , M }.
(33)
n1 :n2 , An1 , An1 +1 , . . . , An2
The scheme could be assumed to be symmetric, or else we could build a symmetric scheme via a non-symmetric scheme
by replicating all permutations of servers and files. Therefore we may assume that for any two sets of indices of P desired
files P1 , P2 and for any two servers, say the nth and the mth server, we have
[P2 ]
H(An[P1 ] |Q) = H(Am
|Q).

(34)

2 We claim that we have also considered the complementary case P < M and adapted our PIR scheme. However, the redundancy within atoms towards
2
desired files are very complex and thus the whole tedious scheme is not very satisfactory and thus omitted. A neater scheme is considered for future research.

13

The equality above also holds when one considers conditional entropy with prior knowledge of any subset of files, i.e.,
[P2 ]
H(An[P1 ] |W [S] , Q) = H(Am
|W [S] , Q) for any S ⊂ {1, 2, . . . , M }.

(35)

The key to the analysis of the multi-file PIR capacity is the following inductive relation.
P L = H(W [P] )
= H(W
=
=
=
≤
Note that

P

[P]

(36)

|Q)

(37)

[P]
[P]
I(W ; A1:N |Q) + H(W [P] |A1:N , Q)
[P]
I(W [P] ; A1:N |Q)
[P]
[P]
H(A1:N |Q) − H(A1:N |W [P] , Q)
X
[P]
[P]
H(A[P]
, Q).
n |Q) − H(A1:N |W
1≤n≤N
[P]

(38)
(39)
(40)
(41)

[P]

1≤n≤N

H(An |Q) is exactly the total download cost. So the inductive relation above can be rewritten as
[P]

ΩM ≥ P L + H(A1:N |W [P] , Q).

(42)

The remaining trick is how to bound the second part in the inequality above. We are now ready to analyze the capacity for
two degenerating cases, i.e., either T = 1 or K = 1.
• Case 1: T = 1.
From the symmetry argument and the fact that any K servers possess independent messages, we have
[P]

[P]

H(A1:N |W [P] , Q) ≥ KH(A1 |W [P] , Q).

(43)

One way for a server to analyze P is by analyzing the entropy of the queries it receives (or equivalently, the feedbacks it
produces) conditioned on any subset of files. Since each server is not allowed to know any information of the identity of the
retrieved files, we must have
[P]

[P]

′

H(A1 |W [P] , Q) = H(A1 |W [P ] , Q), ∀P ′ ⊂ {1, 2, . . . , M }, |P ′ | = P.

(44)

′
[P]
H(A1 |W [P ] , Q)

characterises the amount
When M ≥ 2P , we may choose the index set P ′ to be disjoint from P. Thus,
of download from a server in a PIR scheme with the same parameters P, N, K, T but a different number of files M − P . So
we have the following inductive relation.
ΩM ≥ P L +

K
ΩM−P , M ≥ 2P.
N

(45)

[P]

)L
Plus, when M < 2P , H(A1 |W [P] , Q) is lower bounded by (M−P
, as shown in [2, Lemma 2]. So we have ΩM ≥
N
K
P L + N (M − P )L, M < 2P . Recursively using the inductive relation (45), we have

ΩM ≥ P L(1 +

K M
M
K
K
K M
+ ( )2 + · · · + ( )⌊ P ⌋−1 ) + ( )⌊ P ⌋ (M − P ⌊ ⌋)L.
N
N
N
N
P

(46)

So the multi-file PIR capacity C P is upper bounded by
CP

M

M

⌊P ⌋
1 − (K
M  K⌊ P ⌋
M
N)
−
⌊
⌋
+
P
P N⌊M
P ⌋
1− K
N

PL
≤
=
ΩM

And in particular, when M ≤ 2P , we have

K(M − P ) −1
.
PN
One can check that when K = 1, the results (47) and (48) agree with those in [2].
• Case 2: K = 1.
Similarly as (43), we have the following claim.
CP ≤ 1 +

[P]

[P]

H(A1:N |W [P] , Q) ≥ T H(A1 |W [P] , Q).

!−1

.

(47)

(48)

(49)

No matter how we design a PIR scheme, we have two kinds of queries. The first kind is a query dependent on the desired
files. The second kind is a query independent on the desired files (serving as side information). Each query of the first kind
will contribute one bit to the retrieved messages. In an optimal scheme, it is certain that all the queries of the first kind will
contribute independent bits, or otherwise the redundancy could be made use of to improve the scheme. From the perspective
of any T colluding servers, since they are not allowed to learn any information of the identity of the retrieved files, then the

14

queries of the second kind on these T servers should contribute independent bits as well. Therefore we have the claim (49)
above.
[P]
Using the analyses above of H(A1 |W [P] , Q) again, we can deduce the following inductive relation.
ΩM ≥ P L +

T
ΩM−P , M ≥ 2P.
N

(50)

[P]

)L
Plus, when M < 2P , H(A1 |W [P] , Q) is lower bounded by (M−P
, as shown in [2, Lemma 2]. So we have ΩM ≥
N
T
P L + N (M − P )L, M < 2P . Recursively using the inductive relation (50), we have

ΩM ≥ P L(1 +

T
T M
T M
M
T
+ ( )2 + · · · + ( )⌊ P ⌋−1 ) + ( )⌊ P ⌋ (M − P ⌊ ⌋)L.
N
N
N
N
P

(51)

So the multi-file PIR capacity C P is upper bounded by
C

P

PL
=
≤
ΩM

And in particular, when M ≤ 2P , we have

M

M

T ⌊P ⌋
)
1 − (N
M  T⌊P ⌋
M
−
⌊
⌋
+
T
P
P N⌊M
P ⌋
1− N

!−1

.

(52)

T (M − P ) −1
.
PN
One can check that when T = 1, the results (52) and (53) agree with those in [2].
CP ≤ 1 +

B. A general multi-file PIR scheme for P ≥

(53)

M
2

In this subsection we shall present a general multi-file PIR scheme for P ≥ M
2 , i.e., a user wants to retrieve at least half of
all the files.
M
1) Multi-file PIR scheme for P ≥ M
2 : Constructing the multi-file PIR scheme for P ≥ 2 contains the following steps.
• Step 1: Let α and β be the smallest positive integers satisfying
 
  
!
N
N
N −T
α
= (α + β)
−
.
(54)
K
K
K


N
Assume the existence of an (α+β) N
N .
K , α K -MDS code. The transpose of its generator matrix is denoted as MDS(α+β)(N
K )×α(K )

N
• Step 2: Let L = (α + β) K . Independently choose M random matrices, S1 , . . . , SM , uniformly from all the L × L full
rank matrices over Fq .


−1
N
• Step 3: Build an assisting array of size N
K−1 × N consisting of K symbols. Each symbol appears K times and every
K columns share a common symbol.
• Step 4: [Building basic blocks of the query structure] The query structure is divided into M α + P β blocks.
[m]
The M α blocks are denoted as Λλ , 1 ≤ λ ≤ α and 1 ≤ m ≤ M . In such a block any query is an atom towards the
[m]
[m]
[m]
corresponding file W . The atoms appeared in a block Λλ are the atoms a[(β+λ−1) N +1:(β+λ) N ] . The block is set in an
(K )
(K )
“isomorphic” form with the assisting array, i.e., every K servers share a common atom.
Pick a random MDS generator matrix H ∈ FqP ×M . For example, this could be done by choosing a Reed-Solomon generator
matrix and then randomly permuting the columns, resulting in a matrix H of the form

 

h11 h12 · · · h1M
h1
 h2   h21 h22 · · · h2M 

 

(55)
H= . = .
..
..  .
..
 ..   ..
.
.
. 
hP 1 hP 2 · · · hP M
hP
The P β blocks are denoted as ΛΣ
λ,p , 1 ≤ p ≤ P , 1 ≤ λ ≤ β. In such a block any query is a mixture of M atoms. Again the
block is set in an“isomorphic” form with the assisting array. If the corresponding entry in the assisting array is the number
Σ
x ∈ {1, 2, . . . , N
K }, then we set the corresponding query in the block Λλ,p to be the formal sum
[1]

hp · (a(λ−1)

[2]

[M]

,a
, . . . , a(λ−1) N +x ) =
( )+x (λ−1)(N
(K )
K )+x
N
K

M
X

m=1

[m]

hpm a(λ−1)

N
(K
)+x

.

(56)

• Step 5: [Constructing the atoms for the desired files] The atoms for each desired file W [m] , 1 ≤ m ≤ P are just built by
= Sm W [m] .

[m]
a[1:L]

15

• Step 6: [Constructing the atoms for the undesired files] For each undesired file W [m] , choose the first α

[m]
denoted as Sm [(1 : α N
K ), :]. The atoms a[1:L] are built by
 
N
[m]
a[1:L] = MDS(α+β)(N )×α(N ) Sm [(1 : α
), :]W [m] .
K
K
K

N
K



rows of Sm ,

(57)

The construction of the multi-file PIR scheme for P ≥ M
2 is finished. Comparing the scheme with the prototype, one
can see that the main adaptation is a different query structure. Instead of having blocks labelled by any nonempty subset
D ⊆ {W [1] , W [2] , . . . , W [M] }, now we only have blocks labelled by subsets of cardinality 1 and M .
2) An example: N = 4, K = 2, T = 2, M = 3, P = 2: Denote the three files by W [1] , W [2] and W [3] . The parameters
throughout the construction can be calculated as α = 5, β = 1 and L = 36. Assume each file is of length 72 and represented
in a matrix of size 36 × 2, i.e.,
[1]

W

[1]

w1
..
.

=

[1]
w36
[1]

[2]

!

W

[2]

=

w1
..
.

[2]
w36

[3]

!

W

[3]

w1
..
.

=

[3]
w36

!

(58)

[3]

[2]

where wi , wi , wi ∈ F2q , 1 ≤ i ≤ 36. Here Fq is a sufficiently large finite field. Let W [1] and W [2] be the desired files.
Independently choose three random matrices S1 , S2 , S3 ∈ Fq36×36 uniformly from all the 36 × 36 full rank matrices over Fq .
[2]
[1]
Construct a list of atoms a[1:36] = S1 W [1] . Similarly let a[1:36] = S2 W [2] . Suppose there exists a (36, 30)-MDS code and the
transpose of its generator matrix is denoted as MDS36×30 . Select the first 30 rows of S3 , denoted as S3 [(1 : 30), :]. Construct
[3]
a list of atoms a[1:36] = MDS36×30 S3 [(1 : 30), :]W [3] .
[3]

[2]

[1]

The atoms a[1:36] , a[1:36] and a[1:36] will form the queries for the servers. The queries for the servers are divided into
Σ
seventeen blocks. In fifteen blocks each query is only a single atom and in two blocks ΛΣ
1 and Λ2 each query is a mixture of
three atoms. The query structure is as follows.

ΛΣ
1 :

ΛΣ
2 :

(

[1]
z 1 a1
[1]
z 1 a3
[1]
z 1 a5

(

[1]
a1
[1]
a3
[1]
a5

Server I
[2]
[3]
+ a1 + a1
[2]
[3]
+ a3 + a3
[2]
[3]
+ a5 + a5

Server I
[2]
[3]
+ z 2 a1 + z 3 a1
[2]
[3]
+ z 2 a3 + z 3 a3
[2]
[3]
+ z 2 a5 + z 3 a5

[1]
z 1 a1
[1]
z 1 a4
[1]
z 1 a6

[1]
a1
[1]
a4
[1]
a6

Server II
[2]
[3]
+ a1 + a1
[2]
[3]
+ a4 + a4
[2]
[3]
+ a6 + a6

[1]
a2
[1]
a3
[1]
a6

Server II
[2]
[3]
+ z 2 a1 + z 3 a1
[2]
[3]
+ z 2 a4 + z 3 a4
[2]
[3]
+ z 2 a6 + z 3 a6

Server III
[2]
[3]
+ a2 + a2
[2]
[3]
+ a3 + a3
[2]
[3]
+ a6 + a6

[1]
z 1 a2
[1]
z 1 a3
[1]
z 1 a6

Server IV
)
[2]
[3]
+ a2 + a2
.
[2]
[3]
+ a4 + a4
[2]
[3]
+ a5 + a5

[1]
a2
[1]
a4
[1]
a5

Server III
[2]
[3]
+ z 2 a2 + z 3 a2
[2]
[3]
+ z 2 a3 + z 3 a3
[2]
[3]
+ z 2 a6 + z 3 a6

[1]
z 1 a2
[1]
z 1 a4
[1]
z 1 a5

Server IV
)
[2]
[3]
+ z 2 a2 + z 3 a2
[2]
[3]
+ z 2 a4 + z 3 a4
[2]
[3]
+ z 2 a5 + z 3 a5

where z1 , z2 , z3 are randomly chosen distinct elements in Fq .

[x]

Λλ

I Server II Server III Server IV )
( Server
[x]
[x]
[x]
[x]
a6λ+1
a6λ+1
a6λ+2
a6λ+2
:
[x]
[x]
[x]
[x]
a6λ+3
a6λ+4
a6λ+3
a6λ+4
[x]
[x]
[x]
[x]
a6λ+5
a6λ+6
a6λ+6
a6λ+5

for λ ∈ {1, 2, 3, 4, 5}, x ∈ {1, 2, 3}.
[1]

[2]

Retrieving the files W [1] and W [2] is equivalent to retrieving a[1:36] and a[1:36] since S1 and S2 are both full rank matrices.

[1]

[2]

[3]

[3]

[3]

a[7:36] , a[7:36] and a[7:36] could be retrieved. Then a[1:6] could be solved from a[7:36] due to the property of MDS36×30 . Therefore,
[1]

[2]

[1]

[2]

Σ
the interferences can be eliminated in the blocks ΛΣ
1 and Λ2 . So the queries of the form ai +ai and z1 ai +z2 ai , 1 ≤ i ≤ 6,
[2]
[1]
could be retrieved. Then we can solve the six systems of equations to retrieve a[1:6] and a[1:6] .
The scheme is private against any two colluding servers. From the perspective of any two colluding servers, altogether they
have 30 distinct atoms towards each file. Extract the coefficients of each atom as a vector in F36
q . Recall how we select the
random matrices S1 , S2 S3 and the (36, 30)-MDS code. It turns out that the 30 vectors with respect to each file form a random
subspace of dimension 30 in F36
q , so the two servers cannot tell any difference among the atoms towards different files and
thus the identity of the retrieved files is disguised.
36×2×2
12
The rate of the scheme above is then 12×5×3+12+12
= 17
. As a comparison, for the sake of retrieving two files a trivial
approach is to execute two independent (single-file) PIR schemes as shown in the example in Section III (note that 25 extra
bits of W [2] could be retrieved in the scheme designed for retrieving 36 bits of W [1] out of the 91 downloaded bits) and the
12
rate is only 61
91 < 17 .

16

3) Analysis of the multi-file PIR scheme for P ≥ M
2 : Each query appears in K different servers and thus can be successfully
[m]
retrieved. So we have retrieved all the atoms a[β N +1:L] for each file W [m] . Then by the property of MDS(α+β)(N )×α(N ) ,
(K )
K
K
[m]
[m]
we can solve a[1:β N ] from a[β N +1:L] for each undesired file. After eliminating these interferences from the queries in those
(K )
(K )
P β blocks ΛΣ
,
we
are
facing
with β systems of equations. The coefficients of each system come from some P columns
λ,p
[m]
of H and therefore form a non-singular P × P matrix. By solving these systems we retrieve a[1:β N ] for every desired file.
(K )
Therefore for every desired file we have retrieved all the L atoms towards the file, which is equivalent to the retrieval of the
file itself since each Sm is a full rank matrix.
The scheme is private against any T colluding servers. From the perspective of any T colluding servers, the query structure
is completely symmetric
with

 respect to all the files. The number of atoms towards Lany file known by these T colluding servers
N −T
is (α + β) N
−
. Extractthe coefficients of an atom as a vector in Fq . Recall how we build the atoms and the
K
K
N
N
property of the (α + β) K
 , α KL -MDS code. One can see that the vectors with respect to each file will form a random
N
subspace of dimension α K in Fq . So these T colluding servers cannot tell any difference among the atoms towards different
files and thus the identity of the retrieved files is disguised.
The rate of the scheme can be calculated as

N
Pα + Pβ
P LK
K
=

=


.
(59)
N
N
N −T
−T
M
Mα + Pβ
(M α + P β)K K
+ NK
P
K −
K
K(M−P ) −1
, meeting the
Recall that we are now dealing with the case P ≥ M
2 . When T = 1, the rate above is exactly 1 +
PN
) −1
upper bound of the capacity shown in (48). When K = 1, the rate above is exactly 1 + T (M−P
,
meeting
the
upper bound
PN
,
we
determine
the
exact
multi-file
PIR
capacity
for
the
degenerating
of the capacity shown in (53). Therefore, when P ≥ M
2
cases. Again the condition T + K ≤ N is essential since otherwise the equality (54) does not make sense. We summarize our
main result as follows.
(N ) 
when T + K ≤ N and
Theorem 4: There exists an (N, K, T ; M ) P -files PIR scheme with rate M N NK
N −T
−T
P (K )−( K ) +( K )
P ≥ M
2 . The rate of the scheme is optimal when either K = 1 or T = 1.
We close this subsection by briefly discussing the naive approach of executing P independent (single-file) PIR schemes.
Using our general (single-file) scheme, we can only have a P -file PIR scheme with rate
(1 + RM−1 P − RM−1 )(1 + R + R2 + · · · + RM−1 )−1 ,

(60)

N −T
K
N
K

)
(
where R = 1 −
. Within this calculation one should take into consideration that we can retrieve a certain amount of each
( )
of the other P − 1 files for free when we execute a (single-file) PIR scheme towards a fixed file. To check that the adapted
multi-file PIR scheme performs better than the trivial approach is equivalent to showing
1 + R + · · · + RM−1 > (

M
R + 1 − R)(1 + RM−1 P − RM−1 ).
P

(61)

The right-hand side achieves maximum at either P = M (then its value is 1 + (M − 1)RM−1 ) or P = M
2 (then its value is
M−1
(1 + R)(1 + ( M
−
1)R
)),
both
smaller
than
the
left-hand
side.
So
the
adapted
multi-file
PIR
scheme
is
indeed better than
2
the trivial approach.
VII. PIR WITH ARBITRARY

COLLUSION PATTERNS

In this section we deal with the last variant model, PIR with arbitrary collusion patterns. In this model the files are stored via
an arbitrary (N, K)-MDS code as usual. We have a collusion pattern T, which is a family of subsets of the set of servers. A
collusion subset T ∈ T indicates that this set of servers may collude in attacking on the identity of the desired file. Naturally,
any subset of a collusion set is again a collusion set, and therefore T is closed under inclusion. Thus collusion pattern T could
be denoted by its maximal collusion sets, say T =< T1 , T2 , . . . , Tr >. Designing PIR schemes in this model may follow a
case-by-case analysis due to the property of the specific collusion pattern. Suppose the cardinality of the largest collusion set
is T , then a PIR scheme against any T colluding servers certainly works. However, there is some space for improvements.
To adapt our general PIR scheme for this model, the trick is to adjust the assisting array used in the construction. First
we need to analyze the following optimization problem, which is closely related to combinatorial design theory. A family
of K-subsets of the servers is denoted as B = {B1 , B2 , . . . , Bb }. For every maximal collusion set Ti , 1 ≤ i ≤ r, let #(Ti )
denote the number of K-subsets in B which have non-empty intersections with Ti . Let ∆ = max{#(Ti ) : 1 ≤ i ≤ r}. The
problem is to find a proper family B to minimize ∆/b. For example, when we consider the previous models where T denotes

every T -subset
ofthe servers, we simply set B to be the collection of every K-subset of the servers. Then b = N
K and

N −T
∆= N
.
K −
K

17

A. PIR scheme with arbitrary collusion patterns
Constructing the PIR scheme with arbitrary collusion patterns contains the following steps.
• Step 0: Given the collusion pattern T, find a proper family B to solve the optimization problem above.
• Step 1: Let α and β be the smallest positive integers satisfying
αb = (α + β)∆.
(62)

Assume the existence of an (α + β)b, αb -MDS code. The transpose of its generator matrix is MDS(α+β)b×αb .
• Step 2: Let L = b(α + β)M−1 . Independently choose M random matrices, S1 , . . . , SM , uniformly from all the L × L full
rank matrices over Fq .
• Step 3: Build an assisting array according to the choice of B. Each symbol appears K times and every subset of servers
B ∈ B share a common symbol.
• Step 4: [Construction of the query structure] The query structure is divided into several blocks, where each block is
labelled by D ⊆ {W [1] , W [2] , . . . , W [M] }, a subset of files. In a block labelled by D, the queries are of the same form, i.e.,
every query is a mixture of |D| atoms related to the files in D. Set each block in an “isomorphic” form with the assisting
array. We further call a block labelled by D a d-block if |D| = d. For any D ⊆ {W [1] , W [2] , . . . , W [M] }, |D| = d, we require
that the number of d-blocks labelled by D is αM−d β d−1 .
• Step 5: [Constructing the atoms for the desired file in each block] The atoms for the desired file W [1] are just built by
S1 W [1] and then distributed to different blocks.
• Step 6: [Dividing the query structure into groups] Now let D denote a nonempty set of files not containing
the desired
S
file W [1] . There are totally αM−|D| β |D|−1 blocks labelled by D and αM−|D|−1 β |D| blocks labelled by D {W [1] }. Partition
M−|D|−1 |D|−1
these blocks into αM−|D|−1 β |D|−1 groups, S
denoted by ΓD
β
, where each group consists of α blocks
λ, 1 ≤λ ≤α
[1]
labelled by D and β blocks labelled by D {W }. Repeat this process for every nonempty set D not containing W [1] and
thus the whole query structure is partitioned into groups.
• Step 7: [Constructing the atoms for undesired files in each group] For each group constructed with respect to D and any
file W [m] ∈ D, m 6= 1, the number of atoms towards W [m] within the blocks in this group is (α + β)b, among
S which αb
atoms appear in blocks labelled by D and the other βb atoms appear as interferences in blocks labelled by D {W [1] }. Let
′
′
these (α + β)b atoms for W [m] be built by MDS(α+β)b×αb Sm
W [m] , where Sm
denotes some αb rows in the matrix Sm . 
M−2
Repeat this process for all the groups. Note that we shall come across the same file W [M] several times. We have |D|−1
choices for a subset D of size |D|, containing W [M] but without W [1] . With respect to any such D we have αM−|D|−1 β |D|−1
groups. So the exact number of times we come across W [M] can be computed as


M−1
X
M −2
= (α + β)M−2 .
(63)
αM−|D|−1 β |D|−1
|D| − 1
|D|=1

Every time we come across the same file W [M] , we have to ensure that the rows we select from Sm are non-intersecting.
This can be satisfied since (α + β)M−2 αb ≤ L.
The construction of the PIR scheme with respect to the particular collusion pattern T is finished. Comparing the scheme
with the prototype, one can see that the main adaptation is changing the assisting array and then adjusting the ratio of different
blocks according to the new assisting array.
B. An example
Let N = 5, K = 3, M = 2. The collusion pattern is T = {{I, II}, {II, III}, {III, IV }, {IV, V }, {I, V }}. Instead of
choosing the collection of every 3-subset, we could set B = {{I, II, III}, {II, III, IV }, {III, IV, V }, {I, IV, V }, {I, II, V }}
and build the corresponding assisting array such that every subset of servers B ∈ B share a common entry:
(
)
1 2 3 4 5
5 1 2 3 4 .
4 5 1 2 3
The parameters throughout the construction can be calculated as b = 5, ∆ = 4, α = 4, β = 1 and then L = 25.
Now we have two files U and V . Let each file be of length 75 and represented in a matrix of size 25 × 3, i.e.,
U=

u1 !
..
.

u25

V =

v1 !
..
.

(64)

v25

where ui , vi ∈ F3q , 1 ≤ i ≤ 25. Here Fq is a sufficiently large finite field. Let U be the desired file. We shall construct two
lists of atoms a[1:25] and b[1:25] corresponding to each file accordingly. Following Step 4, the query structure is divided into
several blocks as follows. In each block we set the queries in an “isomorphic” form with the assisting array.

18

Λ

ΛX
η

( Server I
x5η+1
:
x5η+5
x5η+4

UV

Server II
x5η+2
x5η+1
x5η+5

( Server I
a1 + b 1
:
a5 + b 5
a4 + b 4

Server II
a2 + b 2
a1 + b 1
a5 + b 5

Server III Server IV Server V )
a3 + b 3
a4 + b 4
a5 + b 5
,
a2 + b 2
a3 + b 3
a4 + b 4
a1 + b 1
a2 + b 2
a3 + b 3

Server III Server IV Server V )
x5η+3
x5η+4
x5η+5
for (x, X) ∈ {(a, U ), (b, V )} and η ∈ {1, · · · , 4}.
x5η+2
x5η+3
x5η+4
x5η+1
x5η+2
x5η+3

The remaining task is then to determine the atoms. In Step 2 we have a (25, 20)-MDS code and the transpose of its generator
matrix is denoted as MDS25×20 . Independently choose two random matrices S1 , S2 ∈ Fq25×25 , uniformly from all the 25 × 25
full rank matrices over Fq . The atoms a[1:25] are just built by S1 U . The atoms b[1:25] are built by MDS25×20 S2 [(1 : 20), :]V .
Retrieving the file U is equivalent to retrieving a[1:25] since S1 is a full rank matrix. Retrieving a[6:25] and b[6:25] is
straightforward. Using the MDS property of MDS25×20 , b[1:5] can be solved from b[6:25] . Eliminating these interferences we
now retrieve a[1:5] .
The scheme is private against the specific collusion pattern. The query structure is completely symmetric with respect to
all the files. From the perspective of any two possible colluding servers, altogether the number of atoms towards each of the
three files is 20. Extract the coefficients of each atom as a vector in F25
q . Recall how we select the random matrices S1 , S2 ,
and the (25, 20)-MDS code. It turns out that the 20 vectors with respect to each file form a random subspace of dimension
20 in F25
q , so the two servers cannot tell any difference among the atoms towards different files and thus the identity of the
retrieved file is disguised.
Note that if Server I and Server III collude, then the scheme fails. Server I and Server III know all the atoms. They will
discover that the 25 atoms towards U are independent and the 25 atoms towards V have certain redundancy. Therefore they
will realize that U is the desired file.
10
25×3
= 95 . This improves on the result 19
if we use a general scheme against any
The rate of the scheme above is then 3×5×9
two colluding servers.
C. Analysis of the PIR scheme with arbitrary collusion patterns
Each query in the scheme appears in K distinct servers and is thus retrieved. For each group constructed with respect to
D, using the property of MDS(α+β)b×αb
, we can use the αb queries in the blocks labelled by D to eliminate the interferences
S
in the βb blocks labelled by D {W [1] }. Therefore all the atoms towards W [1] can be retrieved. By the singularity of S1 , the
desired file is successfully retrieved.
The scheme is private against any set of possible colluding servers. For a maximal colluding set T ∈ T, the atoms towards
any file known by these servers is (α + β)M−1 ∆. Extract the coefficients of each atom as a vector in FL
q . Recall how we
build the atoms by using the full rank matrices S1 , . . . , Sm and the MDS code. One can see that the vectors of all the atoms
towards any file will form a random subspace of dimension (α + β)M−1 ∆ in FL
q . So these colluding servers cannot tell any
difference among the atoms towards different files and thus the identity of the retrieved file is disguised.
We compute the rate of the PIR scheme. The retrieved file is of length LK. The download cost in any block is bN . So the
rate can be computed as
LK
bK

PM

=

M−|F | β |F |−1 M
|F |=1 α
|F |

bβ −1

L
=
1+
(α + β)M − αM

α
α+β

1
.
α
+ · · · + ( α+β
)M−1

Similarly as before, a final remark is that our scheme only works for the case b > ∆ since otherwise the equality (27) does
not make sense (This can be satisfied as long as T + K ≤ N , where T is the cardinality of a maximal colluding set). To sum
up, we have the following theorem.
Theorem 5: Given an arbitrary collusion pattern T, suppose we can build a family of K-subsets of servers B = {B1 , B2 , . . . , Bb }
such that any T ∈ T intersects with at most ∆ subsets in B. If b > ∆, then there exists an (N, K; M )-PIR scheme with
respect to this collusion pattern whose rate is (1 + R + R2 + · · · + RM−1 )−1 , where R = ∆b .
VIII. C ONCLUSION
In this paper, we adapt our general PIR scheme presented in [33] for four variant PIR models. The idea can be generalized
(although maybe tedious) further to some hybrid models, say a multi-file PIR model with both robust and Byzantine servers.
The results contain a series of previous works as special cases. However, it is not clear to evaluate the performance of the
scheme for non-degenerating parameters K and T , since the exact PIR capacity (or even only a good upper bound) remains
unknown. A first step to analyze the PIR capacity for the general model will be of great interest.

19

R EFERENCES
[1] D. Augot, F. Levy-dit-Vehel and A. Shikfa, A storage-efficient and robust Private Information Retrieval Scheme allowing few servers, in Proceedings of
Cryptology and Network Security (CANS), pp. 222-239, 2014.
[2] K. Banawan and S. Ulukus, Multi-message private information retrieval: capacity results and near-optimal schemes, arXiv:1702.01739, 2017.
[3] K. Banawan and S. Ulukus, The capacity of private information retrieval from Byzantine and colluding databases, arXiv:1706.01442, 2017.
[4] K. Banawan and S. Ulukus, The capacity of private information retrieval from coded databases, arXiv:1609.08138, 2016.
[5] A. Beimel, Y. Ishai, E. Kushilevitz and J.-F. Raymond, Breaking the O(n1/(2k−1) ) barrier for information-theoretic private information retrieval, in
Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pp. 261-270, 2002.
[6] S. Blackburn, T. Etzion and M. Paterson, PIR schemes with small download complexity and low storage requirements, arXiv:1609.07027, 2016.
[7] T. Chan, S. Ho and H. Yamamoto, Private information retrieval for coded storage, in Proceedings of IEEE International Symposium on Information
Theory (ISIT), pp. 2842-2846, 2015.
[8] Z. Chen, Z. Wang and S. Jafar, The capacity of private information retrieval with private side information, arXiv:1709.03022, 2017.
[9] B. Chor, O. Goldreich, E. Kushilevitz and M. Sudan, Private information retrieval, in Proceedings of the Annual Symposium on Foundations of Computer
Science (FOCS), pp. 41-50, 1995.
[10] B. Chor, E. Kushilevitz, O. Goldreich and M. Sudan, Private information retrieval, Journal of the ACM, vol. 45, no. 6, pp. 965-981, 1998.
[11] Z. Dvir and S. Gopi, 2-server PIR with sub-polynomial communication, Journal of the ACM, vol. 63, no. 4, article 39, 2016.
[12] K. Efremenko, 3-query locally decodable codes of subexponential length, SIAM Journal on Computing, vol. 41, no. 6, pp. 1694-1703, 2012.
[13] R. Freij-Hollanti, O. Gnilke, C. Hollanti and D. Karpuk, Private information retrieval from coded databases with colluding servers, arXiv:1611.02062,
2016.
[14] S. Kadhe, B. Garcia, A. Heidarzadeh, S. E. Rouayheb and A. Sprintson, Private information retrieval with side information, arXiv:1709.00112, 2017.
[15] S. Kumar, E. Rosnes and A. G. i Amat, Private information retrieval in distributed storage systems using an arbitrary linear code, arXiv:1612.07084,
2016.
[16] N. B. Shah, K. V. Rashmi and K. Ramchandran, One extra bit of download ensures perfectly private information retrieval, in Proceedings of IEEE
International Symposium on Information Theory (ISIT), pp. 856-860, 2014.
[17] H. Sun and S. Jafar, Multiround Private Information Retrieval: Capacity and Storage Overhead, arXiv:1611.02257, 2016.
[18] H. Sun and S. Jafar, Private information retrieval from MDS coded data with colluding servers: settling a conjecture by Freij-Hollanti et al.,
arXiv:1701.07807, 2017.
[19] H. Sun and S. Jafar, The capacity of private information retrieval, IEEE Transactions on Information Theory, vol. 63, no. 7, pp. 4075-4088, 2017.
[20] H. Sun and S. Jafar, The capacity of robust private information retrieval with colluding databases, arXiv:1605.00635, 2016.
[21] H. Sun and S. Jafar, The capacity of symmetric private information retrieval, arXiv: 1606.08828, 2016.
[22] R. Tajeddine and S. E. Rouayheb, Private information retrieval from MDS coded data in distributed storage systems, in Proceedings of IEEE International
Symposium on Information Theory (ISIT), pp. 1411-1415, 2016.
[23] R. Tajeddine and S. E. Rouayheb, Private information retrieval from MDS coded data in distributed storage systems, arXiv:1602.01458, 2016.
[24] R. Tajeddine and S. E. Rouayheb, Robust private information retrieval on coded data, arXiv:1707.09916, 2017.
[25] R. Tajeddine, O. Gnilke, D. Karpuk, R. Freij-Hollanti, C. Hollanti and S. E. Rouayheb, Private information retrieval schemes for coded data with arbitrary
collusion patterns, arXiv:1701.07636, 2017.
[26] R. Tandon, The capacity of cache aided private information retrieval, arXiv:1706.07035, 2017.
[27] Q. Wang and M. Skoglund, Symmetric private information retrieval for MDS coded distributed storage, arXiv:1610.04530, 2016.
[28] Q. Wang and M. Skoglund, Linear symmetric private information retrieval for MDS coded distributed storage with colluding servers, arXiv:1708.056730,
2017.
[29] Y.-P. Wei, K. Banawan and S. Ulukus, Fundamental limits of cache-aided private information retrieval with unknown and uncoded prefetching,
arXiv:1709.01056, 2017.
[30] Y.-P. Wei, K. Banawan and S. Ulukus, The capacity of private information retrieval with partially known private side information, arXiv:1710.00809,
2017.
[31] S. Yekhanin, Private information retrieval, Communications of the ACM, vol. 53, no. 4, pp. 68-73, 2010.
[32] S. Yekhanin, Towards 3-query locally decodable codes of subexponential length, Journal of the ACM, vol. 55, no. 1, article 1, 2008.
[33] Y. Zhang and G. Ge, A general private information retrieval scheme for MDS coded databases with colluding servers, arXiv:1704.06785, 2017.

