1

Achieving Private Information Retrieval Capacity in
Distributed Storage Using an Arbitrary Linear Code

arXiv:1712.03898v2 [] 16 Dec 2017

Siddhartha Kumar, Student Member, IEEE, Hsuan-Yin Lin, Member, IEEE,
Eirik Rosnes, Senior Member, IEEE, and Alexandre Graell i Amat, Senior Member, IEEE

Abstract—We propose three private information retrieval
(PIR) protocols for distributed storage systems (DSSs) where data
is stored using an arbitrary linear code. The first two protocols,
named Protocol 1 and Protocol 2, achieve privacy for the scenario
with noncolluding nodes. Protocol 1 requires a file size that is
exponential in the number of files in the system, while the file size
required for Protocol 2 is independent of the number of files and
is hence simpler. We prove that, for certain linear codes, Protocol
1 achieves the PIR capacity, i.e., its PIR rate (the ratio of the
amount of retrieved stored data per unit of downloaded data) is
the maximum possible for any given (finite and infinite) number
of files, and Protocol 2 achieves the asymptotic PIR capacity (with
infinitely large number of files in the DSS). In particular, we
provide a sufficient and a necessary condition for a code to be
PIR capacity-achieving and prove that cyclic codes, Reed-Muller
(RM) codes, and optimal information locality local reconstruction
codes achieve both the finite PIR capacity (i.e., with any given
number of files) and the asymptotic PIR capacity with Protocols
1 and 2, respectively. Furthermore, we present a third protocol,
Protocol 3, for the scenario with multiple colluding nodes, which
can be seen as an improvement of a protocol recently introduced
by Freij-Hollanti et al. We also present an algorithm to optimize
the PIR rate of the proposed protocol. Finally, we provide a
particular class of codes that is suitable for this protocol and
show that RM codes achieve the maximum possible PIR rate for
the protocol.

I. I NTRODUCTION
In data storage applications, besides resilience against disk
failures and data protection against illegitimate users, the
privacy may also be of concern. For instance, one may be
interested in designing a storage system in which a file can be
downloaded without revealing any information of which file
is actually downloaded to the servers storing it. This form of
privacy is usually referred to as private information retrieval
(PIR). PIR is important to, e.g., protect users from surveillance
and monitoring.
PIR protocols were first studied in the computer science
literature by Chor et al. in [1], [2], which introduced the
concept of an n-server PIR protocol, where a binary storage
node is replicated among n servers (referred to as nodes)
and the aim is to privately retrieve a single bit from the
This work was partially funded by the Research Council of Norway
(grant 240985/F20) and the Swedish Research Council (grant #2016-04253).
This paper was presented in part at the IEEE International Symposium on
Information Theory (ISIT), Aachen, Germany, June 2017.
S. Kumar, H.-Y. Lin, and E. Rosnes are with Simula@UiB, N5020 Bergen, Norway (e-mail: kumarsi@simula.no; lin@simula.no;
eirikrosnes@simula.no).
A. Graell i Amat is with the Department of Electrical Engineering,
Chalmers University of Technology, SE-41296 Gothenburg, Sweden (e-mail:
alexandre.graell@chalmers.se).

storage nodes while minimizing the total upload and download
communication cost. Additionally, an n-server PIR protocol
assumes that the n nodes do not collude in order to reveal the
identity of the requested file. The communication cost in [1]
was further reduced in [3]–[5]. Since then, coded PIR schemes
have been introduced, where the data is encoded (as opposed
to simply being replicated) across several nodes [6]. With the
advent of distributed storage systems (DSSs), where the user
data is encoded and then stored on n nodes, there has been an
increasing interest in implementing coded PIR protocols for
these systems.
In recent years PIR has become an active research area in
the information theory community with a fundamental difference in the measurement of efficiency. In the informationtheoretic sense, the message sizes are much larger than the
size of all queries sent to the storage nodes. Thus, rather
than accounting for both the upload and the download cost,
download cost forms the primary measurement of efficiency
as the upload cost can be neglected. The ratio between the
requested file size to the amount of downloaded data is referred
to as the PIR rate, where higher PIR rates mean higher
efficiency. The highest achievable PIR rate for any n-server
PIR protocol is referred to as the PIR capacity.
In the information theory literature, the authors in [7] were
the first to present PIR protocols for DSSs where data is
stored using codes from two explicit linear code constructions.
In [8], the authors presented upper bounds on the tradeoff
between the storage and the PIR rates for a certain class of
linear PIR protocols. In [9], Fazeli et al. introduced PIR codes
which, when used in conjunction with traditional n-server PIR
protocols, allow to achieve PIR on DSSs. These codes achieve
high code rates without sacrificing on the communication cost
of an n-server PIR protocol. In [10], given an arbitrary number
of files, the authors derived the PIR capacity for noncolluding
and replicated databases, where the data can be seen as being
encoded by a particular class of maximum distance separable
(MDS) codes, the repetition code. For the case of noncolluding
nodes, Banawan and Ulukus [11] derived the PIR capacity for
DSSs using an [n, k] MDS code to store a given number of
files. In this paper, we will refer to the PIR capacity for a given
finite number of files as the finite PIR capacity. In [12], a PIR
protocol for MDS-coded DSSs was proposed and shown to
achieve the PIR capacity for the case of noncolluding nodes
when the number of files stored in the DSS goes to infinity.
Here, we will refer to the PIR capacity for an infinite number
of files as the asymptotic PIR capacity, while the PIR capacity
for the colluding case is still an open problem. The problem

2

of symmetric PIR for DSSs was recently considered in [13],
where an expression for the symmetric PIR capacity for linear
schemes in the general case of colluding nodes and an MDS
linear storage code was derived. In the symmetric case, the
user should not only be able to privately retrieve the requested
file from the system, but also learn nothing about the other files
stored from the retrieved data. See also the related work [14],
which deals with replicated databases. The PIR capacity for
the case where a given number of storage nodes fail to respond
(so-called robust PIR) was given in [15] for the scenario of
colluding servers with replication coding.
In the storage community, it is well-known that MDS codes
are inefficient in the repair of failed nodes. Repair is essential
to maintain the initial state of reliability of the DSS. To address
efficient repair, Pyramid codes [16], locally repairable codes
[17], local reconstruction codes (LRCs) [18], [19], and locally
recoverable codes [20] have been proposed. These four classes
of codes follow the same design philosophy and for simplicity,
we will refer to them generically as LRCs. LRCs achieve low
locality, i.e., a low number of nodes need to be contacted
to repair a single failed node. Following the motivation of
using non-MDS codes in DSSs, the authors of [21] presented
a PIR protocol for DSSs that store data using arbitrary linear
codes for the scenario of noncolluding nodes. Independently,
Freij-Hollanti et al. in [22] presented an MDS PIR protocol
that ensures privacy even when a subset of at most n − k
nodes collude. The PIR property of the protocol in [22] was
ensured for storage nodes that store data using generalized
Reed-Solomon (GRS) codes. Moreover, they showed that their
protocol could work with certain non-MDS codes, but it
is well-known that not all linear codes can work with this
protocol. However, for such non-MDS codes the PIR rates that
can be achieved are at most the code rate of the underlying
code. In [23], Freij-Hollanti et al. showed that Reed-Muller
(RM) codes can be used with the aforementioned protocol.
However, the PIR rates achieved are quite low.
In this paper, as an extension of [21], we present three
PIR protocols for DSSs using arbitrary linear codes. These
protocols share the fact that all of them are constructed by
making use of correctable erasure patterns and information
sets of the underlying storage code. We first focus on the
noncolluding scenario and propose two PIR protocols, referred
to as Protocol 1 and Protocol 2. Protocol 1 requires a file
size that is exponential in the number of files in the system,
while the file size required for Protocol 2 is independent of
the number of files and is therefore simpler. Furthermore,
Protocol 1 is designed such that its PIR rate depends on
the number of files in the system, while Protocol 2 is such
that its PIR rate is independent of the number of files. We
prove that, interestingly, for certain non-MDS code families,
Protocol 1 achieves the finite PIR capacity (and hence the
asymptotic PIR capacity as well) and Protocol 2 achieves the
asymptotic (i.e., when the number of files tends to infinity)
PIR capacity. Thus, we show that the MDS property required
to achieve PIR capacity in [10]–[12] is not necessary and
overly restrictive. In particular, we give a sufficient condition
based on automorphisms and a necessary condition connected
to generalized Hamming weights for arbitrary linear codes

to achieve PIR capacity. We prove that optimal information
locality LRCs, RM codes, and all cyclic codes achieve the
finite PIR capacity (and thus the asymptotic PIR capacity, too)
with Protocol 1 and the asymptotic PIR capacity with Protocol
2. For other codes, we present an optimization algorithm for
PIR Protocols 1 and 2 such that they can achieve the best
possible PIR rates. We furthermore present a third protocol,
Protocol 3, that can attain privacy for the scenario of multiple
colluding nodes and non-MDS codes. This protocol is based
on and improves the protocol in [22], [23], and achieves PIR
rates that are no longer limited by the rate of the underlying
non-MDS storage code as in [22]. We provide an optimization
algorithm for the protocol to optimize the PIR rate. Such
an optimization is in itself an extension of the optimization
algorithm for Protocols 1 and 2 for the case of noncolluding
nodes. Besides GRS and RM codes as in [22], [23], we also
prove that (U|U + V) codes [24] with U being an arbitrary
linear code and V a repetition code can be used in conjunction
with Protocol 3. Moreover, we show that RM codes can
achieve an upper bound on the PIR rate which is higher than
the one reported in [23] and give examples of all-symbol
locality LRCs with good PIR rates.
The remainder of this paper is organized as follows. We
provide some definitions and preliminaries in Section II. In
Section III, we provide a general system model for the three
PIR protocols proposed in the paper. In Sections IV and V,
we present PIR Protocols 1 and 2 for the scenario with
noncolluding nodes. In Section VI, we give a sufficient and
a necessary condition for codes to achieve PIR capacity.
Furthermore, we prove that several families of codes can
achieve the PIR capacity, and we also give an optimization
algorithm to optimize the PIR rate. In Section VII, we consider
the scenario with colluding nodes and propose PIR Protocol 3.
In the same section, we also present a family of storage codes
that can be used with this protocol. Lastly, we show that RM
codes can achieve an upper bound on the PIR rate for this
protocol. In Section VIII, we optimize the PIR Protocols 1, 2,
and 3 to maximize their PIR rates for different storage codes
under the scenarios of noncolluding and colluding nodes.
Finally, some conclusions are drawn in Section IX.
A. Notations and Conventions
In this paper, we use the following notations. We use lower
case bold letters to denote vectors, upper case bold letters to
denote matrices, and calligraphic upper case letters to denote
sets. For example: x, X, and X denote a vector, a matrix,
and a set, respectively. An identity matrix of order m is
denoted as Im . An all-zero matrix of dimension a × b is
denoted as 0a×b , while an all-one matrix of dimension a × b
is referred to as 1a×b . (·)⊤ represents the transpose of its
argument and h·, ·i denotes the scalar dot product between
two vectors. The operator ◦ represents the Hadamard product.
As such, x◦y represents the Hadamard product of two lengthn vectors x and y. Consider the column vectors x1 , . . . , xa ,
then (x1 | . . . |xa ) represents the horizontal concatenation of
the column vectors. Similarly, the horizontal concatenation of
the matrices X1 , . . . , Xa , all with the same number of rows,

3

will be denoted by (X1 | . . . |Xa ). We represent a submatrix of
X that is restricted in columns by the set I and in rows by the
set J by X|J
I , and the matrix rank of X by rank (X). The
function LCM(a, b) computes the lowest common multiple of
two real numbers a and b, and a | b denotes that a is a
divisor of b, while the function H(·) represents the entropy
of its argument.
In the rest of the paper, C will denote a linear code over
a finite field GF(q). The operations over GF(q), such as
addition, multiplication, etc., will be clearly understood from
the context. We use the customary code parameters [n, k] to
refer to a code of blocklength n and dimension k, having
a code rate RC = k/n. The dimension of a code C will
sometimes be denoted by dim (C). Furthermore, [n, k, dCmin ]
represents an [n, k] code of minimum Hamming distance
dCmin . Since a code C can be seen as a codebook matrix,
the shortened and punctured codes are denoted by C|J
I , with
column indices I and row coordinates J . In addition, H C ,
GC , and C ⊥ represent the parity-check matrix, the generator
matrix, and the dual code, respectively, of C. We denote
by N the set of all positive integers, Na , {1, 2, . . . , a},
and Nn1 :n2 , {n1 , n1 + 1, . . . , n2 } for two positive integers
n1 ≤ n2 , n1 , n2 ∈ N. The Hamming weight of a binary vector
x is denoted by wH (x), while the support of a vector x
(either binary or nonbinary), i.e., the set of nonzero entires
of x, will be denoted by χ(x). Note that sometimes, for
the sake of convenience, we will omit the superscripts and/or
the subscripts if the arguments we refer to are contextually
unambiguous. Also, with some abuse of language, the index
of a coordinate of a vector is sometimes referred to simply as
the coordinate.
II. D EFINITIONS

AND

P RELIMINARIES

In this section, we review some basic notions in coding
theory and some classes of codes that will be used throughout
the paper.
Definition 1: Let C be an [n, k] code defined over GF(q).
A set of coordinates of C, I ⊆ Nn of size k is said to be an
information set if and only if GC |I is invertible.
Definition 2: Let D be a subcode of an [n, k] code C. The
support of D is defined as
χ(D) , {j ∈ Nn : ∃ x = (x1 , . . . , xn ) ∈ D, xj 6= 0}.
It is noted that
χ(D) =

[

χ(x),

x∈D

where χ(x) denotes the support of x.
Next, we introduce the concept of generalized Hamming
weights [25].
Definition 3: The s-th generalized Hamming weight of an
[n, k] code C, denoted by dCs , s ∈ Nk , is defined as the
cardinality of the smallest support of an s-dimensional subcode
of C, i.e.,

dCs , min |χ(D)| : D is an [n, s] subcode of C .
For the sequel, we introduce the notion of Hadamard
product [26] of vector spaces.

Definition 4: Let X and Y be two vector spaces in GF(q)n .
The Hadamard product of X and Y, X ◦ Y, is defined as the
space in GF(q)n generated by the Hadamard products x ◦ y
for all x ∈ X and y ∈ Y.
A. Reed-Muller Codes
We review the family of linear binary RM codes [27] and
then quickly summarize a result related to information sets of
an RM code. We adapt the concept and definition from [24,
Ch. 13], and the details can be found therein.
Definition 5: For a given m ∈ N, the v-th order binary
RM code R(v, m) is an [n, k]Plinear code
with length n =

v
2m and code dimension k = i=0 mi for v ∈ {0} ∪ Nm ,
constructed as the linear space spanned by the set of all mvariable Boolean monomials of degree at most v.
For example, R(2, 3) can be viewed as the linear space spanned by the set of Boolean monomials
{1, z1 , z2 , z3 , z1 z2 , z1 z3 , z2 z3 }.
Next, we introduce a way to number the coordinate index
of an RM codeword. Without loss of generality, since there
are in total n = 2m codeword coordinates, each coordinate
index j ∈ N2m can be described by a binary column m-tuple
µ = (µ1 , . . . , µm )⊤ , µi ∈ GF(2), such that
j ,1+

m
X

µi 2i−1 .

(1)

i=1

For instance, for m = 4, the 7-th coordinate of an RM code
corresponds to (0 1 1 0)⊤ . Hence, a set of coordinates I ⊆ Nn
can alternatively be written as a set of corresponding m-tuples
for RM codes.
Let V be an m × m invertible matrix over GF(2) and
σ ∈ GF(2)m×1 be a length-m binary column vector. It is
well-known that the coordinate transformation mapping µ onto
V µ + σ is an automorphism for the RM code [24, Ch. 13].
Hence, we obtain the following important property concerning
information sets for RM codes.
Proposition 1: Let I = {µi }i∈Nk ⊆ GF(2)m×1 be an information set of R(v, m), and define the following coordinate
set
I ′ , {g(µi ) : µi ∈ I},
where g(µ) , V µ + σ for an arbitrary m × m invertible
binary matrix V and an arbitrary σ ∈ GF(2)m×1 . Then, I ′
also forms an information set of the RM code.
For the sake of simplicity, throughout the paper we assume
V = Im .
Example 1: Consider the RM code R(1, 3) with generator
matrix


1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1

GR(1,3) = 
0 0 1 1 0 0 1 1 .
0 0 0 0 1 1 1 1

Clearly, I = {(0 0 0)⊤ , (1 0 0)⊤ , (0 1 0)⊤ , (0 0 1)⊤ } forms
an information set for R(1, 3). Pick an automorphism g with
V = I3 being the identity matrix and σ = (0 0 1)⊤ . Then,
I ′ = {g(µ) = µ + σ : µ ∈ I}

4

= {(0 0 1)⊤ , (1 0 1)⊤ , (0 1 1)⊤ , (0 0 0)⊤ }
is also an information set of R(1, 3).
The following lemma shows how to determine an information set for an RM code.
Lemma 1: Consider the RM code R(v, m) with v ∈ {0} ∪
Nm , m ∈ N. Then, the set of m-tuples given by
I , {µ ∈ GF(2)m×1 : wH (µ) ≤ v}
is an information set for R(v, m).
Proof: The proof is based on the definition of RM codes.
The details are given in Appendix A.
Lemma 1 can be extended to nonbinary generalized RM
codes (see the comprehensive work in [28] that determines
the information sets for generalized RM codes).
B. Local Reconstruction Codes
LRCs are a family of codes that are used in DSSs because
of their low repair locality, i.e., they need to contact a
relatively low number of nodes in order to repair a failed node.
Systematic codes that focus on lowering the locality for the
systematic nodes (i.e., the nodes that store the systematic code
symbols; see the system model in Section III) are referred
to as information locality codes. Examples of such codes are
presented in [16], [18]. On the contrary, LRCs that achieve
low locality for all nodes are referred to as all-symbol locality
codes. The codes presented in [20] are examples of all-symbol
locality codes. Formally, information locality codes are defined
as follows.
Definition 6 ((r, δ) information locality code [19]): An
[n, k] erasure correcting code of length n and dimension k
is said to be an (r, δ) information locality code if there exists
Lc punctured codes Ci , C|Si of C with a column coordinate
set Si ⊂ Nn for i ∈ NLc . Furthermore, {C|Si }i∈NLc should
satisfy the following conditions:
1) |Si | ≤ r + δ − 1, ∀ i ∈ NLc ,
i
2) dCmin
≥ δ, ∀ i ∈
 NLc , and
3) rank G|Si Si = k.
The overall code C has minimum Hamming distance dCmin ≤
n − k + 1 − (⌈k/r⌉ − 1)(δ − 1) and can repair δ − 1
systematic nodes by contacting r storage nodes. In other
words, Definition 6 says that there are Lc local codes in C
each having a block length of at most r + δ − 1, a minimum
Hamming distance of at least δ, and the union of all local codes
forms an information set. Codes that achieve the upper bound
on the minimum Hamming distance are known as optimal
(r, δ) information locality codes and they have the following
structure.
Definition 7 (Optimal information locality code [19,
Th. 2.2]): Let r | k such that Lc = k/r. An (r, δ) information
locality code C as defined in Definition 6 is optimal if:
1) Each local code C|Si , i ∈ NLc , is an [r + δ − 1, r]
MDS code defined by a parity-check matrix H C|Si =
(Pi |Iδ−1 ) of dimension (δ − 1) × (r + δ − 1) and minimum Hamming distance δ. The matrix Pi of dimension
(δ − 1) × r is the parity-check matrix of the i-th local
code.

2) The sets {Si }i∈NLc are disjoint, i.e., Si ∩ Si′ = ∅ for all
i, i′ ∈ NLc , i 6= i′ .
3) The code C has a parity-check matrix of the form


P1 Iδ−1


P2 Iδ−1




.
..
H=
,




PLc Iδ−1
0
M1
0
M2
0
· · · ML c
Ia
(2)
where the matrices M1 , . . . , MLc are arbitrary matrices of
dimension (n − Lc (r + δ − 1)) × r in GF(q), and a , n −
Lc (r + δ − 1).
For ease of exposition, we refer to the local parities as the
parity symbols that take part in local codes, while the parity
symbols that are not part of the Lc local codes are referred to
as global parity symbols. According to Definition 7, there exist
n − Lc (r + δ − 1) global parities and Lc (δ − 1) local parities.
We partition the coordinates
of these parities into L + 1 sets,

n
. For i ∈ NL+1 , we have
where L , r+δ−1


{(i − 1)nc + r + 1, . . . , inc } if i ∈ NLc ,
Pi = {(i − 1)nc + 1, . . . , inc }
if i ∈ NLc +1:L , (3)


{Lnc + 1, . . . , n}
if i = L + 1,

where nc , r + δ − 1 is the block length of each local
code. The sets Pi , i ∈ NLc , represent the coordinates of the
local parities of the i-th local code Ci . The remaining sets
Pi , i ∈ NLc +1:L+1 , represent the coordinates
of the global
SL+1
parities of C. As such, the set P = i=1 Pi represents the
parity coordinates of C.
C. UUV Codes
Consider an [n1 , k1 ] code U and an [n1 , k2 ] code V both
over GF(q). An [n = 2n1 , k = k1 + k2 ] (U | U + V) code
[24] (herein referred to as a UUV code) has codewords of the
form (u | u + v), where u ∈ U and v ∈ V. A UUV code has
generator matrix


GU
GU
UUV
G
=
,
0k2 ×n1 GV
where GU and GV are the generator matrices of U and V,
respectively. One can construct RM codes using UUV codes
in an iterative manner [24, p. 374].
III. S YSTEM M ODEL
We consider a DSS that stores f files X (1) , . . . , X (f ) ,
(m)
where each file X (m) = (xi,j ), m ∈ Nf , is a β × k matrix
αℓ
over GF(p ), with β, k, α, ℓ ∈ N, and p some prime number.
Each file is divided into β stripes (blocks) and encoded using a
(m)
(m)
(m)
linear code as follows. Let xi = (xi,1 , . . . , xi,k ), i ∈ Nβ ,
be a message vector corresponding to the i-th row of X (m) .
(m)
Each xi is encoded by an [n, k] code C over GF(q) with
α
q , p , having subpacketization
α, into a length-n codeword
(m)
(m) 
(m)
(m)
ci = ci,1 , . . . , ci,n , where ci,j ∈ GF(q ℓ ). For α = 1,
the code C is referred to as a scalar code. Otherwise, the code

5

(c)

(b)
(2)

c1,n
(2)

r1

rk+1

rk

c2,n
..
.

rn

(2)

Q(1)

Q(k)

Q(k+1)

···

Q(n)

cβ,n

···
..
.

..
.

n storage nodes
(a)

Fig. 1. System Model. (a) The colored boxes in each storage node represent
the f coded chunks pertaining to the f files. (b) Coded chunk corresponding
(2)
to the 2nd file in the n-th node. It consists of β code symbols, ci,n , i ∈ Nβ .
(j)
(c) The user sends the queries Q , j ∈ Nn , to the storage nodes and receives
responses rj .
(m)

is called a vector code [29]. The βf generated codewords ci
⊤
are then arranged in the array C = (C (1) )⊤ | . . . |(C (f ) )⊤
⊤
(m)
(m)
of dimension βf ×n, where C (m) = (c1 )⊤ | . . . |(cβ )⊤
for m ∈ Nf . For a given column j of C, we denote the vector
(m) 
(m)
c1,j , . . . , cβ,j as a coded chunk pertaining to file m. The f
coded chunks in column j are stored on the j-th storage node
as shown in Fig. 1(a), j ∈ Nn . In case the [n, k] code C is
systematic, the nodes that store the systematic code symbols
are referred to as systematic nodes.

(l)

The i-th subqueries qi , l ∈ Nn , of the n queries aim at
recovering Γ unique code symbols1 of the file X (m) . In
response to the received query matrix, node l sends the column
vector
(1)
(1)
(f ) ⊤
rl = (rl,1 , . . . , rl,d )⊤ = Q(l) c1,l , . . . , cβ,l , . . . , cβ,l , (4)

referred to as the response vector, back to the user as illustrated
in Fig. 1(c). We refer to rl,i as the i-th subresponse of the l-th
node. Perfect information-theoretic PIR for such a scheme is
defined in the following.
Definition 8: Consider a DSS with n nodes storing f files
in which a set of T nodes T ⊂ Nn , 1 ≤ |T | = T ≤ n − k,
act as spies and collude with each other. A user who wishes
to retrieve the m-th file sends the queries Q(l) , l ∈ Nn , to
the storage nodes, which return the responses rl . This scheme
achieves perfect information-theoretic PIR if and only if

(5a)
Privacy:
H m|Q(1) , . . . , Q(T ) = H(m);

(m)
Recovery:
H X |r1 , . . . , rn = 0.
(5b)

Queries satisfying (5a) ensure that the colluding nodes in
T are not able to determine which file is being downloaded
by the user. The recovery constraint in (5b) ensures that the
user is able to recover the requested file from the responses
sent by the DSS.
The efficiency of a PIR protocol is defined as the amount
of retrieved data per unit of total amount of downloaded
data, since it is assumed that the content of the retrieved file
dominates the total communication cost, i.e., ℓ is much larger
than f [12].
Definition 9: The PIR rate of a PIR protocol, denoted by R,
is the amount of information retrieved per downloaded symbol,
i.e.,
R,

A. Privacy Model
We consider a DSS where a set of T nodes may act as spies.
Further, they might collude and hence they are referred to as
colluding nodes. In addition, it is assumed that the remaining
nonspy nodes do not collaborate with the spy nodes. The
scenario of T = 1 spy nodes in the DSS is analogous to having
a system with no colluding nodes. Let T ⊂ Nn , |T | = T ,
denote the set of spy nodes in the DSS. The role of the spy
nodes is to determine which file m is accessed by the user. We
assume that the user does not know T , since otherwise it can
trivially achieve PIR by avoiding contacting the spy nodes. To
retrieve the file X (m) from the DSS, the user sends a d × βf
matrix query Q(l) over GF(q) ⊆ GF(q ℓ ) to the l-th node for
all l ∈ Nn . The query matrices are represented in the form of
(l)
d subquery vectors qi of length βf as

Q(l)

  (l)
(l)
q1,1
q1
 (l)   (l)
q2  q2,1
 
=
 ..  =  ..
 .   .
(l)
(l)
qd
qd,1


(l)

q1,2
(l)
q2,2
..
.
(l)
qd,2

···
···
···
···

(l) 
q1,βf
(l) 
q2,βf 

..  .
. 
(l)
qd,βf

βk
.
nd

Since the size of each file is βk, the parameters d and Γ
should be chosen such that βk = Γd. As such, for the (fileindependent) Protocols 2 and 3 in Sections V and VII we have
β=

LCM(k, Γ)
k

and d =

LCM(k, Γ)
.
Γ

(6)

In general, βk = Γd may be any multiple of Γ, but in order to
have practical schemes, we choose the lowest possible value.
This is not the case for Protocol 1 in Section IV, where β
is exponential in the number of files in order achieve optimal
PIR rates. By choosing the values above for β and d, the PIR
rate for Protocols 2 and 3 become
R=

Γ
.
n

We will write R(C) to highlight that the PIR rate depends
on the underlying storage code C. In general, the maximum
achievable PIR rate is the PIR capacity. It was shown in [11]
that for the noncolluding case and for a given number of files
1 In general, the i-th subqueries recover Γ unique code symbols such that
i
P
among the i Γi recovered code symbols there are βk distinct information
symbols. However, for the sake of simplicity, we assume Γi = Γ for all i.

6

f stored using an [n, k] code, the PIR capacity, denoted as
Cf , is equal to

 k f −1
n−k
Cf ,
.
(7)
1−
n
n

Throughout the paper we refer to the capacity in (7) as the
finite PIR capacity as it depends on the number of files.2 On
the contrary when the number of files f → ∞, the asymptotic
PIR capacity is

n−k
.
(8)
n
It was shown in [8, Th. 3] that the PIR rate for a DSS with
noncolluding nodes is upperbounded by C∞ for a special class
of linear retrieval schemes. In the case of colluding nodes,
an explicit upper bound is currently unknown, as well as an
expression for the PIR capacity. Some initial work for the case
of two colluding nodes has recently been presented in [30].
C∞ ,

IV. F INITE C APACITY-ACHIEVING PIR P ROTOCOL
THE N ONCOLLUDING C ASE

FOR

In this section, we propose a capacity-achieving protocol,
named Protocol 1, that achieves the finite PIR capacity (7) for
the scenario of noncolluding nodes. The protocol is inspired
by the protocol introduced in [11].
A. PIR Achievable Rate Matrix
In [10], the concept of exploiting side information for
PIR problems was introduced. By side information we mean
additional redundant symbols not related to the requested file
in order to maintain privacy and downloaded by the user. These
symbols will be exploited by the user to retrieve the requested
file from the responses of the storage nodes. In [11, Sec. 5.1],
it was shown that a [5, 3, 3] MDS storage code can be used to
achieve the finite PIR capacity, where the side information is
decoded by utilizing other code coordinates forming an information set in the code array. For instance, the authors chose
the n = 5 information sets I1 = {1, 2, 3}, I2 = {1, 4, 5},
I3 = {2, 3, 4}, I4 = {1, 2, 5}, and I5 = {3, 4, 5} of the
[5, 3, 3] MDS code in their PIR achievable scheme. Observe
that in {Ii }i∈N5 each coordinate of the [5, 3, 3] code appears
exactly k = 3 times. This motivates the following definition.
Definition 10: Let C be an arbitrary [n, k] code. A ν × n
binary matrix Λκ,ν (C) is said to be a PIR achievable rate
matrix for C if the following conditions are satisfied.
1) The Hamming weight of each column of Λκ,ν is κ, and
2) For each matrix row λi , i ∈ Nν , χ(λi ) always contains
an information set.
In other words, each coordinate j of C, j ∈ Nn , appears
exactly κ times in {χ(λi )}i∈Nν , and every set χ(λi ) contains
an information set.
Lemma 2: If a matrix Λν,κ (C) exists for an [n, k] code, then
we have
k
κ
≥ ,
ν
n
2 In [11] and [30] C is referred to as the capacity of MDS-PIR for the
f
noncolluding case where the data is stored using an MDS storage code.

where equality holds if χ(λi ), i ∈ Nν , are all information sets.
Proof: Since by definition each row λi of Λν,κ always
contains an information set, we have wH (λi ) ≥ k, i ∈ Nν .
Let vj , j ∈ Nn , be the j-th column of Λκ,ν . If we look at
Λκ,ν from both a row-wise and a column-wise point of view,
we obtain
n
ν
X
X
wH (vj ) = κn,
wH (λi ) =
νk ≤
j=1

i=1

from which the result follows. Clearly, equality holds if χ(λi ),
i ∈ Nν , are all information sets.
Example 2: Let us consider a [5, 3, 2] systematic code whose
generator matrix is given by


1 0 0 1 0
G = 0 1 0 1 0 .
0 0 1 0 1
One can easily verify that

Λ2,3

0 1
= 1 0
1 1

1 1
0 1
1 0


1
1
0

is a PIR achievable rate matrix for this code.
Before we state our main results, in order to clearly illustrate
our example and the following achievability proof, we first
introduce two PIR interference matrices.
Definition 11: For a given ν × n PIR achievable rate matrix
Λκ,ν (C) = (λu,j ), we define the PIR interference matrices
Aκ×n = (ai,j ) and B(ν−κ)×n = (bi,j ) with
ai,j , u if λu,j = 1, ∀ j ∈ Nn , i ∈ Nκ , u ∈ Nν ,
bi,j , u if λu,j = 0, ∀ j ∈ Nn , i ∈ Nν−κ , u ∈ Nν .
For j ∈ Nn , let Aj , {ai,j : i ∈ Nκ } and Bj , {bi,j : i ∈
Nν−κ }. It can be observed that Bj = Nν \ Aj , ∀ j ∈ Nn .
Definition 12: By S(a|Aκ×n ) we denote the set of column
coordinates of a matrix Aκ×n = (ai,j ) such that at least one
of its entries is equal to a, i.e.,
S(a|Aκ×n ) , {j ∈ Nn : ∃ ai,j = a, i ∈ Nκ }.
The following claim can be directly verified.
Claim 1: S(a|Aκ×n ) contains an information set ∀ a ∈
Nν . Moreover, for an arbitrary entry bi,j of B(ν−κ)×n ,
S(bi,j |Aκ×n ) ⊆ Nn \ {j} and it must contain an information
set.
We illustrate the previous points in the following example.
Example 3: Continuing with Example 2 and following
Definition 11, we obtain



2 1 1 1 1
A2×5 =
and B1×5 = 1 2 2 3 3
3 3 3 2 2

for Λ2,3 . One can see that Aj ∪Bj = N3 , ∀ j ∈ N5 . Moreover,
for instance, take a = 1, then S(1|A2×5 ) = {2, 3, 4, 5}
contains an information set of the [5, 3, 2] systematic code of
Example 2.
Now consider the two matrices

 (m)
(m)
(m)
ca1,1 ,1 ca1,2 ,2 · · · ca1,n ,n

 .
 and
 .

 .
(m)
(m)
(m)
caκ,1 ,1 caκ,2 ,2 · · · caκ,n ,n

7



(m)

(m)

cb ,1
 1,1
..

.

(m)
cbν−κ,1 ,1

cb1,2 ,2

···

(m)

···

cbν−κ,2 ,2

(m)

cb1,n ,n
(m)

cbν−κ,n ,n






of code symbols of the m-th file. Observe that if the user
knows the first matrix of code symbols, from Claim 1, since
the coordinate set S(bi,j |Aκ×n ) ⊆ Nn \ {j} contains an
information set and the user knows the structure of the storage
(m)
code C, the code symbols cbi,j ,j of the second matrix can be
obtained. Here, the entries of A and B are respectively marked
in red and blue. We are now ready to state Protocol 1.

file from the desired symbols. For the desired symbols, we will
distinguish between round ℓ = 1 and round ℓ ∈ N2:f .
Undesired symbols. The undesired symbols refer to sums
of code symbols which do not contain symbols from the
requested file. For every round ℓ, where ℓ ∈ Nf −1 , the user
downloads the code symbols
(
X (m′ )
y((i−1)U(f −1)+U(ℓ−1))·ν+a1,j ,j ,
m′ ∈M

X

...,

(m′ )

y((i−1)U(f −1)+U(ℓ−1))·ν+aκ,j ,j ,

m′ ∈M

X

...,

B. PIR Protocol 1

(m′ )

y((i−1)U(f −1)+U(ℓ)−1)·ν+a1,j ,j ,

m′ ∈M

The proposed PIR Protocol 1 generalizes the MDS-coded
PIR protocol in [11] to DSSs where the files are stored
using an arbitrary linear code. Inspired by [10] and [11], a
PIR capacity-achievable scheme should follow three important
principles: 1) enforcing symmetry across storage nodes, 2)
enforcing file symmetry within each storage node, and 3)
exploiting side information of undesired symbols to retrieve
new desired symbols. Note that principle 1) is in general not
a necessary requirement for a feasible PIR protocol. However,
as pointed out in [11] and [30], any PIR scheme can be made
symmetric, hence we keep this principle for the purpose of
simplifying the implementation.
The PIR achievable rate matrix Λκ,ν for the given storage
code C plays an important role in the proposed PIR protocol. Moreover, the protocol requires β = ν f stripes and
exploits the corresponding PIR interference matrices Aκ×n
and B(ν−κ)×n . Note that the number of stripes depends on
the number of files f , hence Protocol 1 depends on f as well.
We first outline the steps of the protocol, and then we will
prove that the proposed protocol satisfies the perfect privacy
condition of (5a) and results in the PIR rate of Theorem 1
below. Without loss of generality, we assume that the user
wants to download the first file, i.e., m = 1. The algorithm is
composed of four steps as described below.
Step 1. Index Preparation: For all files, the user interleaves
the indices of the rows of C (m) randomly and independently
of each other, and it generates the interleaved code array
⊤
(m)
(m)
Y (m) = (y1 )⊤ | . . . |(yβ )⊤ , ∀ m ∈ Nf , with rows
(m)

yi

(m)

= cπ(i) ,

i ∈ Nβ ,

where π(·) : Nβ → Nβ is a random permutation, which is
privately known to the user only. Therefore, when the user
requests code symbols from each storage node, this procedure
is designed to make the requested row indices to be random
and independent of the requested file index.
Step 2. Download Symbols in the i-th Repetition: The user
downloads the needed symbols in κ repetitions. In the i-th
repetition, i ∈ Nκ , the user downloads the required symbols
in a total of f rounds. Using the terminology in [11], there
are two types of symbols the user downloads, desired symbols,
which are directly related to the requested file index m = 1,
and undesired symbols, which are not related to the requested
file index m = 1, but will be exploited to decode the requested

...,

X

(m′ )
y((i−1)U(f −1)+U(ℓ)−1)·ν+aκ,j ,j

m′ ∈M

)

(9)

for all possible subsets M ⊆ N2:f with |M| = ℓ, where U(ℓ)
is given by
U(ℓ) ,

ℓ
X

κf −(h+1) (ν − κ)h−1 .

h=1

Desired symbols in the first round. In contrast to undesired
symbols, desired symbols are sums of code symbols which
contain symbols of the requested file. The main idea of the
protocol is that the user downloads the desired symbols,
which are linear sums of the requested symbols and undesired
symbols from the previous round. In the first round the user
has downloaded κ · U(1) = κκf −(1+1) (ν − κ)1−1 = κf −1 undesired symbols. However, these symbols cannot be exploited.
Hence, due to symmetry, in round ℓ = 1, the user downloads
the κf −1 desired symbols
n
o
(1)
(1)
yκf −1 (ai,j −1)+1,j , . . . , yκf −1 (ai,j −1)+κf −1 ,j
(10)

from the j-th storage node, j ∈ Nn , i.e., the user also
downloads κf −1 symbols for m = 1 from each storage node.

Desired symbols in higher rounds. In the (ℓ + 1)-th round,
ℓ ∈ Nf −1 , in order to exploit the side information, i.e., the
undesired symbols in the previous round, the user downloads
the symbols
(
(1)

yD(ℓ−1)·ν+ai,j ,j
X

+

(m′ )

y((i−1)U(f −1)+U(ℓ−1))·ν+b1,j ,j ,

m′ ∈M1
(1)

. . . , y(D(ℓ−1)+(ν−κ)−1)·ν+ai,j ,j
X (m′ )
+
y((i−1)U(f −1)+U(ℓ−1))·ν+bν−κ,j ,j ,
m′ ∈M1

(1)
, y(D(ℓ−1)+(ν−κ))·ν+ai,j ,j

X

+

(m′ )

y((i−1)U(f −1)+U(ℓ−1)+1)·ν+b1,j ,j ,

m′ ∈M1
(1)

. . . , y



D(ℓ−1)+(U(ℓ)−U(ℓ−1))(ν−κ)−1 ·ν+ai,j ,j

8

X

(m′ )

y((i−1)U(f −1)+U(ℓ)−1)·ν+bν−κ,j ,j ,

individual file m ∈ Nf among all the linear sums are the
same for each storage node.

. . . , y(D(ℓ)−(ν−κ))·ν+ai,j ,j
X
(m′ )
+
y((i−1)U(f −1)+U(ℓ)−1)·ν+b1,j ,j ,

Step 3. Complete κ Repetitions: The user repeats Step 2)
until i = κ. We will show that by our designed parameters
of U(ℓ) and D(ℓ), the user has indeed downloaded in total
β = ν f stripes for the requested file (see again Appendix B).

+

m′ ∈M1
(1)

m′ ∈MN(ℓ)
(1)

. . . , y(D(ℓ)−1)·ν+ai,j ,j
X

+

(m′ )

y((i−1)U(f −1)+U(ℓ)−1)·ν+bν−κ,j ,j

m′ ∈MN(ℓ)

)

(11)

for all distinct ℓ-sized subsets M1 , . . . , MN(ℓ) ⊆ N2:f , where
N(ℓ) , f −1
and D(ℓ) is given by
ℓ

ℓ 
X
f − 1 f −(h+1)
f −1
D(ℓ) , κ
+
κ
(ν − κ)h .
h
h=1

This indicates that for each combination
of files M

 l, l ∈
NN(ℓ) , the user has downloaded U(ℓ)−1−U(ℓ−1)+1 (ν−κ)
new desired symbols, and since there are in total N(ℓ) combinations of files, in each round D(ℓ) − 1 − D(ℓ − 1) + 1 extra
desired symbols are downloaded.
Exploiting the side information. Using the fact that for a
linear code C any linear combination of codewords is also
a codeword, and together with Claim 1, it is not too hard to
see that by fixing an arbitrary coordinate j ∈ Nn , there always
exist some coordinates S ⊂ Nn \ {j} such that for a subset
M ⊆ N2:f with |M| = ℓ, the so-called aligned sum
(
X (m′ )
y((i−1)U(f −1)+U(ℓ−1))·ν+b1,j ,j ,
m′ ∈M

...,

X

m′ ∈M

(m′ )
y((i−1)U(f −1)+U(ℓ)−1)·ν+bν−κ,j ,j

)

for ℓ ∈ Nf −1 and i ∈ Nκ , can be decoded. Consequently, in
the (ℓ + 1)-th round, at each storage node we can collect the
code symbols related to m = 1 from the desired symbols, i.e.,
n
o
(1)
(1)
yD(ℓ−1)·ν+ai,j ,j , . . . , y(D(ℓ)−1)·ν+ai,j ,j
(12)
is obtained.

Symmetry across storage nodes. In the previous steps,
since the user downloads the same amount of required symbols
for each j ∈ Nn and for every round, symmetry across storage
nodes is ensured.
File symmetry within each storage node. To ensure that
the privacy condition of (5a) is fulfilled, we have to make
sure that in each round ℓ ∈ Nf of each repetition, for each
storage node and for every combination of files M ⊆ Nf
with |M| = ℓ, the user requests the same number of linear
P
(m)
sums η(M) ,
m∈M yηm ,j , where ηm depends on m.
This will be shown to be inherent from the protocol (see
proof of Theorem 1 in Appendix B). In addition, since the
user always requests the same number of linear sums for
every combination of files, the scheme also implies that the
frequencies of requested code symbols pertaining to each

Step 4. Shuffling the Order of Queries Within Each Node:
The order of the queries within each storage node is uniformly
shuffled to prevent the storage node to be able to identify
which file is requested from the index of the first downloaded
symbol.
C. Achievable PIR Rate
The PIR rate, R(C), of Protocol 1 in Section IV-B for a DSS
where f files are stored using an arbitrary [n, k] linear code
C is given in the following theorem.
Theorem 1: Consider a DSS that uses an [n, k] code C to
store f files and Protocol 1 in Section IV-B. Then, the PIR
rate

 κ f −1
(ν − κ)k
R(C) =
1−
(13)
κn
ν
is achievable if a PIR achievable rate matrix Λκ,ν (C) exists.
Proof: See Appendix B.
We remark that from Lemma 2, (13) is smaller than or equal
to the finite PIR capacity (7) since
h
i
νk
κ

κ
 κ f −1 −1
κn 1 − ν
νk
i
R(C) = h
=
1
+
+
·
·
·
+
f
κn
ν
ν
1− κ
ν



≤ 1+

k
n

+ ··· +

 k f −1 −1
n

,

(14)

and it becomes the finite PIR capacity expression in (7) if
there exists a Λκ,ν for C such that κν = nk . The inequality in
(14) follows from Lemma 2. This gives rise to the following
definition.
Definition 13: If there exists a PIR achievable rate matrix
Λκ,ν such that κν = nk for an [n, k] code C, then this code
achieves the finite PIR capacity (7) and is referred to as a PIR
capacity-achieving code. Accordingly, the PIR achievable rate
matrix Λκ,ν is called a PIR capacity-achieving matrix.
Note that the largest achievable PIR rate in the noncolluding
case where the data is stored using an arbitrary linear code
is still unknown. Interestingly, it is observed from Lemma 2
and (14) that the largest possible achievable PIR rate for an
arbitrary linear code with Protocol 1 strongly depends on the
smallest possible value of κν for which a PIR achievable rate
matrix Λκ,ν (C) exists.
Since the existence of a PIR achievable rate matrix is
connected to the information sets of a code, we review a
widely known result in coding theory.
Proposition 2 ([31, Th. 1.4.15]): Let C be an [n, k, dmin ]
code. Then, every set of n− dmin + 1 coordinates of C contains
an information set. Furthermore, n − dmin + 1 is the smallest
number of coordinates with this property.

9

Lemma 3: For a given [n, k, dmin ] code C, there always exists
a PIR achievable rate matrix Λk,ν such that
ν = k + min (k, dmin − 1) .
Proof: The proof is given in Appendix C.
Note that when we say that a code is PIR capacityachieving, it does not necessarily require (ν, κ) = (n, k) for
a PIR capacity-achieving matrix Λκ,ν . Moreover, Lemma 3
and (14) actually tell us that Definition 10 is well-defined for
any [n, k] code. General upper and lower bounds on R(C) are
given as follows.
Corollary 1: For any DSS that uses an [n, k, dmin ] storage
code C and Protocol 1 in Section IV-B, the PIR achievable
rate R(C) is upperbounded and lowerbounded by

 k f −1
n−k
1−
and
R(C) ≤
n
n


f −1
min (k, dmin − 1)
k
R(C) ≥
1−
,
n
k + min (k, dmin − 1)
respectively.
We remark that because every set of k coordinates of an
[n, k] MDS code is an information set, we can construct n
information sets by cyclically shifting an arbitrary information
set n times, hence a PIR capacity-achieving matrix Λk,n of
an MDS code can easily be constructed. In other words, the
protocol with MDS codes is PIR capacity-achieving and MDS
codes are a class of PIR capacity-achieving codes.
In Section VI, we will give a necessary and a sufficient
condition for a code to be PIR capacity-achieving under
Protocol 1 and give certain families of PIR capacity-achieving
codes. For illustration purposes, in the next subsection, we
give an example of a PIR capacity-achieving code.
D. A [5, 3] PIR Capacity-Achieving Code for f = 2
In this subsection, we compute the PIR achievable rate of
a [5, 3] non-MDS code for a DSS that stores two files, f = 2,
and show that it is PIR capacity-achieving.
Let C be a non-MDS binary [5, 3, 2] code with generator
matrix


1 0 0 1 0
G = 0 1 0 1 1  .
(15)
0 0 1 0 1

One can see that the ν × n = 5 × 5 matrix


1 1 1 0 0
1 0 0 1 1



Λ3,5 (C) = 
0 1 0 1 1
0 1 1 1 0
1 0 1 0 1

is a PIR achievable rate matrix. From Λ3,5 (C), we obtain the
following sets:
χ(λ1 ) = {1, 2, 3}, χ(λ2) = {1, 4, 5}, χ(λ3) = {2, 4, 5},
χ(λ4 ) = {2, 3, 4}, χ(λ5) = {1, 3, 5}.

All of these sets contain an information set of C (see Definition 10). Furthermore, we get the following PIR interference
matrices


1 1 1 2 2
A3×5 = 2 3 4 3 3,
5 4 5 4 5


3 2 2 1 1
B2×5 =
.
4 5 3 5 4
One can see that Claim 1 holds. For example, S(3|A3×5 ) =
{2, 4, 5} contains an information set for C.
In the next step, for each m ∈ N2 and for β = ν f = 52 , we
first generate the interleaved code array Y (m) with row vectors
(m)
(m)
= cπ(i) , i ∈ N52 , by a randomly selected permutation
yi
function π(·). We list all downloaded sums of code symbols in
Table I, which is similar to [11, Table 2]. Similar to the PIR
protocol in [11], Protocol 1 requires f = 2 rounds in each
repetition, and the scheme needs to be repeated κ = 3 times.
Note that since the protocol requests an equal amount of code
symbols associated with X (1) and X (2) , it is straightforward
to see that the privacy constraint is satisfied.
It should be mentioned that here we strongly make use
of the PIR interference matrices. For example, in round
2 of repetition 1 (see Table I), since the user knows
(2)
(2)
(2)
C, the code symbols y5·0+3,1 , y5·0+2,2 , and y5·0+2,3 can
(2)
(2)
(2)
be obtained by knowing {y5·0+3,2 , y5·0+3,4 , y5·0+3,5 } and
(2)
(2)
(2)
{y5·0+2,1 , y5·0+2,4 , y5·0+2,5 }, from which the corresponding
(1)
(1)
(1)
coded symbols {y3·5+1,1 , y3·5+1,2 , y3·5+1,3 } can be obtained
by cancelling the side information cancellation. Since {1, 2, 3}
is an information set, the corresponding requested file vector
of length k can also be decoded. Hence, in summary, it
is sufficient to reliably decode 52 = 25 different length-k
requested file vectors for m = 1. In summary, for f = 2,
the user downloads 3 × 5 undesired symbols based on (9) and
(3 + 2) × 5 = 25 desired symbols according to (10) and (11)
in each repetition. Hence, the PIR achievable rate is equal to
R=

1 − 53
3 · 25
5
= =
2 ,
3 · (25 + 15)
8
1 − 35

which corresponds to the PIR capacity in (7), i.e., the [5, 3, 2]
non-MDS code given by (15) is PIR capacity-achieving.
V. A SYMPTOTIC C APACITY-ACHIEVING P ROTOCOL
THE N ONCOLLUDING C ASE

FOR

In this section, we present Protocol 2, a file-independent
PIR protocol that achieves the asymptotic capacity (8) for the
case of noncolluding nodes. We assume that the DSS uses an
[n, k] code over GF(q) of rate RC and subpacketization α.
For such a code C, the user designs the l-th, l ∈ Nn , query as
Q(l) = U + V (l) ,

(16)

where U = (ui,j ) is a d × βf matrix whose elements ui,j are
chosen independently
and uniformly at random from GF(q),
(l) 
and V (l) = vi,j is a d× βf deterministic binary matrix over
(l)
GF(q), where vi,j = 1 means that the j-th symbol in node l
is accessed by the i-th subquery of Q(l) .

10

round 1
round 1
round 1
rnd. 2

repetition 3

rnd. 2

repetition 2

rnd. 2

repetition 1

TABLE I
P ROTOCOL 1 WITH A [5, 3, 2] NON -MDS CODE FOR f = 2.
Server 1

Server 2

Server 3

Server 4

Server 5

(1)
y3(1−1)+1,1
(1)
y3(1−1)+2,1
(1)
y3(1−1)+3,1
(2)
y5·0+1,1
(2)
y5·0+2,1
(2)
y5·0+5,1
(1)
(2)
y3·5+1,1 + y5·0+3,1
(2)
(1)
y4·5+1,1 + y5·0+4,1
(1)
y3(2−1)+1,1
(1)
y3(2−1)+2,1
(1)
y3(2−1)+3,1
(2)
y5·1+1,1
(2)
y5·1+2,1
(2)
y5·1+5,1
(1)
(2)
y3·5+2,1 + y5+3,1
(1)
(2)
y4·5+2,1 + y5+4,1
(1)
y3(5−1)+1,1
(1)
y3(5−1)+2,1
(1)
y3(5−1)+3,1
(2)
y5·2+1,1
(2)
y5·2+2,1
(2)
y5·2+5,1
(1)
(2)
y3·5+5,1 + y5·2+3,1
(1)
(2)
y4·5+5,1 + y5·2+4,1

(1)
y3(1−1)+1,2
(1)
y3(1−1)+2,2
(1)
y3(1−1)+3,2
(2)
y5·0+1,2
(2)
y5·0+3,2
(2)
y5·0+4,2
(1)
(2)
y3·5+1,2 + y5·0+2,2
(2)
(1)
y4·5+1,2 + y5·0+5,2
(1)
y3(3−1)+1,2
(1)
y3(3−1)+2,2
(1)
y3(3−1)+3,2
(2)
y5·1+1,2
(2)
y5·1+3,2
(2)
y5·1+4,2
(1)
(2)
y3·5+3,2 + y5+2,2
(1)
(2)
y4·5+3,2 + y5+5,2
(1)
y3(4−1)+1,2
(1)
y3(4−1)+2,2
(1)
y3(4−1)+3,2
(2)
y5·2+1,2
(2)
y5·2+3,2
(2)
y5·2+4,2
(1)
(2)
y3·5+4,2 + y5·2+2,2
(1)
(2)
y4·5+4,2 + y5·2+5,2

(1)
y3(1−1)+1,3
(1)
y3(1−1)+2,3
(1)
y3(1−1)+3,3
(2)
y5·0+1,3
(2)
y5·0+4,3
(2)
y5·0+5,3
(1)
(2)
y3·5+1,3 + y5·0+2,3
(2)
(1)
y4·5+1,3 + y5·0+3,3
(1)
y3(4−1)+1,3
(1)
y3(4−1)+2,3
(1)
y3(4−1)+3,3
(2)
y5·1+1,3
(2)
y5·1+4,3
(2)
y5·1+5,3
(1)
(2)
y3·5+4,3 + y5+2,3
(1)
(2)
y4·5+4,1 + y5+3,3
(1)
y3(5−1)+1,3
(1)
y3(5−1)+2,3
(1)
y3(5−1)+3,3
(2)
y5·2+1,3
(2)
y5·2+4,3
(2)
y5·2+5,3
(1)
(2)
y3·5+5,3 + y5·2+2,3
(1)
(2)
y4·5+5,3 + y5·2+3,3

(1)
y3(2−1)+1,4
(1)
y3(2−1)+2,4
(1)
y3(2−1)+3,4
(2)
y5·0+2,4
(2)
y5·0+3,4
(2)
y5·0+4,4
(1)
(2)
y3·5+2,4 + y5·0+1,4
(2)
(1)
y4·5+2,4 + y5·0+5,4
(1)
y3(3−1)+1,4
(1)
y3(3−1)+2,4
(1)
y3(3−1)+3,4
(2)
y5·1+2,4
(2)
y5·1+3,4
(2)
y5·1+4,4
(1)
(2)
y3·5+3,1 + y5+1,4
(1)
(2)
y4·5+3,1 + y5+5,4
(1)
y3(4−1)+1,4
(1)
y3(4−1)+2,4
(1)
y3(4−1)+3,4
(2)
y5·2+2,4
(2)
y5·2+3,4
(2)
y5·2+4,4
(1)
(2)
y3·5+4,1 + y5·2+1,4
(1)
(2)
y4·5+4,4 + y5·2+5,4

(1)
y3(2−1)+1,5
(1)
y3(2−1)+2,5
(1)
y3(2−1)+3,5
(2)
y5·0+2,5
(2)
y5·0+3,5
(2)
y5·0+5,5
(1)
(2)
y3·5+2,5 + y5·0+1,5
(2)
(1)
y4·5+2,5 + y5·0+4,5
(1)
y3(3−1)+1,5
(1)
y3(3−1)+2,5
(1)
y3(3−1)+3,5
(2)
y5·1+2,5
(2)
y5·1+3,5
(2)
y5·1+5,5
(1)
(2)
y3·5+3,5 + y5+1,5
(1)
(2)
y4·5+3,5 + y5+4,5
(1)
y3(5−1)+1,5
(1)
y3(5−1)+2,5
(1)
y3(5−1)+3,5
(2)
y5·2+2,5
(2)
y5·2+3,5
(2)
y5·2+5,5
(1)
(2)
y3·5+5,5 + y5·2+1,5
(1)
(2)
y4·5+5,5 + y5·2+4,5

In order to construct V (l) , we define a d × n binary matrix
Ê = (êi,j ), where êi,j = 1 implies that the i-th subquery
of the j-th query wants to access a code symbol stored in
the j-th node. Additionally, Ê is a matrix having strictly Γd
nonzero entries. The meaning of Ê will become clear in the
following. Also, let I1 , . . . , Iβ be β information sets for C and
define Fj , {i ∈ Nβ : j ∈ Ii } to be the set of indices of the
information sets I1 , . . . , Iβ containing the j-th coordinate.
We consider now the construction of V (l) . For l ∈ Nn , V (l)
has the form

V (l) = 0d×(m−1)β | ∆l | 0d×(f −m)β ,
where ∆l is the d × β binary matrix

⊤
⊤
⊤
⊤
∆l = ω (l) | ω (l) | . . . | ω (l)
,
j1

j2

jd

(17)

with ωi , i ∈ Nβ , being the i-th β-dimensional unit vector, i.e.,
a length-β weight-1 binary vector with a single 1 at the i-th
position and ω0 = 01×β . Also, given a chosen d × n matrix
Ê,
(
(l)
if êi,l = 1,
si
(l)
ji =
(18)
0
otherwise,
(l)

(l)

(l)

where si ∈ Fl and si 6= si′ for i 6= i′ , i, i′ ∈ Nd . This
completes the construction of the protocol.

After describing the construction of the queries, we derive
the following conditions that Ê has to satisfy.
C1. The user should be able to recover Γ unique code symbols
(l)
of the requested file X (m) from the i-th subqueries qi
that are sent to the n nodes. This is to say that each row
of Ê should have exactly Γ ones.
C2. Let tj , j ∈ Nn , denote the j-th column vector of Ê.
The protocol should be able to recover wH (tj ) unique
code symbols from the j-th node, which means that
it is required that wH (tj ) = |Fj |. We call the set
{wH (tj )}j∈Nn the column weight profile of Ê.
C3. The user should be able to recover all Γd code symbols
of the requested file X (m) . This means that each row
êi = (êi,1 , . . . , êi,n ) of Ê, i ∈ Nd , should be correctable
by a maximum likelihood (ML) decoder for the code C
on the binary erasure channel (BEC). In other words, the
rows of Ê can be considered as length-n ML-correctable
erasure patterns, or equivalently, the support χ 1 − êi
should contain an information set.
We remark that for a code C, Ê and {Ii }i∈Nβ need
not be unique. Furthermore, each set Ii , i ∈ Nβ , can
alternatively be represented as a correctable erasure pattern
ēi = (ēi,1 , . . . , ēi,n ), where ēi,j , 0, ∀ j ∈ Ii . Also, the
information sets {Ii }i∈Nβ can alternatively be defined by a

11

matrix Ē of size β × n as




ē1
 .. 
Ē =  .  .
ēβ

The two matrices Ê and Ē can be stacked into the matrix
E = (ei,j ) as
 
Ê
E=
.
(19)
Ē
To meet the conditions above, the only requirement is that for
each j ∈ Nn , wH (tj ) = β − wH (wj ), where tj and wj are
columns of Ê and Ē, respectively. This is equivalent to finding
a (β + d) × n matrix E with regular column weight β, and
such that each row is a correctable erasure pattern. Hence,
we conclude that the requirements for E are equivalent to
determine a PIR achievable rate matrix
Λd,β+d(C) = 1(β+d)×n − E(β+d)×n .

(20)

{Ii }i∈Nβ . In the following corollary, we provide a valid set of
values.
Corollary 2: Let C be an [n, k, dmin ] code. For Γ =
min (k, dmin − 1), it holds that

(21)
H X (m) |r1 , . . . , rn = 0,

and the PIR rate is R(C) ≥ Γn .
Proof: Let d = k and β = Γ. Then, (21) follows directly
from Theorem 2, since we have shown in Lemma 3 that the
required matrix Λk,k+Γ (C) exists for C, and the existence of
E(k+Γ)×n follows from (20).
For systematic codes with rate RC > 1/2, a better lower
bound on the PIR rate compared to that of Corollary 2 can be
given as follows.
Corollary 3: Let C be an [n, k] systematic code with RC >
1/2 and H C = (P | In−k ). Consider the [n = k, k ′ ] code
′
′
C ′ with parity-check matrix H C = P . For Γ = dCmin − 1, it
holds that

(22)
H X (m) |r1 , . . . , rn = 0,
′

Remark 1: If there exists a valid E such that Γ = n − k,
d
= nk , and it ensures that the above protocol achieves
then β+d
the asymptotic PIR capacity in (8). Correspondingly, the PIR
achievable rate matrix Λd,β+d (C) is a PIR capacity-achieving
d
= nk .
matrix as β+d
In the following lemma, we prove that our construction of
the queries ensures that the privacy condition (5a) is satisfied.
Lemma 4: Consider a DSS that uses an [n, k] code with
subpacketization α to store f files, each divided into β stripes.
Then, the queries Q(l) , l ∈ Nn , designed as in (16) satisfy
H m|Q(l) = H(m), where l ∈ Nn represents the spy node.
Proof: The queries Q(l) , l ∈ Nn , are a sum of a random
matrix U and a deterministic matrix V (l) . The resulting
queries have elements that are independently and uniformly
distributed at random from GF(q). Hence, any Q(l) obtained
by the spy node is statistically independent of m. This ensures
that H m|Q(l) = H(m).
In order to show that Protocol 2 achieves perfect
information-theoretic PIR, it remains to be proved that from
the responses rl in (4) sent by the nodes back to the user, one
can recover the requested file, i.e., that the constructed PIR
protocol satisfies the recovery condition in (5b).
Theorem 2: Consider a DSS that uses an [n, k] code with
subpacketization α to store f files, each divided into β stripes.
In order to retrieve the file X (m) , m ∈ Nf , from the DSS, the
user sends the queries Q(l) , l ∈ Nn , in (16) to the n storage
nodes. Then, for the responses rl in (4) received by the user,
H X (m) |r1 , . . . , rn = 0.
Proof: See Appendix D.
Theorem 2 generalizes [12, Th. 1] to any linear code. We
remark that for the theorem to hold there is an implicit assumption that the three conditions for the matrix Ê mentioned above
are all satisfied (Ê is used in the construction of the queries
Q(l) ). Thus, parameters Γ, β, and d (which are not explicitly
mentioned in the theorem) have to be carefully selected such
that a Γ-row regular matrix Ê (satisfying condition C3)
actually exists with a valid collection of information sets

dC −1

and the PIR rate is R(C) ≥ Γn = minn .
Proof: As for the proof of Corollary 2, let d = k and
β = Γ. Then, (22) follows directly from Theorem 2. Select k
′
erasure patterns e′i , i ∈ Nk , of length k and wH (e′i ) = dCmin −1.
The patterns are all ML-correctable by the code C ′ . Thus, the
erasure patterns
ei = (e′i , 0, · · · , 0)
| {z }
n−k

are also correctable by C. Choosing the information sets Ii =
Nk , i ∈ NΓ , the required Γ-regular matrix E(β+d)×n can then
be constructed from {ei }i∈Nk and {Ii }i∈NΓ .
Observe that RC > 12 implies k > dCmin − 1. In [22], under
the assumption that k > dCmin − 1, a PIR protocol achieving a
′
dC −1
PIR rate of minn was given. Note that dCmin ≤ dCmin , and thus
C
d −1
R ≥ minn for our construction.
Below we give two examples to elucidate Protocol 2.
Example 4 illustrates the PIR protocol when the underlying
code has rate R > 1/2, with parameters d = k and β = Γ. On
the other hand, Example 5 uses an underlying code that has
rate R < 1/2, again with parameters d = k and β = Γ.
Example 4: Consider a DSS that uses the [5, 3, 2] scalar
(α = 1) binary code C in Section IV-D (with generator matrix
given in (15)) to store a single file by dividing it into β stripes.
Its parity-check matrix is given by


1 1 0 1 0
C
H = (P |In−k ) =
.
0 1 1 0 1
To determine the value of parameter β, we compute the
′
minimum distance dCmin of the [n′ = 3, k ′ = 1] code C ′ with
′
′
parity-check matrix H C = P . From H C it follows that
′
dCmin = 3. Hence, from Corollary 3, β = 2. Let the file to
be stored be denoted by the 2 × 3 matrix X = (xi,j ), where
the message symbols xi,j ∈ GF(2ℓ ) for ℓ ∈ N. Then,


x1,1 x1,2 x1,3 x1,1 + x1,2 x1,2 + x1,3
C=
.
x2,1 x2,2 x2,3 x2,1 + x2,2 x2,2 + x2,3

12

The user wants to download the file X from the DSS and sends
a query Q(l) , l ∈ N5 , to the l-th storage node. The queries take
the form shown in (16). For l ∈ N5 , we construct the matrix
V (l) = ∆l by choosing an appropriate matrix Ê. To do this,
we carefully choose the information sets I1 = {1, 2, 3} and
I2 = {1, 2, 3} (and hence V (4) = V (5) = 0d×β ). This allows
us to generate a column weight profile in Ê. More specifically,
let tj be the j-th column of Ê, j ∈ N5 . We have wH (t1 ) =
wH (t2 ) = wH (t3 ) = 2 and wH (t4 ) = wH (t5 ) = 0. A valid
matrix Ê is


1 0 1 0 0
Ê = 1 1 0 0 0
0 1 1 0 0

and we construct ∆1 according to (17). Focusing on the first
column of Ê, we can see that the first two rows have a one
(1)
(1)
(1)
(1)
in the first position. Thus, we choose j1 = s1 , j2 = s2 ,
(1)
and j3 = 0, since ê1,1 = 1, ê2,1 = 1, and ê3,1 = 0. We take
(1) (1)
(1)
(1)
s1 , s2 ∈ N2 . We arbitrarily choose s1 = 1 and s2 = 2
to get
  

ω1
1 0
∆ 1 = ω 2  = 0 1  .
ω0
0 0

Similarly, we construct



0 0
0
∆2 = 1 0 and ∆3 = 0
0 1
1


1
0 .
0

The queries Q(l) are sent to the respective nodes and the
responses

 

u1,1 x1,1 +u1,2 x2,1 +x1,1
I1 +x1,1
r1 = u2,1 x1,1 +u2,2 x2,1 +x2,1 = I4 +x2,1 ,
u3,1 x1,1 +u3,2 x2,1
I7
 

 u x +u x
I2
1,1 1,2
1,2 2,2
r2 = u2,1 x1,2 +u2,2 x2,2 +x1,2 = I5 +x1,2 ,
u3,1 x1,2 +u3,2 x2,2 +x2,2
I8 +x2,2

 u x +u x +x  
I3 +x2,3
1,1 1,3
1,2 2,3
2,3
u
x
+u
x
I6
2,1 1,3
2,2 2,3
,
=
r3 =
u3,1 x1,3 +u3,2 x2,3 +x1,3
I9 +x1,3



 u1,1 u1,2  
I1 +I2
x1,1 +x1,2
= I4 +I5 ,
r4 = uu2,1 uu2,2
x
+x
2,1
2,2
3,1
3,2
I7 +I8
  I2 +I3 
 u1,1 u1,2  
x1,2 +x1,3
= I5 +I6 ,
r5 = uu2,1 uu2,2
x2,2 +x2,3
3,1

P2

3,2

I8 +I9

where Ii = j=1 uh,j xj,h′ and i = 3(h−1)+h′ , with h, h′ ∈
N3 , are collected by the user. Notice that each storage node
sends back k = 3 symbols. The user obtains the requested file
as follows. Knowing I2 , the user obtains I1 and I3 from the
first components of r4 and r5 . This allows the user to obtain
x1,1 and x2,3 . In a similar fashion, knowing I6 the user gets
I5 from the second component of r5 , then uses this to obtain
I4 from the second component of r4 . This allows the user to
obtain x2,1 and x1,2 . Similarly, knowing I7 allows the user to
get I8 from the third component of r4 . Knowing I8 allows
the user to obtain I9 from the third component of r5 , which
then allows to recover the symbols x2,2 and x1,3 . In this way,
the user recovers all symbols of the file and hence recovers
2
X. Note that R = 2·3
5·3 = 5 , which is equal to the asymptotic
capacity C∞ in (8).

Example 5: Consider a DSS consisting of n = 7 storage
nodes that stores a single file X. The DSS uses a [7, 3, 4]
scalar code C over GF(2). The parity-check matrix of the
code is


0 1 1 1 0 0 0
1 0 1 0 1 0 0

HC = 
1 1 0 0 0 1 0 .
1 1 1 0 0 0 1
We take β = Γ = n − k = 4. File X is of size β × k and
hence consists of βk symbols in GF(2ℓ ). Accordingly, the
code array is


x1,1
x2,1
C=
x3,1
x4,1

x1,2
x2,2
x3,2
x4,2

x1,3
x2,3
x3,3
x4,3

x1,2 + x1,3
x2,2 + x2,3
x3,2 + x3,3
x4,2 + x4,3

x1,1 + x1,3
x2,1 + x2,3
x3,1 + x3,3
x4,1 + x4,3

x1,1 + x1,2
x2,1 + x2,2
x3,1 + x3,2
x4,1 + x4,2


x1,1 + x1,2 + x1,3
x2,1 + x2,2 + x2,3 
.
x3,1 + x3,2 + x3,3 
x4,1 + x4,2 + x4,3

The queries sent to each node, each consisting of d = k = 3
subqueries take the form in (16). The aim of each subquery is
to recover Γ code symbols using the PIR protocol. In order to
do so, we construct the information sets {Ii }i∈N4 . With careful
consideration, we choose I1 = {3, 4, 6}, I2 = {2, 6, 7}, I3 =
{1, 3, 4}, and I4 = {1, 5, 6}. The column weight profile of Ê
is wH (t1 ) = wH (t3 ) = wH (t4 ) = 2, wH (t2 ) = wH (t5 ) =
wH (t7 ) = 1, and wH (t6 ) = 3. A valid matrix Ê is


0 0 1 1 1 1 0
Ê = 1 1 0 1 0 1 0 .
1 0 1 0 0 1 1

Note that each erasure pattern in Ê (each row) is correctable
by the code C. As in Example 4, we map the columns of Ê
and {Ii }i∈N4 to the matrix V (l) and obtain




0 0 0 0
0 0 0 0
∆1 = 0 0 1 0 , ∆2 = 0 1 0 0 ,
0 0 0 1
0 0 0 0




1 0 0 0
1 0 0 0
∆3 = 0 0 0 0 , ∆4 = 0 0 1 0 ,
0 0 1 0
0 0 0 0




0 0 0 1
1 0 0 0
∆5 = 0 0 0 0 , ∆6 = 0 1 0 0 ,
0 0 0 0
0 0 0 1


0 0 0 0
∆7 = 0 0 0 0 .
0 1 0 0
As an example, we next show the reconstruction of symbols
from the first pair of subqueries and subresponses. We have
r1,1 = I1 , r2,1 = I2 , r3,1 = I3 + x1,3 ,
r4,1 = I2 + I3 + x1,2 + x1,3 , r5,1 = I1 + I3 + x4,1 + x4,3 ,
r6,1 = I1 + I2 + x1,1 + x1,2 , r7,1 = I1 + I2 + I3 ,
where P
rl,1 denotes the first subresponse from the l-th node,
4
′
′
Ii =
j=1 uh,j xj,h′ and i = 3(h − 1) + h , h, h ∈ N3 .
Clearly, the subresponses r1,1 , r2,1 , and r7,1 allow the user
to obtain the three interference symbols I1 , I2 , and I3 . This
is solely because the first row of Ê (pertaining to the first
subqueries) is an erasure pattern correctable by C. Having this
knowledge, the user obtains the symbols x1,3 , x1,2 + x1,3 ,

13

x4,1 + x4,3 , and x1,1 + x1,2 from the remaining subresponses.
From the obtained code symbols the user can decode x1,3 ,
x1,2 , and x1,1 , hence obtaining the message symbols in the
first row of C. The code symbol x4,1 + x4,3 is used to decode
x4,1 , x4,2 , and x4,3 from the code symbols that are further
obtained from the third subresponse. In the same way, the
remaining two subresponses allow the recovery of βk = 12
message symbols.
4
The PIR rate is R = 4·3
7·3 = 7 , which is equal to the
asymptotic capacity C∞ in (8).
VI. O PTIMIZING

THE

PIR R ATE FOR THE N ONCOLLUDING
C ASE

For given values of n and k, whether an [n, k] code is PIR
capacity-achieving or not is of great interest. In this section,
we provide a necessary condition for an arbitrary linear code
to achieve the PIR capacities Cf and C∞ . Furthermore, we
provide families of PIR capacity-achieving codes. For codes
for which we are not able to prove that they achieve the PIR
capacity, we provide an algorithm to search for an optimal (in
terms of PIR rate) PIR achievable rate matrix.
As shown in the previous sections, the only requirement for
a code C to achieve capacity is that there exists a PIR capacityachieving matrix Λκ,ν (C) (or a (Γ = n − k)-regular matrix
E of size (β + d) × n). In other words, the code C should be
able to correct β + d erasure patterns of n − k erasures that
satisfy the regularity condition of E.
A. PIR Capacity-Achieving Codes
Let us first consider a fact for any information set of an
[n, k] code.
Proposition 3 ([31, Th. 1.6.2]): If I is an information set
of an [n, k] code C, then Nn \ I is an information set for its
[n, n − k] dual code C ⊥ .
Based on Proposition 3, the subsequent result follows.
Corollary 4: The dual of an [n, k] PIR capacity-achieving
code is an [n, n − k] PIR capacity-achieving code.
To check the PIR capacity-achievability of a linear code,
sometimes it might be easier to verify the PIR capacityachieving condition for its dual code.
Next, we derive a useful result that gives the relation
between an information set and a subcode of dimension s.
Lemma 5: Given an [n, k] code C, for any information set
I and an s-dimensional subcode D ⊆ C, we have

there exist information sets Ii , i ∈ Nν , such that in {Ii }i∈Nν
each coordinate j of C, j ∈ Nn , appears exactly κ times. Let
D be any subcode of dimension s of the [n, k] code C. This
implies that
κ |χ(D)| =

ν
X

(a)

Ii ∩ χ(D) ≥ νs,

i=1

where (a) follows from Lemma 5. Based on the definition of
dCs , s ∈ Nk , there exists a rank-s subcode D∗ that achieves
dCs . We then have
n
ν
dCs ≥ s = s, ∀ s ∈ Nk .
κ
k
Based on the necessary condition, it can be shown that the
code C in Example 2 is not PIR capacity-achieving, since dC2 =
3 < 53 · 2, i.e., it is impossible to find a PIR capacity-achieving
matrix Λk,n for the code.
We would like to emphasize that it seems that the necessary
condition for PIR capacity-achieving codes in Theorem 3 is
also a sufficient condition. We have performed an exhaustive
search for codes with parameters k ∈ Nn and n ∈ N11
(except for [n, k] = [10, 5] and [n, k] = [11, 4 ≤ k ≤ 7]) and
seen that for codes that satisfy the necessary condition, there
always exists a PIR capacity-achieving matrix. Therefore, we
conjecture that (23) in Theorem 3 is an if and only if condition
for an [n, k] PIR capacity-achieving code.
Conjecture 1: A PIR capacity-achieving matrix Λκ,ν (C)
where κν = nk exists for an [n, k] code C if and only if
n
dCs ≥ s, ∀ s ∈ Nk .
k
In the following, we prove that certain families of codes
achieve the PIR capacity by directly showing the existence of
a PIR capacity-achieving matrix Λk,n or an (n − k)-regular
n × n matrix E. Note that since we prove that the following
code families are PIR capacity-achieving, all the codes must
satisfy the necessary condition of Theorem 3.
B. Cyclic Codes
Lemma 6: Cyclic codes are PIR capacity-achieving.
Proof: The result follows from the fact that for an [n, k]
cyclic code any set of k consecutive coordinates forms an
information set. Hence, a valid PIR capacity-achieving matrix
Λk,n can be obtained by cyclically shifting an information set
I = Nk n times.

I ∩ χ(D) ≥ s.
Proof: See Appendix E.
Now, we are able to provide a necessary condition for a code
to be PIR capacity-achieving.
Theorem 3: If an [n, k] code C is a PIR capacity-achieving
code, then
n
(23)
dCs ≥ s, ∀ s ∈ Nk .
k
Proof: Assume that an [n, k] code C is PIR capacityachieving. Then, by definition, there exists a PIR capacityachieving matrix Λκ,ν (C) such that κν = nk . This means that

C. Reed-Muller Codes
Lemma 7: RM codes are PIR capacity-achieving.
Proof: Consider an arbitrary RM code R(v, m) with v ∈
{0} ∪ Nm for some m ∈ N. We will show that there exists
a PIR achievable rate matrix Λκ,ν for R(v, m) for (κ, ν) =
(k, n). Let us consider the automorphisms g(µ) , µ + σ for
all 2m -tuples of σ ∈ GF(2)m×1 , and order them as g1 , . . . , gn ,
n = 2m (see Section II-A). Since any [n, k] RM code contains
at least one information set I, Proposition 1 guarantees that
Ii , {gi (µ) : µ ∈ I},

i ∈ Nn ,

14

are all information sets for the RM code. This implies that for
a given µ ∈ I, among {Ii }i∈Nn , the set
{µ + σ1 , µ + σ2 , . . . , µ + σn }
form the vector space GF(2)m×1 . There are in total k coordinates µ of I, hence every m-tuple represented coordinate
appears exactly k times, and we are able to find n information
sets satisfying Definition 10.
We remark here that because of the property of invertible
and affine automorphisms for binary RM codes, it is not too
hard to see that the PIR capacity-achievability of RM codes
can be extended to nonbinary generalized RM codes [32]. The
detailed discussion is omitted.
We further emphasize that the proofs of Lemmas 6 and 7
indicate that the automorphisms of an [n, k] code are very
important to design a PIR capacity-achieving code. The following lemma gives a sufficient condition for a code to be PIR
capacity-achieving.
Lemma 8: Given an [n, k] code C, if there exist n distinct
automorphisms π1 , π2 , . . . , πn such that for every code coordinate j ∈ Nn ,
{π1 (j), . . . , πn (j)} = Nn ,
then the code C is PIR capacity-achieving.
Proof: The proof follows a similar reasoning to the proof
of Lemma 7.
Note that cyclic codes and RM codes satisfy the sufficient
condition in Lemma 8. There exist other families of codes
satisfying Lemma 8, for instance, the class of low-density
parity-check (LDPC) codes constructed from array codes [33],
[34].
D. Local Reconstruction Codes
Consider an (r, δ)-optimal information locality code with
parameters [n, k] (see Definition 7). Furthermore, we impose
the additional assumption that


P1 P2 · · · PLc
MDS
In′ −k
(24)
H
=
M1 M2 · · · ML c

of size (n′ −k)×n′ forms the parity-check matrix of an [n′ , k]
MDS code over GF(q), where n′ = n − (Lc − 1)(δ − 1).3
For such a class of codes, we give an explicit construction
of the matrix
 E in order to design the PIR protocol. Recall
that L = nnc , nc = r + δ − 1, and let r̄ , n mod nc . We
consider


E1,1
E1,2
...
E1,L+1


..
..
..
E =  ...

.
.
.
EL+1,1

EL+1,2

. . . EL+1,L+1

having (L + 1)2 submatrices El,h , l, h ∈ NL+1 . For any l, h ∈
NL , the submatrices El,h have size nc × nc , El,L+1 has size
nc × r̄, EL+1,h has size r̄ × nc , and EL+1,L+1 is an r̄ ×
r̄ matrix. The i-th row of the matrix El,1 | . . . |El,L+1 is
(l)
(l)
denoted by ei , l ∈ NL+1 . The coordinates of ei represent
3 Examples of codes that satisfy (24) are Pyramid codes, the LRCs in [18],
and codes from the parity-splitting construction of [19].

the coordinates of the code C defined by its parity-check matrix
in (2). Furthermore, each row vector is subdivided into L + 1
(l)
subvectors ei,j , j ∈ NL+1 , as
(l)

(l)

(l)

(l)

(l)

(l)

ei = (ei,1 , . . . , ei,n ) = (ei,1 , . . . , ei,L , ei,L+1 ).
(l)

(l)

(l)

The subvectors ei,1 , . . . , ei,L are of length nc , while ei,L+1
is of length r̄. Correspondingly, we can think about matrix E
as partitioned into L + 1 column-wise partitions, where the
first Lc partitions correspond to the Lc local codes and the
remaining L + 1 − Lc partitions correspond to global parities
(l)
(l)
(see also (3)). Each subvector ei,j has support χ(ei,j ). We can
write E as

 (1)   (1)
(1)
(1)
(1)
e1,1
e1,2
···
e1,L
e1,L+1
e1
 .  
..
..
..
.. 

 ..  
.
.
·
·
·
.
. 




(1)
(1)
(1)
(1)
 (1)  
enc ,2 · · · enc ,L enc ,L+1 
enc ,1
 enc  

 .  
..
..
..
.. 
 .  

 .  
.
.
·
·
·
.
.
.
E ,  (L)  = 

(L)
(L)
(L)
(L)

 enc   e
enc ,2 · · · enc ,L enc ,L+1 

  nc ,1

 (L+1)   (L+1)
(L+1)
(L+1)
(L+1) 
 e1
 e1,1
e
·
·
·
e
e

1,2
1,L
1,L+1


 ..  
..
..
..
.. 


 .   .
.
···
.
. 
(L+1)
(L+1)
(L+1)
(L+1)
(L+1)
er̄
er̄,1
er̄,2
· · · er̄,L
er̄,L+1

We represent E using the matrices Ẽ, W , Z, and O defined
as
 (1) 
 (1)
(1)
(1) 
e1,L+1
e1,1 e1,2 · · · e1,L
 (1) 
 (1)
(1)
(1) 
 e2,L+1 
 e2,1 e2,2 · · · e2,L 



Ẽ,
.. , Z ,  .. ,
..
 ..
 . 
 .
. 
.
···
(L)
(L)
(L)
(L)
enc ,L+1
enc ,1 enc ,2 · · · enc ,L
 (L+1) 

 (L+1)
(L+1)
(L+1)
e
e1,1
e1,2
· · · e1,L

 1,L+1

 .
.
.



..  , O ,  ... 
..
W , ..
···
, (25)
(L+1)

er̄,1

(L+1)

er̄,2

···

(L+1)

(L+1)

er̄,L+1

er̄,L

where Ẽ is an nc L×nc L matrix, having L2 submatrices Eℓ,h ,
ℓ, h ∈ NL .
In the following, we give a systematic procedure for permuting columns of certain rows in E in order to obtain an
(n − k)-regular matrix.
a) Initialize the matrices Ẽ, W , Z, and O. The matrix
Z is initialized to the all-zero matrix of size (n − r̄) × r̄.
(L+1)
= 1,
Matrices W and O are initialized by setting ei,j
SL+1
i ∈ Nr̄ , j ∈ P = i=1 Pi , where P corresponds to the
parity coordinates of C and the sets Pi are defined
 in
Section II-B (see (3)). Consider an integer m , n−k
L
and m1 , m + 1. Let ρ1 = · · · = ρt = m1 and ρt+1 =
· · · = ρL = m, where t , (n − k) mod L. The matrix Ẽ
is initialized with the structure


π1 π2 · · ·
πL
πL π1 · · · πL−1 


(26)
Ẽ =  .
..
..  ,
 ..
. ···
. 
π2

π3

···

π1

where each matrix entry πl , l ∈ NL , is a ρl -regular square
matrix of order nc . Notice that due to the structure of Ẽ

15

in (26), it has row and column weight equal to n − k,
and each row in E has a row weight of n − k.
b) Swapping elements between Ẽ and Z. We consider
the j ′ -th column of Z, where j ′ ∈ Nr̄ . Without loss of
generality, let Ej ′ = {e′1 , . . . , e′τ }, where τ = n−k − r̄ ≥
0, be a set of rows from the matrix (Ẽ | Z). Note that
from Definition 7, the total number of parities in (2) is
equal to n − k. Therefore, we have
(δ − 1)Lc + (L − Lc )nc + r̄ = n − k

(27)

and τ = n − k − r̄ ≥ 0.
For s ∈ Nτ , the s-th row in Ej ′ will have a unique
SL
coordinate ps ∈ χ(e′s ) such that ps ∈ i=1 Pi . Note that
ps 6= ps′ , s′ ∈ Nτ , s 6= s′ . Now, we begin swapping
elements in the set Ej ′ . That is to say, swap values
between e′s,ps and e′s,nc L+j ′ . This process is repeated
recursively for all j ′ . In each iteration, the weight of the
ps -th column in E is reduced by 1, and the weight of
the (nc L + j ′ )-th column is increased by τ , resulting in
a column weight of τ + r̄ = n − k.
This completes the construction of E, which will have row
and column weight n − k. In the following theorem, we show
that each row of E (considered as an erasure pattern) can be
corrected by any code from the class of optimal information
locality codes whose parity-check matrices are as in (2) and
confirm (24). Thus, this class of codes are PIR capacityachieving.
Theorem 4: An (r, δ)-optimal information locality code C
with parameters [n, k], parity-check matrix as in (2), and that
satisfies (24) is a PIR capacity-achieving code.
Proof: See Appendix F.
In the following, we present an example to illustrate the
construction of matrix E. The existence of such a matrix
ensures that the PIR protocols presented in Sections IV and V
achieve the finite PIR capacity Cf (7) and the asymptotic PIR
capacity C∞ (8), respectively.
Example 6: Consider an [n = 7, k = 4] Pyramid code C
that is constructed from an [n′ = 6, 4] Reed-Solomon (RS)
code over GF(23 ) with parity-check matrices
 3

z 1 1 0 0 0 0
H C =  0 0 0 z 3 z 1 0 ,
z4 1 0 z5 z5 0 1
 3

z 1 z3 z 1 0
H MDS =
,
z4 1 z5 z5 0 1
respectively, where z denotes a primitive element of GF(23 ).
It is easy to see that C is an (r = 2, δ = 2)-optimal information
locality code. We have nc = 3, L = 2, and r̄ , n mod nc = 1.
By choosing ρ1 = 2 and ρ2 = 1, we get

 

1 1 0 1 0 0
0
0
 0 1 1 0 1 0 

 

 
0
 1 0 1 0 0 1 
π1 π2



, Z=
Ẽ =
=

0 .
π2 π1
 
 1 0 0 1 1 0 
0
 0 1 0 0 1 1 
0
0 0 1 1 0 1

Algorithm 1: Optimizing the PIR rate
Input : Distributed storage code C of length n
Output: Optimized matrix
Eopt and largest possible Γ

C
1 Γ ← min k, dmin − 1
2 Eopt ← ∅, Γopt ← Γ
3 Ln−k ← ComputeErasurePatternList(C, n − k)
4 while Γ ≤ n − k do
5
LΓ ← ComputeErasurePatternList(C, Γ)
6
if LΓ 6= ∅ then
7
E ← ComputeMatrix(LΓ, Ln−k )
8
if E 6= ∅ then
9
Eopt ← E, Γopt ← Γ
10
else
11
return (Eopt , Γopt )
12
end
13
end
14
Γ←Γ+1
15 end
16 return (Eopt , Γopt )
The set of parity coordinates is P = {3, 6, 7}, and we set
(3)
(3)
(3)
e1,3 = e1,6 = e1,7 = 1. As such, we get


W = 0 0 1 0 0 1 and O = 1 .

This completes Step a) of the construction in Section VI-D.
Note that each row of E has now weight 3. The second step
of the procedure (Step b)) is as follows. We have j ′ = 1
S2
(1) (2)
and i=1 Pi = {3, 6}. Also, E1 = {e′1 , e′2 } = {e2 , e3 },
(1)
(2)
where the row entries e2 and e3 of the set have support
(1)
(2)
χ(e2 ) = {2, 3, 5} and χ(e3 ) = {3, 4, 6}, respectively. Fur(1)
(2)
thermore, note that p1 = 3 ∈ χ(e2 ) and p2 = 6 ∈ χ(e3 ).
This condition satisfies the choice of E1 . We do the following
swaps,
(1)

(1)

(2)

(2)

e2,3 = 0, e2,7 = 1,
e3,6 = 0, e3,7 = 1,
which result in






E=





1
0
1
1
0
0
0

1
1
0
0
1
0
0

0
0
1
0
0
1
1

1
0
0
1
0
1
0

0
1
0
1
1
0
0

0
0
1
0
1
0
1

0
1
0
0
0
1
1







.





The entries in red indicate the swapped values within each
row. It can easily be verified that each row of E is an erasure
pattern that is ML-correctable by the code C.
E. Optimization Algorithm
We now provide an algorithm to optimize the PIR Protocols
1 and 2 in order to achieve the highest possible PIR rate R
for a given code by taking the structure of the underlying
code into consideration. The algorithm is given in Algorithm 1
and is based on Theorem 2. In particular, we need to find a

16

(d + β) × n matrix E (19) in which Ê consists of erasure
patterns of weight Γ that are all correctable by C, and in
which Ē corresponds to information sets of C (the support
of each row is the complement of an information set). In
addition, it is required that each column weight of Ê is equal
to the corresponding column weight of 1 − Ē (see Section V).
Note that from the resulting matrix E we can find a PIR
achievable rate matrix by taking its binary complement as
(20) (see Section V), thus optimizing PIR Protocols 1 and
2 in Sections IV and V.
The main issues that need to be addressed are the efficient
enumeration of the set of erasure patterns of a given weight Γ
(Ê) and also of weight n−k (Ē, corresponding to information
sets) that can be corrected by C under ML decoding, and the
efficient computation of the matrix E. The ML-correctable
erasure patterns (of length n) are erasure patterns with erasures
corresponding to the 1-entries that can be corrected by an
ML decoder for the BEC. These issues are addressed by
the subprocedures ComputeErasurePatternList(C, ·)
and ComputeMatrix(LΓ, Ln−k ), in Lines 3, 5, and 7
of Algorithm 1, and discussed below in Sections VI-E1
and VI-E2, respectively. Here, LΓ and Ln−k correspond to
erasure patterns for Ê and Ē, respectively. We remark that
the algorithm will always return a valid E 6= ∅, since initially
Γ = min (k, dmin − 1). This follows directly from the fact that
we can construct an arbitrary Ê with row weights Γ such that
its column weights match the corresponding weights in 1− Ē.
Each row in Ê is an erasure pattern that is correctable by C.
Let d = k and β = n − k. In the particular case of C
being a rate RC > 1/2 systematic MDS code, dCmin = n −
k + 1, and the algorithm will do exactly one iteration of the
main loop. This follows directly from the construction of E:
the matrix E can be constructed by taking the support of an
arbitrary information set of C and cyclically shifting it n times
to construct an n × n PIR achievable rate matrix, after which
the resulting matrix is complemented as (20) to get E. In this
case, the overall PIR scheme reduces to the one described
in [12, Sec. IV] for systematic MDS codes of rate RC >
1/2. Clearly, for general MDS codes (including nonsystematic
codes) of rate RC > 1/2, the same construction of E works,
and the algorithm will perform exactly one iteration of the
main loop also for nonsystematic MDS codes. In the case of
C being a rate RC ≤ 1/2 general MDS code, the initial value
of Γ becomes k (since Γ = min k, dCmin − 1 = min(k, n −
k) = k), but the algorithm will also find a valid matrix E for
Γ = n − k ≥ k. Again, the existence of E follows from the
same argument of cyclically shifting an existing information
set n times. In the general case of d 6= k and β 6= n − k, a
similar argument to the one above can be made.
1) ComputeErasurePatternList(C, ·): Computing
a list of erasure patterns that are correctable under ML
decoding for a given short code can be done using any
ML decoding algorithm. For small codes, all length-n binary
vectors of weight Γ (or n − k) correspond to erasure patterns
that are ML-correctable can be found by exhaustive search,
while for longer codes a random search can be performed, in
the sense of picking length-n binary vectors of weight Γ (or
n−k) at random, and then verifying whether the corresponding

erasure patterns are ML-correctable or not. Alternatively, one
can apply a random permutation π to the columns of H C ,
apply the Gauss-Jordan algorithm to the resulting matrix to
transform it into row echelon form, collect a subset of size
Γ of the column indices of leading-one-columns,4 and finally
apply the inverse permutation π −1 to this subset of column
indices. The resulting set corresponds to erased coordinates in
C that can be recovered by the code. Finally, one can check
whether all cyclic shifts of the added erasure pattern are MLcorrectable or not and add the ML-correctable cyclic shifts to
LΓ (or Ln−k ).
2) ComputeMatrix(LΓ, Ln−k ): Given the lists LΓ and
Ln−k of erasure patterns of weight Γ and n − k, respectively,
that are correctable
under ML decoding, we construct a

|LΓ | + |Ln−k | × n matrix, denoted by Ψ = (ψi,j ), in which
each row i ∈ N|LΓ | is one of the erasure patterns from LΓ
and each row i ∈ N|LΓ |+1:|LΓ |+|Ln−k | is one of the erasure
patterns from Ln−k . The problem is now to find a d × n
submatrix Ψ̂ of the upper part of Ψ (rows 1 to |LΓ |) and a
β × n submatrix Ψ̄ of the lower part of Ψ (rows |LΓ | + 1 to
|LΓ | + |Ln−k |) such that the column weight of each of the n
columns is the same for Ψ̂ and the binary complement of Ψ̄.
This can be formulated as an integer program (in the integer
variables η1 , . . . , η|LΓ |+|Ln−k | ) in the following way,
|LΓ |+|Ln−k |

maximize

X

ηi

i=1

|LΓ |

s. t.

X
i=1

|LΓ |+|Ln−k |

ηi ψi,j =

X

ηi (1 − ψi,j ), ∀ j ∈ Nn ,

i=|LΓ |+1

ηi ∈ {0, 1}, ∀ i ∈ N|LΓ |+|Ln−k | ,
X
i=1

(28)

|LΓ |+|Ln−k |

|LΓ |

ηi = d, and

X

ηi = β.

i=|LΓ |+1

A valid (d + β) × n matrix E is constructed from the rows
of Ψ with ηi -values equal to one in any feasible solution of
(28). When |LΓ | + |Ln−k | is large, solving (28) may become
impractical (solving a general integer program is known to
be NP-hard), in which case one can take several random
subsets (of some size) of the lists LΓ and Ln−k , construct
the corresponding matrices Ψ, and try to solve the program
in (28).
VII. M ULTIPLE C OLLUDING N ODES
In this section, we consider the scenario where T > 1 nodes
act as spies and have the ability to collude. In particular, we
consider the PIR protocol in [22] and we refer to it as the
¯
(C, C)-retrieval
protocol (or scheme), since it is based on two
¯
linear codes; an [n, k] linear code C and an [n, k̄] linear code C,
where C is the underlying storage code of the DSS. Originally,
the protocol was designed to work with GRS codes, a class of
MDS codes, i.e., both C and C¯ are GRS codes. When C is a
non-GRS code and under the assumption that the code C¯ exists
4 The leading-one-columns are the columns containing a leading one, where
the first nonzero entry in each matrix row of a matrix in row echelon form is
called a leading one.

17

for a given T (existing in the sense that the Hadamard product
of C and C¯ has rate strictly smaller than 1), the PIR rate of the
protocol is limited by the code rate of C. Furthermore, it was
shown in [23] that if C is either a GRS code or an RM code,
then C¯ always exists for any T ≤ n − k. In this section, we
look at this protocol from the perspective of arbitrary linear
codes C and improve the PIR rate. Also, for a given T we
present a code family for C for which C¯ exists.

(l)

(l)

(l)

and si 6= si′ for i 6= i′ , i, i′ ∈ Nd . The index si denotes
(l)
the symbol downloaded from the si -th row of the chunk
(m)
pertaining to X
in the l-th node in the i-th iteration.
Clearly, we see that the symbols downloaded from
P all nodes
across all iterations form β information sets as di=1 |Ji | =
Pβ
i=1 |Ii | = βk.
2) Response Construction: For the i-th iteration, the response symbol from the l-th node is constructed as
(l)

The protocol presented here, referred to as Protocol 3, can
be seen as an extension of Protocol
2 in Section V. We assume
(m) 
that each file X (m) = xi,j , m ∈ Nf , of size β ×k is stored
(m)
using an [n, k] code C over GF(q), where xi,j ∈ GF(q ℓ ) for
some ℓ ∈ N. The protocol involves d iterations between the
user and the nodes. Let C¯ be an [n, k̄] code over GF(q). The
(l)
code C¯ is used to design the n query vectors qi over GF(q),
l ∈ Nn , in the i-th iteration, where i ∈ Nd . The query vector
in the i-th iteration can be viewed as the i-th subquery of Q(l)
(see Section III-A). Furthermore, C¯ characterizes T , i.e., the
maximum number of colluding nodes the PIR protocol can
handle whilst maintaining information-theoretic privacy. The
i-th iteration response vector ρ(i) = (r1,i , . . . , rn,i )⊤ , which is
a collection of the n response symbols rl,i from the n storage
¯
nodes, is related to the codewords of an [n, k̃] code C˜ = C ◦ C.
˜
Furthermore, C characterizes the PIR rate of the protocol.
1) Query Construction: The protocol requires that the
(m)
=
user constructs queries by choosing βf codewords c̄i
(m)
(m)
(c̄i,1 , . . . , c̄i,n ), i ∈ Nβ and m ∈ Nf , drawn independently
¯ It then constructs
and uniformly at random from the code C.
the vector
(1)

(f )

c̊j = (c̊j , . . . , c̊j ),
(m)

(m)

j ∈ Nn ,

(m)

= (c̄1,j , . . . , c̄β,j ). Thus, the vector c̊j is of
where c̊j
(m)
length βf . The vector c̊j is a collection of the entries of the
(m)
(m)
j-th coordinates of the codewords c̄1 , . . . , c̄β that pertain
to the m-th file. We denote by Ji ⊆ Nn , i ∈ Nd , |Ji | = Γ,
the set of nodes from which the protocol obtains code symbols
pertaining to the m-th file in the i-th iteration.
Similar to Protocol 2 for the case of noncolluding nodes
presented in Section V, we need to construct a matrix Ê and
β information sets {Ii }i∈Nβ . The matrix Ê is a d × n binary
matrix where each row represents an erasure pattern of weight
¯ The column weight profile of Ê is
Γ correctable by C˜ = C ◦ C.
determined from {Ii }i∈Nβ as in Section V. Note that Ji is the
support of the i-th row vector of Ê. Let m denote the index
of the requested file. Then, the queries in the i-th iteration are
constructed as
(
c̊l + ωβ(m−1)+s(l) if l ∈ Ji ,
(l)
i
qi =
(29)
c̊l + ω0
otherwise,
for l ∈ Nn , where ωt , t ∈ Nβf , is the t-th (βf )-dimensional
(l)
unit vector and ω0 = 01×βf . The index si is defined as
(l)
si

(1)

(f )

rl,i = hqi , (c1,l , . . . , cβ,l )i.

A. The (C, C̄)-Retrieval Protocol

∈ Fl = {t ∈ Nβ : l ∈ It }

(30)

(31)

The response symbol in (31) is the dot product between the
query vector for the l-th node and the content of that node.
The user obtains a response vector ρ(i) , consisting of response
symbols from n nodes as
 (m′ ) (m′ )   (i) 


c̄i′ ,1 ci′ ,1
o1
r1,i
′
′
 (i) 
β X
f  (m ) (m ) 
 r2,i  X
c̄i′ ,2 ci′ ,2  o2 


 +  .  , (32)

ρ(i) =  .  =
..
  . 

 .. 
  . 

′
′
.
i =1 m =1
′
′
(i)
(m ) (m )
rn,i
on
c̄i′ ,n ci′ ,n
|
{z
}
∈ x∈(GF(qℓ ))n : H C̃ x=0

where H C̃ is the parity-check
(i)
symbol ol denotes the symbol
in the i-th iteration, and
(
(m)
ci′ ,l
(i)
ol =
0

˜ 5 the
matrix of the code C,
obtained from the l-th node
if l ∈ Ji ,
otherwise,

(l)

where i′ = si . These symbols are obtained by postprocessing (32) as follows,
 (i) 
o1
 (i) 

o2 

H C̃ ρ(i) = H C̃ 
(33)
 ..  .
 . 
(i)

on

This completes the construction of the PIR protocol. In
the following, we prove that this protocol satisfies the PIR
conditions (5a) and (5b) in Definition 8.
Lemma 9: Consider a DSS that uses an [n, k] code C with
subpacketization α to store f files, each divided into β stripes,
and assume the privacy model of Section III-A with a set T =
⊥
{t1 , . . . , t|T | } ⊂ Nn of |T | ≤ T ≤ dC̄min − 1 colluding nodes.
(l)
Then, the queries qi , l ∈ Nn , designed as in (29) for the
(l)
i-th row in Q , i ∈ Nd , satisfy H m|Q(t1 ) , . . . , Q(t|T | ) =
H(m).
Proof: The addition of a deterministic vector in (29)
does not change the probability distribution of the vectors
(t
)
(t )
qi 1 , . . . , qi |T | . The same can be said about their joint
distribution. Furthermore, in each query matrix Q(l) , l ∈
(l)
{t1 , . . . , t|T | }, the rows qi are independent of each other.
Thus, the proof follows the same lines as the proof of [22,
Th. 8].
5 Note that the upload cost of the PIR scheme in [22], [23] grows linearly
with f . However, the requested upload cost can actually be ignored by
extending the field size of the stored files.

18

Theorem 5: Consider a DSS that uses an [n, k] code C with
subpacketization α to store f files, each divided into β stripes.
Let C¯ be an [n, k̄] code such that there exists an [n, kC̃ ] code
C˜ = C ◦ C¯ of rate RC̃ < 1 In order to retrieve the file X (m) ,
(l)
m ∈ Nf , from the DSS, the user sends the queries qi , l ∈ Nn ,
i ∈ Nd , in (29) to the n nodes. Then, for the responses ρ(i)
in (32) received by the user, H(X (m) |ρ(1) , . . . , ρ(d) ) = 0.
Proof: By construction there exists a matrix Ê of size
d×n having row weight Γ. Furthermore, again by construction,
˜
each row of Ê is an erasure pattern that is correctable by C.
For the i-th iteration, from (29), (33) results in
H C̃ ρ(i) = H C̃ |χ(êi ) ρ(i) ,
where êi is the i-th row vector of Ê. The above linear system
of equations is full rank as H C̃ |χ(êi ) is full rank. This is
˜ As such,
because êi is a correctable erasure pattern for C.
(i)
the Γ symbols {oj }j∈Ji are obtained. Across iterations, the
user obtains Γd = βk code symbols of the code C. Further,
from (30), these Γd symbols are a part of the
 β information
sets {Ii }i∈Nβ . Thus, H X (m) |ρ(1) , . . . , ρ(d) = 0.
Unlike [22], where the authors consider sets Ji with a fixed
¯
structure, we generalize the sets to match arbitrary codes C, C,
˜
and C. In particular, the sets in [22] were constructed targeting
MDS codes. However, the use of these sets for arbitrary codes
C and C¯ does not allow to obtain the requested file X (m) .
Thus, Theorem 5 can be seen as a generalization of [22, Th. 7]
where the PIR rate was shown to be R = (dC̃min − 1)/n. Our
proposed protocol can achieve higher rates. More precisely,
the PIR rate is upperbounded by
n − k̃
Γ
≤ RUB ,
.
(34)
n
n
Lemma 9 proves that the proposed protocol provides privacy
⊥
up to T = dC̄min − 1 colluding nodes. This is illustrated in the
example below.
R=

B. Example
Consider a DSS with n = 12 nodes that stores a single file
X (1) of size 1 × 4. X (1) is encoded using the [12, 4, 6] binary
code C with parity-check matrix


0 1 1 0 1 0 0 0 0 0 0 0
 1 0 1 0 0 1 0 0 0 0 0 0 


 1 1 1 0 0 0 1 0 0 0 0 0 


 1 1 0 1 0 0 0 1 0 0 0 0 
C

.
H =

 1 0 1 1 0 0 0 0 1 0 0 0 
 0 1 1 1 0 0 0 0 0 1 0 0 


 1 1 1 1 0 0 0 0 0 0 1 0 
0 0 1 1 0 0 0 0 0 0 0 1

Let C¯ = C, and the code C˜ = C ◦ C¯ has parity-check matrix


1 1 1 1 0 0 1 1 1 1 0 0
H C̃ =
.
1 1 0 1 1 1 0 1 0 0 1 1

⊥
Note that the dual code C¯⊥ has minimum distance dC̄min = 3,
⊥
thus this protocol protects against T = dC̄min − 1 = 2 colluding
nodes. Choosing Γ = dC̃min − 1 = 1, one can use the PIR
1
protocol as presented in [22] to get a PIR rate of R = 12
.

However, we can set Γ = 2 and use the PIR protocol described
in Section VII-A to achieve a higher PIR rate. Note that the
value of Γ cannot be greater than 2 as the number of redundant
symbols in C˜ is not larger than 2. We choose


0 0 0 0 0 0 0 0 1 0 0 1
Ê =
0 1 1 0 0 0 0 0 0 0 0 0
and I1 = {2, 3, 9, 12}. Thus, β = 1 and d = 2. Note that
each row of Ê is an erasure pattern that is correctable by the
˜ and that I1 is an information set of C. In
[12, 10, 2] code C,
order to form the queries for all d = 2 iterations, we need to
(3)
(2)
(12)
(9)
choose s1 , s1 , s2 , and s2 . From (30), we have
(12)

(9)

s1 = 1, s1

(3)

(2)

= 1, s2 = 1, and s2 = 1.
(9)

Now, consider the first iteration. The query vectors q1
(12)
q1 are

and

(9)

q1 = c̊9 + ω1 = c̊9 + 1,
(12)

q1

= c̊12 + ω1 = c̊12 + 1,

(l)

and q1 = c̊l , ∀ l ∈ N12 \{9, 12}. These queries are sent to
the storage nodes. The response vector is


0
 . 
 (m) (m) 
 .. 
c̄i,1 ci,1


 0 
2 X
1  (m) (m) 
X
c
c̄




 i,2 i,2  +  (1)  .
ρ(1) =
..
 c1,9 





.
i=1 m=1 
 0 
(m) (m)


c̄i,12 ci,12
 0 
{z
}
|
(1)
c1,12
∈ x∈(GF(qℓ ))n : H C̃ x=0
Finally, the user computes



C̃ (1)

H ρ


0
 . 
 .. 


 0 


(1) 
= H C̃ 
 c1,9  =


 0 


 0 
(1)
c1,12

(1)

c1,9
(1)
c1,12

!

.

In a similar manner, in the second iteration the user obtains
(1)
(1)
c2,2 and c2,3 . Clearly, the indices of the symbols downloaded
by the user form the information set I1 , from which we can
obtain the requested file X (1) . The PIR rate of the scheme is
4
= 61 , i.e., double of the PIR rate of the protocol in
R = 24
[22]. Furthermore, it achieves the upper bound in (34).
A limiting factor for this PIR protocol is that the upper
bound on the PIR rate RUB in (34) depends on the dimension
˜ Furthermore, in order to achieve the PIR property with
of C.
large T , one requires C¯ to be of large dimension such that C¯⊥
has large minimum distance. Therefore, for arbitrary C and C¯
the chances that C˜ = C ◦ C¯ has rate RC̃ = 1 (the code does not
even correct a single erasure) are quite high for large values
of T , since the Hadamard product is highly nonlinear. In other
words, the probability that RUB = 0 is high. Below, we present
code constructions for which RUB > 0.

19

¯
C. Codes for the (C, C)-Retrieval
Protocol
As seen in the preceding sections, the linear codes C and C¯
must be chosen such that the code C˜ = C ◦ C¯ has rate RC̃ < 1
for the PIR protocol to work. In this section, we provide a
family of codes C and C¯ that satisfy RC̃ < 1 for a given T .
In particular, we show that a special class of UUV codes
˜ Let
can be used for the codes C and C¯ to obtain a valid C.
U be an [n1 , k1 ] code and V an [n1 , 1] repetition code, both
over GF(2). We construct the [n = 2n1 , k = k1 + 1] code
C = (U | U + V) with generator matrix
 U

G
GU
C
G =
.
(35)
01×n1 11×n1
Theorem 6: Let U be an [n1 , k1 ] binary linear code where
n1 ≥ k1 + 2 and V an [n1 , 1] binary repetition code. Then, the
[n = 2n1 , k = k1 + 1] codes C and C¯ constructed using (35)
ensure that the vector space C˜ = C ◦ C¯ of length n is a linear
code of dimension strictly less than n, i.e., RC̃ < 1.
Proof: See Appendix G.
Theorem 6 proves that for an arbitrary linear code U, the
˜ < n and thus C˜ is a valid code.
UUV code ensures that dim(C)
The fact that any code U can be used in the protocol makes
the UUV construction attractive. Also, the UUV construction
may produce dmin -optimal binary linear codes. For instance,
the codes C and C¯ in Section VII-B are optimal binary linear
codes. One drawback of the UUV construction, however, is
that the constructed codes are in general low rate codes.
In [23], the authors showed that choosing C and C¯ to be
RM codes with carefully selected parameters ensures that C˜
˜ < n. However, the
is also an RM code of dimension dim(C)
PIR rate is very low [23, Th. 15]. In the following subsection,
we show that RM codes
 can indeed achieve a higher PIR rate
˜ /n, which is equal to the upper bound
of R = n − dim(C)
(34).
¯
D. Codes Achieving the Maximum PIR Rate of the (C, C)Retrieval Protocol
In order to consider the codes achieving the maximum
¯
possible PIR rate for the (C, C)-retrieval
protocol, we give a
definition similar to Definition 10 in Section IV.
Definition 14: Let C be an [n, k] code and C¯ an [n, k̄] code.
Denote by C˜ = C ◦ C̄ the k̃-dimensional code generated by the
¯ A (k +n− k̃)×n binary matrix
Hadamard product of C and C.
¯
Λ̃k,k+n−k̃ is called a PIR maximum rate matrix for the (C, C)retrieval protocol if the following conditions are satisfied.
1) The weight of each column of Λ̃k,k+n−k̃ is k, and
2) there are exactly k rows {λi }i∈Nk and n − k̃ rows
{λi+k }i∈Nn−k̃ of Λ̃k,k+n−k̃ , such that ∀ i ∈ Nk , χ(λi )
are information sets for C˜ and ∀ i ∈ Nn−k̃ , χ(λi+k ) are
information sets for C.
Similar to the case of noncolluding nodes in Section V, it
is not difficult to show that the existence of a k × n matrix Ê
for the code C˜ = C ◦ C¯ and an (n − k̃) × n matrix Ē for the
code C is equivalent to the existence of Λk,k+n−k̃ .
The following corollary follows immediately from a similar
reasoning as that for Theorem 3.

Corollary 5: If a PIR maximum rate matrix Λ̃k,k+n−k̃ exists
¯
for the (C, C)-retrieval
protocol, then
n − k̃
s, ∀ s ∈ Nk ,
k
dC̃s ≥ s,
∀ s ∈ Nk̃ .

dCs ≥

Proof: Using an argumentation similar to the proof of
Theorem 3, the existence of a PIR maximum rate matrix
for the (C, C̄)-retrieval protocol implies that there exist k
information sets {Ĩi }i∈Nk of C˜ and n − k̃ information sets
{Ii′ }i′ ∈Nn−k̃ of C such that each coordinate j of C appears

exactly k times in Ĩi , Ii′ , i ∈ Nk , i′ ∈ Nn−k̃ , j ∈ Nn .
Hence, we obtain
k |χ(D)| =

k
X

Ĩi ∩ χ(D) +

i=1

≥

|

n−
Xk̃

{z

≥0

}

n−
Xk̃

Ii′ ∩ χ(D)

i′ =1

Ii′ ∩ χ(D) ≥ (n − k̃)s;

i′ =1

k χ(D̃) =

k
X

Ĩi ∩ χ(D̃) +

k
X

Ii′ ∩ χ(D̃)

i′ =1

i=1

≥

n−
Xk̃

|

Ĩi ∩ χ(D̃) ≥ ks,

{z

≥0

}

i=1

where D is an [n, s] subcode of C, s ∈ Nk , and D̃ is an [n, s]
˜ s∈N .
subcode of C,
k̃
It can be seen from the proof above that we can only have
|Ĩ ∩ χ(D)| ≥ 0 for an information set Ĩ of C˜ and a subcode
D ⊆ C (or |I ∩ χ(D̃)| ≥ 0 for an information set I of C and
˜ Hence, unlike in Conjecture 1, we do not
a subcode D̃ ⊆ C).
conjecture this necessary condition to be sufficient.
Theorem 7: Let C be an [n, k] RM code R(v, m), C¯ an
m
RM code R(v̄, m) code,
[n, k̄]P
Pv̄ andmk̃ = k + k̄, where n = 2 ,
v
m
k = i=0 i , and k̄ = i=0 i . Then, a PIR maximum
¯
rate matrix Λ̃k,k+n−k̃ exists for the (C, C)-retrieval
protocol,
and its PIR rate is
˜
n − dim(C)
n − k̃
=
.
R=
n
n
Proof: It can be easily shown that C˜ = C ◦ C¯ is an RM
code R(ṽ, m) with ṽ = v + v̄. Consider two information sets
˜ respectively. (Lemma 1 gives one way
I and Ĩ of C and C,
to construct these two information sets.) We construct the k +
n − k̃ information sets
Ĩi , {σ + µi : σ ∈ Ĩ},

i ∈ Nk ,

Ij , {µ + σ̄j : µ ∈ I}, j ∈ Nn−k̃ ,
where {µi }i∈Nk and {σ̄j }j∈Nn−k̃ are the numbered binary
m-tuples in I and GF(2)m×1 \ Ĩ, respectively. From Proposition 1, {Ĩi }i∈Nk and {Ij }j∈Nn−k̃ are information sets for C˜
and C, respectively.
To prove the existence of a PIR maximum rate matrix for the
¯
(C, C)-retrieval
protocol with C = R(v, m) and C¯ = R(v̄, m),

20

it is sufficient to show that each m-tuple representing a
coordinate of the RM code appears exactly k times in the
k + n − k̃ constructed information sets above. Without loss of
generality, the i-th information set Ĩi , i ∈ Nk , can be written
as
Ĩi = {µi + σ1 , . . . , µi + σk̃ },
where σj ′ ∈ Ĩ, j ′ ∈ Nk̃ . Furthermore, consider the i-th
elements across all sets Ij , j ∈ Nn−k̃ . They have the form
µi + σ̄j ,
where µi ∈ I. Since σ̄j ∈ GF(2)m×1 \ Ĩ and σi ∈ Ĩ, the set
{µi + σ1 , . . . , µi + σk̃ } ∪ {µi + σ̄1 , . . . , µi + σ̄n−k̃ }
with cardinality n = 2m is equal to GF(2)m×1 , i.e., the set
containing the elements of the i-th information set Ĩi and the ith elements µi +σ̄j in all sets Ij is equal to the set of all binary
n = 2m tuples. There exist k such
 pairs, thus each element
in GF(2)m×1 occurs k times in Ĩi , Ij , i ∈ Nk , j ∈ Nn−k̃ .
This completes the proof.
We remark again that Theorem 7 can be extended to
nonbinary generalized RM codes.
E. Optimizing the PIR rate
¯ and subsequently C,
˜ the informationGiven codes C, C,
¯
theoretic limit on the PIR rate for the (C, C)-retrieval protocol
in this section is limited by the dimension of C˜ (see (34)). We
now provide an algorithm to optimize the PIR rate R such that
it comes closer to the upper bound RUB in (34). The algorithm
is identical to Algorithm 1 for the case of noncolluding nodes
with some key differences which we highlight below.
• In Line 1, Γ in initialized to 1.
• The while loop in Line 4 runs up to n − k̃.
• The
first
argument
to
the
subprocedure
ComputeErasurePatternList(·, Γ) is changed
from C to C ◦ C¯ in Line 5.
With these minor modifications, Algorithm 1 can be used
to optimize the PIR rate in the case of T colluding nodes.
Numerical results are presented below in Section VIII. Note

that Γ is initialized to 1 as opposed to min k, dCmin − 1 in
the case of noncolluding nodes. This is because Ê and Ē of
E are based on different codes. This also guarantees that the
algorithm always returns Eopt 6= ∅ (assuming dC̃min ≥ 2), since
˜
in this case all weight-1 erasure patterns are correctable by C,
and a valid matrix E can be trivially constructed.
VIII. N UMERICAL R ESULTS
In this section, we present maximized PIR rates for the
PIR protocols described in Sections IV, V, and VII. Unless
specified otherwise, these protocols are optimized using Algorithm 1 with minimum possible values for the parameters β
and d as in (6). In contrast to Sections VI-A to VI-D, where
different classes of codes were proved to be PIR capacityachieving, we consider here other codes (with two exceptions
as detailed below) and their highest possible PIR rates. The
results are tabulated in Tables II and III for the case of

TABLE II
O PTIMIZED VALUES FOR THE PIR RATE FOR DIFFERENT CODES HAVING
CODE RATES STRICTLY LARGER THAN 1/2 FOR THE CASE OF
NONCOLLUDING NODES .
Code
C1
C2
C3
C4
C5
C6
C7

: [5, 3] (Example 4)
: [11, 6]
: [12, 8] Pyramid
: [16, 10] LRC
: [18, 12] Pyramid
: [154, 121] LRC
: [187, 121] LRC

′

dC
min

dC
min

Rnon−opt

Ropt

C∞

2
4
4
5
5
4
7

3
4
4
5
5
6
16

0.4
0.2727
0.25
0.25
0.2222
0.0325
0.0802

0.4
0.4545
0.3333
0.3750
0.3333
0.2013
0.3262

0.4
0.4545
0.3333
0.3750
0.3333
0.2143
0.3529

TABLE III
O PTIMIZED VALUES FOR THE PIR RATE FOR DIFFERENT CODES HAVING
CODE RATES AT MOST 1/2 FOR THE CASE OF NONCOLLUDING NODES .
Code
C8 : [7, 3] (Example 5)
C9 : [9, 4] LRC ( [20, Ex. 1])
C10 : [12, 6] LRC ( [20, Ex. 2])

dC
min

Rnon−opt

Ropt

C∞

4
5
6

0.4286
0.4444
0.4167

0.5714
0.5555
0.5

0.5714
0.5555
0.5

noncolluding nodes, and in Table IV for the colluding case.
Results in Table II are for code rates strictly larger than 1/2,
while codes of rate at most 1/2 are tabulated in Table III.
In Tables II and III, C∞ (see (8)) is the asymptotic PIR
capacity and Ropt is the optimized PIR rate computed from
′

Algorithm 1. In Table II, Rnon−opt =
dC
min −1
n .

dC
min −1
n ,

while in Table III,

−1)
In Table IV, CLB,∞ , n−(k+T
is
Rnon−opt =
n
a lower bound (taken from [22]) on the asymptotic PIR
capacity in the case of at most T colluding nodes, while Ropt
is the optimized PIR rate computed from Algorithm 1 and
dC̃ −1

Rnon−opt = minn .
The code C1 in Table II is from Example 4, C2 is an
[11, 6] binary linear code with optimum minimum Hamming
distance, while codes C3 and C5 are Pyramid codes, taken
from [16], of locality 4 and 6, respectively,6 C4 is an LRC
of locality 5 borrowed from [17]. In [35], a construction of
optimal (in terms of minimum Hamming distance) binary
LRCs with multiple repair groups was given. In particular,
in [35, Constr. 3], a construction based on array LDPC codes
was provided. The minimum distance of array LDPC codes
is known for certain sets of parameters (see, e.g., [36] and
references therein). Codes C6 and C7 in Table II are optimal
LRCs based on array LDPC codes constructed using [35,
Constr. 3] and having information locality 11. The protocols
for these two underlying codes have β = Γ and d = k.
Code C8 in Table III is the dual code of the [7, 4, 3]
Hamming code and is taken from Example 5, while the codes
C9 and C10 are dmin -optimal LRCs over GF(13) of all-symbol
locality 2 and 3, respectively, taken from [20] (see Examples 1
and 2, respectively, in [20]). These two codes are also tabulated
in Table IV. The corresponding C¯ codes are RS codes and
their parameters are given in Table IV (an RS code of length
n and dimension k is denoted by RS[n, k]). Code C11 (from
Table IV) is taken from Section VII-B, while code C12 (also
from Table IV) is taken from [20] (see Example 5 in [20]).
6 Note that the Pyramid codes C and C satisfy the conditions of Theo3
5
rem 4. Thus, they are PIR capacity-achieving.

21

TABLE IV
O PTIMIZED VALUES FOR THE PIR RATE FOR DIFFERENT CODES FOR THE COLLUDING CASE WITH T = 2 AND T = 3.
T
Rnon−opt
Ropt
RUB
CLB,∞
Code C
C¯
C̃
dC
min

C9 : [9, 4] LRC ( [20, Ex. 1])
C10 : [12, 6] LRC ( [20, Ex. 2])
C11 : [12, 4] (Section VII-B)
C12 : [12, 4] LRC ( [20, Ex. 5])
C13 : [26, 9] (U | U + V)
C14 : [32, 6] (U | U + V)

RS[9, 2]
RS[12, 2]
C
RS[12, 2]
C
C

RS(9, 6)
RS(12, 8)
[12, 10, 2]
[12, 7, 5]
[26, 22, 1]
[32, 16, 8]

Note that C12 is an LRC of length 12 over GF(13) with
two disjoint recovering sets of sizes 2 and 3, respectively,
for every symbol of the code (all-symbol locality). Code C13
(from Table IV) is a binary [26, 9, 8] UUV code that is close to
an optimal binary linear code (the best known code for these
parameters has a minimum Hamming distance of 9), while the
code C14 is a UUV code where U is a [16, 5, 8] RM code (the
code R(1, 4)). Note that C becomes the RM code R(1, 5).
Due to the high computational complexity of Algorithm 1 for
C14 , we are unable to compute the maximum rate of Protocol
3 for the minimum values of β and d. Instead, we take β = Γ
and d = k and use Theorem 7 to obtain the maximum rate of
the protocol.
It is observed in Tables II and III that in the case of
noncolluding nodes Ropt is equal to the asymptotic capacity
C∞ for all tabulated codes except C6 and C7 . Furthermore,
by the nature of the optimization procedure (see Remark 1),
PIR capacity-achieving matrices Λk,n of all tabulated codes
except C6 and C7 are found. This implies that they are also
PIR capacity-achieving codes for any finite number of files
and must satisfy the necessary condition based on generalized
Hamming weights in Theorem 3. Due to the high computational complexity of Algorithm 1, it is difficult to maximize
the PIR rates of C6 and C7 . Therefore, it is an open problem
whether or not they are PIR capacity-achieving codes. For the
colluding case (see Table IV) the lower bound CLB,∞ on the
asymptotic capacity is not achieved, even after optimization.
To the best of our knowledge, GRS codes is the only known
class of codes where this bound is actually achieved [22].
On the other hand, the upper bound RUB (from (34)) is
attained in all cases. We believe that the fundamental reason
for not achieving the bound CLB,∞ is due the nature of the
protocol itself (which is tailored to MDS codes) and not the
optimization procedure.
IX. C ONCLUSION
We presented three different PIR protocols, namely Protocol 1, Protocol 2, and Protocol 3, for DSSs where data is
stored using an arbitrary linear code. We first considered the
case when no nodes in the DSS collude. Under this scenario,
Protocols 1 and 2 achieve the PIR property. We proved that,
for certain non-MDS codes, Protocol 1 achieves the finite PIR
capacity (and also the asymptotic PIR capacity) and Protocol
2, which is a much simpler protocol compared to Protocol
1, achieves the asymptotic PIR capacity. Thus, the MDS
property is not necessary in order to achieve the PIR capacity
(both finite and asymptotic). We also provided a necessary

5
6
6
6
8
16

2
2
2
2
3
3

0.3333
0.3333
0.0833
0.3333
0
0.2188

0.3333
0.3333
0.1667
0.4167
0.1538
0.5

0.3333
0.3333
0.1667
0.4167
0.1538
0.5

0.4444
0.4167
0.5833
0.5833
0.5769
0.75

and a sufficient condition for codes to be PIR capacityachieving. The necessary condition is based on generalized
Hamming weights while the sufficient condition is obtained
from automorphisms of linear codes. We proved that cyclic
codes, RM codes, and optimal information locality LRCs are
PIR capacity-achieving codes. For other codes, we provided
an optimization algorithm that optimizes PIR Protocols 1 and
2 in order to maximize their PIR rates. We also considered the
scenario where a subset of nodes in the DSS collude. For such
a scenario, we proposed Protocol 3, which is an improvement
of the PIR protocol by Freij-Hollanti et al. The improvement
allows the protocol to achieve even higher PIR rates, and
the PIR rates for non-MDS codes are no longer limited by
their code rates. Subsequently, we presented an optimization
algorithm to optimize the PIR rate of the protocol, and a family
of codes based on the classical (U | U + V) construction that
can be used with this protocol. Furthermore, we proved that
RM codes can achieve much higher PIR rates than previously
reported by Freij-Hollanti et al. Finally, we presented some
numerical results on the PIR rates for several linear codes,
including optimal all-symbol locality LRCs constructed by
Tamo and Barg.

A PPENDIX A
P ROOF OF L EMMA 1
We need to ensure that
matrix G
Pvgivenma k × n generator
m
of R(v, m) with k =
and
n
=
2
,
the
k×k
i=0 i
matrix G|I that comprises the columns of the generator matrix
indexed by the coordinates of I is invertible. We are going to
µm
elaborate on this by considering all the monomials z1µ1 · · · zm
,
µi ∈ GF(2), in a so-called graded lexicographic order, where
each vector µ = (µ1 , . . . , µm )⊤ ∈ GF(2)m×1 defines a
column of the generator matrix G according to (1). Formally
′
µm
speaking, denote z1µ1 · · · zm
by z µ . We say z µ ≺ z µ either
if wH (µ) < wH (µ′ ) or if wH (µ) = wH (µ′ ) and the topmost
nonzero entry of µ − µ′ (subtraction is over the reals) is
positive. For instance, in graded lexicographical ordering we
have z1 ≺ z2 ≺ z3 ≺ z1 z2 ≺ z1 z3 ≺ z2 z3 ≺ z1 z2 z3 for
m = 3.
Now we are ready for the proof. It is noted that a basis
of R(v, m) can be viewed as B , {1, z1 , z2 , z3 , . . . } =
′
{z µ : wH (µ′ ) ≤ v}. Let us list the monomials in B in graded
lexicographical order, and let the ℓ-th monomial fℓ (z) of the
ordered list represent the ℓ-th row of G, ℓ ∈ Nk . According
to the generator matrix construction of R(v, m), it is known
that the (ℓ, µ) entry of G is equal to the value of the ℓ-th

22

monomial fℓ (z) at z = µ [24, Ch. 13]. Furthermore, given a
column coordinate µ ∈ I, for ℓ ∈ Nk , we have
(
1 if z µ = fℓ (z),
fℓ (µ) =
0 if z µ ≺ fℓ (z).
Thus, the (z µ , µ) entry can be seen as a pivot of G|I and
G|I is obviously invertible.
A PPENDIX B
P ROOF OF T HEOREM 1
The proof is completed by showing that the following
statements are true.
File symmetry within each storage node. For all repetitions, we investigate file symmetry for every possible combination of files in each round within each storage node. In
the first round (ℓ = 1) of all κ repetitions, it follows from (9)
that, for each m′ ∈ N2:f , the downloaded number of undesired
(m′ )
symbols ys,j is equal to κU(1) = κf −1 , while for the desired
symbols, from (10), it follows that the user requests κf −1 code
(1)
symbols for ys,j . In the (ℓ + 1)-th round of all κ repetitions,
ℓ ∈ Nf −1 , arbitrarily choose a combination of files M ⊆ N2:f ,
where |M| = ℓ. It follows from (11) that the total number of
requested desired symbols for files pertaining to {1} ∪ M is
equal to



(ν − κ) U(ℓ) − 1 − U(ℓ − 1) + 1
= (ν − κ)κf −(ℓ+1) (ν − κ)ℓ−1 = κf −(ℓ+1) (ν − κ)ℓ .

On the other hand, for the undesired symbols, it follows from
(9) that in the (ℓ + 1)-th round the user requests



κ U(ℓ + 1) − 1 − U(ℓ) + 1
= κκf −(ℓ+2) (ν − κ)ℓ = κf −(ℓ+1) (ν − κ)ℓ

linear sums for a combination of files M ⊆ N2:f , |M| = ℓ+1.
Thus, in rounds Nf −1 , an equal number of linear sums for all
combinations of files M ⊆ Nf are downloaded. By construction, these are linear sums of unique code symbols pertaining
to f files. Thus, symmetry in all f −1 rounds is ensured. In the
f -th round, only desired symbols are downloaded. Since each
desired symbol is a linear combination of code symbols from
all f files, an equal number of linear sums is again downloaded
from each file. Therefore, symmetry within each node and in
each round is ensured.
The β × k file X (1) can be reliably decoded. In the first
round (ℓ = 1) of all κ repetitions, ∀ s ∈ Nκf −1 , the user
has downloaded the matrix
 (1)

(1)
yκf −1 (a1,1 −1)+s,1 · · · yκf −1 (a1,n −1)+s,n


..
..


.
···
.


(1)
(1)
yκf −1 (aκ,1 −1)+s,1 · · · yκf −1 (aκ,n −1)+s,n

of code symbols. Given an a ∈ Nν , recalling Definitions 11
and 12, it follows that for each s ∈ Nκf −1 , the coordi-
nate set S κf −1 (a − 1) + s κf −1 (Aκ×n − 1κ×n ) + s1κ×n
contains an information set. Hence, the (κf −1 (a − 1) +
1)-th, . . . , (κf −1 (a−1)+κf −1)-th stripes are recovered. Since
ai,j ∈ Nν , we know until now that the user has obtained

the 1-st, 2-nd, . . . , (κf −1 (v − 1) + κf −1 )-th stripes. Note that
κf −1 (v − 1) + κf −1 = D(0)ν. Moreover, owing to (12), in
the (ℓ′ = ℓ + 1)-th round of all κ repetitions with ℓ ∈ Nf −1 ,
∀ s ∈ ND(ℓ−1):(D(ℓ)−1) the matrices

 (1)
(1)
ys·ν+a1,1 ,1 · · · ys·ν+a1,n ,n


..
..


.
···
.


(1)
(1)
ys·ν+aκ,1 ,1 · · · ys·ν+aκ,n ,n

of code symbols are downloaded. Similarly, fix an s ∈
ND(ℓ−1):(D(ℓ)−1) . Then,
∀ a ∈ Nν , the coordinate set S sν +

a sν1κ×n + Aκ×n must contain an information set, and
the user can recover the (sν + 1)-th, . . . , (sν + ν)-th stripes.
Observe that in the last (ℓ′ = (f − 1) + 1)-th round, the row
index of the last recovered strip is equal to (D(f −1)−1)ν +ν.
Hence, the total number of stripes the user has recovered is

D(f − 1) − 1 ν + ν
"f −1 
#
X f − 1
f −(ℓ+1)
ℓ
=
κ
(ν − κ) − 1 ν + ν
ℓ
ℓ=0

= (ν f −1 − 1)ν + ν = ν f .

This indicates that the user has restored all ν f stripes for X (1) ,
and X (1) is in fact reliably reconstructed.
The PIR achievable rate is expressed as (13). According
to (9), since there are f −1
combinations of files other than
ℓ
the first file with index m = 1, the user has downloaded



f −1 
U(ℓ) − 1 − U(ℓ − 1) + 1
κ
ℓ


f − 1 f −(ℓ+1)
=κ
κ
(ν − κ)ℓ−1
ℓ


f − 1 f −ℓ
=
κ (ν − κ)ℓ−1
ℓ

undesired symbols from each storage node in the ℓ-th round,
ℓ ∈ Nf −1 . Moreover, from (10) and (11), the user has
downloaded κf −1 desired symbols from each storage node
in round ℓ = 1, and




f − 1 f −(ℓ+1)
D(ℓ) − 1 − D(ℓ − 1) + 1 =
κ
(ν − κ)ℓ
ℓ
extra desired symbols from each storage node in the (ℓ + 1)-th
round, ℓ ∈ Nf −1 . In summary, the total download cost for
Protocol 1 using Λκ,ν (C) is equal to
nd = total number of undesired symbols
+ total number of desired symbols

f
−1 
X
f − 1 f −ℓ
= κn
κ (ν − κ)ℓ−1
ℓ
ℓ=1

f
−1 
X
f − 1 f −(ℓ+1)
+κn
κ
(ν − κ)ℓ
ℓ
ℓ=0
"

f −1 
κ X f − 1 f −(ℓ+1)
κ
(ν − κ)ℓ
= κn
ν−κ
ℓ
ℓ=1
#

f
−1 
X
f − 1 f −(ℓ+1)
ℓ
+
κ
(ν − κ)
ℓ
ℓ=0

23


κ
(ν f −1 − κf −1 ) + ν f −1
ν −κ
i
κn h f −1
κν
− κf + ν f − κν f −1
=
ν − κh
i
κn
ν f − κf .
=
ν−κ
= κn



A PPENDIX D
P ROOF OF T HEOREM 2
Consider the i-th subresponse of each response rj . Out of
the n subresponses generated from the n storage nodes, there
are Γ subresponses originating from a subset of nodes J ⊂
Nn , |J | = Γ, of the form

Therefore, the PIR achievable rate R(C) is given by
R(C) =

βk
=
nd

f

κn
ν−κ

ν k
i =
h
ν f − κf

(m)

(ν−κ)k
h κn  i .
f
1 − κν

(m)

cs,j =

ai,j = k + i, if j ∈ Ii , i ∈ NΓ .

(36)

In this way, kΓ entries of Ak×n are constructed. Next, denote
the remaining nonconstructed entries in each column of Ak×n
by

1

s(j)

j ∈ Nn ,

where s(j) ≤ k is the total number of nonconstructed entries
in each column. Hence, there are in total kn − kΓ = k(n − Γ)
nonconstructed entries as follows,
o
n
. (37)
ai(1) ,1 , . . . , ai(1) ,1 , . . . , ai(n) ,n , . . . , ai(n)
1

s(1)

1

k
X

(m)

gj ′ ,j xs,j ′ ,

(39)

gj ′ ,j I(i−1)k+j ′ ,

(40)

j ′ =1

By setting κ = k and using Definition 11, we prove the
existence of Λk,ν with ν = k + min (k, dmin − 1). In fact,
given an [n, k, dmin ] code C, observe that for an interference
array Ak×n derived from a valid Λk,ν (C), S(a|A) must
contain an information set ∀ a ∈ Nν . We first choose Γ =
min (k, dmin − 1) information sets of C. Note that since every
code contains at least one information set, one can always
arbitrarily choose Γ information sets even if some of them are
repeatedly chosen. Let us denote the selected information sets
by Ii , i ∈ NΓ , and start to construct the corresponding matrix
Ak×n with

o
,
,j

(38)

Yj is referred to as code interference symbol. Considering
GC = (gl,j ), for j ∈ Nn , each code symbol and code
interference symbol have the form

A PPENDIX C
P ROOF OF L EMMA 3

n
Aj , ai(j) ,j , . . . , ai(j)

∀ j ∈ J , s ∈ Nβ .

rj,i = Yj + cs,j ,

s(n),n

If we consecutively assign {1, . . . , k} to the entries of Ak×n
in (37) and repeat this process n − Γ times, the remaining
k(n − Γ) entries of Ak×n will certainly be constructed. Note
that since we consecutively assign values of Nk and the largest
number of empty entries of each column of Ak×n is k, it
is impossible to have repeated values of Nk in each column
of the constructed Ak×n . From (36) and (37), it can be
seen that each a ∈ Nk occurs in n − Γ columns of Ak×n .
From Proposition 2, we can then say that the set S(a|A) of
cardinality n − Γ ≥ n − (dmin − 1) contains an information set.
For the remaining a ∈ Nk+1:k+Γ , (36) ensures that S(a|A)
contains an information set. Thus, this procedure will result
in a valid PIR interference matrix Ak×n . The proof is then
completed, since we can construct a PIR achievable rate matrix
Λk,k+Γ (C) from Ak×n .

Yj =

k
X

j ′ =1
(m)

where xs,j ′ is an information symbol of C, and I(i−1)k+j ′ =
Pf
Pmβ
(m)
′′
m=1
j ′′ =(m−1)β+1 ui,j xj ′′ −(m−1)β,j ′ is an interference
symbol. To obtain Γ code symbols from (38), the user requires
the knowledge of the code interference symbols Yj . This is
obtained from the remaining n − Γ subresponses of the nodes
in J , Nn \ J , which are
rj,i = Yj ,

∀j ∈ J.

(41)

From (39) and (40) we can observe that the interference symbols Yj have the same form as the code symbols of C. Since
there are Γ unknowns, solving (41) resembles ML decoding
of the code C. (41) is a full rank system in the unknowns
I1 , . . . , Ik (from the third requirement of Ê in Section V)
in GF(q ℓ ). Hence, knowing the interference symbols allows
the recovery of Γ unique (from the first requirement for Ê
in Section V) code symbols from the i-th subquery as the
user has the knowledge of Yj , j ∈ J . In a similar way,
from all subqueries, the user obtains dΓ = βk unique code
symbols pertaining to file X (m) . These βk code symbols are
part of β information sets (from the second requirement of Ê
in Section V and (18)), thus the user can recover the whole
 file
X (m) , from which it follows that H X (m) |r1 , . . . , rn = 0.
A PPENDIX E
P ROOF OF L EMMA 5

We prove the inequality by using the well-known Sylvester’s
rank inequality:7 If U is an s × k matrix and G is a matrix
of size k × n, then
rank (U G) ≥ rank (U ) + rank (G) − k.
Let C be an [n, k] code with generator matrix G. Given an
arbitrary information set I, G|I is by definition invertible (see
Definition 1). We next choose an arbitrary subcode D ⊆ C of
rank s that can be generated by U G for some s × k matrix
U of rank s.
7 The proof of this inequality is available in the literature on linear algebra,
so here we omit the proof.

24

Applying Sylvester’s rank inequality, we have
rank (U (G|I )) ≥ s + k − k = s.
Because each basis vector of the space U (G|I ) must at least
contain one nonzero component, this leads to
|I ∩ χ(D)| = |χ(D|I )| = |χ(U (G|I ))| ≥ s,
where χ(D) is the support of D (see Definition 2).
A PPENDIX F
P ROOF OF T HEOREM 4
In order to prove the theorem, we start by proving two key
lemmas (Lemmas 10 and 11 below), which will form the basis
of the overall proof of the theorem.
Lemma 10: Let C be an (r, δ)-optimal information locality
[n, k] code consisting of Lc local codes and with parity-check
matrix as in (2). Additionally, it adheres to the condition
in (24). Then, the code can simultaneously correct δ − 1 + νi
erasures in each local code C|Si , provided that the number of
global parities available is at least ν1 + · · · + νLc .
Proof: We begin by defining H C |IJ as the submatrix of
C
H restricted in columns by the set J and in rows by the set
I. For i ∈ NLc , consider the i-th local code. Let Ei denote the
set of coordinates that are erased in the i-th local code, where
|Ei | = δ − 1 + νi . Let
Ri = {(δ − 1)(i − 1) + 1, . . . , (δ − 1)i} ∪ Ai
be a set of rows of H C of cardinality |Ri | = |Ei |, where
Ai ⊂ NLc (δ−1)+1:(n−k) , |Ai | = νi , is a set of rows of H C
(which correspond to parity-check equations of the available
global parities). In order to prove the lemma one needs to
prove that

rank H C

∪i Ri
∪ i Ei



=

Lc
X
(δ − 1 + νi ).

(42)

i=1

For each i′ ∈ NLc and i′ 6= i, assume that there exists a
set Ai′ ⊂ NLc (δ−1)+1:(n−k) such that Ai ∩ Ai′ = ∅. Then, it
follows that Ri ∩ Ri′ = ∅, and since Ei ∩ Ei′ = ∅,

rank H C

∪i Ri
∪ i Ei



=

Lc
X
i=1


i
rank H C |R
Ei .

Thus, to show (42) it is sufficient to show that

i
rank H C |R
= δ − 1 + νi
Ei

(43)

for all i ∈ NLc .
To show this, consider now the [n′ , k] MDS code C ′ whose
parity-check matrix is given by H MDS in (24). Let Si′ ⊂ Nn′
denote a set of coordinates of C ′ of cardinality |Si′ | = k + δ −
1 + νi . More specifically,
Si′ = {1, . . . , k} ∪ {k + 1, . . . , k + δ − 1} ∪ Bi ,
where Bi = {a − Lc (δ − 1) + (δ − 1) + k : a ∈ Ai } ⊂ Nδ+k:n′ .
In other words, the set Si′ consists of k systematic coordinates
and δ−1+νi parity coordinates of C ′ . The punctured code Ci′ =
′
C ′ |Si′ is defined by a parity-check matrix H Ci of dimension
(δ−1+νi )×(k+δ−1+νi) that is a submatrix of H MDS . Since

the punctured code of an MDS′ code is also an MDS code [37],
Ci
Ci′ has minimum distance dmin
= δ + νi = δ + |Ai |. Note
that for some column index set J ⊂ Nk+δ−1+νi , |J | = |Ei |,
Ci′
i
one can build H C |R
Ei = H |J . From the MDS property, it
follows that


′
i
(44)
= rank H Ci |J = δ − 1 + νi .
rank H C |R
Ei
if the total number of global parities is at least
PFinally,
Lc
ν
,
we
can assign to the set Ai , i ∈ NLc , a set of νi
i=1 i
rows of H C corresponding to global parity-checks such that
the sets Ai are all disjoint, hence (43) holds for all i ∈ NLc ,
and (42) follows, which completes the proof.
Lemma 11: Consider an erasure pattern e of length n of the
form
e = (e1 , . . . , en ) = (e1 , . . . , eL , eL+1 ),
where the subvectors e1 , . . . , eL are all of length nc = r+δ−1
and eL+1 is of length r̄ = n mod nc . Let χ(ej ), j ∈ NL+1 ,
be the support of ej and t = (n − k) mod L. If |χ(e1 )| =
· · · = |χ(et )| = m1 , |χ(et+1
 )| = · · · = |χ(eL )| = m, and
and m1 = m + 1, then e
|χ(eL+1 )| = 0, where m = n−k
L
is correctable by C.
Proof: The erasure pattern e is divided into L + 1 partitions represented by ej = (enc (j−1)+1 , . . . , enc j ), j ∈ NL+1 ,
where ej , j ∈ NLc , corresponds to the coordinates of the j-th
local code, and eLc +1 , . . . , eL+1 correspond to the coordinates
of the global parities of C.
The set χ(ej ), j ∈ NL+1 , is the set of coordinates erased
from the j-th partition, and we construct the erasure patterns
ej , j ∈ NL , such that |χ(ej )| = δ − 1 + νj with
(
m1 − (δ − 1) if j ∈ Nt ,
νj =
m − (δ − 1) if j ∈ Nt+1:L ,
where t = (n − k) mod L, and let χ(eL+1 ) = ∅. In
other words, we construct the erasure patterns such that the
erasures are distributed as equally as possible across the first
L partitions.
From (27), it follows that n − k ≥ (δ − 1)Lc + (L − Lc)(r +
δ − 1) ≥ L(δ − 1) (where the last inequality follows from
L ≥ Lc ), hence δ − 1 is an integer satisfying the inequality
L(δ − 1) ≤ n − k, and subsequently δ − 1 ≤ n−k
L . The
integer m is the largest integer such that m ≤ n−k
.
Therefore,
L
δ − 1 ≤ m. To show that e is correctable it is enough to show
that the erasures in the Lc local codes can be corrected, since
in this case we have a nonerased information set for C, which
allows to correct the remaining erasures in e.
From Lemma 10, to correct δ − 1 + νj erasures in the jth local code for all j ∈ NLc , the number of global parities
available, γtot + r̄, must be
γtot + r̄ ≥
(
m1 t + m(Lc − t) − Lc (δ − 1) if t ≤ Lc ,
νj =
m1 Lc − Lc (δ − 1)
if t > Lc ,
j=1
(45)

Lc
X

where γtot is the number of global parities available in the
(Lc +1)-th, . . . , L-th partitions and r̄ = n−nc L is the number

25

of global parities in the (L + 1)-th partition. By counting the
number of global parities not erased in L − Lc partitions, we
get

(nc − m)(L − Lc )
if t ≤ Lc ,
γtot =
(nc − m1 )(t − Lc ) + (nc − m)(L − t) if t > Lc .
(46)

By substituting (46) into (45), we get (after performing some
simple arithmetic) the condition
n − k − mL ≥ t,

which is valid for both cases of t (t ≤ Lc and t > Lc ). By
definition of t and m, the above inequality is met with equality,
and it follows that e is a correctable erasure pattern.

Due to the cyclic shifts, for j ∈ NL , all the j-th subvectors of
(l+1)
in partition l + 1, l ∈ NL−1 , have support
the vectors ei
(l)
(l+1)
size |χ(ei,j )| = |χ(ei,σ−1 (j) )|. Thus, there exist two indices
′ ′′
′
′′
j , j ∈ NL , j 6= j , such that
(l+1)

(l)

(l)

(l+1)

|χ(ei,j ′ )| − |χ(ei,j ′ )| = |χ(ei,j ′′ )| − |χ(ei,j ′′ )|,
(l+1)

|χ(ei,j

(l)

∀ j ∈ NL \ {j ′ , j ′′ }.
(48)

)| = |χ(ei,j )|,

One can see that there are at most 4 (depending on t and Lc )
choices for the pair (j ′ , j ′′ ) as follows.
(l+1)
−
Case 1. j ′ , j ′′ ∈ NLc : From (48), it follows that νj ′
(l+1)
(l)
(l)
(l+1)
(l+1)
(l)
(l)
= νj , and γtot = γtot . Thus,
νj ′ = νj ′′ − νj ′′ , νj
P c (l+1) PLc (l)
(l+1)
(l)
= j=1 νj = γtot + r̄ = γtot + r̄.
we have L
j=1 νj
(l+1)

A. Completion of the Proof
Let Ẽ, W , Z, and O be submatrices of E as shown
in Section VI-D. We begin the proof by proving
that each

of the nc L rows of the matrix Ẽ | Z are correctable
erasure patterns, where Ẽ is defined in (26). This is proved
by induction on the row partitions of Ẽ | Z .

Base Case. Consider the first row-wise partition of Ẽ | Z ,
given by

π1 π2 · · · πL 0nc ×r̄ .
(1)

For each row vector ei , i ∈ Nnc , in this partition, where
the subscript i indicates the row index and the superscript the
(1)
(1)
partition, consider the subvectors ei,1 , . . . , ei,L . From Step a)
(1)
in Section VI-D, for all i ∈ Nnc , the j-th subvectors ei,j
(1)
have support of cardinality |χ(ei,j )| = m1 for all j ∈ Nt ,
(1)
where t = (n − k) mod L, |χ(ei,j )| = m for j ∈ Nt+1:L ,
(1)
(1)
and |χ(ei,L+1 )| = 0. Thus, the vectors ei in the first row
wise partition of Ẽ | Z have the same structure as the
erasure pattern e from Lemma 11 and are therefore erasure
patterns that are correctable by C. Note that the number of
global parities available in the (Lc +1)-th, . . . , L-th subvectors
(1)
(1)
(1)
(1)
of vector ei , γtot , is γtot = γtot , hence γtot + r̄ = γtot +
PLc
(1)
r̄ ≥ j=1 νj and from Lemma 11 the error pattern ei is
correctable.
(l)

Inductive Step. Assume that the
 vectors ei , i ∈ Nnc , in the
l-th row-wise partition of Ẽ|Z are correctable by C and that
(l)
each local code C|Sj can correct δ −1+νj erasures, j ∈ NLc .
The row vectors are taken from the matrix

πσl−1 (1) πσl−1 (2) · · · πσl−1 (L) 0nc ×r̄ ,

where σ , (L (L − 1) · · · 1) denotes a cycle whose mapping
is L 7→ (L − 1) 7→ · · · 7→ 1 7→ L. The (L + 1)-th subvectors
(l)
satisfy |χ(ei,L+1 )| = 0. From Lemma 10, the underlying
(l)
characteristic of the vectors ei is that they are correctable
erasure patterns if the number of global parities not erased in
PL (l)
(l)
(l)
ei , γtot + r̄, is larger than or equal to j c νj .

In the (l + 1)-th row-wise partition of Ẽ|Z , the nc rows
have the form

πσl (1) πσl (2) · · · πσl (L) 0nc ×r̄ .
(47)

Case 2. j ′ , j ′′ ∈ NLc +1:L : From (48), it follows that γtot =
PLc (l+1)
PLc (l+1) PLc (l)
(l)
=
= j=1 νj . Therefore, j=1
νj
νj
γtot and j=1
(l+1)
γtot + r̄.

Case 3. j ′ ∈ NLc , j ′′ ∈ NLc +1:L : From (48), it follows that
(l+1)
(l)
(l+1)
(l)
νj ′
− νj ′ = γtot − γtot . Moreover, it can be seen that
P
P
(l)
(l+1)
= j6=j ′ ,j∈NLc νj . Hence, we have
j6=j ′ ,j∈NLc νj
Lc
X

(l+1)

νj

=

X

(l+1)

(l+1)

+ νj ′

(l+1)

+ (νj ′

νj

j6=j ′ ,j∈NLc

j=1

=

X

νj

(l+1)

(l)

(l)

− νj ′ ) + νj ′

j6=j ′ ,j∈NLc

=

X

(l)

(l+1)

νj + (γtot

(l)

(l)

− γtot ) + νj ′

j6=j ′ ,j∈NLc

=

Lc
X

(l)

(l)

(l+1)

− γtot )

(l+1)

− γtot )

νj + (γtot

j=1

(b)

(l)

= γtot + r̄ + (γtot

(l)

(l+1)

= γtot

where (b) holds since

+ r̄,
PLc

j=1
′′

(l)

(l)

νj = γtot + r̄.

Case 4. j ′ ∈ NLc +1:L , j ∈ NLc : Following an argumentation
PLc (l+1)
(l+1)
= γtot + r̄.
νj
similar to Case 3, we have j=1
In each
the above cases we see that the condition γtot +
PLcof (l+1)
is satisfied (with equality). From the proof of
r̄ ≥ j νj
Lemma
11,
the
n
c rows in the (l + 1)-th row-wise partition of

Ẽ|Z are correctable by C, which completes the inductive
step.
The rows of (W | O) as shown in Step a) in Section VI-D
have support corresponding to only the parity symbols of C.
Thus, these rows are all correctable by C, and it follows from
the above arguments that each row of E is an erasure pattern
that is correctable by C.
Note, however, that E is still not an (n − k)-regular matrix.
To make E regular, Step b) of Section VI-D is performed.
The transformation of certain rows as performed in Step b) of
Section VI-D does not make these rows uncorrectable by C.
Indeed, notice that in the s-th row of Ej ′ , j ′ ∈ Nr̄ , s ∈ Nτ
(all rows in Ej ′ are correctable from the discussion above),
there is a swap of a 1-entry from some column with an entry

26

in a column of coordinate in PL+1 that pertains to a global
parity symbol. Thus, the counting argument in the proof of
Lemma 11 still holds true and such rows (after the swapping
operation) are still correctable erasure patterns. This completes
the proof.
A PPENDIX G
P ROOF OF T HEOREM 6

The k-th row of GC̃i can be written as

To prove the theorem we need the following lemma.
Lemma 12: Let C be a binary [n = 2n1 , k = k1 + 1] code
constructed from an [n1 , k1 ] code U through the (U | U + V)
construction, where V is an [n, 1] binary repetition code. The
generator matrix GC of C is given in (35). Let C¯ = C and
GC̄ = GC . Then, the code C˜ = C ◦ C¯ is a vector space of
dimension
(

k1 + n1 + 1
if n1 − k1 ≤ k21 ,
˜

dim(C) ≤
(49)
2k1 + k21 + 1 otherwise.

Proof: From Definition 4, we know that c̃ ∈ C˜ has the
form c̃ = (c1 c̄1 , . . . , cn c̄n ), where c = (c1 , . . . , cn ) ∈ C and
¯ Considering GC = (g c ) and GC̄ =
c̄ = (c̄1 , . . . , c̄n ) ∈ C.
i,j
c̄
(gi,j ), the vector space C˜ is spanned by the row space of

 c c̄
c
c
g1,1 g1 g1,2
g2c̄ · · · g1,n
gnc̄
c
c
c
g2,1
g1c̄ g2,2
g2c̄ · · · g2,n
gnc̄ 


C̃
(50)
G = .
..
..  ,
 ..
.
···
. 
c
c
c
gnc̄
g2c̄ · · · gk,n
g1c̄ gk,2
gk,1

where the vector gjc̄ , j ∈ Nn , denotes the j-th column
vector of GC̄ . The matrix GC̃ is a matrix consisting of k 2
˜ of length
row vectors (corresponding to codewords of C)
C̃
C̃
n. We divide G into k submatrices Gi , where GC̃i =
c
c
c
gnc̄ ), i ∈ Nk (see (50)). From (35) and
g2c̄ | . . . |gi,n
(gi,1
g1c̄ |gi,2
c̄
C
c
= 0, j ∈ Nn1 ,
= gk,j
since G = GC̄ , we have gk,j
c
c̄
and gk,j = gk,j = 1, j ∈ Nn1 +1:n . Therefore, (50) can be
expanded to


GC̃ =

 c̄ 
g1,1
c̄ 

 g2,1



 c  . 
g1,1  .. 

 c̄ 


gk1 ,1 


0

 c̄ 

g1,1


c̄ 

g2,1 

 c 
.. 
g 
. 
 2,1 



g c̄ 

k1 ,1


0

..


 . c̄ 


g1,1

c̄ 
 g2,1




 0  .. 
 . 




c̄
g 

k1 ,1
0

···

···

···

···

U




c̄
g1,n
1
c̄
 g2,n

1


 .. 
c
g1,n
 . 
1
 c̄

g

k1 ,n1
0
 c̄ 
g1,n1
c̄
 g2,n

1 

 .. 
c
g2,n1  . 


g c̄

k1 ,n1
0
..
. c̄ 
g1,n1
c̄
 g2,n

1 



0  ... 


g c̄

k1 ,n1
0




c̄
g1,n
1 +1
c̄
 g2,n

+1
1




..
c
g1,n


1 +1
 c̄ .

g

k1 ,n1 +1
1
 c̄

g1,n1 +1
c̄
 g2,n

1 +1 



..
c
g2,n


+1
.
1


g c̄

k1 ,n1 +1
1
..
. c̄

g1,n1 +1
c̄
 g2,n

1 +1 



...
1



g c̄

k1 ,n1 +1
1

···

···

···

···


c̄
g1,n
c̄ 
 g2,n


c  .. 
g1,n
 . 
 c̄ 
g

k1 ,n 

1
 c̄ 
g1,n 

c̄ 
 g2,n



c  .. 
g2,n  . 

.
g c̄ 
k1 ,n 

1

..


.
 c̄ 
g1,n 

c̄ 
 g2,n


 .. 
1  . 


g c̄ 
k1 ,n
1


(51)

u
)
(gi,j

be the generator matrix of U.
Furthermore, let G =
u
c̄
c
for i ∈ Nk1 and
= gi,j
= gi,j
From (35), we have gi,j
j ∈ Nn1 . For i, j ∈ Nk , we denote the i-th row of the j(j)
th submatrix GC̃j as wi . For i ∈ Nk−1 , the i-th row of the
i-th submatrix GC̃i is given as
(i)

(i)

c̄
c
=
Since gi,j
= gi,j
∈ GF(2), (52) reduces to wi
c
c
c
c
(gi,1 , gi,2 , . . . , gi,n ). Furthermore, from (35) we see that gi,j
=
c
u
gi,n
= gi,j
, j ∈ Nn1 , i ∈ Nk1 . Therefore, these k1 = k − 1
1 +j
rows form the k1 basis vectors of the code space (U, U) and
can be arranged in a matrix as

GU GU .
(53)

c
c̄
c
c̄
c
c̄
gi,1
, gi,2
gi,2
, . . . , gi,n
gi,n
).
wi = (gi,1

(52)

n

(i)
wk

z }|1 {
c
c
c
, gi,n
, . . . , gi,n
)
= (0, 0, . . . , 0, gi,n
1 +1
1 +2
(c)

u
u
u
),
= (0, 0, . . . , 0, gi,1
, gi,2
, . . . , gi,n
1

where (c) results from the structure of GC in (35). Stacking
together the k-th row of all k1 submatrices GC̃i , i ∈ Nk1 ,
results in the k1 row vectors

0k1 ×n1 GU .
(54)
(k)

In a similar way, the rows wi , i ∈ Nk , of the k-th submatrix
GC̃k result in the matrix


GU
0k1 ×n1
.
(55)
01×n1 11×n1
¯
Of the remaining
 (k − 1)(k − 2) rows in (51), since C = C,
k1
there exist 2 distinct rows as follows,
 c c̄

c
c̄
c
c̄
g1,1 g2,1
g1,2
g2,2
···
g1,n
g2,n
c
c̄
c
c̄
 g c g c̄

g1,2
g3,2
···
g1,n
g3,n
 1,1 3,1



..
..
..


.
.
···
.


c
c̄
c
c̄
 g c g c̄
g1,2 gk1 ,2
···
g1,n gk1 ,n 
 1,1 k1 ,1

 c c̄

c
c̄
c
c̄
 g2,1 g3,1
g2,2 g3,2
···
g2,n g3,n 
.
Θ=


..
..
..


.
.
·
·
·
.


c
c̄
c
c̄
 g c g c̄

g
g
·
·
·
g
g
2,2 k1 ,2
2,n k1 ,n 
 2,1 k1 ,1




..
..
..


.
.
·
·
·
.


c̄
c
c̄
c
c̄
c
gk1 −1,1 gk1 ,1 gk1 −1,2 gk1 ,2 · · · gk1 −1,n gk1 ,n

Furthermore, from the construction of C in (35), we have
c
c
u
u
c
c
),
) = (gi,n
, . . . , gi,n
) = (gi,1
, . . . , gi,n
(gi,1
, . . . , gi,n
1 +1
1
1
c̄
c̄
¯
i ∈ Nk1 and because C = C, we have (gi,1 , . . . , gi,n1 ) =
c̄
c̄
(gi,n
, . . . , gi,n
). Therefore,
1 +1


(56)
Θ = θ(k21 )×n1 θ(k21 )×n1 ,

where θ(k1 )×n1 is a binary matrix of size k21 × n1 .
2
From (53)–(56), GC̃ can be written as


GU
GU
 0k1 ×n1
GU 


C̃

GU  .
G =  0k1 ×n1

θ(k1 )×n1 θ(k1 )×n1 
2
2
11×n1
01×n1
Using Gaussian elimination, GC̃ can be reduced to


GU
0k1 ×n1
 0k1 ×n1
GU 


C̃
0k1 ×n1  .
0
G =

 k1 ×n1
θ(k1 )×n1 θ(k1 )×n1 
2
2
11×n1
01×n1

(57)

27


Let GU = Ik1 |Pk1 ×(n1 −k1 ) , where Pk1 ×(n1 −k1 ) is the
parity matrix of size k1 × (n1 − k1 ). We now count the
number of independent rows in the matrix
!
!
Ik1 Pk1 ×(n1 −k1 )
GU
.
θ(k1 )×n1 =
θ(k1 )×n1
2
2

Upon performing Gaussian elimination, we get
!
Pk1 ×(n1 −k1 )
Ik1
0(k1 )×k1 ∆(k1 )×(n1 −k1 ) ,
2

2


where ∆(k1 )×(n1 −k1 ) is a matrix of dimension k21 × (n1 −
2
k1 ) with elements in
 GF(2). Hence, we have rank (∆) ≤
min k21 , (n1 − k1 ) . From this and (57), we can easily see
that

˜ = rank GC̃
dim(C)
= k1 + k1 + rank (∆) + 1
(
k1 + n1 + 1
if n1 − k1 ≤

≤
k1
2k1 + 2 + 1 otherwise.

k1
2


,

˜ In
Lemma 12 gives an upper bound on the dimension of C.
˜
order to prove dim(C) < n, we check when the upper bound
in (49) is at most n − 1. For the first case in (49), we need to
show
˜ ≤ k1 + n1 + 1 ≤ 2n1 − 1.
dim(C)
Clearly, this is true since n1 ≥ k1 + 2 by assumption. For the
second case in (49) we have to show
 
k1
˜
+ 1 ≤ 2n1 − 1.
dim(C) ≤ 2k1 +
2

Since n1 > k21 + k1 , the above inequality reduces to
 
k1
> 2.
2

Clearly, this is true for k1 ∈ N3:∞ . In the following, we argue
for k1 ∈ N2 . Since n1 ≥ k1 + 2 by assumption, we have
 
k1
+ 1,
2n1 − 1 ≥ 2(k1 + 2) − 1 = 2k1 + 3 > 2k1 +
2
˜ < n for n1 ≥ k1 + 2.
for k1 ∈ N2 . Therefore, dim(C)
R EFERENCES
[1] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Private information retrieval,” in Proc. Annual IEEE Symp. Foundations Comp. Sci.
(FOCS), Milwaukee, WI, Oct. 1995, pp. 41–50.
[2] ——, “Private information retrieval,” Journal of the ACM, vol. 45, no. 6,
pp. 965–981, Nov. 1998.
[3] A. Beimel, Y. Ishai, E. Kushilevitz, and J.-F. Raymond, “Breaking
the O(n1/(2k−1) ) barrier for information-theoretic private information
retrieval,” in Proc. Annual IEEE Symp. Foundations Comp. Sci. (FOCS),
Vancouver, BC, Canada, Nov. 2002, pp. 261–270.
[4] S. Yekhanin, “Towards 3-query locally decodable codes of subexponential length,” Journal of the ACM, vol. 55, no. 1, pp. 1–16, Feb. 2008.
[5] K. Efremenko, “3-query locally decodable codes of subexponential
length,” in Proc. 41th Annual ACM Symp. Theory Comput. (STOC),
Bethesda, MD, Jun. 2009, pp. 39–44.
[6] Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai, “Batch codes and
their applications,” in Proc. 36th Annual ACM Symp. Theory Comput.
(STOC), Chicago, IL, Jun. 2004, pp. 262–271.

[7] N. B. Shah, K. V. Rashmi, and K. Ramchandran, “One extra bit of
download ensures perfectly private information retrieval,” in Proc. IEEE
Int. Symp. Inf. Theory (ISIT), Honolulu, HI, Jun./Jul. 2014, pp. 856–860.
[8] T. H. Chan, S.-W. Ho, and H. Yamamoto, “Private information retrieval
for coded storage,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Hong
Kong, China, Jun. 2015, pp. 2842–2846.
[9] A. Fazeli, A. Vardy, and E. Yaakobi, “Codes for distributed PIR with low
storage overhead,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Hong
Kong, China, Jun. 2015, pp. 2852–2856.
[10] H. Sun and S. A. Jafar, “The capacity of private information retrieval,”
IEEE Trans. Inf. Theory, vol. 63, no. 7, pp. 4075–4088, Jul. 2017.
[11] K. A. Banawan and S. Ulukus, “The capacity of private information
retrieval from coded databases,” Sep. 2016, arXiv:1609.08138v1 [].
[Online]. Available: http://arxiv.org/abs/1609.08138
[12] R. Tajeddine and S. El Rouayheb, “Private information retrieval from
MDS coded data in distributed storage systems,” in Proc. IEEE Int.
Symp. Inf. Theory (ISIT), Barcelona, Spain, Jul. 2016, pp. 1411–1415.
[13] Q. Wang and M. Skoglund, “Linear symmetric private information
retrieval for MDS coded distributed storage with colluding
servers,” Aug. 2017, arXiv:1708.05673v1 []. [Online]. Available:
https://arxiv.org/abs/1708.05673
[14] ——, “Secure symmetric private information retrieval from colluding
databases with adversaries,” Jul. 2017, arXiv:1707.02152v1 [].
[Online]. Available: https://arxiv.org/abs/1707.02152
[15] H. Sun and S. A. Jafar, “The capacity of robust private information
retrieval with colluding databases,” May 2016, arXiv:1605.00635v1
[]. [Online]. Available: https://arxiv.org/abs/1605.00635
[16] C. Huang, M. Chen, and J. Li, “Pyramid codes: Flexible schemes to
trade space for access efficiency in reliable data storage systems,” in
Proc. IEEE Int. Symp. Net. Comp. Appl. (NCA), Cambridge, MA, Jul.
2007, pp. 79–86.
[17] M. Sathiamoorthy, M. Asteris, D. Papailiopoulos, A. G. Dimakis,
R. Vadali, S. Chen, and D. Borthakur, “XORing elephants: Novel erasure
codes for big data,” in Proc. 39th Very Large Data Bases Endowment
(VLDB), Trento, Italy, Aug. 2013, pp. 325–336.
[18] C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li,
and S. Yekhanin, “Erasure coding in Windows Azure storage,” in Proc.
USENIX Annual Tech. Conf., Boston, MA, Jun. 2012.
[19] G. M. Kamath, N. Prakash, V. Lalitha, and P. V. Kumar, “Codes with
local regeneration and erasure correction,” IEEE Trans. Inf. Theory,
vol. 60, no. 8, pp. 4637–4660, Aug. 2014.
[20] I. Tamo and A. Barg, “A family of optimal locally recoverable codes,”
IEEE Trans. Inf. Theory, vol. 60, no. 8, pp. 4661–4676, Aug. 2014.
[21] S. Kumar, E. Rosnes, and A. Graell i Amat, “Private information retrieval
in distributed storage systems using an arbitrary linear code,” in Proc
IEEE Int. Symp. Inf. Theory (ISIT), Aachen, Germany, Jun. 2017, pp.
1421–1425.
[22] R. Freij-Hollanti, O. Gnilke, C. Hollanti, and D. Karpuk,
“Private information retrieval from coded databases with colluding
servers,” Aug. 2017, arXiv:1611.02062v3 []. [Online]. Available:
https://arxiv.org/abs/1611.02062
[23] R. Freij-Hollanti, O. Gnilke, C. Hollanti, A.-L. Horlemann-Trautmann,
D. Karpuk, and I. Kubjas, “Reed-Muller codes for private information
reterival,” in Proc. 10th Int. Workshop Coding Cryptography (WCC),
Saint-Petersburg, Russia, Sep. 2017.
[24] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting
Codes. Amsterdam, The Netherlands: North-Holland, 1977.
[25] V. K. Wei, “Generalized Hamming weights for linear codes,” IEEE
Trans. Inf. Theory, vol. 37, no. 5, pp. 1412–1418, Sep. 1991.
[26] R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed. Cambridge
University Press, 2013.
[27] I. S. Reed, “A class of multiple-error-correcting codes and the decoding
scheme,” Trans. IRE Prof. Gro. Inf. Theory, vol. 4, no. 4, pp. 38–49,
Sep. 1954.
[28] J. D. Key, T. P. McDonough, and V. C. Mavron, “Information sets and
partial permutation decoding for codes from finite geometries,” Finite
Fields Th. App., vol. 12, no. 2, pp. 232–247, Jun. 2006.
[29] M. Blaum, J. Brady, J. Bruck, and J. Menon, “EVENODD: An efficient
scheme for tolerating double disk failures in RAID architectures,” IEEE
Trans. Comput., vol. 44, no. 2, pp. 192–202, Feb. 1995.
[30] H. Sun and S. A. Jafar, “Private information retrieval from MDS coded
data with colluding servers: Settling a conjecture by Freij-Hollanti et
al.” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Aachen, Germany, Jun.
2017, pp. 1893–1897.
[31] W. C. Huffman and V. Pless, Eds., Fundamentals of Error-Correcting
Codes. Cambridge, UK: Cambridge University Press, 2010.

28

[32] P. Delsarte, J. M. Goethals, and F. J. MacWilliams, “On generalized
Reed-Muller codes and their relatives,” Inf. Contr., vol. 16, no. 5, pp.
403–442, Jul. 1970.
[33] J. L. Fan, “Array codes as low-density parity-check codes,” in Proc. 2nd
Int. Symp. Turbo Codes & Rel. Topics (ISTC), Brest, France, Sep. 2000,
pp. 543–546.
[34] K. Yang and T. Helleseth, “On the minimum distance of array codes as
LDPC codes,” IEEE Trans. Inf. Theory, vol. 49, no. 12, pp. 3268–3271,
Dec. 2003.

[35] J. Hao and S.-T. Xia, “Constructions of optimal binary locally repairable
codes with multiple repair groups,” IEEE Commun. Lett., vol. 20, no. 6,
pp. 1060–1063, Jun. 2016.
[36] E. Rosnes, M. A. Ambroze, and M. Tomlinson, “On the minimum/stopping distance of array low-density parity-check codes,” IEEE
Trans. Inf. Theory, vol. 60, no. 9, pp. 5204–5214, Sep. 2014.
[37] C. Feyling, “Punctured maximum distance separable codes,” Electron.
Lett., vol. 29, no. 5, pp. 470–471, Mar. 1993.

