1

Cache-Aided Private Information Retrieval with
Partially Known Uncoded Prefetching:

arXiv:1712.07021v1 [] 18 Dec 2017

Fundamental Limits
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

Abstract
We consider the problem of private information retrieval (PIR) from N non-colluding and replicated
databases, when the user is equipped with a cache that holds an uncoded fraction r of the symbols from
each of the K stored messages in the databases. This model operates in a two-phase scheme, namely,
the prefetching phase where the user acquires side information and the retrieval phase where the user
privately downloads the desired message. In the prefetching phase, the user receives

r
N

uncoded fraction

of each message from the nth database. This side information is known only to the nth database and
unknown to the remaining databases, i.e., the user possesses partially known side information. We
investigate the optimal normalized download cost D∗ (r) in the retrieval phase as a function of K, N ,
r. We develop lower and upper bounds for the optimal download cost. The bounds match in general
for the cases of very low caching ratio (r ≤

1
N K−1 )

and very high caching ratio (r ≥

K−2
N 2 −3N +KN ).

We fully characterize the optimal download cost caching ratio tradeoff for K = 3. For general K, N ,
and r, we show that the largest gap between the achievability and the converse bounds is

5
32 .

I. I NTRODUCTION
In today’s communication networks, the end-users are equipped with large memories, and
the data transmitted in the network has shifted from real-time generated data like voice to pregenerated content like movies. These two factors together have enabled caching techniques,
which store data in user cache a priori in order to reduce the peak-hour network traffic load. In
This work was supported by NSF Grants CNS 13-14733, CCF 14-22111, CNS 15-26608 and CCF 17-13977.

2

the meanwhile, privacy has become an important consideration for users, who wish to download
data from publicly accessable databases as privately and as efficiently as possible. This is studied
under the subject of private information retrieval (PIR). In this paper, we combine the caching
and PIR approaches, and consider the problem of PIR for a cache-enabled end-user.
The PIR problem considers the privacy of the requested message by a user from distributed
databases. In the classical setting of PIR [1], there are N non-communicating databases, each
storing the same set of K messages. The user wishes to download one of these K messages
without letting the databases know the identity of the desired message. A feasible scheme is
to download all the K messages from a database. However, this results in excessive download
cost since it results in a download that is K times the size of the desired message. The goal
of the PIR problem is to construct an efficient retrieval scheme such that no database knows
which message is retrieved. The PIR problem has originated in computer science [1]–[5] and
has drawn significant attention in information theory [6]–[11] in recent years.
Recently, Sun and Jafar [12] have characterized the optimal normalized download cost for

1
1
the classical PIR problem to be D
=
1
+
+
·
·
·
+
, where L is the message size and
K−1
L
N
N
D is the total number of downloaded bits from the N databases. Since the work of Sun-Jafar

[12], many interesting variants of the classical PIR problem 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, cache-aided PIR, PIR with private side information (PSI),
PIR for functions, storage constrained PIR, and their several combinations [13]–[35].
Also recently, Maddah-Ali and Niesen [36] have proposed a theoretical framework to study
the tradeoff between the cache memory size of users and the network traffic load for a two-phase
scheme. In the prefetching phase, when the network traffic is low, the server allocates data to
the user’s cache memory. In the retrieval phase, when the network traffic is high, the server
delivers the messages according to the users’ requests. By jointly designing the prefetching of
the cache content during the low traffic period and the delivery of the requested content during
the high traffic period, the coded-caching technique proposed in [36] achieves a global caching
gain significantly reducing the peak-time traffic load. The concept of coded-caching has been
applied to many different scenarios, such as, decentralized networks, device to device networks,

3

random demands, online settings, general cache networks, security constraints, finite file size
constraints, broadcast channels and their several combinations [37]–[55].
The caching technique not only reduces the traffic load but can also help the user to privately
retrieve the desired file more efficiently by providing additional side information. The interplay
between side information and the PIR problem has been studied recently in [27], [29]–[32]. We
first recall that the achievability scheme proposed in [12] is based on three principles: database
symmetry, message symmetry, and side information utilization. The side information in [12]
comes from the undesired bits downloaded from the other (N − 1) databases. Side information
plays an important role in the PIR problem; for instance, when N = 1 (single database), i.e.,
when no side information is available, the normalized download cost is K, which is the largest
possible. Caching can improve PIR download cost by providing useful side information.
Reference [27] is the first to study the cache-aided PIR problem. In [27], the user has a memory
of size KLr bits and can store an arbitrary function of the K messages, where 0 ≤ r ≤ 1 is the
caching ratio. [27] considers the case when the cached content is fully known to all N databases,

1
and determines the optimal normalized download cost to be (1 − r) 1 + N1 + · · · + N K−1
.

Although the result is pessimistic since it implies that the user cannot utilize the cached content
to further reduce the download cost, [27] reveals two new dimensions for the cache-aided PIR
problem. The first one is the databases’ awareness of the side information at its initial acquisition.
Different from [27], [29]–[31] study the case when the databases are unaware of the cached side
information, and [32] studies the case when the databases are partially aware of the cached
side information. The second one is the structure of the side information. Instead of storing an
arbitrary function of the K messages, [29], [31], [32] consider caching M full messages out of
total K messages, and [30] considers storing an r fraction of each message in uncoded form.
This paper is closely related to [30]. In [30], the databases are assumed to be completely
unaware of the side information. However, this may be practically challenging to implement.
Here, we consider a more natural model which uses the same set of databases for both prefetching
and retrieval phases. Therefore, different from [30], here each database gains partial knowledge
about the side information, that is the part it provides during the prefetching phase. Our aim is to
determine if there is a rate loss due to this partial knowledge with respect to the fully unknown
case in [30], and characterize this rate loss as a function of K, N and r.

4

In this work, we consider PIR with partially known uncoded prefetching. We consider the
PIR problem with a two-phase scheme, namely, prefetching phase and retrieval phase. In the
prefetching phase, the user caches an uncoded
The nth database is aware of these

KLr
N

r
N

fraction of each message from the nth database.

bit side information, while it has no knowledge about

the cached bits from the other (N − 1) databases. We aim at characterizing the optimal tradeoff
between the normalized download cost

D(r)
L

and the caching ratio r. For the outer bound, we

explicitly determine the achievable download rates for specific K + 1 caching ratios. Download
rates for any other caching ratio can be achieved by memory-sharing between the nearest explicit
points. Hence, the outer bound is a piece-wise linear curve which consists of K line segments.
For the inner bound, we extend the techniques of [12], [30] to obtain a piece-wise linear curve
which also consists of K line segments. We show that the inner and the outer bounds match
exactly at three line segments for any K. Consequently, we characterize the optimal tradeoff
for the very low (r ≤

1
)
N K−1

and the very high (r ≥

K−2
)
N 2 −3N +KN

caching ratios. As a direct

corollary, we fully characterize the optimal download cost caching ratio tradeoff for K = 3
messages. For general K, N and r, we show that the worst-case gap between the inner and the
outer bounds is

5
.
32

II. S YSTEM M ODEL
We consider a PIR problem with N non-communicating databases. Each database stores an
identical copy of K statistically independent messages, W1 , . . . , WK . Each message is L bits
long,
H(W1 ) = · · · = H(WK ) = L,

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

(1)

The user (retriever) has a local cache memory which can store up to KLr bits, where 0 ≤ r ≤ 1,
and r is called the caching ratio. There are two phases in this system: the prefetching phase and
the retrieval phase.
In the prefetching phase, for each message Wk , the user randomly and independently chooses
Lr bits out of the L bits to cache. The user caches the Lr bits of each message by prefetching the
same amount of bits from each database, i.e., the user prefetches

KLr
N

bits from each database.

∀n ∈ [N], where [N] = {1, 2, . . . , N}, we denote the indices of the cached bits from the nth

5

database by Hn and the cached bits from the nth database by the random variable Zn . Therefore,
P
the overall cached content Z is equal to (Z1 , . . . , ZN ), and H(Z) = N
n=1 H(Zn ) = KLr. We
S
further denote the indices of the cached bits by H. Therefore, we have H = N
n=1 Hn , where

Hn1 ∩ Hn2 = ∅, if n1 6= n2 . Since the user caches a subset of the bits from each message, this

is called uncoded prefetching. Here, we consider the case where database n knows Hn , but it
does not know H \ Hn . We refer to Z as partially known prefetching.
In the retrieval phase, the user privately generates an index θ ∈ [K], and wishes to retrieve
message Wθ such that it is impossible for any individual database to identify θ. Note that during
the prefetching phase, the desired message is unknown a priori. Therefore, the cached bit indices
H are independent of the desired message index θ. Note further that the cached bit indices H are
independent of the message contents. Therefore, for random variables θ, H, and W1 , . . . , WK ,
we have
H (θ, H, W1 , . . . , WK ) = H (θ) + H (H) + H(W1 ) + · · · + H(WK ).
[θ]

[θ]

(2)

[θ]

The user sends N queries Q1 , . . . , QN to the N databases, where Qn is the query sent to the
nth database for message Wθ . The queries are generated according to H, which are independent
of the realizations of the K messages. Therefore,
[θ]

[θ]

I(W1 , . . . , WK ; Q1 , . . . , QN ) = 0.

(3)

To ensure that individual databases do not know which message is retrieved, we need to satisfy
the following privacy constraint, ∀n ∈ [N], ∀θ ∈ [K],
[1]
[θ]
[θ]
(Q[1]
n , An , W1 , . . . , WK , Hn ) ∼ (Qn , An , W1 , . . . , WK , Hn ),

(4)

where A ∼ B means that A and B are identically distributed.
[θ]

[θ]

After receiving the query Qn , the nth database replies with an answering string An , which
[θ]

is a function of Qn and all the K messages. Therefore, ∀θ ∈ [K], ∀n ∈ [N],
H(An[θ] |Qn[θ] , W1 , . . . , WK ) = 0.
[θ]

[θ]

(5)

After receiving the answering strings A1 , . . . , AN from all the N databases, the user needs

6

to decode the desired message Wθ reliably. By using Fano’s inequality, we have the following
reliability constraint


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

where o(L) denotes a function such that

(6)

→ 0 as L → ∞.

For a fixed N, K, and caching ratio r, a pair (D(r), L) is achievable if there exists a PIR
scheme for message of size L bits long with partially known uncoded prefetching satisfying
the privacy constraint (4) and the reliability constraint (6), where D(r) represents the expected
number of downloaded bits (over all the queries) from the N databases via the answering strings
[θ]

[θ]

[θ]

[θ]

A1:N , where A1:N = (A1 , . . . , AN ), i.e.,
D(r) =

N
X
n=1


H A[θ]
n .

(7)

In this work, we aim at characterizing the optimal normalized download cost D ∗ (r) corresponding
to every caching ratio 0 ≤ r ≤ 1, where
∗

D (r) = inf




D(r)
: (D(r), L) is achievable ,
L

(8)

which is a function of the caching ratio r.
III. M AIN R ESULTS
We provide a PIR scheme for general K, N and r, which achieves the following normalized
download cost, D̄(r).
Theorem 1 (Outer bound) In the cache-aided PIR with partially known uncoded prefetching,
let s ∈ {1, 2, · · · , K − 1}, for the caching ratio rs , where

K−2
rs =

s−1

K−2
s−1



+

PK−1−s
i=0

,

(N − 1)i+1

K−1
s+i

(9)

the optimal normalized download cost D ∗ (rs ) is upper bounded by,
D ∗ (rs ) ≤ D̄(rs ) =

PK−1−s

K
(N − 1)i+1
i=0
s+1+i
.

P
K−1−s K−1
K−2
i+1
+
(N
−
1)
i=0
s−1
s+i



(10)

7

Moreover, if rs < r < rs+1 , and α ∈ (0, 1) such that r = αrs + (1 − α)rs+1 , then
D ∗ (r) ≤ D̄(r) = αD̄(rs ) + (1 − α)D̄(rs+1 ).

(11)

The proof of Theorem 1 is provided in Section IV. The outer bound in Theorem 1 is a piecewise linear curve, which consists of K line segments. These K line segments intersect at the
points rs .
We characterize an inner bound (converse bound), which is denoted by D̃(r), for the optimal
normalized download cost D ∗ (r) for general K, N, r.
Theorem 2 (Inner bound) In the cache-aided PIR with partially known uncoded prefetching,
the normalized download cost is lower bounded as,
∗

D (r) ≥ D̃(r) =
=

(1 − r)

max

i∈{2,··· ,K+1}

max

i∈{2,··· ,K+1}

K+1−i
X
j=0

K+1−i
X
j=0

 K−i

1
1 XK +1−i−j
−r 1−
Nj
N j=0
Nj

1
− (K + 2 − i)r.
Nj

(12)

(13)

The proof of Theorem 2 is provided in Section V. The inner bound in Theorem 2 is also a
piece-wise linear curve, which consists of K line segments. Interestingly, these K line segments
intersect at the points as follows,
r̃i =

1
N K−i

,

i = 1, · · · , K − 1.

(14)

The outer bounds provided in Theorem 1 and the inner bounds provided in Theorem 2 match
for some caching ratios r as summarized in the following corollary.
Corollary 1 (Optimal tradeoff for very low and very high caching ratios)

In the cache-

aided PIR with partially known uncoded prefetching, for very low caching ratios, i.e., for r ≤
1
,
N K−1

the optimal normalized download cost is given by,


1
1
+ · · · + K−1 − Kr.
D (r) = 1 +
N
N
∗

On the other hand, for very high caching ratios, i.e., for r ≥

K−2
,
N 2 −3N +KN

(15)
the optimal normalized

8

download cost is given by,

 1 + 1 − 2r,
N
∗
D (r) =
 1 − r,

K−2
N 2 −3N +KN
1
N

≤r≤

1
N

.

(16)

≤r≤1

Proof: From (9) and (14), we have

r1 = r̃1 =
rK−2 =
rK−1 = r̃K−1 =

1
N K−1
N2

,

K−2
,
− 3N + KN

1
.
N

For the outer bound of the case of very low caching ratios, from (10), we have
PK−2 K 
(N − 1)i+1
i=0
2+i
D̄(r1 ) = K−2 PK−2

K−1
+
(N − 1)i+1
i=0
0
1+i

P
K−2 K
1
(N − 1)i+2
i=0
2+i
(N −1)
=
N K−1

1
K
N
−
1
−
K(N
−
1)
(N −1)
=
N K−1
K
N − KN + K − 1
=
.
N K − N K−1

(17)
(18)
(19)

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

For the inner bound of the case of very low caching ratios, from (12), by choosing i = 2 and
using r = r1 , we have
 K−2

1
1 X K −1−j
D̃(r1 ) ≥ (1 − r1 )
− r1 1 −
j
N
N j=0
Nj
j=0




− 1 + N1K
1 − N1K
1
1
1 K−K
N
−
= 1 − K−1
1
−
2
N
N K−1
N
1 − N1
1 − N1





1
1
1
1
K
1

1 − K−1
=
1 − K − K−1 K −
−1+ K
N
N
N
N
N
1 − N1
K−1
X

=

N K − KN + K − 1
= D̄(r1 ).
N K − N K−1

(24)
(25)
(26)
(27)

Thus, since D̃(r1 ) ≤ D̄(r1 ) by definition, (27) implies D̃(r1 ) = D̄(r1 ).
For the outer bound of the case of very high caching ratios, from (10), we have

P1
K
i+1
N
i=0 K−1+i (N − 1)


D̄(rK−2) =
P1
K−2
K−1
N K−3 + i=0 K−2+i (N − 1)i+1 N

(28)

9

=

N 2 + KN − 2N − K + 1
,
N 2 − 3N + KN

(29)

and for the inner bound of the case of very high caching ratios, from (12) by choosing i = K
and using r = rK−2 ,
 0

1
X
1
1 X1−j
D̃(rK−2) ≥ (1 − rK−2 )
− rK−2 1 −
j
N
N j=0 N j
j=0
1
− 2rK−2
N
N 2 + KN − 2N − K + 1
=
= D̄(rK−2)
N 2 − 3N + KN
=1+

(30)
(31)
(32)

implying D̃(rK−2 ) = D̄(rK−2).
Finally, from (10), D̄(rK−1 ) =

N −1
,
N

and from (12) by choosing i = K +1 and using r = rK−1,

D̃(rK−1 ) ≥

N −1
= D̄(rK−1 )
N

(33)

implying D̃(rK−1 ) = D̄(rK−1).
Therefore, D̃(r) = D̄(r) at r = r1 , r = rK−2 and r = rK−1 . In addition to that D̃(0) = D̄(0)
and D̃(1) = D̄(1). Since both D̄(r) and D̃(r) are linear functions of r, and since D̃(0) = D̄(0)
and D̃(r1 ) = D̄(r1 ), we have D̃(r) = D̄(r) = D ∗ (r) for 0 ≤ r ≤ r1 . This is the very low caching
ratio region. In addition, since D̃(rK−2) = D̄(rK−2), D̃(rK−1) = D̄(rK−1) and D̃(1) = D̄(1),
we have D̃(r) = D̄(r) = D ∗ (r) for rK−2 ≤ r ≤ 1. This is the very high caching ratio region.

We use the example of K = 4, N = 2 to illustrate Corollary 1 (see Figure 1). In this case,
r1 = r̃1 = 81 , rK−2 = 13 , and rK−1 = r̃K−1 = 21 . Therefore, we have exact results for 0 ≤ r ≤
(very low caching ratios) and

1
3

1
8

≤ r ≤ 1 (very high caching ratios). We have a gap between the

achievability and the converse for medium caching ratios in

1
8

≤ r ≤ 13 . More specifically, line

segments connecting (0, 15
) and ( 81 , 11
); connecting ( 13 , 65 ) and ( 12 , 21 ); and connecting ( 21 , 12 ) and
8
8
(1, 0) are tight.
For the case K = 3, we have exact tradeoff curve for any N, r as shown in the following
corollary.
Corollary 2 (Optimal tradeoff for K = 3) In the cache-aided PIR with partially known uncoded prefetching with K = 3 messages, the optimal download cost caching ratio tradeoff is

10

2

(0,15/8)

Achievability
Converse

1.8
1.6

(1/8, 11/8)

1.4

D
L

1.2
1

(1/4, 1)

(1/3, 5/6)

0.8
0.6

(1/2, 1/2)

0.4
0.2
0

(1,0)
0

0.2

0.4

r

0.6

0.8

1

Fig. 1. Inner and outer bounds for K = 4, N = 2.

given explicitly as,


1 + N1 + N12 − 3r,



D ∗ (r) =
1 + N1 − 2r,




1 − r,

0≤r≤

1
N2

1
N2

≤r≤

1
N

1
N

≤r≤1

.

(34)

Proof: The proof follows from the proof of Corollary 1. Note that in this case, from (17) and
(18), r1 = rK−2 =
0 ≤ r ≤ r1 =

1
N2

1
;
N2

and from (19), r2 = rK−1 =

1
.
N

Thus, we have a tight result for

(very low caching ratios) and a tight result for rK−2 = r1 =

1
N2

≤ r ≤ 1,

i.e., a tight result for all 0 ≤ r ≤ 1. We have three segments in this case: [0, r1 ], [r1 , r2 ] and
[r2 , 1] with three different line expressions for the exact result as given in (9)-(10) and written
explicitly in (34). 
IV. ACHIEVABLE S CHEME
In this section, we present an achievable scheme for the outer bounds provided in Theorem 1.
Our achievable scheme is based on [12], [27], [30]. We first provide achievable schemes for the
caching ratios rs in (9) by applying the principles in [12]: 1) database symmetry, 2) message
symmetry within each database, and 3) exploiting undesired messages as side information. For

11

an arbitrary caching ratio r 6= rs , we apply the memory-sharing scheme in [27]. Since the cached
content is partially known by the databases, the achievable scheme is different from that in [30].
We first use the case of K = 3, N = 2 to illustrate the main ideas of our achievability scheme.
A. Motivating Example: K = 3 Messages and N = 2 Databases
We use ai , bi , and ci to denote the bits of messages W1 , W2 and W3 , respectively. We assume
that the user wants to retrieve message W1 privately without loss of generality.
1) Caching Ratio r1 = 41 : We choose the message size as 8 bits. In the prefetching phase,
for caching ratio r1 = 41 , the user caches 2 bits from each message. Therefore, the user caches
1 bit from each database for each message. Therefore, Z1 = (a1 , b1 , c1 ) and Z2 = (a2 , b2 , c2 ).
In the retrieval phase, for s = 1, we first mix 1 bit of side information with the desired bit.
Therefore, the user queries a3 + b2 and a4 + c2 from database 1. Note that database 1 knows
that the user prefetches Z1 . Therefore, the user does not use side information Z1 to retrieve
information from database 1. To keep message symmetry, the user further queries b3 + c3 from
database 1. Similarly, the user queries a5 + b1 , a6 + c1 and b4 + c4 from database 2. Then,
the user exploits the side information b4 + c4 to query a7 + b4 + c4 from database 1 and the
side information b3 + c3 to query a8 + b3 + c3 from database 2. After this step, no more side
information can be used and the message symmetry is attained for each database. Therefore, the
PIR scheme ends here. The decodability of message W1 can be shown easily, since the desired
bits are either mixed with cached side information or the side information obtained from other
databases. Overall, the user downloads 8 bits. Therefore, the normalized download cost is 1. We
summarize the queries in Table. I.
TABLE I

s

DB1

DB2

s=1

Q UERY TABLE FOR K = 3, N = 2, r1 = 14 .

a 3 + b2

a 5 + b1

a4 + c2

a6 + c1

b3 + c3

b4 + c4

a7 + b4 + c4

a8 + b3 + c3

Z1 = (a1 , b1 , c1 )

Z2 = (a2 , b2 , c2 )

12

2) Caching Ratio r2 = 21 : We choose the message size as 4 bits. In the prefetching phase,
for caching ratio r2 = 21 , the user caches 2 bits from each message. Therefore, the user caches
1 bit from each database for each message. Therefore, Z1 = (a1 , b1 , c1 ) and Z2 = (a2 , b2 , c2 ).
In the retrieval phase, for s = 2, we first mix 2 bits of side information with the desired bit.
Therefore, the user queries a3 + b2 + c2 from database 1. Similarly, the user queries a4 + b1 + c1
from database 2. After this, no more side information can be used and the message symmetry
is attained for each database. Therefore, the PIR scheme ends here. Overall, the user downloads
2 bits. Therefore, the normalized download cost is 21 . We summarize the queries in Table. II.
TABLE II
Q UERY TABLE FOR K = 3, N = 2, r2 = 21 .
s

DB1

DB2

s=2

a3 + b2 + c2

a4 + b1 + c1

Z1 = (a1 , b1 , c1 )

Z2 = (a2 , b2 , c2 )

3) Caching Ratio r = 31 : We choose the message size as 12 bits. In the prefetching phase,
for caching ratio r = 13 , the user caches 4 bits from each message. Therefore, the user caches
2 bits from each database for each message. Therefore, Z1 = (a1 , a2 , b1 , b2 , c1 , c2 ) and Z2 =
(a3 , a4 , b3 , b4 , c3 , c4 ). In the retrieval phase, we combine the achievable schemes in Section IV-A1
and IV-A2 as shown in Table III. The normalized download cost is 65 . By applying [27, Lemma 1]
and taking α = 32 , we can show that D̄( 13 ) = D̄( 23 · 41 + 13 · 12 ) = 32 D̄( 14 )+ 31 D̄( 12 ) = 32 ·1+ 13 · 21 = 56 .
TABLE III

s

DB1

DB2

s=1

Q UERY TABLE FOR K = 3, N = 2, r = 13 .

a 5 + b3

a 7 + b1

a6 + c3

a8 + c1

b5 + c5

b6 + c6

a9 + b6 + c6

a10 + b5 + c5

a11 + b4 + c4

a12 + b2 + c2

Z1 = (a1 , a2 , b1 , b2 , c1 , c2 )

Z2 = (a3 , a4 , b3 , b4 , c3 , c4 )

s=2

13

B. Achievable Scheme
We first present the achievable scheme for the caching ratios rs given in (9). Then, we apply
the memory-sharing scheme provided in [27] for the intermediate caching ratios.
1) Achievable Scheme for the Caching Ratio rs : For fixed K and N, there are K − 1 nondegenerate corner points (in addition to degenerate caching ratios r = 0 and r = 1). The caching
ratios, rs , corresponding to these non-degenerate corner points are indexed by s, which represents
the number of cached bits used in the side information mixture at the first round of the querying.
For each s ∈ {1, 2, . . . , K − 1}, we choose the length of the message to be L(s) for the corner
point indexed by s, where
 K−1−s
X K − 1
K−2
(N − 1)i+1 N.
+
L(s) = N
s+i
s−1
i=0


(35)

In the prefetching phase, for each message the user randomly and independently chooses


K−2
N K−2
bits
to
cache,
and
caches
bits from each database for each message. Therefore,
s−1
s−1

the caching ratio rs is equal to
rs =

K−2
s−1
PK−1−s K−1
(N
i=0
s+i

N

N

K−2
s−1



+



− 1)i+1 N

.

(36)

In the retrieval phase, the user applies the PIR scheme as follows:
1) Initialization: Set the round index to t = s + 1, where the tth round involves downloading
sums of every t combinations of the K messages.
2) Exploiting side information: If t = s + 1, for the first database, the user forms queries by
mixing s undesired bits cached from the other N − 1 databases in the prefetching phase
to form one side information equation. Each side information equation is added to one bit
from the uncached portion of the desired message. Therefore, for the first database, the

user downloads K−1
(N −1) equations in the form of a desired bit added to a mixture of s
s

cached bits from other messages. On the other hand, if t > s + 1, for the first database, the

user exploits the K−1
(N −1)t−s side information equations generated from the remaining
t−1
(N − 1) databases in the (t − 1)th round.

3) Symmetry across databases: The user downloads the same number of equations with the

same structure as in step 2 from every database. Consequently, the user decodes K−1
(N −
t−1

14

1)t−s desired bits from every database, which are done either using the cached bits as side
information if t = s+1, or the side information generated in the (t−1)th round if t > s+1.
4) Message symmetry: To satisfy the privacy constraint, the user should download the same

amount of bits from other messages. Therefore, the user downloads K−1
(N − 1)t−s
t
undesired equations from each database in the form of sum of t bits from the uncached
portion of the undesired messages.
5) Repeat steps 2, 3, 4 after setting t = t + 1 until t = K.
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.
Since the desired bits are added to the side information which is either obtained from the
cached bits (if t = s + 1) or from the remaining (N − 1) databases in the (t − 1)th round when
t > s + 1, the user can decode the uncached portion of the desired message by canceling out the
side information bits. In addition, for each database, each message is queried equally likely with
the same set of equations, which guarantees privacy as in [12]. Therefore, the privacy constraint
in (4) and the reliability constraint in (6) are satisfied.
We now calculate the total number of downloaded bits for the caching ratio rs in (36). For the
round t = s + 1, we exploit s cached bits to form the side information equation. Therefore, each
download is a sum of s + 1 bits. For each database, we utilize the side information cached from
other N − 1 databases. In addition to the message symmetry step enforcing symmetry across K

K
messages, we download s+1
(N − 1) bits from a database. Due to the database symmetry step,

K
in total, we download s+1
(N − 1)N bits. For the round t = s + i > s + 1, we exploit s + i − 1
undesired bits downloaded from the (t − 1)th round to form the side information equation. Due

K
to message symmetry and database symmetry, we download s+1+i
(N − 1)i+1 N bits. Overall,
the total number of downloaded bits is,
D(rs ) =

K−1−s
X 
i=0


K
(N − 1)i+1 N.
s+1+i

(37)

By canceling out the undesired side information bits using the cached bits for the round t =

s + 1, we obtain K−1
(N − 1)N desired bits. For the round t = s + i > s + 1, we decode
s

K−1
(N −1)i+1 N desired bits by using the side information obtained in (t−1)th round. Overall,
s+i

15

we obtain L(s) − N

K−2
s−1



desired bits. Therefore, the normalized download cost is,

D(rs )
D̄(rs ) =
=
L(s)
N

PK−1−s

K
(N − 1)i+1 N
i=0
s+1+i

P
K−1−s K−1
K−2
(N − 1)i+1 N
+
i=0
s+i
s−1



.

(38)

2) Achievable Scheme for the Caching Ratios not Equal to rs : For caching ratios r which
are not exactly equal to (36) for some s, we first find an s such that rs < r < rs+1 . We choose
0 < α < 1 such that r = αrs + (1 − α)rs+1. By using the memory-sharing scheme in [27,
Lemma 1], we achieve the following normalized download cost,
D̄(r) = αD̄(rs ) + (1 − α)D̄(rs+1 ).

(39)

V. C ONVERSE P ROOF
In this section, we derive an inner bound for the cache-aided PIR with partially known uncoded
prefetching. We extend the techniques in [12], [30] to our problem. The main difference between
this proof and that in [30] is the usage of privacy constraint given in (4).
Lemma 1 (Interference lower bound) [30, Lemma 1] For the cache-aided PIR with partially
known uncoded prefetching, the interference from undesired messages within the answering
strings D(r) − L(1 − r) is lower bounded by,


[k−1]
[k−1]
D(r) − L(1 − r) + o(L) ≥ I Wk:K ; H, Q1:N , A1:N |W1:k−1, Z

(40)

for all k ∈ {2, . . . , K}.
The proof of Lemma 1 is similar to [30, Lemma 1]. In the following lemma, we prove an
inductive relation for the mutual information term on the right hand side of (40).
Lemma 2 (Induction lemma) For all k ∈ {2, . . . , K}, the mutual information term in Lemma 1
can be inductively lower bounded as,


[k−1]
[k−1]
I Wk:K ; H, Q1:N , A1:N |W1:k−1, Z
 L(1 − r) − o(L) 1 − N
1 
[k]
[k]
≥ I Wk+1:K ; H, Q1:N , A1:N |W1:k , Z +
+
(K − k + 1)Lr. (41)
N
N
N

16

Lemma 2 is a generalization of [12, Lemma 6] and [30, Lemma 2], and it reduces to [12,
Lemma 6] when r = 0. Compared to [30, Lemma 2], the lower bound in (41) is increased by
(K−k+1)Lr
,
N

since the cached content is partially known by the databases.

Proof: We start with the left hand side of (41),


[k−1]
[k−1]
I Wk:K ; H, Q1:N , A1:N |W1:k−1 , Z


[k−1]
[k−1]
= I Wk:K ; H, Q1:N , A1:N , Z|W1:k−1 − I(Wk:K ; Z|W1:k−1).

(42)

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


[k−1]
[k−1]
I Wk:K ; H, Q1:N , A1:N , Z|W1:k−1


1
[k−1]
[k−1]
= NI Wk:K ; H, Q1:N , A1:N , Z|W1:k−1
N
N

1 X
≥
I Wk:K ; Hn , Qn[k−1] , An[k−1], Zn |W1:k−1
N n=1
" N
#
N
X

1 X
I (Wk:K ; Hn , Zn |W1:k−1) +
I Wk:K ; Qn[k−1] , An[k−1]|W1:k−1 , Hn , Zn
=
N n=1
n=1
" N
#
N
X
X

1
I (Wk:K ; Zn |W1:k−1 ) +
I Wk:K ; Qn[k−1] , An[k−1] |W1:k−1, Hn , Zn
≥
N n=1
n=1
"
#
N
X

1
(K − k + 1)Lr
=
N×
I Wk:K ; Qn[k−1] , An[k−1] |W1:k−1, Hn , Zn
+
N
N
n=1
=
(4)

=

(2),(3)

=

(5)

=

≥

N

1 X
(K − k + 1)Lr
I Wk:K ; Qn[k−1] , An[k−1] |W1:k−1, Hn , Zn
+
N
N n=1
N

(K − k + 1)Lr
1 X
[k]
I Wk:K ; Q[k]
+
n , An |W1:k−1 , Hn , Zn
N
N n=1

N

1 X
(K − k + 1)Lr
[k]
+
I Wk:K ; A[k]
n |W1:k−1 , Hn , Zn , Qn
N
N n=1

N

1 X
(K − k + 1)Lr
[k]
H A[k]
+
n |W1:k−1 , Hn , Zn , Qn
N
N n=1

N

(K − k + 1)Lr
1 X  [k]
[k]
[k]
H An |W1:k−1 , H, Z, Q1:N , A1:n−1
+
N
N n=1

N

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

(K − k + 1)Lr
1 
[k]
[k]
=
+ I Wk:K ; A1:N |W1:k−1 , H, Z, Q1:N
N
N

(5)

=

(43)
(44)
(45)
(46)
(47)
(48)
(49)
(50)
(51)
(52)
(53)
(54)

17


(K − k + 1)Lr
1 
[k]
[k]
+ I Wk:K ; H, Q1:N , A1:N |W1:k−1, Z
(55)
N
N
 o(L)
1 
(6) (K − k + 1)Lr
[k]
[k]
+ I Wk:K ; Wk , H, Q1:N , A1:N |W1:k−1, Z −
(56)
=
N
N
N

i
1 h
(K − k + 1)Lr
[k]
[k]
I (Wk:K ; Wk |W1:k−1, Z) + I Wk:K ; H, Q1:N , A1:N |W1:k , Z
+
=
N
N
o(L)
−
(57)
N
 o(L)
(K − k + 1)Lr L(1 − r)
1 
[k]
[k]
=
+
+ I Wk+1:K ; H, Q1:N , A1:N |W1:k , Z −
,
(58)
N
N
N
N

(2),(3)

=

where (44) and (46) follow from the non-negativity of mutual information, (47) is due to the fact
that from the nth database, the user prefetches

KLr
N

bits, (49) follows from the privacy constraint,
[k]

(50) and (55) follow from the independence of Wk:K and Qn , (51) and (53) follow from the
[k]

[k]

fact that the answering string An is a deterministic function of (W1:K , Qn ), (52) follows from
conditioning reduces entropy, and (56) follows from the reliability constraint.
For the second term on the right hand side of (42), we have
I(Wk:K ; Z|W1:k−1) = H (Z|W1:k−1 ) − H(Z|W1:K )
= (K − k + 1) Lr

(59)
(60)

where (60) follows from the uncoded nature of the cached bits.
Combining (42), (58) and (60) yields (41). 
Now, we are ready to derive the general inner bound for arbitrary K, N, r. To obtain this
bound, we use Lemma 1 to find K lower bounds by varying the index k in the lemma from
k = 2 to k = K, and by using the non-negativity of mutual information for the Kth bound.
Next, we inductively lower bound each term of Lemma 1 by using Lemma 2 (K − k + 1) times
to get K explicit lower bounds.
Lemma 3 For fixed N, K and r, we have
D(r) ≥ L(1 − r)

K+1−k
X
j=0

where k = 2, . . . , K + 1.

 K−k

1
1 X K +1−k−j
− Lr 1 −
+ o(L),
Nj
N j=0
Nj

(61)

18

Proof: We have
(40)

D(r) ≥ L(1 − r) + I



[k−1]
[k−1]
Wk:K ; H, Q1:N , A1:N |W1:k−1 , Z



− o(L)

L(1 − r)
1
≥ L(1 − r) +
− (K − k + 1)Lr + (K − k + 1)Lr
N
N

1 
[k]
[k]
+ I Wk+1:K ; H, Q1:N , A1:N |W1:k , Z − o(L)
N 

 

(41)
1
1
(K − k)
Lr
≥ L(1 − r) 1 +
+ 2 +
− Lr (K − k + 1) +
N
N
N
N

1 
[k+1]
[k+1]
+ 2 I Wk+2:K ; H, Q1:N , A1:N |W1:k+1 , Z − o(L)
N

(41)

(62)

(63)

(64)

(41)

≥ ...

(65)

 K−k

K+1−k
X 1
(41)
1 X K +1−k−j
− Lr 1 −
+ o(L),
≥ L(1 − r)
Nj
N j=0
Nj
j=0

(66)

where (62) follows from Lemma 1, and the remaining steps follow from the successive application of Lemma 2. 
We conclude the converse proof by dividing by L and taking the limit as L → ∞. Then, for
k = 2, · · · , K + 1, we have
∗

D (r) ≥ (1 − r)

K+1−k
X
j=0

 K−k

1
1 X K +1−k−j
−r 1−
.
Nj
N j=0
Nj

(67)

Since (67) gives K intersecting line segments, the normalized download cost is lower bounded
by their maximum value as follows
∗

D (r) ≥

max

(1 − r)

i∈{2,··· ,K+1}

K+1−i
X
j=0

 K−i

1 XK +1−i−j
1
−r 1−
.
Nj
N j=0
Nj

(68)

VI. F URTHER E XAMPLES
A. K = 4 Messages, N = 2 Databases
For K = 4 and N = 2, we present achievable PIR schemes for caching ratios r1 =
Table IV, r2 =

1
3

in Table V, and r3 =

1
2

1
8

in

in Table VI. The PIR schemes aim to retrieve message

W1 , where we use ai to denote its bits. The achievable normalized download costs for these
caching ratios are
in Figure 1.

11 5
,
8 6

and 21 , respectively. The plot of the inner and outer bounds can be found

19

TABLE IV
Q UERY TABLE FOR K = 4, N = 2 AND r1 = 81 .
s

DB2

a 3 + b2

a 6 + b1

a4 + c2

a7 + c1

a 5 + d2

a 8 + d1

b3 + c3

b5 + c5

b4 + d 3

b6 + d 5

c4 + d4

c6 + d6

a9 + b5 + c5

a12 + b3 + c3

a10 + b6 + d5

a13 + b4 + d3

a11 + c6 + d6

a14 + c4 + d4

b7 + c7 + d7

b8 + c8 + d8

a15 + b8 + c8 + d8

a16 + b7 + c7 + d7

Z1 = (a1 , b1 , c1 , d1 )

Z2 = (a2 , b2 , c2 , d2 )

s=1

DB1

TABLE V
Q UERY TABLE FOR K = 4, N = 2, r2 = 13 .
s

DB2

a5 + b3 + c3

a8 + b1 + c1

a 6 + d 3 + b4

a 9 + d 1 + b2

a7 + c4 + d4

a10 + c2 + d2

b5 + c5 + d5

b6 + c6 + d6

a11 + b6 + c6 + d6

a12 + b5 + c5 + d5

Z1 = (a1 , a2 , b1 , b2 , c1 , c2 , d1 , d2 )

Z2 = (a3 , a4 , b3 , b4 , c3 , c4 , d3 , d4 )

s=2

DB1

TABLE VI
Q UERY TABLE FOR K = 4, N = 2, r3 = 12 .
s

DB1

DB2

s=3

a3 + b2 + c2 + d2

a4 + b1 + c1 + d1

Z1 = (a1 , b1 , c1 , d1 )

Z2 = (a2 , b2 , c2 , d2 )

20

2

Achievability
Converse

1.8
1.6
1.4

D
L

1.2
1
0.8
0.6
0.4
0.2
0

0

0.2

0.4

r

0.6

0.8

1

Fig. 2. Inner and outer bounds for K = 5, N = 2.

B. K = 5, K = 10 and K = 100 Messages, N = 2 Databases
For N = 2, we show the numerical results for the inner and outer bounds for K = 5, K = 10
and K = 100 in Figures 2, 3 and 4. For fixed N as K grows, the gap between the achievable
bound and converse bound increases. This observation will be made specific in Section VII.
VII. G AP A NALYSIS
In this section, we analyze the gap between the achievable bounds given in (10) and the
converse bounds given in (12). We first observe that for fixed number of databases N, as the
number of messages K increases, the achievable normalized download cost increases. In addition
to the monotonicity, the achievable normalized download cost for K + 1 messages has a special
relationship with the achievable normalized download cost for K messages. We first use an
example to illustrate this property. For N = 2, K = 3, K = 4, and K = 5, the achievable
bounds are shown in Figure 5. The achievable bound for K = 5 is above the achievable bound
for K = 4, and the achievable bound for K = 4 is above the achievable bound for K = 3. By
(K)

denoting rs
(5)

as the caching ratio with total K messages and parameter s (see (9)), we observe
(5)

(4)

(4)

(4)

(4)

that (r1 , D̄(r1 )) falls on the line connecting (r0 , D̄(r0 )) and (r1 , D̄(r1 )). This observation

21

2

Achievability
Converse

1.8
1.6
1.4

D
L

1.2
1
0.8
0.6
0.4
0.2
0

0

0.2

0.4

r

0.6

0.8

1

Fig. 3. Inner and outer bounds for K = 10, N = 2.

2

Achievability
Converse

1.8
1.6
1.4

D
L

1.2
1
0.8
0.6
0.4
0.2
0

0

0.2

0.4

r

0.6

0.8

1

Fig. 4. Inner and outer bounds for K = 100, N = 2.

(K+1)

is general, (rs

(K+1)

, D̄(rs

(K)

(K)

(K)

(K)

)) falls on the line connecting (rs−1 , D̄(rs−1 )) and (rs , D̄(rs )).

We summarize this result in the following lemma.
Lemma 4 (Monotonicity of the achievable bounds) In cache-aided PIR with partially known

22

2

K=3
K=4
K=5

1.8
1.6
1.4

D
L

1.2
1
0.8
0.6
0.4
0.2
0

0

0.2

0.4

r

0.6

0.8

1

Fig. 5. Outer bounds for N = 2, K = 3, K = 4 and K = 5.

uncoded prefetching, for fixed number of databases N, if the number of messages K increases,
then the achievable normalized download cost increases. Furthermore, we have
(K)

rs(K+1) = αrs−1 + (1 − α)rs(K) ,

(69)

(K)

D̄(rs(K+1) ) = αD̄(rs−1 ) + (1 − α)D̄(rs(K) ),

(70)

where 0 ≤ α ≤ 1.
The proof of Lemma 4 is similar to [30, Lemma 4].
After showing the monotonicity of the achievable bounds, we show that as K → ∞, the
asymptotic upper bound for the achievable bounds is given as in the following lemma. With this
asymptotic upper bound, we conclude that the worst-case gap is

5
.
32

Lemma 5 (Asymptotics and the worst-case gap) In cache-aided PIR with partially known
uncoded prefetching, as K → ∞, the outer bound is upper bounded by,
D̄(r) ≤
Hence, the worst-case gap is

N
(1 − r)2
N −1

5
.
32

The proof of Lemma 4 is provided in Section X-A.

(71)

23

2
1.8
1.6
1.4

D
L

1.2
1
0.8
0.6

[31] [32]
[29]
[27]
This work
[30]

0.4
0.2
0

0

0.2

0.4

r

0.6

0.8

1

Fig. 6. Outer bounds for N = 2, K = 12 for different cache-aided PIR models.

VIII. C OMPARISONS

WITH

OTHER C ACHE -A IDED PIR M ODELS

In this section, we compare the normalized download costs between different cache-aided
PIR models subjected to same memory size constraint. We first use an example of N = 2 and
K = 12 (see Figure 6) to show the relative normalized download costs for different models. In
[29], [31], [32], the user caches M full messages out of total K messages. In order to compare
with other cache-aided PIR schemes, we use

M
K

as the caching ratio. Since the PIR schemes

are only reported for the corner points in [29], [31], [32], we use dotted lines to connect the
corner points. For [27], [30] and this work, since we can apply memory-sharing to achieve the
download costs between the corner points, we use solid lines to connect the corner points.
We first compare references [29], [31], [32], in which the user caches M full messages out of
K messages and the databases are (partially) unaware. In [31], [32], the user not only wishes to
protect the privacy of the desired messages but also wishes to protect the privacy of the cached
messages. Note that the other works ( [27], [29], [30] and this work) only consider to protect the
privacy of the desired messages. Since the message privacy constraint is less restricted, reference
[29] achieves lower normalized download cost than references [31], [32]. The main difference
between [32] and [31] is that the databases are totally unaware of the cached M messages as

24

in [31] or the nth database is aware of some of M messages cached from the nth database as
in [32]. Interestingly, these two models result in the same normalized download costs. Although
the nth database’s awareness of some cached messages might increase the download cost, at the
same time the user does not need to protect the privacy of these known messages from the nth
database, which might reduce the download cost.
We then compare references [27], [30] and this work. The main difference between these three
works is the different level of awareness of the side information the user cached. Reference [27]
considers that all the databases are aware of the side information the user cached. In contrast,
reference [30] considers that all the databases are unaware of the side information. This work
considers that ths nth database is aware of the side information cached from the nth database.
Reference [30, Corollary 1] shows the unawareness gain. Therefore, reference [30] achieves lower
normalized download cost than [27]. The same proof technique in [30, Corollary 1] can also show
the partially unawareness gain. Therefore, this work also achieves lower normalized download
cost than [27]. Since these three works consider only the privacy of the desired message, different
from [31], [32], reference [30] achieves lower normalized download cost than this work.
IX. C ONCLUSION
In this paper, we studied the cache-aided PIR problem from N non-communicating and
replicated databases, when the cache stores uncoded bits that are partially known to the databases.
We determined inner and outer bounds for the optimal normalized download cost D ∗ (r) as a
function of the total number of messages K, the number of databases N, and the caching ratio r.
Both inner and outer bounds are piece-wise linear functions in r (for fixed N, K) that consist of
K line segments. The bounds match in two specific regimes: the very low caching ratio regime,
i.e., r ≤

1
,
N K−1

and the very high caching ratio regime, where r ≥

K−2
.
N 2 −3N +KN

As a direct

corollary for this result, we characterized the exact tradeoff between the download cost and the
caching ratio for K = 3. For general K, N, and r, we showed that the largest gap between the
achievability and the converse bounds is

5
.
32

The achievable scheme extends the greedy scheme

in [12] so that it starts with exploiting the cache bits as side information. For fixed K, N,
there are K − 1 non-degenerate corner points. These points differ in the number of cached bits
that contribute in generating one side information equation. The achievability for the remaining
caching ratios is done by memory-sharing between the two adjacent corner points that enclose

25

that caching ratio r. For the converse, we extend the induction-based techniques in [12], [30] to
account for the availability of uncoded and partially prefetched side information at the retriever.
The converse proof hinges on developing K lower bounds on the length of the undesired portion
of the answer string. By applying induction on each bound separately, we obtain the piece-wise
linear inner bound.
X. A PPENDIX
A. Proof of Lemma 5
Proof: From (10), we rewrite D̄(rs ) as
D̄(rs ) =

=

Let λ =

s
.
K

PK−1−s

K
(N − 1)i+1
i=0
s+1+i

PK−1−s K−1
K−2
+
(N − 1)i+1
i=0
s−1
s+i
PK−1−s
K
)(N −1)i+1
(s+1+i
i=0
PK−1−s K−1
ψ1 (N, K, s)
( s+i )(N −1)i+1
i=0



(K−2
s−1 )
PK−1−s K−1
+1
( s+i )(N −1)i+1
i=0

=

ψ2 (N, K, s) + 1

(72)

.

(73)

We first upper bound ψ1 (N, K, s),
ψ1 (N, K, s) =
=
≤

PK−1−s

K
(N − 1)i+1
i=0
s+1+i
PK−1−s K−1
(N − 1)i+1
i=0
s+i
PK−1−s K K−1
(N − 1)i+1
i=0
s+1+i s+i

PK−1−s K−1
(N − 1)i+1
i=0
s+i

PK−1−s K K−1
(N − 1)i+1
1
i=0
s s+i
= .
PK−1−s K−1
λ
(N − 1)i+1
i=0
s+i



(74)
(75)
(76)

We then upper bound the reciprocal of ψ2 (N, K, s) as,
K−1−s
X
1
=
ψ2 (N, K, s)
i=0

K−1
s+i

= (N − 1)



(N − 1)i+1

K−2

i=0
K−1−s
X

(K − 1)(K − 1 − s)(K − 2 − s) · · · (K − i − s)
(N − 1)i (78)
s(s + 1)(s + 2) · · · (s + i)

K(K − s)i
(N − 1)i
i+1
s
i=0
i
(1−λ)K−1 
(N − 1) X
(1 − λ)(N − 1)
.
=
λ
λ
i=0

≤ (N − 1)

(77)

s−1
K−1−s
X

(79)

(80)

26

When λ > 1 −

1 (1−λ)(N −1)
,
N
λ

< 1. As K → ∞,

1
ψ2 (N,K,s)

is upper bounded by

i
∞ 
N − 1 X (1 − λ)(N − 1)
1
≤
lim
K→∞ ψ2 (N, K, s)
λ i=0
λ
N −1
·
λ
1−

=

1

(1−λ)(N −1)
λ

=

N −1
.
Nλ − (N − 1)

(81)
(82)

Now, we lower bound (78) by keeping the first ǫK terms in the sum for any ǫ such that
0 < ǫ < 1 − λ,
ǫK

X (K − 1)(K − 1 − s)(K − 2 − s) · · · (K − i − s)
1
≥ (N − 1)
(N − 1)i
ψ2 (N, K, s)
s(s
+
1)(s
+
2)
·
·
·
(s
+
i)
i=0
≥ (N − 1)
= (N − 1)

ǫK
X
(K − 1)(K − ǫK − s)i

i=0
ǫK
X

(N − 1)i

(84)

− (λ + ǫ))i
(N − 1)i .
(λ + ǫ)i+1

(85)

(s + ǫK)i+1

(1 −

1
)((1
K

i=0

(83)

As K → ∞, for any 0 < ǫ < 1 − λ, we have
i
∞ 
N − 1 X (1 − (λ + ǫ))(N − 1)
1
≥
lim
K→∞ ψ2 (N, K, s)
λ + ǫ i=0
λ+ǫ
=

N −1
.
N(λ + ǫ) − (N − 1)

(86)
(87)

From (86) and (81), as K → ∞, by picking ǫ → 0, we have
ψ2 (N, K, s) →

N
λ − 1.
N −1

(88)

Furthermore, as K → ∞, rs converges to
rs → r = lim

K−2
s−1



K−2
s−1
PK−1−s K−1
(N
i=0
s+i



+
− 1)i+1
ψ2 (N, K, s)
= lim
K→∞ ψ2 (N, K, s) + 1


Nλ − (N − 1)
1 1
=
=1− 1−
.
Nλ
N λ
K→∞

Note that if λ = 1 − N1 , then r = 0, while if λ = 1, then r =
in the region of 0 ≤ r ≤

1
,
N

1
.
N

(89)
(90)
(91)

Since we now consider the gap

without loss of generality, we consider λ > 1 − N1 . We express λ as
λ=

1 − N1
.
1−r

(92)

27

Continuing (73), by using (76), (88) and (92), we have the following upper bound on D̄(r)
D̄(r) ≤

1
λ
N
λ
N −1

1
= 2
λ



N
1
=
1−
(1 − r)2 .
N
N −1

(93)

Now, we compare the inner bound in (12) with the outer bound derived in (93). Note that
the inner bound in (12) consists of K line segments, and these K line segments intersect at the
following K − 1 points given by,
r̃i =

1
,
Ni

i = 1, · · · , K − 1.

(94)

As i increases, r̃i concentrates to r = 0. Therefore, for these K line segments, we only need
to consider small number of them for the worst-gap analysis. Denote the gap between the inner
and the outer bounds by ∆(N, K, r). We note that the gap ∆(N, ∞, r) is a piece-wise convex
function for 0 ≤ r ≤ 1 since it is the difference between a convex function D̄(r) and a piecewise linear function. Hence, the maximizing caching ratio for the gap exists exactly at the corner
points r̃i and it suffices to examine the gap at these corner points.
For the outer bound, by plugging (94) into (93), we have


2

1 − ( N1 )i
1
1
N
1− i .
1− i
D̄(r̃i ) ≤
=
N −1
N
N
1 − N1

(95)

Furthermore, for the inner bound, we have





(i − 1)
1
1
1
1
i+
D̃(r̃i ) =(1 − ri ) 1 +
+ · · · + i − ri 1 −
+ · · · + i−1
N
N
N
N
N

 


(i − 1)
1
1
1
1
i+
+ ···+ i + 1−
+ · · · + i−1
= − ri 1 +
N
N
N
N
N


1
1
+ 1+
+···+ i
N
N


1
1
+···+ i
= − ri (i + 1) + 1 +
N
N
1 i+1
1 − (N )
1 − ( N1 )i+1 i + 1
=
−
r
(i
+
1)
=
−
i
Ni
1 − N1
1 − N1

(96)

(97)
(98)
(99)

Consequently, we can upper bound the asymptotic gap at the corner point r̃i as


1 − ( N1 )i
1
∆(N, ∞, r̃i ) = D̄(r̃i ) − D̃(r̃i ) ≤ i i −
N
1 − N1

(100)

28

Hence, ∆(N, ∞, r̃i ) is monotonically decreasing in N. Therefore,


1 − ( 12 )i
1
∆(N, K, r) ≤ ∆(2, ∞, r) ≤ max i i −
i
2
1 − 21

(101)

For the case N = 2, we note that all the inner bounds after the 7th corner point are concentrated
around r = 0 since r̃i ≤

1
128

for i ≥ 7. Therefore, it suffices to characterize the gap only for

the first 7 corner points. Considering the 7th corner point which corresponds to r̃6 =
1
) = 1.9297. Hence, ∆(2, ∞, r) ≤ 0.07, for r ≤
D̄(r) ≤ 2 trivially for all r, and D̃( 128

1
,
128

1
.
127

and

Now,

we focus on calculating the gap at r̃i , i = 1, · · · , 7. Examining all the corner points, we see that
r=

1
8

is the maximizing caching ratio for the gap (corresponding to i = 3), and ∆(2, ∞, 81 ) ≤

5
,
32

which is the worst-case gap. 
R EFERENCES
[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.
[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 Transactions on Information Theory, 63(7):4075–
4088, July 2017.
[13] H. Sun and S. Jafar. The capacity of robust private information retrieval with colluding databases. 2016. Available at
arXiv:1605.00635.
[14] H. Sun and S. Jafar. The capacity of symmetric private information retrieval. 2016. Available at arXiv:1606.08828.
[15] K. Banawan and S. Ulukus. The capacity of private information retrieval from coded databases. IEEE Transactions on
Information Theory. Submitted September 2016. Also available at arXiv:1609.08138.

29

[16] H. Sun and S. Jafar. Optimal download cost of private information retrieval for arbitrary message length. 2016. Available
at arXiv:1610.03048.
[17] Q. Wang and M. Skoglund. Symmetric private information retrieval for MDS coded distributed storage. 2016. Available
at arXiv:1610.04530.
[18] H. Sun and S. Jafar. Multiround private information retrieval: Capacity and storage overhead. 2016. Available at
arXiv:1611.02257.
[19] 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.
[20] 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.
[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. Available at arXiv:1701.07636.
[22] K. Banawan and S. Ulukus. Multi-message private information retrieval: Capacity results and near-optimal schemes. IEEE
Transactions on Information Theory. Submitted February 2017. Also available at arXiv:1702.01739.
[23] Y. Zhang and G. Ge. A general private information retrieval scheme for MDS coded databases with colluding servers.
2017. Available at arXiv: 1704.06785.
[24] Y. Zhang and G. Ge. Multi-file private information retrieval from MDS coded databases with colluding servers. 2017.
Available at arXiv: 1705.03186.
[25] K. Banawan and S. Ulukus. The capacity of private information retrieval from Byzantine and colluding databases. IEEE
Transactions on Information Theory. Submitted June 2017. Also available at arXiv:1706.01442.
[26] Q. Wang and M. Skoglund. Secure symmetric private information retrieval from colluding databases with adversaries.
2017. Available at arXiv:1707.02152.
[27] R. Tandon. The capacity of cache aided private information retrieval. 2017. Available at arXiv: 1706.07035.
[28] Q. Wang and M. Skoglund. Linear symmetric private information retrieval for MDS coded distributed storage with colluding
servers. 2017. Available at arXiv:1708.05673.
[29] S. Kadhe, B. Garcia, A. Heidarzadeh, S. El Rouayheb, and A. Sprintson. Private information retrieval with side information.
2017. Available at arXiv:1709.00112.
[30] 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.
[31] Z. Chen, Z. Wang, and S. Jafar. The capacity of private information retrieval with private side information. 2017. Available
at arXiv:1709.03022.
[32] Y.-P. Wei, K. Banawan, and S. Ulukus. The capacity of private information retrieval with partially known private side
information. 2017. Available at arXiv:1710.00809.
[33] H. Sun and S. A. Jafar. The capacity of private computation. 2017. Available at arXiv:1710.11098.
[34] M. Mirmohseni and M. A. Maddah-Ali. Private function retrieval. 2017. Available at arXiv:1711.04677.
[35] M. Abdul-Wahid, F. Almoualem, D. Kumar, and R. Tandon. Private information retrieval from storage constrained
databases–coded caching meets PIR. 2017. Available at arXiv:1711.05244.
[36] M. A. Maddah-Ali and U. Niesen. Fundamental limits of caching. IEEE Transactions on Information Theory, 60(5):2856–
2867, May 2014.

30

[37] M. A. Maddah-Ali and U. Niesen. Decentralized coded caching attains order-optimal memory-rate tradeoff. IEEE/ACM
Transactions on Networking, 23(4):1029–1040, August 2015.
[38] R. Pedarsani, M. A. Maddah-Ali, and U. Niesen. Online coded caching. IEEE/ACM Transactions on Networking, 24(2):836–
845, April 2016.
[39] A. Sengupta, R. Tandon, and T. C. Clancy. Fundamental limits of caching with secure delivery. IEEE Transactions on
Information Forensics and Security, 10(2):355–370, February 2015.
[40] M. Ji, G. Caire, and A. F. Molisch. Fundamental limits of caching in wireless D2D networks. IEEE Transactions on
Information Theory, 62(2):849–869, February 2016.
[41] H. Ghasemi and A. Ramamoorthy. Improved lower bounds for coded caching. IEEE Transactions on Information Theory,
63(7):4388–4413, July 2017.
[42] M. Ji, A. M. Tulino, J. Llorca, and G. Caire. Order-optimal rate of caching and coded multicasting with random demands.
IEEE Transactions on Information Theory, 63(6):3923–3949, June 2017.
[43] R. Timo and M. Wigger. Joint cache-channel coding over erasure broadcast channels. In IEEE ISWCS, August 2015.
[44] K. Shanmugam, M. Ji, A. M. Tulino, J. Llorca, and A. G. Dimakis. Finite-length analysis of caching-aided coded
multicasting. IEEE Transactions on Information Theory, 62(10):5524–5537, October 2016.
[45] J. Zhang and P. Elia. Fundamental limits of cache-aided wireless BC: Interplay of coded-caching and CSIT feedback.
IEEE Transactions on Information Theory, 63(5):3142–3160, May 2017.
[46] M. Gregori, J. Gómez-Vilardebó, J. Matamoros, and D. Gündüz. Wireless content caching for small cell and D2D networks.
IEEE Journal on Selected Areas in Communications, 34(5):1222–1234, May 2016.
[47] M. M. Amiri and D. Gündüz. Fundamental limits of coded caching: Improved delivery rate-cache capacity tradeoff. IEEE
Transactions on Communications, 65(2):806–815, February 2017.
[48] C. Tian and J. Chen. Caching and delivery via interference elimination. In IEEE ISIT, July 2016.
[49] K. Wan, D. Tuninetti, and P. Piantanida. On the optimality of uncoded cache placement. In IEEE ITW, September 2016.
[50] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr. The exact rate-memory tradeoff for caching with uncoded prefetching.
In IEEE ISIT, June 2017.
[51] A. A. Zewail and A. Yener. Fundamental limits of secure device-to-device coded caching. In IEEE Asilomar Conference
on Signals, Systems, and Computers, October 2016.
[52] N. Naderializadeh, M. A. Maddah-Ali, and A. S. Avestimehr. On the optimality of separation between caching and delivery
in general cache networks. 2017. Available at arXiv:1701.05881.
[53] S. S. Bidokhti, M. Wigger, and A. Yener. Benefits of cache assignment on degraded broadcast channels. 2017. Available
at arXiv:1702.08044.
[54] L. Tang and A. Ramamoorthy. Low subpacketization schemes for coded caching. 2017. Available at arXiv:1706.00101.
[55] L. Xiang, D. W. K. Ng, R. Schober, and V. W. S. Wong. Cache-enabled physical layer security for video streaming in
backhaul-limited cellular networks. IEEE Transactions on Wireless Communications, November 2017.

