The Capacity of Private Information Retrieval with
Partially Known Private Side Information∗
arXiv:1710.00809v2 [] 27 Nov 2017

Yi-Peng Wei

Karim Banawan

Sennur Ulukus

Department of Electrical and Computer Engineering
University of Maryland, College Park, MD 20742
ypwei@umd.edu

kbanawan@umd.edu

ulukus@umd.edu

November 28, 2017

Abstract
We consider the problem of private information retrieval (PIR) of a single message
out of K messages from N replicated and non-colluding databases where a cacheenabled user (retriever) of cache-size M possesses side information in the form of full
messages that are partially known to the databases. In this model, the user and the
databases engage in a two-phase scheme, namely, the prefetching phase where the user
acquires side information and the retrieval phase where the user downloads desired
information. In the prefetching phase, the user receives mn full messages from the nth
P
database, under the cache memory size constraint N
n=1 mn ≤ M . In the retrieval
phase, the user wishes to retrieve a message such that no individual database learns
anything about the identity of the desired message. In addition, the identities of the
side information messages that the user did not prefetch from a database must remain
private against that database. Since the side information provided by each database
in the prefetching phase is known by the providing database and the side information
must be kept private against the remaining databases, we coin this model as partially
known private side information. We characterize the capacity of the PIR with partially
−1
1− 1
1
= 1−( 1 )NK−M .
known private side information to be C = 1 + N1 + · · · + N K−M
−1
N
Interestingly, this result is the same if none of the databases knows any of the prefetched
side information, i.e., when the side information is obtained externally, a problem posed
by Kadhe et al. and settled by Chen-Wang-Jafar recently. Thus, our result implies that
there is no loss in using the same databases for both prefetching and retrieval phases.
This work was supported by NSF Grants CNS 13-14733, CCF 14-22111, CNS 15-26608 and CCF 1713977.
∗

1

1

Introduction

The private information retrieval (PIR) problem is a canonical problem to study privacy
issues that arise when information is downloaded (retrieved) from public databases. Since
its first formulation by Chor et al. in [1], the PIR problem has become a central research
topic in the computer science literature, see e.g., [2–5]. In the classical setting of PIR in [1],
a user wishes to retrieve a single message (or a file) out of K messages replicated across
N non-communicating databases without leaking any information about the identity of the
retrieved message. To that end, the user submits a query to each database. Each database
responds truthfully with an answer string. The user reconstructs the desired message from
the collected answer strings. Trivially, the user can download the entire database and incur a
linear (in number of messages) download cost, but this retrieval strategy is highly inefficient.
The efficiency of a PIR scheme is measured by the normalized download cost, which is the
cost of privately downloading one bit of the desired message. The goal of the PIR problem is
to devise the most efficient retrieval strategy under the privacy and decodability constraints.
The PIR problem has received attention in recent years in the information and coding
theory literatures, see e.g., [6–11]. In the leading work of Sun-Jafar [12], the classical PIR
problem is re-formulated to conform with the conventional information-theoretic arguments,
and the notion of PIR capacity is introduced, which is defined as the supremum of retrieval
rates over all achievable retrieval schemes. Reference [12] characterizes the capacity of the
−1
1
using a greedy achievable scheme
classical PIR model to be C = 1 + N1 + · · · + N K−1
that is closely related to blind interference alignment [13] and an induction-based converse
argument. Following the work of Sun-Jafar [12], the capacity of many interesting variants of
the classical PIR model have been investigated, such as, PIR from colluding databases, robust
PIR, symmetric PIR, PIR from MDS-coded databases, PIR for arbitrary message lengths,
multi-round PIR, multi-message PIR, PIR from Byzantine databases, secure symmetric PIR
with adversaries, and their several combinations [14–28].
In this paper, we consider the problem of PIR with partially known private side information. Our work is most closely related to [29–32]1 . These works investigate the PIR problem
when the user (retriever) possesses some form of side information about the contents of the
databases. However, the models of [29–32] differ in three important aspects, namely, 1) the
structure of the side information, 2) the presence or absence of privacy constraints on the
side information, and 3) the databases’ awareness of the side information at its initial acquisition. Here, structure of the side information refers to whether the side information is in the
form of full messages or parts of messages or whether messages are mixed through functions
(coded/uncoded); privacy of the side information refers to whether the user further aims to
keep the side information private from the databases; and databases’ awareness of the side
information refers to whether the databases knew the initially prefetched side information.
1

A parallel line of work that studies privacy issues of requests and side information in index coding based
broadcast systems can be found in [33, 34].

2

Specifically, reference [29] studies the capacity of the cache-aided PIR where the user
caches rLK bits in the form of any arbitrary function of the K messages, where L is the
message size, and 0 ≤ r ≤ 1 is the caching ratio. Reference [29] assumes that the cache
content is perfectly known by all the databases, and hence there is no need to protect the
privacy of the cached content. Reference [29] determines the optimal download cost for this

1
1
= (1 −r) 1 + N1 + · · · + N K−1
using a memory-sharing achievable
model to be D ∗ (r) = C(r)
scheme and a converse that utilizes Han’s inequality. This conclusion is somewhat pessimistic
in that the user cannot exploit the cached content as useful side information during PIR to
reduce the download cost, since the databases are fully aware of it; the optimum D ∗ (r)
formula indicates that the user should download the uncached part of the content, i.e.,
(1 − r), via the optimum PIR scheme in [12]. This result motivates [30, 31] to study the
other extreme when the databases are completely unaware of the side information at its
initial acquisition. References [30] and [31] differ in terms of the structure of the cached
content: [30] considers the case where rK full messages are cached, and [31] considers the
case where a random r fraction of the symbols of each of K messages is cached. In this
case, [31] shows a significant reduction in the download cost over [29], as the user can now
leverage the cached bits as side information, since they are unknown to the databases. In [31],
there is no privacy constraint on the cached content.
Reference [30] further introduces another model where the cached content (in the form
of full messages) which is unknown to the databases at the time of initial prefetching, must
remain unknown throughout the PIR, i.e., the queries of the user should not leak any information about the cached content to the databases. The exact capacity for this problem
−1
1
. The optimal achievable scheme in
is settled in [32] to be C = 1 + N1 + · · · + N K−M
−1
this case starts from the traditional achievable scheme without side information in [12] and
reduces the download cost by utilizing the reconstruction property of MDS codes.
In this paper, we take a deeper look at the issue of awareness or otherwise unawareness
of the databases about the cached content at its initial acquisition. We first note that it is
practically challenging to make the side information completely unknown to the databases
at its initial acquisition as assumed in [30–32]. One way to do this could be to employ
one of the databases for prefetching the side information and exclude it from the retrieval
process. Therefore, for the remaining N − 1 databases, the side information is completely
unknown. This solution is strictly sub-optimal as the capacity expression in [32] (shown
as C in the previous paragraph) is monotonically decreasing in N. An alternative solution
could be to devise a refreshing mechanism that ensures that the cached content is essentially
random from the perspective of each database [29], which may be challenging to implement.
We also note that the other extreme of the problem, where the databases are fully aware
of the cached content [29], is discouraging as the user cannot benefit from the cached side
information. Therefore, a natural model is to use the databases for both prefetching and
retrieval phases, such that the databases gain partial knowledge about the side information

3

available to the user, which makes it possible for the user to exploit the remaining side
information that is unknown to each individual database to reduce the download cost during
the retrieval process. This poses the following questions: Can we propose efficient joint
prefetching-retrieval strategies that exploit the limited knowledge of each database to drive
down the download cost? How much is the loss from the fully unknown case in [30, 32]?
In this paper, we investigate the PIR problem when the user and the databases engage in
a two-phase scheme, namely, prefetching phase and retrieval phase. In the prefetching phase,
the user caches mn full messages out of the K messages from the nth database under a total
P
cache memory size constraint N
n=1 mn ≤ M. Hence, each database has a partial knowledge
about the side information possessed by the user, namely, the part of the side information
that this database has provided during the prefetching phase. In the retrieval phase, the
user wants to retrieve a message (which is not present in its memory) without leaking any
information to any individual database about the desired message or the remaining side
information messages that are unknown to each database. The goal of this work is to design
a joint prefetching-retrieval scheme that minimizes the download cost in the retrieval phase.
To that end, we first derive a general lower bound for the normalized download cost that
is independent of the prefetching strategy. Then, we prove that this bound is attainable using
two achievable schemes. The first achievable scheme, which is proposed in [32] for completely
unknown side information, is a valid achievable scheme for our problem with partially known
side information for any prefetching strategy.2 We provide a second achievable scheme for
∈ N, which requires smaller sub-packetization
the case of uniform prefetching, i.e., mn = M
N
and smaller field size for realizing MDS codes. While the first achievable scheme [32] requires
a message size of L = N K , the second achievable scheme proposed here requires a message
M
M
size of L = N K− N , which scales down the message size by an exponential factor N N , which
in turn simplifies the achievable scheme and minimizes the total number of downloaded bits
without sacrificing from the capacity. We prove that the exact capacity of this problem is
−1
1
C = 1 + N1 + · · · + N K−M
. Surprisingly, this is the same capacity expression for the
−1
PIR problem when the databases are completely unaware of the side information possessed
by the user as found in [32] recently. Therefore, our result implies that there is no loss in
the capacity if the same databases are employed in both prefetching and retrieval phases.

2

System Model

We consider a classic PIR problem with K independent messages W1 , . . . , WK , where each
message consists of L symbols,
H(W1 ) = · · · = H(WK ) = L,
2

H(W1 , . . . , WK ) = H(W1 ) + · · · + H(WK ).

We thank Dr. Hua Sun for pointing this out.

4

(1)

There are N non-communicating databases, and each database stores all the K messages.
The user (retriever) has a local cache memory which can store up to M messages.
There are two phases: a prefetching phase and a retrieval phase. In the prefetching phase,
∀n ∈ [N], where [N] = {1, 2, . . . , N}, the user caches mn out of total K messages from the
nth database. We denote the indices of the cached messages from the nth database as Hn .
Therefore, |Hn | = mn . We denote the indices of all cached messages as H,
H=

N
[

(2)

Hn ,

n=1

where Hn1 ∩ Hn2 = ∅, if n1 6= n2 . Due to the cache memory size constraint, we require
|H| =

N
X

mn ≤ M.

(3)

n=1

Since the user caches mn messages from the nth database, Hn is known to the nth database.
Since the databases do not communicate with each other, Hn is unknown to the other
databases. We use m = (m1 , . . . , mN ) to represent the prefetching phase. After the prefetching phase, the user learns |H| messages, denoted as WH = {Wi1 , . . . , Wi|H| }. We refer to WH
as partially known private side information.
In the retrieval phase, the user privately generates a desired message index θ ∈ [K] \ H,
and wishes to retrieve message Wθ such that no database knows which message is retrieved.
Since the desired message index θ and cached message indices H are independent of the
message contents, for random variables θ, H, and W1 , . . . , WK , we have
H (θ, H, W1 , . . . , WK ) = H (θ, H) + H(W1 ) + · · · + H(WK ).
[θ,H]

(4)

[θ,H]

In order to retrieve Wθ , the user sends N queries Q1 , . . . , QN to the N databases,
[θ,H]
where Qn is the query sent to the nth database for message Wθ given the user has partially
known private side information WH . The queries are generated according to H, which is
independent of the realizations of the K messages. Therefore, we have
[θ,H]

I(W1 , . . . , WK ; Q1

[θ,H]

, . . . , QN ) = 0.

(5)

To ensure that individual databases do not know which message is retrieved and also
do not know the cached messages from other databases, i.e., to guarantee the privacy of
(θ, H \ Hn ), we need to satisfy the following privacy constraint, ∀n ∈ [N], ∀H, H′ such that
|H| = |H′ | ≤ M, Hn ⊂ H, Hn ⊂ H′ , and ∀θ ∈ [K] \ H, ∀θ′ ∈ [K] \ H′ ,
′

′

′

′

,H ]
, An[θ ,H ] , W1 , . . . , WK , Hn ),
, W1 , . . . , WK , Hn ) ∼ (Q[θ
, A[θ,H]
(Q[θ,H]
n
n
n

5

(6)

where A ∼ B means that A and B are identically distributed.
[θ,H]
[θ,H]
Upon receiving the query Qn , the nth database replies with an answering string An ,
[θ,H]
which is a function of Qn and all the K messages. Therefore, ∀θ ∈ [K] \ H, ∀n ∈ [N],
H(A[θ,H]
|Q[θ,H]
, W1 , . . . , WK ) = 0.
n
n
[θ,H]

(7)

[θ,H]

After receiving the answering strings A1 , . . . , AN from all the N databases, the user
needs to decode the desired message Wθ reliably. By using Fano’s inequality, we have the
following reliability constraint


[θ,H]
[θ,H]
[θ,H]
[θ,H]
= o(L),
H Wθ |WH , H, Q1 , . . . , QN , A1 , . . . , AN

(8)

→ 0 as L → ∞.
where o(L) denotes a function such that o(L)
L
For fixed N, K, and pretching scheme m = (m1 , . . . , mN ), a pair (D(m), L(m)) is achievable if there exists a PIR scheme for messages of size L(m) symbols long with partially known
private side information satisfying the privacy constraint (6) and the reliability constraint (8),
where D(m) represents the expected number of downloaded symbols (over all the queries)
[θ,H]
[θ,H]
[θ,H]
[θ,H]
from the N databases via the answering strings A1:N , where A1:N = (A1 , . . . , AN ), i.e.,
D(m) =

N
X
n=1


.
H A[θ,H]
n

(9)

In this work, for fixed N, K, and M, we aim to characterize the optimal normalized download
cost D ∗ , where
∗

D = inf
m:(3)

3




D(m)
: (D(m), L(m)) is achievable .
L(m)

(10)

Main Results

We characterize the exact normalized download cost for the PIR problem with partially
known private side information as shown in the following theorem.
Theorem 1 In the PIR problem with partially known private side information under the
cache memory size constraint |H| ≤ M, the optimal normalized download cost is
1
1
+ · · · + K−M −1
N
N
1 K−M
1 − (N )
.
=
1 − N1

D∗ = 1 +

(11)
(12)

The converse proof for Theorem 1 is given in Section 4, and the achievability proof for
Theorem 1 is given in Section 5. Theorem 1 does not assume any particular property for
6

the prefetching strategy, i.e., m is arbitrary except for satisfying the memory size constraint.
We have a few remarks.
1−

1

Remark 1 Theorem 1 implies that C = D1∗ = 1−( 1 )NK−M . Surprisingly, this capacity expresN
sion is exactly the same as the capacity for the PIR problem with completely unknown private
side information in [32]. This implies that there is no loss in capacity due to employing the
same databases for both prefetching and retrieval phases. The reason for this phenomenon
is that although each database has a partial knowledge about some of the cached messages at
the user, the privacy constraint on this known side information is relaxed.
Remark 2 The normalized download cost in Theorem 1 is the same as the normalized download cost for the classical PIR problem [12] if the number of messages is K − M. That is, a
cache of size M messages effectively reduces the total number of messages by M. Noting that
the download cost in [12] monotonically increases in the number of messages, the effective
reduction in the number of messages by the cache size results in a significant reduction in the
download cost due to the presence of side information at the user even though it is partially
known by the databases and it needs to be kept private against other databases.
Remark 3 The optimal prefetching strategy exploits the entire cache memory of the user as
the capacity expression is monotonically increasing in M.
Remark 4 In Section 5, we present the capacity achieving schemes for the partially known
private side information. We note that, in general the PIR scheme in [32] is a valid achievable scheme for our problem as well. Nevertheless, in the special case of uniform prefetching,
= m ∈ N, we provide a different achievable scheme that exploits the prefetchi.e., mn = M
N
M
ing uniformity to work with message size L = N K−m = N K− N in contrast to L = N K
needed for the scheme in [32], i.e., the message size is decreased by an exponential factor
M
N N . Furthermore, we note that although both schemes need an MDS code to reduce the
number of downloaded equations, we note that the field size needed to realize this MDS code
∈ N) compared with the field size needed in
is significantly smaller with our scheme (if M
N
the scheme in [32]. This implies that although uniform prefetching does not affect the PIR
capacity, it significantly simplifies the achievable scheme.

4

Converse Proof

In this section, we derive a general lower bound for the normalized download cost D ∗ given
in (10). We extend the techniques presented in [12, 32] to the PIR problem with partially
known private side information.
For the prefetching vector m = (m1 , . . . , mN ) satisfying (3), we note that satisfying the
memory size constraint with equality leads to a valid lower bound on (10). Consequently, we
P
first consider the case N
n=1 mn = M̃ ≤ M, i.e., we study the case when the user learns M̃
7

messages after the prefetching phase. Since we do not specify the prefetching strategy m in
P
advance, the following lower bound is valid for all m such that N
n=1 mn = M̃ . Without loss
of generality, we relabel the M̃ cached messages as W1 , W2 , . . . , WM̃ , i.e., H = {1, 2, . . . , M̃}
and WH = W1:M̃ . We first need the following lemma, which characterizes a lower bound on
the length of the undesired portion of the answering strings as a consequence of the privacy
constraint on the retrieved message.
Lemma 1 (Interference lower bound) For the PIR with partially known private side
information, the interference from undesired messages within the answering strings, D − L,
is lower bounded by,


[M̃+1,H]
[M̃+1,H]
D − L + o(L) ≥ I WM̃ +2:K ; H, Q1:N
, A1:N
|WH , WM̃ +1 .

(13)

If the privacy constraint is absent, the user downloads only L symbols for the desired
message, however, when the privacy constraint is present, it should download D symbols.
The difference between D and L, i.e., D − L, corresponds to the undesired portion of the
answering strings. Note that Lemma 1 is an extension of [12, Lemma 5] if M̃ = 0, i.e., the
user has no partially known private side information. Lemma 1 differs from its counterpart
in [31, Lemma 1] in two aspects, namely, the left hand side is D(r) − L(1 − r) in [31] as the
user requests to download the uncached bits only, and the bound in [31, Lemma 1] constructs
K − 1 distinct lower bounds by changing k in contrast to one bound here as it always starts
from WM̃ +2 . Finally, we note that a similar argument to Lemma 1 can be implied from [32].
Proof: We start with the right hand side of (13),


[M̃+1,H]
[M̃+1,H]
I WM̃ +2:K ; H, Q1:N
, A1:N
|WH , WM̃ +1



[M̃ +1,H]
[M̃+1,H]
= I WM̃ +2:K ; H, Q1:N
, A1:N
, WM̃ +1 |WH − I WM̃ +2:K ; WM̃+1 |WH .

(14)

For the first term on the right hand side of (14), we have



[M̃ +1,H]
[M̃+1,H]
I WM̃ +2:K ; H, Q1:N
, A1:N
, WM̃ +1 |WH




[M̃+1,H]
[M̃+1,H]
[M̃+1,H]
[M̃ +1,H]
= I WM̃ +2:K ; H, Q1:N
, A1:N
|WH + I WM̃+2:K ; WM̃+1 |H, Q1:N
, A1:N
, WH

(15)


(8)
[M̃ +1,H]
[M̃+1,H]
= I WM̃ +2:K ; H, Q1:N
, A1:N
|WH + o(L)
(16)


(4),(5)
[M̃ +1,H]
[M̃+1,H]
+ o(L)
(17)
= I WM̃ +2:K ; A1:N
|WH , H, Q1:N




[M̃ +1,H]
[M̃ +1,H]
[M̃+1,H]
[M̃ +1,H]
= H A1:N
|WH , H, Q1:N
− H A1:N
|WH , H, Q1:N
, WM̃ +2:K + o(L)
(18)




(8)
[M̃ +1,H]
[M̃+1,H]
[M̃+1,H]
[M̃ +1,H]
− H A1:N
, WM̃+1 |WH , H, Q1:N
, WM̃ +2:K + o(L)
= H A1:N
|WH , H, Q1:N
(19)

8



[M̃ +1,H]
− H WM̃ +1 |WH , H, Q1:N
, WM̃ +2:K + o(L)
≤H



(4),(5)
[M̃ +1,H]
[M̃+1,H]
= H A1:N
|WH , H, Q1:N
− H WM̃ +1 |WH , WM̃+2:K + o(L)


[M̃ +1,H]
[M̃ +1,H]
− L + o(L)
= H A1:N
|WH , H, Q1:N


[M̃ +1,H]
≤ H A1:N
− L + o(L)


[M̃ +1,H]
[M̃+1,H]
A1:N
|WH , H, Q1:N



≤ D − L + o(L),



(20)
(21)
(22)
(23)
(24)

[M̃ +1,H]
[M̃+1,H]
H, Q1:N
, A1:N
, WH



where (16), (19) follow from the decodability of WM̃ +1 given
,


[M̃ +1,H]
, (21) follows from the
(17) follows from the independence of WM̃ +2:K and H, Q1:N


[M̃ +1,H]
independence of WM̃ +1 and H, Q1:N
, and (24) follows from the independence bound.
For the second term on the right hand side of (14), we have



I WM̃ +2:K ; WM̃ +1 |WH = H WM̃ +1 |WH − H WM̃ +1 |WH , WM̃ +2:K
= L − L = 0.

(25)
(26)

Combining (14), (24), and (26) yields (13). 
In the following lemma, we prove an inductive relation for the mutual information term
on the right hand side of (13).
Lemma 2 (Induction lemma) For all k ∈ {M̃ + 2, . . . , K}, the mutual information term
in Lemma 1 can be inductively lower bounded as,


[k−1,H]
[k−1,H]
I Wk:K ; H, Q1:N , A1:N |WH , WM̃ +1:k−1
 L − o(L)
1 
[k,H]
[k,H]
.
≥ I Wk+1:K ; H, Q1:N , A1:N |WH , WM̃+1:k +
N
N

(27)

Lemma 2 is a generalization of [12, Lemma 6] to our setting. The main difference between
Lemma 2 and [32] is that in order to apply the partial privacy constraint, the random variable
H should be used in its local form Hn as it corresponds to the partial knowledge of the nth
database.
Proof: We start with the left hand side of (27),
I



[k−1,H]
[k−1,H]
Wk:K ; H, Q1:N , A1:N |WH , WM̃+1:k−1





1
[k−1,H]
[k−1,H]
× N × I Wk:K ; H, Q1:N , A1:N |WH , WM̃+1:k−1
N
N

1 X
I Wk:K ; Hn , Q[k−1,H]
, A[k−1,H]
|WH , WM̃ +1:k−1
≥
n
n
N n=1
=

N

1 X
≥
I Wk:K ; Q[k−1,H]
, A[k−1,H]
|WH , WM̃ +1:k−1 , Hn
n
n
N n=1

9

(28)
(29)
(30)

N

1 X
=
I Wk:K ; Q[k,H]
, A[k,H]
|WH , WM̃+1:k−1 , Hn
n
n
N n=1

(6)

N

1 X
[k,H]
I Wk:K ; A[k,H]
|W
,
W
,
H
,
Q
=
H
n
n
n
M̃ +1:k−1
N n=1

(4),(5)

N

1 X
=
H A[k,H]
|WH , WM̃ +1:k−1, Hn , Q[k,H]
n
n
N n=1

(7)

N

1 X  [k,H]
[k,H]
[k,H]
H An |WH , WM̃ +1:k−1, H, Q1:N , A1:n−1
≥
N n=1

(31)
(32)
(33)
(34)

N

1 X 
[k,H]
[k,H]
=
(35)
I Wk:K ; A[k,H]
|W
,
W
,
H,
Q
,
A
H
n
1:n−1
M̃ +1:k−1
1:N
N n=1

1 
[k,H]
[k,H]
(36)
= I Wk:K ; A1:N |WH , WM̃ +1:k−1, H, Q1:N
N


(4),(5) 1
[k,H]
[k,H]
=
(37)
I Wk:K ; H, Q1:N , A1:N |WH , WM̃ +1:k−1
N
 o(L)

(8) 1
[k,H]
[k,H]
(38)
= I Wk:K ; Wk , H, Q1:N , A1:N |WH , WM̃ +1:k−1 −
N
N
 o(L)

1 
1
[k,H]
[k,H]
= I Wk:K ; Wk |WH , WM̃+1:k−1 + I Wk:K ; H, Q1:N , A1:N |WH , WM̃+1:k −
N
N
N
(39)


L − o(L)
1
[k,H]
[k,H]
= I Wk+1:K ; H, Q1:N , A1:N |WH , WM̃ +1:k +
,
(40)
N
N
(7)

where (29) follows from the non-negativity of mutual information, (31) follows from the
privacy constraint, (32) follows from the independence of the messages and the queries, (33),
(35) follow from the fact that answer strings are deterministic functions of the messages and
the queries, (34) follows from 
the fact that
 conditioning reduces entropy, (37) follows from
[k,H]
the independence of Wk:K and H, Q1:N , (38) follows from the reliability constraint on Wk ,
and (40) follows from the independence of Wk and (WH , WM̃+1:k−1 ). 
Now, we are ready to derive the lower bound for arbitrary K, N, and M̃ . This can be
obtained by applying Lemma 1 and Lemma 2 successively.
Lemma 3 For fixed N, K, and M̃ ≤ M, we have


1
1
− o(L).
D ≥L 1+
+···+
N
N K−M̃ −1

(41)

Proof: We have


(13)
[M̃ +1,H]
[M̃+1,H]
D ≥ L + I WM̃ +2:K ; H, Q1:N
, A1:N
|WH , WM̃ +1 − o(L)

(27)
L
1 
[M̃ +2,H]
[M̃+2,H]
≥ L+
+ I WM̃ +3:K ; H, Q1:N
, A1:N
|WH , WM̃ +1:M̃ +2 − o(L)
N
N
10

(42)
(43)

(27)

≥ L+

(27)


L
1 
L
[M̃ +3,H]
[M̃+3,H]
+ 2 + I WM̃ +4:K ; H, Q1:N
, A1:N
|WH , WM̃ +1:M̃ +3 − o(L)
N
N
N

≥ ...


(27)
1
1
≥ L 1+
+···+
− o(L),
N
N K−M̃−1

(44)
(45)
(46)

where (42) follows from Lemma 1, (43)-(46) follow from applying Lemma 2 starting from
k = M̃ + 2 to k = K, which differs from [12] in terms of the starting point of the induction.

We conclude the converse proof by dividing by L and taking L → ∞ in (41), to have
D∗ ≥ 1 +

1
1
+···+
.
K−
N
N M̃−1

(47)

Finally, we note that the right hand side of (47) is monotonically decreasing in M̃. Since
M̃ ≤ M, the lowest lower bound is obtained by taking M̃ = M, which yields the final
converse bound,
D∗ ≥ 1 +

1
1
+ · · · + K−M −1 .
N
N

(48)

P
Remark 5 We note that if (48) is tight, any prefetching strategy m such that N
n=1 mn < M
is strictly suboptimal. Furthermore, the lower bound in (48) is the same for all prefetching
P
strategies m satisfying N
n=1 mn = M. In Section 5, we show that this lower bound is tight.

5

Achievability Proof

We first note that the achievability scheme proposed in [32] for the PIR problem with completely unknown private side information also works for the PIR problem with partially
known private side information here. The PIR scheme in [32] is based on MDS codes and
consists of two stages. The first stage determines the systematic part of the MDS code according to the queries generated in [12], which protects the privacy of the desired message,
i.e., in the first stage, the user designs the queries such that no information is leaked about
which message out of the K messages is the desired one. In the second stage, the user reduces
the number of the downloaded equations by downloading the parity part of the MDS code
only. For the case of partially known private side information here, two privacy constraints
should be satisfied: the desired message privacy constraint and the side information privacy
constraint. For the desired message, we note that the user should guarantee that the queries
designed to retrieve any of the K − mn messages should be indistinguishable at the nth
database (i.e., with the exception of the mn messages that the nth database has provided).
Due to the first stage, the privacy of the desired message holds as it was designed to protect

11

the privacy of all K messages, which is more restricted. Furthermore, the PIR scheme in [32]
also protects the privacy of the side information. The scheme in [32] ensures that the queries
do not reveal the identity of the M messages that are possessed by the user as side information. In our model, we note that we need to protect the privacy of M − mn messages from
the nth database, as the remaining mn messages are known to the nth database. Since the
privacy constraint imposed on the side information in our model is less restricted than [32],
using the scheme in [32] satisfies the privacy constraint of the side information in our case as
well. That is, the nth database cannot infer which other M − mn messages the user holds.
The PIR scheme in [32] achieves the normalized download cost in Theorem 1. The PIR
scheme in [32] requires a message size of N K symbols. In the following, we propose another
M
∈ N. Thus, this
achievability scheme which requires a message size of N K− N , if mn = M
N
scheme requires smaller sub-packetization and smaller field size for the MDS code.
Our PIR scheme for partially known private side information is based on the PIR schemes
in [12, 32]. To protect the privacy of the partially known private side information and the
privacy of the desired message, similar to [12], we apply the following three principles recursively: 1) database symmetry, 2) message symmetry within each database, and 3) exploiting
undesired messages as side information. We reduce the download cost by utilizing the reconstruction property of MDS codes by exploiting partially known private side information
as in [32]. The side information enables the user to request reduced number of equations as
a consequence of the user’s knowledge of M messages from the prefetching phase. Nevertheless, to protect the privacy of the side information, the user actually queries MDS coded
symbols which is mixture of K −mn messages. The main difference between our achievability
scheme and that in [12,32] is that since the nth database knows that the user has prefetched
mn messages, the user does not need to protect the privacy for these mn messages from the
nth database. This effectively reduces the number of messages that the scheme in [32] needs
to operate on to K −mn messages in contrast to K in [32]. When M
∈ N, we show that if the
N
, for all n, then
user caches the same number of messages from each database, i.e., mn = M
N
the lower bound in (11) is achievable by this scheme. This scheme reduces the message size
M
requirement from L = N K in [32] to L = N K− N here, simplifying the achievable scheme.

5.1
5.1.1

Motivating Examples
N = 2 Databases, K = 4 Messages, and M = 2 Cached Messages

Assume that each message is of size 8 symbols. We use ai , bi , ci and di , for i = 1, . . . , 8,
to denote the symbols of messages W1 , W2 , W3 and W4 , respectively. In this example, in
the prefetching phase, the user caches message W3 from database 1, and message W4 from
database 2; and in the retrieval phase, the user wishes to retrieve message W1 privately.
The user first generates the query table in Table 1. In Table 1, the user queries 7 symbols.
Since the user knows d1 from the cached message W4 , in order to use the partially known
12

private side information, the user can in fact reduce the number of queries to 6 equations per
database by ignoring d1 . However, if the user simply does not download d1 , it compromises
the privacy of W4 at database 1. Alternatively, the user queries the MDS coded version of
the 7 symbols. By using these 7 symbols as the systematic part, we can use a (13, 7) MDS
code. By downloading the 6 parity symbols, the user can reconstruct the whole 7 symbols
utilizing the knowledge of d1 . Therefore, the normalized download cost for our achievability
= 23 , which matches the lower bound in (11) for this case.
scheme is 6+6
8
For database 1, the query table in Table 1 induces the same distribution on the messages
W1 , W2 and W4 . Therefore, we guarantee the privacy of the desired message. The reliability
constraint can also be verified. Note that b2 is downloaded from database 2, and d2 is
downloaded in the prefetching phase. Therefore, a3 and a4 are decodable. By getting b4 + c3
from database 2, the user can get b4 due to the private side information W3 . Therefore, the
user can decode a7 from a7 + b4 + d4 . Similar arguments follow for database 2.
Table 1: Query table for K = 4, N = 2, M = 2.
DB1
DB2
a1
a2
b1
b2
d1
c1
a3 + b2
a5 + b1
a4 + d2
a6 + c2
b3 + d3
b4 + c3
a7 + b4 + d4 a8 + b3 + c4
WH1 ={W3 }

5.1.2

WH2 ={W4 }

N = 2 Databases, K = 5 Messages, and M = 2 Cached Messages

Assume that each message is of size 16 symbols. We use ai , bi , ci , di and ei , for i = 1, . . . , 16,
to denote the symbols of messages W1 , W2 , W3 , W4 , and W5 , respectively. In this example,
in the prefetching phase, the user caches message W4 from database 1, and message W5 from
database 2; and in the retrieval phase, the user wishes to retrieve message W1 privately. The
user first generates the query table in Table 2. In Table 2, the user queries 15 symbols. Since
the user knows e1 from the cached message W5 , in order to use the partially known private
side information, the user in fact queries the MDS coded version of the 15 symbols. By using
these 15 symbols as the systematic part, we can use a (29, 15) MDS code. By downloading the
14 parity symbols, the user can reconstruct the whole 15 symbols. Therefore, the normalized
download cost for our achievability scheme is 14+14
= 47 , which matches the lower bound in
16
(11) for this case.
For database 1, the query table in Table 2 induces the same distribution on the messages
W1 , W2 , W3 and W5 . Therefore, we guarantee the privacy of the desired message. The
13

reliability constraint can also be verified. Note that b2 , c2 are downloaded from database 2,
and e2 is downloaded in the prefetching phase. Therefore, a3 , a4 and a5 are decodable. By
getting b6 + d3 from database 2, the user can get b6 due to the private side information W4 .
Similarly, c6 is also decodable. Therefore, the user can decode a10 from a10 + b6 + e5 and a11
from a11 + c6 + e6 . By getting b8 + c8 + d7 from database 2, the user can get b8 + c8 due to
the private side information W4 . Therefore, the user can decode a15 from a15 + b8 + c8 + e8 .
Similar arguments follow for database 2.
Table 2: Query table for K = 5, N = 2, M = 2.
DB1
DB2
a1
a2
b1
b2
c1
c2
e1
d1
a3 + b2
a6 + b1
a4 + c2
a7 + c1
a5 + e2
a8 + d2
b3 + c3
b5 + c5
b4 + e3
b6 + d3
c4 + e4
c6 + d 4
a9 + b5 + c5
a12 + b3 + c3
a10 + b6 + e5
a13 + b4 + d5
a11 + c6 + e6
a14 + c4 + d6
b7 + c7 + e7
b8 + c8 + d7
a15 + b8 + c8 + e8 a16 + b7 + c7 + d8
WH1 ={W4 }

5.2

WH2 ={W5 }

General Achievable Scheme for

M
N

∈N

Let M
= m. In the prefetching phase, the user caches m messages from each database. To
N
achieve the lower bound shown in (11), in the retrieval phase, we choose the message size as
L = N K−m symbols. The details of the achievable scheme are as follows:
1. Initialization: The user permutes each message randomly and independently. After the
random permutation, we use Ui (j) to denote the jth symbol of the permuted message
Wi . Suppose the user wishes to retrieve Wθ privately. We then prepare the query table
by first querying Uθ (1) from database 1. Set the round index to r = 1.
2. Symmetry across databases: The user queries the same number of equations with the
same structure as database 1 from the remaining databases.
3. Message symmetry: For each database, to satisfy the privacy constraint, the user
should query equal amount of symbols from all other K − m messages. Since the user
14

has cached m messages from each database in the prefetching phase, the user does not
need to protect the privacy for these m messages. For the rth round, the user queries
sums of every r combinations of the K − m messages.
4. Exploiting side information: For database 1, the user exploits the side information
equations obtained from the other (N −1) databases to query sum of r+1 combinations
of the K − m messages, where sum of r combinations is the side information. If the r
combinations contain the cached message from database 1, we replace the overlapping
symbols through the symbols cached from other databases.
5. Repeat steps 2, 3, 4 after setting r = r + 1 until r = K − m + 1.
6. Shuffling the order of queries: By shuffling the order of queries uniformly, all possible
queries can be made equally likely regardless of the message index. This guarantees
the privacy of the desired message.
7. Downloading MDS parity parts: Now, the query table is finished. For each database,
let p be the number of queried symbols in the query table, and let q be the number of
queried symbols which are determined by the side information the user cached in the
prefetching phase. Apply a (2p − q, p) MDS code to the queried symbols by letting the
p symbols to be the systematic part. Finally, the user downloads the parity parts of
the MDS-coded answering strings which are p − q symbols for each database.

5.3

Normalized Download Cost

We now calculate the total number of downloaded symbols. We first calculate p, which is
the number of queried symbols in the query table for each database,



 

K−m
K −m
K−m
(N − 1)K−m−1
(49)
(N − 1) + · · · +
+
p=
K−m
2
1







K−m
K −m
K −m
1
K−m
2
(50)
(N − 1)
(N − 1) + · · · +
(N − 1) +
=
K−m
2
1
N −1

1
=
N K−m − 1 ,
(51)
N −1

where K−m
in (49) corresponds to the queries of sums of every r combinations of the K −m
r
messages, and (N − 1)r−1 corresponds to the number of sets of the available side information
from other (N − 1) databases.
We then calculate q, which is the number of queried symbols which are determined by
the side information the user cached in the prefetching phase,
q=






 
(N − 1)m
(N − 1)m
(N − 1)m
(N − 1)(N −1)m−1
(N − 1) + · · · +
+
(N − 1)m
2
1
15

(52)






(N − 1)m
(N − 1)m
1
(N −1)m
(N − 1)
(N − 1) + · · · +
=
(N − 1)m
1
N −1

1
=
N (N −1)m − 1 ,
N −1

(53)
(54)


where (N −1)m
in (52) corresponds to the queries which can be determined by the partially
r
known private side information, and (N − 1)r−1 corresponds to the number of sets of queries
consisting of r combinations.
Next, we calculate the number of symbols for the desired message,
L=N







 
K −m−1
K −m−1
K −m−1
K−m−1
(N − 1)
(N − 1) + · · · +
+
K −m−1
1
0
(55)

= N × N K−m−1 = N K−m ,

(56)


where K−m−1
in (55) corresponds to the queries containing the desired message and (N −
r−1
1)r−1 corresponds to the number of sets of queries consisting of r combinations.
Therefore, the normalized download cost becomes,
D
N(p − q)
=
L
L


N
N
K−m
(N −1)m
N
−
1
−
N
−
1
N −1
= N −1
N K−m
N K−m − N (N −1)m
N
×
=
N −1 "
N K−m
 K−M #
1
1
,
=
1 × 1−
N
1− N

(57)
(58)
(59)
(60)

which matches the lower bound in (11).
Remark 6 Note that although our achievable scheme and the scheme in [32] are both using
MDS coding to exploit the available side information, the field size requirements for realizing
the MDS codes are different. For the scheme of [32], a (2p̃ − q̃, p̃) MDS code is used, where
p̃ = N 1−1 (N K − 1) and q̃ = N 1−1 (N M − 1). This requires larger field size than the (2p − q, p)
∈ N), since 2p̃ − q̃ > (2p − q).
MDS code used in our scheme (if M
N

6

Conclusion

In this paper, we have introduced a new PIR model, namely, PIR with partially known
private side information as a natural model for studying practical PIR problems with cached
side information. In this model, the user and the databases engage in a caching/PIR scenario which consists of two phases, namely, prefetching phase and retrieval phase. The nth
16

database provides the user with mn side information messages in the prefetching phase such
P
that N
n=1 mn ≤ M, hence, each database has partial knowledge about the side information
in contrast to full knowledge in [29] and no knowledge in [30–32]. Based on this side information, the user designs a retrieval scheme that does not reveal the identity of the desired
message or the identities of the remaining M − mn messages to the nth database. For this
1− 1
model, we determined the exact capacity to be C = 1−( 1 )NK−M . The capacity is attained
N
for any prefetching strategy that satisfies the cache memory size constraint with equality.
The achievable scheme in [32] can also be used for this model. We further proposed another
PIR scheme which requires smaller sub-packetization and field size for the case of uniform
prefetching. Uniform prefetching, when feasible, is optimal. Interestingly, the capacity expression we derive for this problem is exactly the same as the capacity expression for the
PIR problem with completely unknown side information [32]. Therefore, our result implies
that there is no loss in employing the same databases for prefetching and retrieval purposes.

References
[1] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan. Private information retrieval.
Journal of the ACM, 45(6):965–981, 1998.
[2] W. Gasarch. A survey on private information retrieval. In Bulletin of the EATCS, 2004.
[3] 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.
[4] R. Ostrovsky and W. Skeith III. A survey of single-database private information retrieval: Techniques and applications. In International Workshop on Public Key Cryptography, pages 393–411. Springer, 2007.
[5] S. Yekhanin. Private information retrieval. Communications of the ACM, 53(4):68–73,
2010.
[6] N. B. Shah, K. V. Rashmi, and K. Ramchandran. One extra bit of download ensures
perfectly private information retrieval. In IEEE ISIT, June 2014.
[7] G. Fanti and K. Ramchandran. Efficient private information retrieval over unsynchronized databases. IEEE Journal of Selected Topics in Signal Processing, 9(7):1229–1239,
October 2015.
[8] T. Chan, S. Ho, and H. Yamamoto. Private information retrieval for coded storage. In
IEEE ISIT, June 2015.

17

[9] A. Fazeli, A. Vardy, and E. Yaakobi. Codes for distributed pir with low storage overhead.
In IEEE ISIT, June 2015.
[10] R. Tajeddine and S. El Rouayheb. Private information retrieval from MDS coded data
in distributed storage systems. In IEEE ISIT, July 2016.
[11] H. Sun and S. A. Jafar. The capacity of private information retrieval. In IEEE Globecom,
December 2016.
[12] H. Sun and S. A. Jafar. The capacity of private information retrieval. IEEE Trans. on
Info. Theory, 63(7):4075–4088, July 2017.
[13] H. Sun and S. Jafar. Blind interference alignment for private information retrieval. 2016.
Available at arXiv:1601.07885.
[14] H. Sun and S. Jafar. The capacity of robust private information retrieval with colluding
databases. 2016. Available at arXiv:1605.00635.
[15] 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. Available at arXiv:1701.07636.
[16] H. Sun and S. Jafar. The capacity of symmetric private information retrieval. 2016.
Available at arXiv:1606.08828.
[17] K. Banawan and S. Ulukus. The capacity of private information retrieval from coded
databases. IEEE Trans. on Info. Theory. Submitted September 2016. Also available at
arXiv:1609.08138.
[18] H. Sun and S. Jafar. Optimal download cost of private information retrieval for arbitrary
message length. 2016. Available at arXiv:1610.03048.
[19] H. Sun and S. Jafar. Multiround private information retrieval: Capacity and storage
overhead. 2016. Available at arXiv:1611.02257.
[20] K. Banawan and S. Ulukus. Multi-message private information retrieval: Capacity
results and near-optimal schemes. IEEE Trans. on Info. Theory. Submitted February
2017. Also available at arXiv:1702.01739.
[21] K. Banawan and S. Ulukus. The capacity of private information retrieval from Byzantine
and colluding databases. IEEE Trans. on Info. Theory. Submitted June 2017. Also
available at arXiv:1706.01442.
[22] Q. Wang and M. Skoglund. Symmetric private information retrieval for MDS coded
distributed storage. 2016. Available at arXiv:1610.04530.
18

[23] R. Freij-Hollanti, O. Gnilke, C. Hollanti, and D. Karpuk. Private information retrieval
from coded databases with colluding servers. 2016. Available at arXiv:1611.02062.
[24] H. Sun and S. Jafar. Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al. 2017. Available at arXiv:
1701.07807.
[25] Y. Zhang and G. Ge. A general private information retrieval scheme for MDS coded
databases with colluding servers. 2017. Available at arXiv: 1704.06785.
[26] Y. Zhang and G. Ge. Multi-file private information retrieval from MDS coded databases
with colluding servers. 2017. Available at arXiv: 1705.03186.
[27] Q. Wang and M. Skoglund. Linear symmetric private information retrieval for MDS
coded distributed storage with colluding servers. 2017. Available at arXiv:1708.05673.
[28] Q. Wang and M. Skoglund. Secure symmetric private information retrieval from colluding databases with adversaries. 2017. Available at arXiv:1707.02152.
[29] R. Tandon. The capacity of cache aided private information retrieval. 2017. Available
at arXiv: 1706.07035.
[30] S. Kadhe, B. Garcia, A. Heidarzadeh, S. El Rouayheb, and A. Sprintson. Private
information retrieval with side information. 2017. Available at arXiv:1709.00112.
[31] Y.-P. Wei, K. Banawan, and S. Ulukus. Fundamental limits of cache-aided private
information retrieval with unknown and uncoded prefetching. 2017. Available at
arXiv:1709.01056.
[32] Z. Chen, Z. Wang, and S. Jafar. The capacity of private information retrieval with
private side information. 2017. Available at arXiv:1709.03022.
[33] M. Karmoose, L. Song, M. Cardone, and C. Fragouli. Private broadcasting: an index
coding approach. 2017. Available at arXiv: 1701.04958.
[34] M. Karmoose, L. Song, M. Cardone, and C. Fragouli. Preserving privacy while broadcasting: k-limited-access schemes. 2017. Available at arXiv:1705.08437.

19

