Private Information Retrieval with Side Information

arXiv:1709.00112v1 [] 1 Sep 2017

Swanand Kadhe, Brenden Garcia, Anoosheh Heidarzadeh, Salim El Rouayheb, and Alex Sprintson
Abstract— We study the problem of Private Information
Retrieval (PIR) in the presence of prior side information. The
problem setup includes a database of K independent messages
possibly replicated on several servers, and a user that needs
to retrieve one of these messages. In addition, the user has
some prior side information in the form of a subset of M
messages, not containing the desired message and unknown to
the servers. This problem is motivated by practical settings in
which the user can obtain side information opportunistically
from other users or has previously downloaded some messages
using classical PIR schemes. The objective of the user is to
retrieve the required message without revealing its identity
while minimizing the amount of data downloaded from the
servers.
We focus on achieving information-theoretic privacy in two
scenarios: (i) the user wants to protect jointly its demand
and side information; (ii) the user wants to protect only the
information about its demand, but not the side information. To
highlight the role of side information, we focus first on the case
of a single server (single database). In the first scenario, we
prove that the minimum download cost is K − M messages,
and in the second scenario it is ⌈ MK+1 ⌉ messages, which should
be compared to K messages, the minimum download cost in the
case of no side information. Then, we extend some of our results
to the case of the database replicated on multiple servers. Our
proof techniques relate PIR with side information to the index
coding problem. We leverage this connection to prove converse
results, as well as to design achievability schemes.

I. I NTRODUCTION
Consider the following Private Information Retrieval (PIR)
setting first studied in [1], [2]: a user wishes to privately
download a message belonging to a database with copies
stored on a single or multiple remote servers, without revealing which message it is requesting. In a straightforward
PIR scheme, the user would download all the messages in
the database. This scheme may not be feasible due to the
its high communication cost. In the case of a single server
(i.e., there is only one copy of the database), it can be
shown that downloading the whole database is necessary
to achieve perfect privacy in an information-theoretic sense.
If computational (cryptographic) privacy is desired, then
PIR schemes with lower communication overhead do exist
[3], [4], but they do not offer information-theoretic privacy
guarantees and usually have high computational complexity.
Swanand
Kadhe,
Brenden
Garcia,
Anoosheh
Heidarzadeh,
and Alex Sprintson are with the Department of Electrical
and Computer Engineering at Texas A&M University, USA;
emails:{swanand.kadhe,brendengarcia,anoosheh,spalex}@tamu.edu.
Salim El Rouayheb is with ECE Department at Rutgers University, email:
sye8@soe.rutgers.edu. Part of this work was done while he was with the
ECE department at the Illinois Institute of Technology.
The work of S. El Rouayheb was supported in part by NSF Grant CCF
1652867 and ARL Grant W911NF-17-1-0032.

In contrast, in this paper, we design and analyze schemes
that achieve information-theoretic privacy.
Interestingly, more efficient PIR schemes, achieving perfect information-theoretic privacy, can be constructed when
the database is replicated on multiple servers with restriction
on the servers’ collusion. This replication-based model has
been the one that is predominantly studied in the PIR
literature, with breakthrough results in the past few years
(e.g., [5]–[10]). Recently, there has been a renewed interest
in PIR for the case in which the data is stored on the servers
using erasure codes, which result in better storage overhead
compared to the traditional replication techniques [11]–[18].
In this paper, we study the PIR problem when the user
has prior side information about the database. In particular,
we assume that the user already has a random subset of the
database messages that is unknown to the server(s)1 . This
side information could have been obtained in several ways.
For example, the user could have obtained these messages
opportunistically from other users in its network, overheard
them from a wireless broadcast channel, or downloaded them
previously through classical PIR schemes. The next example
illustrates how this side information could be leveraged to
devise efficient PIR schemes. In particular, the following
example shows that perfect information-theoretic privacy can
be achieved with a single server case without having to
download the entire database.
Example 1 (single-server PIR with side information). Consider a remote server that has a database formed of an even
number of binary messages denoted by X1 , . . . , XK of equal
length. A user wants to download one of these messages
from the server without revealing to the server which one.
Moreover, the user has one message as side information
chosen uniformly at random among all the other messages
and unknown to the server. We propose two PIR schemes
that leverage the side information and compare them to the
straightforward scheme that downloads all the K messages.
1) Maximum Distance Separable (MDS) PIR scheme.
This scheme downloads K − 1 messages. The user
sends to the server the number of messages in its side
information (one in this example). The server responds
by coding all the messages using a (2K − 1, K)
systematic MDS code and sending the K − 1 parity
symbols of the code. Therefore, the user can always
decode all the messages using its side information and
the coded messages received from the server.
1 We assume that this side information subset does not contain the desired
message. Otherwise, the problem is degenerate.

2) Partition and Code PIR scheme. This scheme downloads K/2 messages. Suppose the message the user
wants is XW and the one in its side information is
XS for some W, S ∈ {1, . . . , K}, W 6= S. The user
chooses a random partition of {1, . . . , K} formed only
of sets of size 2 and containing {W, S}, and sends
indices of all pairs in the partition to the server. The
server sends back the XOR of the messages indexed
by each subset. For example, suppose W = 1 and
S = 2, i.e, the user wants X1 and has X2 as side
information. The user chooses a random partition
{{i1 , i2 }, {i3, i4 }, . . . , {iK−1 , iK }} and sends it to the
server. The partition is chosen such that {1, 2} is a
part of the partition (i.e., ij = 1 and ij+1 = 2 for
some j ∈ {1, 3, . . . , K − 1}. The server responds
with Xi1 + Xi2 , . . . , XiK−1 + XiK . The user can
always decode because it always receives XW + XS .
Intuitively, perfect privacy is achieved here because the
index of the desired message can be in any subset of
the partition, and in each subset it could be either one
of messages in the subset, since the server does not
know the index of the side information.
We will show later that the two schemes above are optimal
but achieve different privacy constraints. The MDS PIR
scheme protects both the indices of the desired message and
that of the side information, whereas the Partition and Code
scheme protects only the former.
A. Our Contributions
We consider the PIR with side information problem as illustrated in Example 1. A user wishes to download a message
from a set of K messages that belong to a database stored on
a single remote server or replicated on several non-colluding
servers. The user has a random subset of M messages as
side information. The identity of the messages in this subset
is unknown to the server. We focus on PIR schemes that
achieve information-theoretic privacy. The figure of merit
that we consider for the PIR schemes is the download rate,
which dominates the total communication rate (download
plus upload) for large message sizes. Under this setting,
we distinguish between two types of privacy constraints:
(i) hiding both the identity of the requested message and
that of the side information from the server; and (ii) hiding
only the identity of the desired message. The latter, and
less stringent, privacy constraint is justified when the side
information is obtained opportunistically given that it is
random and assumed to be independent of the user’s request.
In the case in which the side information messages were
obtained previously through PIR, this constraint implies that
the identity of these messages may be leaked to the server(s).
However, this type of privacy can still be relevant when
privacy is only desired for a certain duration of time, i.e.,
when the user is ambivalent about protecting the identity of
messages downloaded as long as it has happened far enough
in the past.

First, we focus on the single server scenario as the canonical case to understand the role of side information in PIR.
We characterize the capacity of PIR with side information
in the case of a single server for the two privacy constraints
mentioned above. We show that when protecting both the
side information and the request, the minimum download
rate2 for PIR is (K − M )−1 , and this can be achieved by
a generalization of the MDS PIR scheme in Example 1.
Moreover, we show that when only protecting the request,
K
⌉−1 , and this can be
the minimum download rate is ⌈ M+1
achieved by a generalization of the Partition and Code PIR
scheme in Example 1. We present achievability and converse
proofs that use among others connections to index coding.
Second, we tackle the case of N > 1 servers storing replicas
of the database. In this case, when (M + 1) | K, we devise a
PIR scheme with side information that achieves a download
rate equal to

−1
1
1
1+
.
+ ···+
K
N
N M +1 −1
Our scheme for the multiple servers uses ideas from the
single server scheme in conjunction with the scheme due
to Sun and Jafar [5] for settings with no side information.
B. Related Work
The initial work on PIR in [1], [2] and in the literature that
followed focused on designing PIR schemes for replicated
data that have efficient communication cost accounting for
both the size of the user queries and the servers’ responses.
PIR schemes with communication cost that is subpolynomial
in the number of messages were devised in [9] and [19].
Information-theoretic bounds on the download rate (servers’
responses) and achievable schemes were devised in [5] and
[6]. Recently, there has been a growing body of work
studying PIR for coded data motivated by lower overhead
of codes [11]–[18], [20], [21].
The role of side information in improving PIR schemes has
so far received little attention in the literature. The closest
work to ours is the concurrent work of Tandon [22] in which
the capacity of cache-aided PIR is characterized. The main
difference with the model in [22] is our assumption that the
indices of the side information messages are unknown to the
servers, as is the case in the scenarios mentioned above. This
lack of knowledge at the servers can be leveraged to reduce
the communication cost of PIR even in the case of a single
server. We also restrict our study to side information that is
subset of the data, whereas the cache model in [22] allows
any function of the data. Another related line of work is
that of private broadcasting by Karmoose et al. [23], which
considers the index coding setting with multiple users with
side information and a single server. Here too, the server
does know the content of the side information at the users.
Moreover, the privacy constraint is to protect the request and
side information of a user from the other users through a
2 The download rate is defined as the inverse of the normalized download
cost.

carefully designed encoding matrix. In contrast, the goal of
our scheme is to protect the identity of the requested data
from the server. We also note that the case in which the side
information is unknown at the server was also considered in
the index coding literature under the name of blind index
coding [24]. However, the goal there was to minimize the
broadcast rate without privacy constraints.
II. P ROBLEM F ORMULATION

AND

M AIN R ESULTS

For a positive integer K, denote {1, . . . , K} by [K].
For a set {X1 , . . . , XK } and a subset S ⊂ [K], let
XS = {Xj : j ∈ S}. For a subset S ⊂ [K], let 1S denote the
characteristic vector of the set S, which is a binary vector
of length K such that, for all j ∈ [K], its j-th entry is 1
if j ∈ S, otherwise it is 0. Let Fq denote the finite field of
order q.
We assume that the database consists of a set of K
messages X = {X1 , . . . , XK }, with each message being
independently and uniformly distributed over F2t (i.e., each
message Xj is t bits long). We also assume that there are
N ≥ 1 non-colluding servers which store identical copies of
the K messages.
A user is interested in downloading a message XW for
some W ∈ [K]. We refer to W as the demand index and
XW as the demand. The user has the knowledge of a subset
XS of the messages for some S ⊂ [K], |S|= M , M < K.
We refer to S as the side information index set and XS as
the side information.
Let W and S denote the random variables corresponding
to the demand index and the side information index set. We
restrict our attention to the class of distributions pW (·) of
W such that pW (W ) > 0 for every W ∈ [K].
An important distribution of W and S that we focus on
in this work is as follows. Let the demand index W be
distributed uniformly over [K], i.e.,
1
,
(1)
K
for all W ∈ [K]. Further, let the side information index set
S have the following conditional distribution given W :
(
1
, if W 6∈ S and |S|= M,
(K−1
M )
(2)
pS|W (S|W ) =
0,
otherwise.
pW (W ) =

We note that this implies the following joint distribution on
(W, S):
(
1
W 6∈ S, |S|= M,
K ,
(K−M)(M
)
pW,S (W, S) =
(3)
0,
otherwise.
We assume that the servers do not know the side information
realization at the user and only know the a priori distributions pW (W ) and pS|W (S|W ).
To download the message XW given the side information
[W,S]
from an alphabet Q to the
XS , the user sends a query Qj
j-th server. The j-th server responds to the query it receives
[W,S]
over an alphabet A. We refer to the
with an answer Aj
set of queries and answers as the PIR with side information

(PIR-SI) scheme. Our focus in this paper is on non-interactive
(single round) schemes. Further, we assume that the servers
do not collude with each other. A PIR-SI scheme should
satisfy the following requirements.
[W,S]
to the server j is a
1. For every j ∈ [N ], the query Qj
(potentially stochastic) function of W , S, and XS . We
assume that the answer from the server is a deterministic
function of the query and the messages, i.e.,


[W,S]
[W,S]
(4)
, X1 , X2 , · · · , XK = 0,
| Qj
H Aj
for all W ∈ [K], S ⊆ [K] \ {W }, and j ∈ [N ].
[W,S]
[W,S]
and the side in2. From the answers A1
, . . . , AN
formation XS , the user should be able to decode the
desired message XW , i.e.,


[W,S]
[W,S]
(5)
H XW | A1
, · · · , AN , XS = 0,

for all W ∈ [K], S ⊆ [K] \ {W }.
3. The PIR-SI scheme should guarantee privacy for the
user by ensuring one of the following two conditions,
referred to as W -privacy and (W, S)-privacy as defined
below.
Definition 1. W -privacy: Any server cannot infer any
information about the demand index from the query,
answer, and messages i.e., for all j ∈ [N ], we have


[W,S]
[W,S]
, X1 , X2 , · · · , XK = 0. (6)
, Aj
I W ; Qj

Definition 2. (W, S)-privacy: Any server cannot infer
any information about the demand index as well as the
side information index set from the query, answer, and
messages i.e., for all j ∈ [N ], we have


[W,S]
[W,S]
, X1 , X2 , · · · , XK = 0.
, Aj
I W, S ; Qj
(7)
We refer to a PIR-SI scheme preserving W -privacy or
(W, S)-privacy as W -PIR-SI or (W, S)-PIR-SI scheme,
respectively.
The rate of a a PIR-SI scheme is defined as the ratio of
the message length (t bits) to the total length of the answers
(in bits) as follows:3
R= P
N

t


[W,S]

j=1 H Aj

.

(8)

The capacity of W -PIR-SI or (W, S)-PIR-SI problem, respectively denoted by CW or CW,S , is defined as the supremum of rates over all W -PIR-SI or (W, S)-PIR-SI schemes
for a given N , K, and M , respectively.
III. M AIN R ESULTS
First, we summarize our main results for single server case
in Theorems 1 and 2, which characterize the capacity W PIR-SI and (W, S)-PIR-SI, respectively.
3 Note that the download rate dominates the total communication rate for
large enough messages.

Theorem 1. For the W -PIR-SI problem with N = 1 server,
K messages, and side information size M , when the demand
index W and the side information index set S are jointly
distributed according to (3), the capacity is
−1

K
.
(9)
CW =
M +1
Our proof for Theorem 1 is based on two parts. We
prove the converse in Section IV-B for any joint distribution
of (W, S). Then, we construct an achievability scheme in
Section IV-C for the distribution given in (3).
Theorem 2. For the (W, S)-PIR-SI problem with N = 1
server storing K messages and for any arbitrary joint
distribution of the demand index W and the side information
index set S such that the size of S is equal to M , the capacity
is
CW,S = (K − M )−1 .
(10)
First, we show that the capacity CW,S of the (W, S)PIR-SI problem with N = 1 server, K messages, and size
information size M is upper bounded by (K − M )−1 for
any joint distribution of the side information index set and
the demand index (see Section V-A). Further, we construct a
scheme based on maximum distance separable (MDS) codes,
which achieves this bound for any arbitrary joint distribution
of (W, S) such that the size of S is equal to M (see
Section V-B).
Next, we state our main result for multiple servers storing
replicas of the database, which gives a lower bound on the
capacity of W -PIR-SI problem based on an achievability
scheme.
Theorem 3. For the W -PIR-SI problem with N servers,
each storing K messages, and side information size M such
that (M + 1) | K, when the demand index W and the
side information index set S are jointly distributed according
to (3), the capacity is lower bounded as

−1
1
1
CW ≥ 1 +
+ ···+
.
(11)
K
N
N M +1 −1
Our PIR scheme builds up on the scheme in [5], which is
for the case of no side-information.
IV. W -P RIVACY P ROBLEM
Our converse proofs for Theorems 1 and 2 in the singleserver case use the following simple yet powerful observation.
Proposition 1. Let A[W,S] be an answer from the server that
satisfies the decodability requirement (5) and the W -privacy
requirement (6). Then, the following two conditions hold:
1) For each message Xi , i = 1, . . . , K, there exists a subset XSi ⊆ {X1 , · · · , XK } \ Xi , with |XSi |= M , and
a decoding function Di satisfying Di A[W,S] , XSi =
Xi .
2) There exists a function DW
such that
DW A[W,S] , XS = XW .

Proof. The first condition is implied by the W -privacy
requirement. Indeed, if this was not the case, then the server
would know that message Xi is not one of the messages
requested by the user which, in turn, would violate the W privacy condition (6). Note that the first condition holds
under the assumption that W has a distribution such that
pW (W ) > 0 ∀W ∈ [K].
The second condition is implied by the decodability requirement.

The above proposition enables us to show a relation of
the PIR-SI problem with an instance of index coding with
side information problem [25]–[27]. We begin with briefly
reviewing the index coding problem.
A. Index Coding problem
Consider a server with K messages X1 , · · · , XK of length
t with Xj ∈ {0, 1}t. Consider L clients R1 , · · · , RL , L ≥ K,
where for each i, Ri is interested in one message, denoted
by Xf (i) ∈ {Xi }, and knows some subset XSi ⊂ {Xi } of
the other messages, referred to as its side information.
An index code of length ℓ for this setting is a set of
codewords in {0, 1}ℓ together with an encoding function
E : {0, 1}tK → {0, 1}ℓ, and a set of L decoding functions
D1 , · · · , DL such that Di (E (X1 , · · · , XK ) , XSi ) = Xf (i)
for all i ∈ [L] and [X1 , · · · , XK ] ∈ {0, 1}tK . We refer to
E (X1 , · · · , XK ) as a solution to the instance of the index
coding problem.
When L = K and every client requires a distinct message,
the side information of all the clients can be represented by a
simple directed graph G = (V, E), where V = {1, 2, · · · , K}
with the vertex i corresponding to the message Xi , and there
is an arc (i, j) ∈ E if j ∈ Si . We denote the out-neighbors
of a vertex i as N (i).
For a given instance of the index coding problem, the
minimum encoding length ℓ as a function of message-length
t is denoted as βt , and the broadcast rate is defined as in
[28], [29]
βt
β = inf
(12)
t t
B. Converse for Theorem 1
The key step of the converse is to show that for any
scheme that satisfies the W -privacy constraint (6), the answer
from the server must be a solution to an instance of the
index coding problem that satisfies certain requirements as
specified in the following lemma.
Lemma 1. For a W -PIR-SI scheme, for any demand index
W and side information index set S, the answer A[W,S] from
the server must be a solution to an instance of the index
coding problem that satisfies the following requirements:
1) The instance has the messages X1 , · · · , XK ;
2) There are K clients such that each client wants to
decode a distinct message from X1 , · · · , XK , and possesses a side information that includes M messages;

3) The client that wants XW has the side information set
XS ; for each other client the side information set has
M arbitrary messages from X1 , · · · , XK .
Proof. The sets XSi mentioned in Proposition 1 can be
used to construct the following instance of the Index Coding
problem. The instance has the message set X1 , · · · , XK and
K clients {R1 , · · · , Rk } such that:
• Client RW requires packet XW and has the side information set XS ;
• Each other client Ri , i 6= W requires Xi and has side
information set XSi .
It is easy to verify that the instance satisfies all the conditions
stated in the lemma and that A[W,S] is the feasible index code
for this instance.

[W,S]

Note that Lemma 1 shows that the answer A
from
the server must be a solution to an instance of the index
coding problem in which the out-degree of every vertex in
the corresponding side information graph G is equal to M .
Next, we lower bound the broadcast rate for an index coding
problem with side information graph G such that out-degree
of every vertex in G is M as follows.
Lemma 2. Let G be a directed graph on K vertices such
that each vertex has out-degree M . Then, the broadcast rate
of the corresponding instance of the index coding problem
K
is lower bounded by ⌈ M+1
⌉.
Proof. For any side information graph G, the broadcast rate
β is lower bounded by the size of the maximum acyclic
induced subgraph (MAIS) of G, denoted as M AIS(G) [28],
[30].
We show that for any graph G that satisfies the conditions
of the lemma (i.e., the out-degree of each of the K vertices
of G is M ) it holds that


K
.
M AIS(G) ≥
M +1
Specifically, we build an acyclic subgraph of G induced
by set Z through the following procedure:
Step 1. Set Z = ∅ and a candidate set of vertices V ′ = V ;
Step 2. Add an arbitrary vertex i ∈ V ′ into Z, i.e.,
Z = Z ∪ {i};
Step 3. Set V ′ = V ′ \ (N (i) ∪ {i});
Step 4. There are two cases:
Case 1: If V ′ 6= ∅, then repeat Steps 2-4.
Case 2: If V ′ = ∅, then terminate the procedure and
return Z.
It is easy to see that the vertices in set Z returned by the
procedure induce an acyclic subgraph of G. If the vertices
are ordered in the order they are added to Z, then there can
only be an edge (i, j) if j was added to Z before i. This
implies that the subgraph induced by Z cannot contain a
cycle.
K
Further, note that the set Z contains at least ⌈ M+1
⌉
vertices. At each removal step, there are at most M + 1

vertices removed from V . Thus, the procedure iterates at
K
least ⌈ M+1
⌉ times, and in each iteration we add one vertex
K
⌉. 
to Z. This implies that the size of Z is at least ⌈ M+1
Corollary 1 (Converse of Theorem 1). For the W -PIR-SI
problem with single server, K messages,
and
l
m side informa-

tion size M , the capacity is at most

K
M+1

−1

.

Proof. Lemmas 1 andl2 imply
m that the length of the answer
K
bits for any given W and S.
A[W,S] is at least t · M+1
m−1
l
K
.

Then, by (8), it follows that R ≤ M+1
C. Achievability for Theorem 1
In this section, we propose a W -PIR-SI scheme for N = 1
server, K messages,
l andm side information size M , which
−1

K
achieves the rate M+1
. Recall that we assume that
the distribution of the demand index W and the conditional
distribution of the side information index set S given W are
given respectively in (1) and (2). We describe the proposed
scheme, referred to as the Partition and Code PIR scheme,
in the following.
Partition and
l Code
m PIR Scheme: Given K, M , W , and
K
S, denote g , M+1
. The scheme consists of the following
three steps.
Step 1. The user creates a partition of the K messages
into g sets. For the ease of understanding, we describe the
special case of (M + 1) | K first.
(a) Special case of (M + 1) | K: Denote P1 , W ∪ S.
The user randomly partitions the set of messages [K] \ P1
into g − 1 sets, each of size M + 1, denoted as P2 , . . . , Pg .
(b) General case: Let P1 , . . . , Pg be a collection of g
empty sets. Note that, although empty at the beginning, once
constructed, the sets P1 , . . . , Pg−1 will be of size M +1, and
the set Pg will be of size K −(g−1)(M +1). The user begins
by assigning probabilities to the sets according to their sizes:
the sets P1 , . . . , Pg−1 are each assigned a probability M+1
K ,
.
and the set Pg is assigned a probability K−(g−1)(M+1)
K
Then, the user chooses a set randomly according to the
assigned probabilities of the sets.
If the chosen set is a set P ∈ {P1 , . . . , Pg−1 }, then
the user fills the set P with the demand index W and the
side information index set S of the user. Next, it fills the
remaining sets choosing one index at a time from the set of
indices of the remaining messages uniformly at random until
all the message indices are filled.
If the chosen set is the set Pg , then it fill Pg
with the demand index W , and fill the remaining
K − (g − 1)(M + 1) − 1 places in the set Pg with randomly
chosen elements from the side information index set S. (Note
that once Pg is filled, it is possible that not all of the indices
in the side information index set S are placed in the set.)
Next, fill the remaining sets by choosing one index at a time
from the set of indices of the unplaced packets uniformly at
random until all packet indices are placed.

Step 2. The user sends to the server a uniform random permutation of the partition {P1 , · · · , Pg }, ie., it sends
{P1 , · · · , Pg } in a random order.
Step 3. The server computes the answer A[W,S] as a set of
g inner products given by A[W,S] = {AP1 , . . . , APg }, where
AP = [X1 , . . . , XK ] · 1P for all P ∈ {P1 , . . . , Pg }.
Upon receiving the answer from the server, the user
decodes XW by subtracting off the contributions of its side
information XS from AP for some P ∈ {P1 , . . . , Pg } such
that W ∈ P .
Example 2. Assume that K = 8 and M = 2. Assume that
the user demands the message X2 and has two messages X4
and X6 as side information, i.e., W = 2 and S = {4, 6}.
Following the Partition and Code PIR scheme, the user labels
three sets as P1 , P2 , and P3 , and assigns probability 38 to
each of the two sets P1 and P2 , and assigns probability 28
to the set P3 . Next, the user chooses one of these sets at
random according to the assigned probabilities. Assume the
user has chosen the set P3 . The user then places 2 into the
set P3 , and chooses another element from {4, 6} uniformly at
random to place in P3 as well. Say the user chooses 6 from
the set {4, 6}, then the set P3 becomes P3 = {2, 6}. Then the
user fills the other sets P1 and P2 randomly to exhaust the
elements from {1, 2, 3, 5, 7, 8}. Say the user chooses P1 =
{1, 7, 8} and P2 = {3, 4, 5}. Then the user sends to the
server a random permutation of {1P1 , 1P2 , 1P3 } as the query
Q[2,{4,6}] . The server sends three coded packets back to the
user: Y1 = X1 + X7 + X8 , Y2 = X3 + X4 + X5 , and
Y3 = X2 + X6 . The user can decode for X2 by computing
X2 = Y3 − X6 . From the server’s perspective the user’s
demand is in either {1, 7, 8} or {3, 4, 5} with probability 83
each, or in {2, 6} with probability 28 . The probability P1 (or
P2 ) contains W is 13 , and the probability that P3 contains W
is 21 . In either case, it follows that P(W = W |Q[1,{2,3}] ) =
1
8 = pW (W ).
In the following, we show that the Partition and Code PIR
scheme satisfies the W -privacy requirement for the setting in
which the user’s demand index W and side information index
set S (given W ) are distributed according to (1) and (2),
respectively.
Lemma 3 (Achievability of Theorem 1). Consider the
scenario of a W -PIR-SI problem in which:
• The server has packets {X1 , X2 , ..., XK };
• There is one user with |W |= 1, |S|= M such that 0 ≤
M ≤ K − 1;
• The demand index W and the side information index set
S (given the demand index W ) follow the distributions
given in (1) and (2), respectively.
In this scenario, the Partition and Code
PIR
l
m scheme satisfies
the W -privacy, and has rate R =

K
M+1

−1

.

Proof. To show that the Partition and Code PIR scheme
satisfies the W -privacy, it suffices to show that
P(W = W |Q[W,S] ) = pW (W ).

We consider two cases as follows:
(i) W is in one of the sets in {P1 , . . . , Pg−1 }. In this case,
for every i ∈ [g − 1], we have
X
P(W ∈ Pi |Q[W,S] ) =
P(W = j|Q[W,S] )
j∈Pi

=

M +1
,
K

and
P(W = W |W ∈ Pi , Q[W,S] ) =

1
.
M +1

(ii) W is the set Pg . In this case,
P(W ∈ Pg |Q[W,S] ) =

K − (g − 1)(M + 1)
,
K

and
P(W = W |W ∈ Pg , Q[W,S] ) =

1
.
K − (g − 1)(M + 1)

Thus, we have
P(W = W |Q[W,S] )
g
X
P(W = W |W ∈ Pi , Q[W,S] )P(W ∈ Pi |Q[W,S] )
=
i=1

1
.
K
To compute the rate of the scheme, note that
=

H(A[W,S] ) =
=

H([AP1 , AP2 , . . . , APg ])
X
H(AP )

P ∈{P1 ,P2 ,...,Pg }

=

t × g,

where the equalities follow since the messages Xj ’s (and
hence the answers AP ’s) are independently and uniformly
distributed. Thus, the Partition and Code PIR scheme has
rate
t
1
M +1
R=
= =
.
t×g
g
K

V. (W, S)-P RIVACY P ROBLEM
In this section we consider (W, S)-privacy in the PIRSI problem. We show the proof of the converse and the
achievability for Theorem 2 through a reduction to an index
coding instance and an MDS coding scheme, respectively.
A. Converse for Theorem 2
When protecting the demand index and the side information index set of the user, the privacy constraint becomes
I(W, S; Q[W,S] , A[W,S] , X1 , X2 , ..., XK ) = 0.
For this case, a lower bound of K − M on the number of
transmissions can be shown. The proof of the converse in this
case shows a necessary condition for privacy and a class of
index coding problems that satisfy the necessary condition;
and obtains a lower bound on the number of transmissions

needed to solve the index coding problem that belong to this
class.
Lemma 4. For a (W, S)-PIR-SI scheme, for any demand
index W and side information index set S, the answer A[W,S]
from the server must be a solution to an instance of the index
coding problem that satisfies the following requirements:
1) The instance has the messageset X1 , · · · , XK ;
K
2) There are L = (K − M ) M
clients such that each
client wants to decode one message, and possesses a
side information set that includes M other messages;
3) The client that wants XW has the side information set
XS ; for each i ∈ [K], i 6= W , for each Si ⊂ [K] \ {i}
such that |Si |= M , there exists a client that demands
Xi and possesses XSi as its side information.
Proof. Given a demand index W and a side information
index set S, let A[W,S] be an answer from the server that
satisfies the decodability requirement (5) and the (W, S)privacy requirement (7). First, we note that the decodability
requirement implies that
 there exists a function DW,S such
that DW,S A[W,S] , XS = XW . Second, we note that the
(W, S)-privacy requirement implies that for each message Xi
and every set Si ⊆ [K]\{i} of size M
 , there exists a function
Di,Si satisfying Di,Si A[W,S] , XSi = Xi . Otherwise, for a
particular {i, Si }, the server would know that the user cannot
possess XSi and demand Xi , which, in turn, would violate
the (W, S)-privacy requirement (7).
Now, consider an instance of the index coding problem
satisfying the conditions stated in the lemma. Since decoding
functions exists for each client as argued above, A[W,S] is a
feasible index code for this instance.

Next, we give a lower bound on the broadcast rate for an
instance satisfying the conditions in Lemma 4.
Lemma 5. For any instance of the index coding problem
satisfying the conditions specified in Lemma 4, the broadcast
rate is at least K − M .
Proof. Let J denote an instance of the index coding problem satisfying the conditions in Lemma 4. Let J ′ be an
instance of the index coding problem with the K messages
X1 , · · · , XK and K − M clients. Each client has the side
information XS and wants to decode one distinct message
from {X1 , · · · , XK } \ XS . Clearly, a solution to instance
J is also a solution to instance J ′ . Since the messages are
independent, the broadcast rate for J ′ is at least K − M ,
which completes the proof.

Corollary 2 (Converse of Theorem 2). For the (W, S)PIR-SI problem with N = 1 server, K messages, and side
information size M , the capacity is at most (K − M )−1 .
Proof. Lemmas 4 and 5 imply that the length of the answer
A[W,S] is at least (K − M )t for any given W and S. Thus,
by using (8), it follows that R ≤ (K − M )−1 .


B. Achievability for Theorem 2
In this section, we give a (W, S)-PIR-SI scheme based on
a maximum distance separable (MDS) code that achieves the
rate of 1/(K − M ). We assume that t ≥ log2 (2K − M ).
MDS PIR Scheme: Given a demand index W and a side
information index set S of size M , the user queries the server
to send the K − M parity symbols of a systematic (2K −
M, K) MDS code over the finite field F2t . We assume that
t ≥ log2 (2K − M ), or equivalently, 2t ≥ 2K − M . Thus, it
is possible construct a (2K − M, K) MDS code over F2t .
The answer A[W,S] from the server consists of the K − M
parity symbols.
Lemma 6 (Achievability of Theorem 2). The MDS PIR
scheme satisfies the decodability condition in (5) and the
(W, S)-privacy condition in (7), and it has the rate of
R = (K − M )−1 .
Proof. (Sketch) For a (2K − M, K) systematic MDS code,
given the K − M parity symbols and any M out of the K
messages, the user can decode all of the remaining K − M
messages as the code is MDS. Thus, the user can recover its
demanded message.
To ensure the (W, S)-privacy, note that the query and
the answer are independent of the particular realization of
demand index W and side information index set S, but only
depend on the size M of the side information index set. As
the server already knows the size of the side information
index set, it does not get any other information about W
and S from the query and the answer. Thus, the MDS PIR
scheme satisfies the (W, S)-privacy requirement.
To compute the rate, note that for any W and S, the
answer A[W,S] of the MDS PIR scheme consists of K − M
parity symbols of a (2K − M, K) systematic MDS code
over F2t . For an MDS code, any parity symbol is a linear
combination of all the messages. Thus, as each message is
distributed uniformly over F2t and the code operates over
F2t , every parity symbol is also uniformly distributed over
F2t . Further, since the messages are independent, the parity
symbols are independent. Hence, we have H(A[W,S] ) =
(K − M )t. Therefore, the rate of the MDS PIR scheme is
R = (K − M )−1 .

VI. W -P RIVACY

FOR

M ULTIPLE S ERVERS

In this section, we present a W -PIR-SI scheme, when data
is replicated on multiple servers. The rate achieved by the
proposed scheme gives a lower bound on the capacity of
multiple-server W -PIR-SI problem. Our scheme builds up
on the scheme proposed by Sun and Jafar in [5], which deals
with the case of no side information (M = 0). We refer to it
as Sun-Jafar protocol. Next, we use an example to describe
this Sun-Jafar protocol. The details can be found in [5].
Example 3. (Sun-Jafar Protocol [5]) N = 2 servers, K = 2
messages, and M = 0, i.e., no side information. The protocol
assumes that each of the messages is t = N K = 4 bits
long. For a message Xi , let [Xi,1 , · · · , Xi,t ] be a uniform

random permutation of its t bits. The user chooses a random
permutation of the bits of X1 , and an independent random
permutation of the bits of X2 . Suppose that the user is
interested in downloading X1 . Then, it requests the bits from
the first server (S1) and the second server (S2) as given in
Table I.
S1
X1,1
X2,1
X1,3 + X2,2

S2
X1,2
X2,2
X1,4 + X2,1

TABLE I
Q UERIES FOR THE S UN -JAFAR PROTOCOL WHEN N = 2 SERVERS ,
K = 2 MESSAGES , AND NO SIDE - INFORMATION , WHEN THE USER
DEMANDS X1 .

E ACH MESSAGE IS FORMED OF 4 BITS .

Note that the user can decode the four bits of X1 from the
answers it gets. To ensure privacy, note that each server is
asked for a randomly chosen bit of each message and a sum
of different pair of randomly chosen bits from each message.
Therefore, a server cannot distinguish about which message
is requested by the user.
Next, we give an example to outline our proposed scheme
for multi-server PIR with side information before describing
it formally.
Example 4. (Multi-Server W -PIR-SI Scheme) N = 2
servers, K = 4 messages, and M = 1 message as side
information. Our scheme assumes that each message is t =
K
N M +1 = 4 bits long. The demand is privately chosen by
the user, uniformly at random. The side information set has
size M = 1. It is chosen uniformly at random from the other
messages, and is unknown to the servers.
Consider an instance when the user demands X1 , and the
side information index set S = {2}. First step is that the
user forms a partition of [K] into g = K/(M + 1) = 2 sets
{P1 , P2 }, where P1 = {1, 2}, and P2 = {3, 4}.4 Next, the
user sends a random permutation of {P1 , P2 } to both the
servers. The user and the servers form two super-messages
by taking the sum of the messages indexed by P1 and P2 as
follows: X̂1 = X1 + X2 and X̂2 = X3 + X4 . The last step
is that the user and the servers apply the Sun-Jafar protocol
using the two super-messages X̂1 and X̂2 , such that the user
can download X̂1 . The form of the queries is given in Table I.
From the answers, the user obtains X̂1 , from which it can
decode the desired message X1 using the side-information
X2 . Note that the privacy property of the Sun-Jafar protocol
guarantees that any DB cannot distinguish which supermessage is requested by the user. Since the desired message
can be in either super-message, and in a super-message,
any of the messages can be the demand, the privacy of the
demand index is ensured.
4 The general procedure for forming the partition is elaborated in the
formal description of the scheme.

Note that in the above example the proposed scheme
requires to download 6 bits, achieving the rate of 2/3. It
is shown in [5, Theorem 1] that the capacity of PIR with
N servers and K messages and no side information is
(1+1/N +· · ·+1/N K−1)−1 . Therefore, if the user attempts
to download the demand without using its side information,
then the capacity is (1 + 1/N + 1/N 2 + 1/N 3 )−1 = 8/15,
which is smaller than 2/3.
Next, we describe our W -PIR-SI scheme for N servers
storing identical copies of the K messages, when the user has
a side information set of size M . We assume that (M + 1) |
K, and the messages are t = N K/(M+1) bits long. Recall
that, for a subset S ⊂ [K], 1S denotes the characteristic
K
.
vector of the set S. Let g , M+1
Multi-Server W -PIR-SI Scheme: Assume that each mesK
sage is t = N M +1 bits long. The scheme consists of the
following three steps.
Step 1. Given the demand index W and the side information index set S, let P1 = W ∪ S. The user randomly
partitions the set of messages [K] \ P1 into g − 1 sets of size
M + 1 each, denoted as {P2 , · · · , Pg }.
Step 2. The user sends to all the servers a uniform
random permutation of the partition {P1 , · · · , Pg }, ie., it
sends {P1 , · · · , Pg } in a random order. Then, the user and
the servers form g super-messages {X̂1 , . . . , X̂g }, where
X̂i = [X1 , . . . , XK ] · 1Pi for i ∈ [g].
Step 3. The user and the N servers utilize the Sun-Jafar
protocol with g super-messages in such a way that the user
can download the message X̂1 .
Lemma 7. Consider the scenario of a W -PIR-SI problem
in which:
• The N servers store identical copies of K messages
{X1 , X2 , ..., XK };
• There is one user with |W |= 1, |S|= M such that 0 ≤
M ≤ K − 1;
• The demand index W and the side information index set
S (given the demand index W ) follow the distributions
given in (1) and (2), respectively.
In this scenario, the multi-server W -PIR-SI scheme satisfies
the W -privacy, and has rate
−1

R = 1 + 1/N + · · · + 1/N K/(M+1)−1

Proof. First, note that since the messages {X1 , . . . , XK } are
uniform and independent, the super-messages {X̂1 , . . . , X̂K }
are uniform and independent as well. Therefore, the
rate of the scheme is that of the Sun-Jafar proK
tocol for N servers and M+1
messages, which is

K/(M+1)−1 −1
1 + 1/N + · · · + 1/N
, see [5, Theorem 1].
To prove the privacy, we note that, since the Sun-Jafar
protocol protects the privacy of the demanded super-message,
i.e., any server cannot have any information about which
super-message the user is trying to download. Therefore,
from the perspective of each server, every super-message is
equally likely to include the demanded message in the linear

combination. Further, the demanded message can be any one
of the M + 1 messages in a super-message. In other words,
we have
M +1
, ∀i ∈ [g],
P(W ∈ Pi | Q[W,S] ) =
K
and
P(W = W | W ∈ Pi , Q[W,S] ) =

1
,
M +1

∀i ∈ [g].

Hence, we have
P(W = W |Q[W,S] ) =

1
.
K


VII. C ONCLUSION
In this paper we considered the problem of Private Information Retrieval (PIR) with side information, in which
the user has a priori a subset of the messages at the server
obtained from other sources. The goal of the user is to
download a message, which is not in its side information,
from the server while satisfying a certain privacy constraints.
We consider two privacy requirements: W -privacy in which
the user wants to protect the identity its demand (i.e., which
message it wants to download), and (W, S)-privacy in which
the user wants to protect the identity of the demand and
the side information jointly. First, we focus on the case of
single server (i.e., single database). We establish the PIR
capacity for (W, S)-privacy for arbitrary distribution of the
demand index W and the side information index set S. In
the case of W -privacy, we establish the PIR capacity for the
uniform distribution. Second, we extend our PIR scheme for
W -privacy to the case of multiple servers (multiple copies
of the database). Our scheme for the multiple servers uses
ideas from the single server scheme in conjunction with the
no-side-information scheme of Sun and Jafar in [5]. The
multi-server capacities of PIR with side information under
the W -privacy and (W, S)-privacy constraints remain open.
R EFERENCES
[1] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, “Private information retrieval,” in IEEE Symposium on Foundations of Computer
Science, 1995, pp. 41–50.
[2] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Private information retrieval,” Journal of the ACM (JACM), vol. 45, no. 6, pp.
965–981, 1998.
[3] E. Kushilevitz and R. Ostrovsky, “Replication is not needed: Single
database, computationally-private information retrieval,” in IEEE Symposium on Foundations of Computer Science, 1997, p. 364.
[4] C. Cachin, S. Micali, and M. Stadler, “Computationally private information retrieval with polylogarithmic communication,” in International Conference on the Theory and Applications of Cryptographic
Techniques. Springer, 1999, pp. 402–414.
[5] H. Sun and S. A. Jafar, “The capacity of private information retrieval,”
arXiv preprint arXiv:1602.09134, 2016.
[6] ——, “The capacity of robust private information retrieval with
colluding databases,” arXiv preprint arXiv:1605.00635, 2016.
[7] S. Yekhanin, “Private information retrieval,” Communications of the
ACM, vol. 53, no. 4, pp. 68–73, 2010.
[8] A. Beimel and Y. Ishai, “Information-theoretic private information
retrieval: A unified construction,” in Automata, Languages and Programming. Springer, 2001, pp. 912–926.

[9] A. Beimel, Y. Ishai, E. Kushilevitz, and J.-F. Raymond, “Breaking
the O(n1/(2k−1) ) barrier for information-theoretic private information retrieval,” in 43rd Annual IEEE Symposium on Foundations of
Computer Science, 2002, pp. 261–270.
[10] W. Gasarch, “A survey on private information retrieval,” in Bulletin of
the EATCS. Citeseer, 2004.
[11] N. Shah, K. Rashmi, and K. Ramchandran, “One extra bit of download
ensures perfectly private information retrieval,” in 2014 IEEE International Symposium on Information Theory (ISIT). IEEE, 2014, pp.
856–860.
[12] T. H. Chan, S.-W. Ho, and H. Yamamoto, “Private information retrieval
for coded storage,” arXiv preprint arXiv:1410.5489, 2014.
[13] R. Tajeddine and S. El Rouayheb, “Private information retrieval
from MDS coded data in distributed storage systems,” 2016 IEEE
International Symposium on Information Theory Proceedings (ISIT),
2016.
[14] R. Tajeddine, S. El Rouayheb, “Private Information Retrieval from
MDS Coded data in Distributed Storage Systems (extended version),”
2016, http://www.ece.iit.edu/ salim/PIRv2.pdf.
[15] K. Banawan and S. Ulukus, “The capacity of private information
retrieval from coded databases,” arXiv preprint arXiv:1609.08138,
2016.
[16] A. Fazeli, A. Vardy, and E. Yaakobi, “Pir with low storage overhead:
Coding instead of replication,” arXiv preprint arXiv:1505.06241, 2015.
[17] S. Blackburn and T. Etzion, “PIR array codes with optimal pir rate,”
arXiv preprint arXiv:1607.00235, 2016.
[18] R. Freij-Hollanti, O. Gnilke, C. Hollanti, and D. Karpuk, “Private
information retrieval from coded databases with colluding servers,”
arXiv preprint arXiv:1611.02062, 2016.
[19] Z. Dvir and S. Gopi, “2-Server PIR with subpolynomial communication,” Journal of the ACM (JACM), vol. 63, no. 4, p. 39, 2016.
[20] R. Tajeddine and S. El Rouayheb, “Robust private information retrieval
on coded data,” in 2017 IEEE International Symposium on Information
Theory (ISIT). IEEE, 2017.
[21] R. Tajeddine, O. W. Gnilke, D. Karpuk, R. Freij-Hollanti, C. Hollanti, and S. El Rouayheb, “Private information retrieval schemes for
coded data with arbitrary collusion patterns,” 2017 IEEE International
Symposium on Information Theory (ISIT), 2017.
[22] R. Tandon, “The capacity of cache aided private information
retrieval,” ArXiv e-prints, June 2017. [Online]. Available:
https://arxiv.org/abs/1706.07035
[23] M. Karmoose, L. Song, M. Cardone, and C. Fragouli, “Private
broadcasting: an index coding approach,” CoRR, vol. abs/1701.04958,
2017. [Online]. Available: http://arxiv.org/abs/1701.04958
[24] D. T. Kao, M. A. Maddah-Ali, and A. S. Avestimehr, “Blind index
coding,” IEEE Transactions on Information Theory, vol. 63, no. 4, pp.
2076–2097, 2017.
[25] Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol, “Index coding with
side information,” IEEE Transactions on Information Theory, vol. 57,
no. 3, pp. 1479–1494, March 2011.
[26] M. Effros, S. El Rouayheb, and M. Langberg, “An equivalence
between network coding and index coding,” IEEE Transactions on
Information Theory, vol. 61, no. 5, pp. 2478–2487, 2015.
[27] S. El Rouayheb, A. Sprintson, and C. Georghiades, “On the index
coding problem and its relation to network coding and matroid theory,”
IEEE Transactions on Information Theory, vol. 56, no. 7, pp. 3187–
3195, 2010.
[28] N. Alon, E. Lubetzky, U. Stav, A. Weinstein, and A. Hassidim,
“Broadcasting with side information,” in 2008 49th Annual IEEE
Symposium on Foundations of Computer Science, Oct 2008, pp. 823–
832.
[29] A. Blasiak, R. Kleinberg, and E. Lubetzky, “Broadcasting with side
information: Bounding and approximating the broadcast rate,” IEEE
Transactions on Information Theory, vol. 59, no. 9, pp. 5811–5823,
Sept 2013.
[30] F. Arbabjolfaei, “Index coding: Fundamental limits, coding schemes,
and structural properties,” in PhD Thesis, UC San Diego, 2017.

