# Fundamental Limits of
Demand-Private Coded Caching

Chinmay Gurjarpadhye, Jithin Ravi, Sneha Kamath, Bikash Kumar Dey, and Nikhil
Karamchandani J. Ravi has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grant No. 714161). The work of B. K. Dey was supported in part by
the Bharti Centre for Communication in IIT Bombay. The work of N.
Karamchandani is supported in part by a Science and Engineering Research Board
(SERB) grant on “Content Caching and Delivery over Wireless Networks”. The
material in this paper was presented in part at the IEEE National Conference
on Communications, Kharagpur, India, February 2020, and will be presented in
part at the IEEE Information Theory Workshop, Riva del Garda, Italy, April
2021. C. Gurjarpadhye, B. K. Dey and N. Karamchandani are with Department of
Electrical Engineering, IIT Bombay, Mumbai, India. J. Ravi is with the Signal
Theory and Communications Department, Universidad Carlos III de Madrid, Spain,
and with the Gregorio Marañón Health Research Institute, Madrid, Spain. S.
Kamath is with Qualcomm, India (emails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>nikhilk@ee.iitb.ac.in). Part of the work of J. Ravi and S. Kamath was done
when they were at IIT Bombay.

###### Abstract

We consider the coded caching problem with an additional privacy constraint
that a user should not get any information about the demands of the other
users. We first show that a demand-private scheme for $N$ files and $K$ users
can be obtained from a non-private scheme that serves only a subset of the
demands for the $N$ files and $NK$ users problem. We further use this fact to
construct a demand-private scheme for $N$ files and $K$ users from a
particular known non-private scheme for $N$ files and $NK-K+1$ users. It is
then demonstrated that, the memory-rate pair $(M,\min\\{N,K\\}(1-M/N))$, which
is achievable for non-private schemes with uncoded transmissions, is also
achievable under demand privacy. We further propose a scheme that improves on
these ideas by removing some redundant transmissions. The memory-rate trade-
off achieved using our schemes is shown to be within a multiplicative factor
of 3 from the optimal when $K<N$ and of 8 when $N\leq K$. Finally, we give the
exact memory-rate trade-off for demand-private coded caching problems with
$N\geq K=2$.

##  I Introduction

In their seminal work [1, 2], Maddah-Ali and Niesen analyzed the fundamental
limits of caching in a noiseless broadcast network from an information-
theoretic perspective. A server has $N$ files of equal size. There are $K$
users, each equipped with a cache that can store $M$ files. In the _placement
phase_ , the cache of each user is populated with some functions of the files.
In the _delivery phase_ , each user requests one of the $N$ files, and the
server broadcasts a message to serve the demands of the users. The goal of the
_coded caching_ problem is to identify the minimum required _rate_ of
transmission from the server for any given cache size $M$. For this setup, [1]
proposed an achievability scheme and by comparing the achievable rate with an
information-theoretic lower bound on the optimal rate, demonstrated the scheme
to be _order optimal_ , i.e., the achievable rate is within a constant
multiplicative factor from the optimal for all system parameters $N,K,M$. The
works [3, 4, 5] mainly focused on obtaining improved achievable rates while
the works [6, 7] focused on improving the lower bounds. Different aspects of
the coded caching problem such as _subpacketization_ [8, 9, 10], _non-uniform
demands_ [11, 12, 13] and _asychnronous demands_ [14, 15] have been
investigated in the past. Fundamental limits of caching has also been studied
for some other network models, see for example [16, 17, 18]. We refer the
reader to [19] for a detailed survey.

The schemes proposed in [1, 2] for the coded caching problem exploited the
broadcast property of the network to reduce the rate of transmission. The fact
that this can lead to a coding gain has also been explored in the related
_index coding_ framework [20], where the users may have a subset of files as
side information and request one file from the server that they do not have
access to. While the broadcast property helps in achieving a coding gain under
such settings, it affects the security and privacy of users. Two types of
security/privacy issues have been studied in index coding. The works [21, 22]
addressed the problem of _file privacy_ where the constraint is that each user
should not get any information about any file other than the requested one.
The work [23] studied index coding with _demand privacy_ where each user
should not get any information about the identity of the file requested by
other users. Demand privacy is also studied in a different context called
_private information retrieval_ where a user downloads her file of interest
from one or more servers and does not want to reveal the identity of the
requested file to any server, see [24] for example.

File privacy for the coded caching problem was investigated in [25, 26]. In
particular, [25] considered the privacy of files against an eavesdropper who
has access to the broadcast link, while [26] studied the caching problem with
the constraint that each user should not get any information about any file
other than the requested one. In [26], a private scheme was proposed using
techniques from secret sharing, and the achievable rate was shown to be order
optimal.

In this paper, we consider the coded caching problem with an extra constraint
that each user should not learn any information about the demands of other
users. Coded caching under demand privacy was studied from an information-
theoretic framework in some recent works [27, 28, 29, 30, 31, 32]. The works
[27] and [28] (a preliminary version of this work) demonstrated that a demand-
private scheme for $N$ files and $K$ users can be obtained from a non-private
scheme for $N$ files and $NK$ users. The rate achievable using such schemes
was shown to be order optimal for all regimes except for the case when $K<N$
and $M<N/K$. A demand-private scheme using MDS codes was also proposed for
$M\geq N/2$ in [27]. In [29], the authors focused on obtaining demand-private
schemes that achieve a weaker privacy condition such that one user should not
get any information about the demand of another user, but may gain some
information about the demand vector. They mainly addressed the
subpacketization requirement for $N=K=2$ in [29] and extended their study to
more general cases in [32]. Demand privacy against colluding users was studied
for device-to-device network in [31] where a trusted server helps to co-
ordinate among the users to achieve a demand-private scheme. The case of
colluding users for the coded caching problem was considered in [30] where the
privacy condition was such that one user should not learn any information
about the demands of other users even if she is given all the files.

Now we briefly summarize the main contributions of this paper. We first show
that a demand-private scheme for $N$ files and $K$ users can be obtained from
a non-private scheme that serves only a subset of demands for $N$ files and
$NK$ users (Theorem 1). Our first achievability scheme, Scheme A, is built on
this fact. We then propose Scheme B which is based on the idea that permuting
broadcast symbols and not fully revealing the permutation function helps to
achieve demand privacy. Our third achievability scheme, Scheme C, combines the
ideas of Schemes A and B. Using these achievability schemes, we show the order
optimality for the case when $K<N$ and $M<N/K$, thus completing the order
optimality result for all regimes111This result was first shown in a
preliminary version [33] of this work.. Finally, we characterize the exact
memory-rate trade-off under demand privacy for the case $N\geq K=2$. We detail
the contributions and describe the organization of the paper in the next
subsection.

###  I-A Contributions and organization of the paper

The main contributions of this paper are the following.

  1. 1.

Using the fact that a demand-private scheme for $N$ files and $K$ users can be
obtained from a non-private scheme that serves only a structured subset of
demands for $N$ files and $NK$ users, we propose Scheme A for demand-private
caching that uses the non-private scheme for $N$ files and $NK-K+1$ users from
[5] (which we refer to as the YMA scheme). This then implies that the memory-
rate pairs achievable by the YMA scheme for $N$ files and $NK-K+1$ users are
also achievable under demand privacy for $N$ files and $K$ users (Theorem 2 in
Section III-A).

  2. 2.

In [1, Example 1], it was shown that memory-rate pair
$(M,\min\\{N,K\\}(1-M/N))$ can be achieved for non-private schemes without any
coding in the placement phase or in the delivery phase. In Theorem 3 (Section
III-B), we show that this memory-rate pair $(M,\min\\{N,K\\}(1-M/N))$ is also
achievable under demand privacy. For $N\leq K$, the scheme (Scheme B) that
achieves this pair is trivial, while for $K<N$, the scheme is non-trivial.

  3. 3.

We then propose a demand-private scheme (Scheme C) that builds on the ideas of
Schemes A and B. The memory-rate pairs achievable using Scheme C are given in
Theorem 4 (Section III-C). Using numerical computations, we demonstrate that,
for $K<N$, a combination of Schemes B and C outperforms Scheme A. In contrast,
Scheme A outperforms Schemes B and C for $N\leq K$.

  4. 4.

The characterization of the exact memory-rate trade-off is known to be
difficult for non-private schemes. So, the order optimality of the achievable
rates is investigated. We show that the rates achievable using our schemes are
within a constant multiplicative gap of the optimal non-private rates (Theorem
5 in Section III-E) in all parameter regimes. In particular, we prove this for
$K<N$ and $M<N/K$, the regime that was left open in previous works. This gives
the order optimality result since the optimal rates under privacy is lower
bounded by the optimal non-private rates. This also implies that the optimal
private and non-private rates are always within a constant factor.

  5. 5.

One class of instances for which we have the exact trade-off [1, 34] for non-
private schemes is when $K=2$ and $N\geq 2$. For this class, we characterize
the exact trade-off under demand privacy in Theorem 6 (Section III-F). Our
characterization shows that the exact trade-off region under demand privacy
for this class is strictly smaller than the one without privacy. To
characterize the exact trade-off, we give a converse bound that accounts for
the privacy constraints. To the best of our knowledge, this converse bound is
the first of its kind, and also that this is the first instance where it is
demonstrated that the optimal rates with privacy can be strictly larger than
the optimal rates without privacy.

The rest of the paper is organized as follows. In Section II, we give our
problem formulation. We present our results and briefly describe our proposed
schemes in Section III. All the proofs of our results can be found in Section
IV and the appendices.

###  I-B Notations

We denote the set $\\{0,1,\ldots,N-1\\}$ by $[0:N-1]$, the cardinality of a
set $\cal{A}$ by $|\mbox{$\cal{A}$}|$, and the closed interval between two
real numbers $a$ and $b$ by $[a,b]$. For a positive integer $\ell$, if $\pi$
denotes a permutation of $[0:\ell-1]$, and
$Y=(Y_{0},Y_{1},\ldots,Y_{\ell-1})$, with abuse of notation, we define
$\pi(Y)=\left(Y_{\pi^{-1}(i)}\right)_{i\in[0:\ell-1]}$. We denote random
variables by upper case letters (e.g. $X$) and their alphabets by calligraphic
letters (e.g. $\cal{X}$). For a random variable/vector $B$, $len(B)$ denotes
$\log_{2}|\mbox{$\cal{B}$}|$.

##  II Problem formulation and definitions

Consider one server connected to $K$ users through a noiseless broadcast link.
The server has access to $N$ independent files of $F$ bits each. These files
are denoted as $(W_{0},W_{1},\ldots,W_{N-1})$ and each file is uniformly
distributed in $\\{0,1\\}^{F}$. Each user has a cache of size $MF$ bits. The
coded caching problem has two phases: prefetching and delivery. In the
prefetching phase, the server places at most $MF$ bits in the cache of each
user. The cache content of user $k\in[0:K-1]$ is denoted by $Z_{k}$. In the
delivery phase, each user demands one of the $N$ files from the server and
this demand is conveyed secretly to the server. Let the demand of user $k$ be
denoted by $D_{k}\in[0:N-1]$. We define
$\bar{D}=(D_{0},D_{1},\ldots,D_{K-1})$. $\bar{D}$ is independent of the files
$W_{i},i\in[0:N-1]$ and caches $Z_{k},k\in[0:K-1]$, and is uniformly
distributed in $[0:N-1]^{K}$.

In the delivery phase, the server broadcasts a message $X$ to all the $K$
users such that user $k\in[0:K-1]$ can decode file $W_{D_{k}}$ using $X$ and
$Z_{k}$ (see Fig. 1). If message $X$ consists of $RF$ bits, then $R$ is said
to be the rate of transmission. In addition to the decodability of the
demanded file, demand-privacy imposes another constraint that the demands of
all other users should remain perfectly secret to each of the $K$ users. To
ensure demand-privacy, the server can share some randomness denoted by $S_{k}$
with user $k\in[0:K-1]$ in the prefetching phase. This shared randomness is of
negligible size and hence, it is not included in the memory size. We define
$S=(S_{0},S_{1},\ldots,S_{K-1})$. The server also has access to some private
randomness which we denote by $P$. The random variables
$S,P,\\{W_{i}|i\in[0:N-1]\\},\\{D_{k}|k\in[0:K-1]\\}$ are independent of each
other.

Figure 1: Demand-private coded caching model.

Non-private coded caching scheme: An non-private coded caching scheme consists
of the following.

Cache encoding functions: For $k\in[0:K-1]$, the cache encoding function for
the $k$-th user is a map

$\displaystyle C_{k}:{[0:2^{F}-1]}^{N}\rightarrow[0:2^{MF}-1],$ (1)

and the cache content $Z_{k}$ is given by $Z_{k}=C_{k}(\bar{W})$.

Broadcast transmission encoding function: The transmission encoding is a map

$\displaystyle
E:{[0:2^{F}-1]}^{N}\times\mbox{$\cal{D}$}_{0}\times\cdots\times\mbox{$\cal{D}$}_{K-1}\rightarrow[0:2^{RF}-1],$
(2)

and the transmitted message is given by $X=(E(\bar{W},\bar{D}),\bar{D})$.

Decoding functions: User $k$ uses a decoding function

$\displaystyle
G_{k}:\mbox{$\cal{D}$}_{0}\times\cdots\times\mbox{$\cal{D}$}_{K-1}\times[0:2^{RF}-1]\times[0:2^{MF}-1]\rightarrow[0:2^{F}-1].$
(3)

Let $\mbox{$\cal{C}$}=\\{C_{k}:k=0,\ldots,K-1\\}$ and
$\mbox{$\cal{G}$}=\\{G_{k}:k=0,\ldots,K-1\\}$. Then the triple
$(\mbox{$\cal{C}$},E,\mbox{$\cal{G}$})$ is called an $(N,K,M,R)$-non-private
scheme if it satisfies

$\displaystyle W_{D_{k}}=G_{k}(\bar{D},E(\bar{W},\bar{D}),C_{k}(\bar{W}))$ (4)

for all values of $\bar{D}$ and $\bar{W}$. A memory-rate pair $(M,R)$ is said
to be achievable for the $(N,K)$ coded caching problem if there exists an
$(N,K,M,R)$-non-private scheme for some $F$. The memory-rate trade-off
$R^{*}_{N,K}(M)$ for the non-private coded caching problem is defined as

$\displaystyle R^{*}_{N,K}(M)$ $\displaystyle=\inf\\{R:(M,R)\mbox{ is
achievable for $(N,K)$ coded caching problem}\\}.$ (5)

Private coded caching scheme: A private coded caching scheme consists of the
following.

Cache encoding functions: For $k\in[0:K-1]$, the cache encoding function for
the $k$-th user is given by

$\displaystyle
C_{k}:\mbox{$\cal{S}$}_{k}\times\mbox{$\cal{P}$}\times{[0:2^{F}-1]}^{N}\rightarrow[0:2^{MF}-1],$
(6)

and the cache content $Z_{k}$ is given by
$Z_{k}=(C_{k}(S_{k},P,\bar{W}),S_{k})$.

Broadcast transmission encoding function: The transmission encoding functions
are

$\displaystyle
E:{[0:2^{F}-1]}^{N}\times\mbox{$\cal{D}$}_{0}\times\cdots\times\mbox{$\cal{D}$}_{K-1}\times\mbox{$\cal{P}$}\times\mbox{$\cal{S}$}_{0}\times\cdots\times\mbox{$\cal{S}$}_{K-1}\rightarrow[0:2^{RF}-1],$
$\displaystyle
J:\mbox{$\cal{D}$}_{0}\times\cdots\times\mbox{$\cal{D}$}_{K-1}\times\mbox{$\cal{P}$}\times\mbox{$\cal{S}$}_{0}\times\cdots\times\mbox{$\cal{S}$}_{K-1}\rightarrow\mbox{$\cal{J}$}.$

The transmitted message $X$ is given by

$\displaystyle
X=\left(E(\bar{W},\bar{D},P,\bar{S}),J(\bar{D},P,\bar{S})\right).$

Here $\log_{2}|\mbox{$\cal{J}$}|$ is negligible222 The auxiliary transmission
$J$ essentially captures any additional transmission, that does not contribute
any rate, in addition to the main payload. Such auxiliary transmissions of
negligible rate are used even in non-private schemes without being formally
stated in most work. For example, the scheme in [1] works only if the server
additionally transmits the demand vector in the delivery phase. We have chosen
to formally define such auxiliary transmission here. compared to file size
$F$.

Decoding functions: User $k$ has a decoding function

$\displaystyle
G_{k}:\mbox{$\cal{D}$}_{k}\times\mbox{$\cal{S}$}_{k}\times\mbox{$\cal{J}$}\times[0:2^{RF}-1]\times[0:2^{MF}-1]\rightarrow[0:2^{F}-1].$
(7)

Let $\mbox{$\cal{C}$}=\\{C_{k}:k=0,\ldots,K-1\\}$ and
$\mbox{$\cal{G}$}=\\{G_{k}:k=0,\ldots,K-1\\}$. The tuple
$(\mbox{$\cal{C}$},E,J,\mbox{$\cal{G}$})$ is called as an $(N,K,M,R)$-private
scheme if it satisfies the following decoding and privacy conditions:

$\displaystyle
W_{D_{k}}=G_{k}\bigl{(}D_{k},S_{k},J(\bar{D},P,\bar{S},),E(\bar{W},\bar{D},P,\bar{S}),C_{k}(S_{k},P,\bar{W})\bigr{)},\quad\text{
for }k\in[0:K-1],$ $\displaystyle
I\left({\bar{D}_{\tilde{k}}};D_{k},S_{k},J(\bar{D},P,\bar{S},),E(\bar{W},\bar{D},P,\bar{S}),C_{k}(S_{k},P,\bar{W})\
\right)=0,\quad\text{ for }k\in[0:K-1],$

where $\bar{D}_{\tilde{k}}=(D_{0},\ldots,D_{k-1},D_{k+1},\ldots,D_{K-1})$. The
above conditions are respectively equivalent to

$\displaystyle H(W_{D_{k}}|Z_{k},X{},D_{k})$ $\displaystyle=0,\quad\text{ for
}k\in[0:K-1],$ (8) $\displaystyle I({\bar{D}_{\tilde{k}}};Z_{k},X{},D_{k})$
$\displaystyle=0,\quad\text{ for }k\in[0:K-1].$ (9)

A memory-rate pair $(M,R)$ is said to be achievable with demand privacy for
the $(N,K)$ coded caching problem if there exists an $(N,K,M,R)$-private
scheme for some $F$. The memory-rate trade-off with demand privacy is defined
as

$\displaystyle R^{*p}_{N,K}(M)$ $\displaystyle=\inf\\{R:(M,R)\mbox{ is
achievable with demand privacy for $(N,K)$ coded caching problem}\\}.$ (10)

######  Remark 1 (Different privacy metrics)

A weaker notion of privacy was considered in [29, 32] given by

$\displaystyle I(D_{i};Z_{k},D_{k},X)=0,\quad i\neq k.$ (11)

In words, the privacy condition in (11) requires that user $k\in[0:K-1]$
should not get any information about $D_{i},i\neq k$, but may have some
information about the demand vector. Note that a scheme that satisfies the
privacy condition (9) also satisfies (11). The model in [30] assumed that the
users can collude, and the following stronger notion of privacy metric was
considered

$\displaystyle
I(D_{[0:K-1]\setminus\mbox{$\cal{S}$}};Z_{\mbox{$\cal{S}$}},D_{\mbox{$\cal{S}$}},X|\bar{W})=0,\quad\forall\mbox{$\cal{S}$}\subseteq[0:K-1]$
(12)

where $D_{\mbox{$\cal{S}$}}$ and $Z_{\mbox{$\cal{S}$}}$ denote the demands and
the caches of users in $\cal{S}$, respectively. This stronger privacy metric
is also satisfied by our Scheme A described in Subsection III-A (see Remark
2). In contrast, Schemes B and C, described in Subsections III-B and III-C,
respectively, do not satisfy this stronger privacy metric (see Remark 3).

##  III Results

In this section, we present our results that include our achievability
schemes, the tightness of the memory-rate pairs achievable using these schemes
and the exact trade-off for $N\geq K=2$. In Subsections III-A, III-B and
III-C, we discuss Schemes A, B and C, respectively and the memory-rate pairs
achievable using these schemes. We give a comparison of the memory-rate pairs
achievable using Schemes A, B and C in Subsection III-D. In particular, we
show that Scheme A outperforms Schemes B and C for $N\leq K$, while a
combination of Schemes B and C outperforms Scheme A for $K<N$. In Subsection
III-E, we discuss the tightness of the achievable memory-rate pairs, and show
the order optimality result for all regimes. Finally, we present the exact
memory-rate trade-off under demand privacy for the case $N\geq K=2$ in
Subsection III-F.

###  III-A Scheme A

It was observed in [27, 28] that a demand-private scheme for $N$ files and $K$
users can be obtained using an existing non-private achievable scheme for $N$
files and $NK$ users as a blackbox. Here every user is associated with a stack
of $N$ virtual users in the non-private caching problem. For example, demand-
private schemes for $N=K=2$ are obtained from the non-private schemes for
$N=2$ and $K=4$. We next show that only certain types of demand vectors of the
non-private scheme are required in the private scheme. To this end, we define
this particular subset of demand vectors.

Consider a non-private coded caching problem with $N$ files and $NK$ users. A
demand vector $\bar{d}$ in this problem is an $NK$-length vector, where the
$j$-th component denotes the demand of user $j$. Then $\bar{d}$ can also be
represented as $K$ subvectors of length $N$ each, i.e.,

$\displaystyle\mbox{$\bar{d}$}=[\mbox{$\bar{d}$}^{(0)},\mbox{$\bar{d}$}^{(1)},\ldots,\mbox{$\bar{d}$}^{(K-1)}]$
(13)

where $\mbox{$\bar{d}$}^{(i)}\in[0:N-1]^{N}$ is an $N$-length vector for all
$i\in[0:K-1]$. We now define a _restricted demand subset_ $\cal{D}_{RS}$.

######  Definition 1 (Restricted Demand Subset $\cal{D}_{RS}$)

The restricted demand subset $\cal{D}_{RS}$ for an $(N,NK)$ coded caching
problem is the set of all $\bar{d}$ such that $\mbox{$\bar{d}$}^{(i)}$ is a
cyclic shift of the vector $(0,1,\ldots,N-1)$ for all $i=0,1,\ldots,K-1$.

Since $N$ cyclic shifts are possible for each $\mbox{$\bar{d}$}^{(i)}$, there
are a total of $N^{K}$ demand vectors in $\cal{D}_{RS}$.

For a given $\mbox{$\bar{d}$}\in\mbox{$\cal{D}_{RS}$}$ and $i\in[0:K-1]$, let
$c_{i}$ denote the number of right cyclic shifts of $(0,1,\ldots,N-1)$ needed
to get $\mbox{$\bar{d}$}^{(i)}$. Then,
$\mbox{$\bar{d}$}\in\mbox{$\cal{D}_{RS}$}$ is uniquely identified by the
vector $\bar{c}(\mbox{$\bar{d}$}):=(c_{0},\ldots,c_{K-1})$. For $N=2$ and
$NK=4$, the demands in $\cal{D}_{RS}$ and their corresponding
$\bar{c}(\bar{d}_{s})$ are given in Table I.

$D_{0}$ | $D_{1}$ | $D_{2}$ | $D_{3}$ | $\bar{c}(\bar{d}_{s})$
---|---|---|---|---
$0$ | $1$ | $0$ | $1$ | $(0,0)$
$0$ | $1$ | $1$ | $0$ | $(0,1)$
$1$ | $0$ | $0$ | $1$ | $(1,0)$
$1$ | $0$ | $1$ | $0$ | $(1,1)$
TABLE I: Restricted Demand Subset $\cal{D}_{RS}$ for $N=2$ and $NK=4$.

A non-private scheme for an $(N,K)$ coded caching problem that serves all
demand vectors in a particular set $\mbox{$\cal{D}$}\subseteq[0:N-1]^{K}$, is
called a $\cal{D}$-non-private scheme. We have the following theorem.

###### Theorem 1

If there exists an $(N,NK,M,R)$ $\cal{D}_{RS}$-non-private scheme, then there
exists an $(N,K,M,R)$-private scheme.

The proof of Theorem 1 is given in Subsection IV-A. The proof follows by
showing a construction of an $(N,K,M,R)$-private scheme using an $(N,NK,M,R)$
$\cal{D}_{RS}$-non-private scheme as a blackbox. The following example shows a
construction of $(2,2,\frac{1}{3},\frac{4}{3})$-private scheme from
$(2,4,\frac{1}{3},\frac{4}{3})$-$\cal{D}_{RS}$-non-private scheme. This
particular non-private scheme is from [34]. It is important to note that the
memory-rate pair $(\frac{1}{3},\frac{4}{3})$ is not achievable for $N=2,K=4$
under no privacy requirement. Thus, we observe that there exist memory-rate
pairs that are achievable for the $\cal{D}_{RS}$-non-private scheme, but not
achievable for the non-private scheme which serves all demands.

###### Example 1

We consider the demand-private coded caching problem for $N=2,K=2,M=1/3$. It
was shown in [34] that for memory $M=1/3$, the optimum non-private rate for
$N=2,K=4$ satisfies $R^{*}_{2,4}(1/3)>4/3$. Next we give a scheme which
achieves a rate $4/3$ under demand privacy for $N=2,K=2,M=1/3$. The other
known demand-private schemes also do not achieve $R=4/3$ for $N=2,K=2$. See
Fig. 5 for reference.

Let $A$ and $B$ denote the two files. We will now give a scheme which achieves
a rate $4/3$ for $M=1/3$ with $F=3l$ for some positive integer $l$. We denote
the 3 segments of $A$ and $B$ by $A_{1},A_{2},A_{3}$ and $B_{1},B_{2},B_{3}$
respectively, of $l$ bits each. First let us consider a $\cal{D}_{RS}$-non-
private scheme for $N=2$ and $K=4$ from [34]. Let $C_{i,j}(A,B),i,j=0,1$, as
shown in Table II, correspond to the cache content of user $2i+j$ in the
$\cal{D}_{RS}$-non-private scheme. The transmission $T_{(p,q)}(A,B),p,q=0,1$,
as given in Table III, is chosen for the demand
$\bar{d}\in\mbox{$\cal{D}_{RS}$}$ such that $(p,q)=\bar{c}(\bar{d})$. Using
Tables II and III, it is easy to verify that the non-private scheme satisfies
the decodability condition for demands in $\cal{D}_{RS}$. From this scheme, we
obtain a demand-private scheme for $N=2,K=2$ as follows.

Cache | Cache Content
---|---
$C_{0,0}(A,B)$ | $A_{1}\oplus B_{1}$
$C_{0,1}(A,B)$ | $A_{3}\oplus B_{3}$
$C_{1,0}(A,B)$ | $A_{2}\oplus B_{2}$
$C_{1,1}(A,B)$ | $A_{1}\oplus A_{2}\oplus A_{3}\oplus B_{1}\oplus B_{2}\oplus B_{3}$
TABLE II: Choices for the caches of user 0 and user 1. $T_{(0,0)}(A,B)$ | $B_{1},B_{2},A_{3},A_{1}\oplus A_{2}\oplus A_{3}$
---|---
$T_{(0,1)}(A,B)$ | $A_{2},A_{3},B_{1},B_{1}\oplus B_{2}\oplus B_{3}$
$T_{(1,0)}(A,B)$ | $B_{2},B_{3},A_{1},A_{1}\oplus A_{2}\oplus A_{3}$
$T_{(1,1)}(A,B)$ | $A_{1},A_{2},B_{3},B_{1}\oplus B_{2}\oplus B_{3}$
TABLE III: Transmissions for $(2,2,\frac{1}{3},\frac{4}{3})$-private scheme.

Let the shared key $S_{k},k=0,1$ of user $k$ be a uniform binary random
variable. The cache encoding functions and the transmission encoding function
are denoted as

$\displaystyle C_{k}(S_{k},A,B)$ $\displaystyle=C_{k,S_{k}}(A,B)\text{ for
}k=0,1,$ $\displaystyle E(A,B,D_{0},D_{1},S_{0},S_{1})$
$\displaystyle=T_{(D_{0}\oplus S_{0},D_{1}\oplus S_{1})}(A,B).$

User $k$ chooses $C_{k,S_{k}}(A,B)$ given in Table II as the cache encoding
function. In the delivery phase, for given $(S_{0},S_{1})$ and
$(D_{0},D_{1})$, the server broadcasts $T_{(D_{0}\oplus S_{0},D_{1}\oplus
S_{1})}(A,B)$ as the main payload and $(D_{0}\oplus S_{0},D_{1}\oplus S_{1})$
as the auxiliary transmission. For such a transmission, the decodability
follows from the decodability of the chosen non-private scheme.

Further, the broadcast transmission will not reveal any information about the
demand of one user to the other user since one particular transmission
$T_{(p,q)}(A,B)$ happens for all demand vectors $(D_{0},D_{1})$, and also that
$S_{i}$ acts as one time pad for $D_{i}$ for each $i=0,1$. Here, all the
transmissions consist of $4l$ bits (neglecting the 2 bits for $(D_{0}\oplus
S_{0},D_{1}\oplus S_{1})$). Since $F=3l$, this scheme achieves a rate $R=4/3$.

Example 1 showed that there exists an $(M,R)$ pair that is not achievable for
$N$ files and $NK$ users, but it is achievable with demand privacy for $N$
files and $K$ users. This was possible because a $\cal{D}_{RS}$-non-private
scheme needs to serve only a subset of demands. Our Scheme A as described
later utilizes this fact, and obtains a general scheme for any parameters $N$
and $K$. Specifically, we show that a $\cal{D}_{RS}$-non-private scheme for
$N$ files and $NK$ users can be obtained from the non-private scheme given in
[5] for $N$ files and $NK-K+1$ users. The memory-rate pairs achievable using
Scheme A are presented in Theorem 2. We use the following lemma to prove
Theorem 2.

###### Lemma 1

For the $(M,R)$ pairs given by

$\displaystyle(M,R)=\left(\frac{Nr}{NK-K+1},\frac{{NK-K+1\choose
r+1}-{NK-K+1-N\choose r+1}}{{NK-K+1\choose r}}\right),\quad\text{ for
}r\in\\{0,1,\ldots,NK-K\\}$

which are achievable for the non-private coded caching problem with $N$ files
and $NK-K+1$ users by the YMA scheme [5], there exists an $(N,NK,M,R)$
$\cal{D}_{RS}$-non-private scheme.

The proof of Lemma 1 can be found in Subsection IV-B. The proof follows by
dividing $NK$ users in the $\cal{D}_{RS}$-non-private scheme into two groups
with the first group containing $K-1$ users and the second group containing
$NK-K+1$ users. Users in the second group follow the prefetching of the YMA
scheme while users in the first group follow coded prefetching. In particular,
the users in the first group follow the coded prefetching of Type III caching
discussed in [35]. In the delivery phase, for a given
$\bar{d}\in\mbox{$\cal{D}_{RS}$}$, the server chooses the transmission of the
YMA scheme corresponds to the demands in the second group of users. Due to the
special nature of the demand vectors in $\cal{D}_{RS}$, using this
transmission, the demands of all users in the first group can also be served.

Scheme A: Scheme A consists of two steps. In the first step, a
$\cal{D}_{RS}$-non-private scheme is obtained from the non-private YMA scheme
for $N$ files and $NK-K+1$ users. In the second step, an $(N,K,M,R)$-private
scheme is obtained using this $\cal{D}_{RS}$-non-private scheme as a blackbox.
Scheme A achieves the memory-rate pairs given in the following theorem.

###### Theorem 2

There exists an $(N,K,M,R)$-private scheme with the following memory-rate
pair:

$\displaystyle(M,R)=\left(\frac{Nr}{NK-K+1},\frac{{NK-K+1\choose r+1}-{NK-
K-N+1\choose r+1}}{{NK-K+1\choose r}}\right),\quad\mbox{ for
}r=\\{0,\ldots,NK-K+1\\}.$ (14)

###### Proof.

The given memory-rate pair is achievable by the YMA scheme for $N$ files and
$NK-K+1$ users. So, the theorem follows from Theorem 1 and Lemma 1. ∎

###### Remark 2

If a private scheme is derived from a $\cal{D}_{RS}$-non-private scheme using
the construction described in the proof of Theorem 1, then it also satisfies
the stronger notion of privacy metric (12). This can be shown by replacing
${\bar{D}_{\tilde{k}}}$ by $D_{[0:K-1]\setminus\mbox{$\cal{S}$}}$, $D_{k}$ by
$D_{\mbox{$\cal{S}$}}$, and $Z_{k}$ by $Z_{\mbox{$\cal{S}$}}$ in the proof of
privacy that led to (26). Since Scheme A is obtained using a
$\cal{D}_{RS}$-non-private scheme as a blackbox, it also satisfies the
stronger privacy condition (12).

###  III-B Scheme B

Now we describe Scheme B. For $N\leq K$, Scheme B is trivial, where the caches
of all users are populated with the same $M/N$ fraction of each file in the
placement phase. In the delivery phase, the uncached parts of all files are
transmitted. In this scheme, all users get all files, and the rate of
transmission is given by $N(1-M/N)=N-M$. Since the broadcast transmission is
independent of the demands, it clearly satisfies the privacy condition (9).
However, if the number of users is less than the number of files, then this
scheme is very wasteful in terms of rate. For $K<N$, next we give an outline
of Scheme B. It achieves a rate $K(1-M/N)$ that, in this case, is an improved
rate compared to $N-M$.

For $K<N$, let us first consider the non-private scheme [1, Example 1] which
achieves rate $K(1-M/N)$. In this scheme, all users store the same $M/N$
fraction of each file in the placement phase. In the delivery phase, the
server transmits $K$ components where $i$-th component consists of the
uncached part of the file demanded by user $i$. However, this scheme does not
ensure demand privacy since if the $i$-th component is different from the
$j$-th component, $i\neq j$, then user $i$ learns that $D_{j}\neq D_{i}$. This
clearly violates demand privacy. For $K<N$, the placement phase in Scheme B is
the same as that of for $N\leq K$. In the delivery phase, the server transmits
$K$ components without violating demand privacy. We next illustrate Scheme B
using an example with $N>2$ and $K=2$.

###### Example 2

Let us consider that there are two users and more than two files, i.e., $N>2$
and $K=2$. In the placement phase, each user stores $M/N$ fraction of each
file. In the delivery phase, first let us consider the case of $D_{0}\neq
D_{1}$. In this case, the server transmits two components which correspond to
the uncached parts of each demanded file. To achieve privacy, the position
where the uncached part of $W_{D_{0}}$ is placed, is selected from one out of
two possible choices uniformly at random. The uncached fraction of $W_{D_{1}}$
is placed in the other position. These positions are conveyed to each user in
the auxiliary transmissions. The random variable to convey the position to
user $0$ is XOR-ed with shared randomness $S_{0}$. Since $S_{0}$ is known only
to user $0$, it acts as an one-time pad. Similarly, $S_{1}$ helps in
protecting the privacy against user $0$. When $D_{0}=D_{1}$, the uncached part
of the file is placed in a position chosen randomly. The other position is
filled with random bits. Since one user does not have any information about
the component from which the other user’s demanded file is decoded, and since
the files are independent of the demands, this scheme preserves the demand
privacy.

For $K<N$, Scheme B is a generalization of the scheme presented in Example 2.
Scheme B achieves the memory-rate pairs given in the following theorem.

###### Theorem 3

There exists an $(N,K,M,R)$-private scheme with the memory-rate pair
$(M,\min\\{N,K\\}(1-M/N))$.

Full description of Scheme B and the proof of Theorem 3 are provided in
Subsection IV-C.

###  III-C Scheme C

For $K<N$, the broadcast in scheme A contains symbols which are not necessary
for decoding, but are still broadcasted to preserve privacy. In this section,
we propose Scheme C which gets rid of such redundant symbols using the idea of
permuting the broadcast symbols as in Scheme B, thus improving the memory-rate
trade-off. In Theorem 4, we give the memory-rate pairs achievable using Scheme
C.

###### Theorem 4

There exists an $(N,K,M,R)$-private scheme with the following memory-rate
pair:

$\displaystyle(M,R)=$ $\displaystyle\left(\frac{N\sum_{s=t}^{NK-1}{NK-1\choose
s-1}r^{NK-s-1}}{\sum_{s=t}^{NK-1}{NK\choose
s}r^{NK-s-1}},\frac{\sum_{s=t+1}^{NK}[{NK\choose s}-{NK-K\choose
s}]r^{NK-s}}{\sum_{s=t}^{NK-1}{NK\choose s}r^{NK-s-1}}\right),$
$\displaystyle\qquad\mbox{ for }t=\\{1,\ldots,NK-1\\},\;r\in[1,N-1].$ (15)

Note that for the memory-rate pairs in Theorem 4, we have 2 free parameters
$t$ and $r$. By fixing the value of $r$, one can obtain a memory-rate curve by
varying the value of $t$. We have observed through numerical computations that
the memory-rate curve achieved for $r=r_{1}$ is better than that for $r=r_{2}$
if $r_{1}>r_{2}$ (see Fig. 5). The memory-rate curve for $r<N-1$, although
empirically suboptimal compared to $r=N-1$, is useful in showing the order
optimality result presented in Theorem 5.

###### Remark 3

For $K<N$, Scheme B does not satisfy the stronger privacy metric in (12).
Since Scheme C builds on the ideas of Scheme B, it also does not satisfy this
stronger privacy metric. The fact that Scheme B does not satisfy (12) can be
intuitively observed from Example 2. For $K=2$, the privacy condition (12) is
achieved if there is no leakage of privacy after one user gets to know all the
files. If one user has all the files, then she can easily verify that the part
of the broadcast that she has not used for decoding is some random bits or a
part of a file. Thus, she can infer some knowledge about the demand of the
other user in Scheme B. This was also observed in [30] (see [30, Example 1]).

Figure 2: Memory-rate pairs in Theorem 4 are plotted for different values of
$r$. The first figure is for $N=5,K=3$ and the second one is for $N=5,K=7$.

Next we illustrate Scheme C for $N=3,K=2$.

###### Example 3

Let us consider the demand-private coded caching problem for $N=3$ files and
$K=2$ users. By choosing $r=2$ and $t=3$ in the expression for memory in
Theorem 4, we get $M=\frac{195}{116}$. The same parameters give
$R=\frac{69}{116}$. Next we describe the scheme which achieves this memory-
rate pair with $F=116l$ for some positive integer $l$. We partition each file
$W_{i},i\in[0:2]$ into $\sum_{j=t}^{NK-1}{NK\choose j}=\sum_{j=3}^{5}{6\choose
j}=41$ segments of three different sizes. These segments are grouped into
three groups such that all segments in one group have the same size. The
segments are labelled by some subsets of $[0:NK-1]=[0:5]$. The segments of
$W_{i}$ are $W_{i,\mbox{$\cal{R}$}}$;
$\mbox{$\cal{R}$}\subset[0:5],|\mbox{$\cal{R}$}|=3,4,5$. These segments are of
different sizes, and these are grouped into 3 groups as

$\displaystyle\mbox{$\cal{T}$}^{i}_{5}$
$\displaystyle=(W_{i,\mbox{$\cal{R}$}})_{\mbox{$\cal{R}$}\subset[0:5],|\mbox{$\cal{R}$}|=5},$
$\displaystyle\mbox{$\cal{T}$}^{i}_{4}$
$\displaystyle=(W_{i,\mbox{$\cal{R}$}})_{\mbox{$\cal{R}$}\subset[0:5],|\mbox{$\cal{R}$}|=4},$
$\displaystyle\mbox{$\cal{T}$}^{i}_{3}$
$\displaystyle=(W_{i,\mbox{$\cal{R}$}})_{\mbox{$\cal{R}$}\subset[0:5],|\mbox{$\cal{R}$}|=3}.$

The size of segment $W_{i,\mbox{$\cal{R}$}},i\in[0:2]$ is chosen as follows:

$len(W_{i,\mbox{$\cal{R}$}})=\left\\{\begin{array}[]{lcl}l&\text{if
}|\mbox{$\cal{R}$}|=5\\\ \\\ rl=2l&\text{if }|\mbox{$\cal{R}$}|=4\\\ \\\
r^{2}l=4l&\text{if }|\mbox{$\cal{R}$}|=3.\\\ \end{array}\right.$

Thus, each segment in $\mbox{$\cal{T}$}^{i}_{5},\mbox{$\cal{T}$}^{i}_{4}$ and
$\mbox{$\cal{T}$}^{i}_{3}$ has respectively $l,2l$ and $4l$ bits. Then, for
all $i\in[0:2]$, we have

$\displaystyle len(W_{i})$
$\displaystyle=(|\mbox{$\cal{T}$}^{i}_{5}|+|\mbox{$\cal{T}$}^{i}_{4}|\times
r+|\mbox{$\cal{T}$}^{i}_{3}|\times r^{2})l$ $\displaystyle=(6+15\times
2+20\times 4)l$ $\displaystyle=116l.$

Caching: The cache content of user $k\in\\{0,1\\}$ is determined by the key
$S_{k},k=0,1$ which is shared only between the server and user $k$. Shared key
$S_{k},k=0,1$ is distributed as $S_{k}\sim unif\\{[0:N-1]\\}=unif\\{[0:2]\\}$.
The cache contents of each user is grouped into three parts. The
$j^{th},j=1,2,3$ part of user $k\in\\{0,1\\}$ is denoted by
$\mbox{$\cal{G}$}_{k,j}$ and is shown in Table IV. Thus, the number of bits
stored at one user is given by $3\left({5\choose 4}+2\times{5\choose
3}+4\times{5\choose 2}\right)l=195l$. Thus, we have $M=\frac{195}{116}$. Other
than $S_{k}$ the server also places some additional random keys of negligible
size in the cache of user $k\in\\{0,1\\}$. These will be used as keys for one-
time pad in the delivery phase.

$\mbox{$\cal{G}$}_{k,1}$ | $(W_{i,\mbox{$\cal{R}$}}|W_{i,\mbox{$\cal{R}$}}\in\mbox{$\cal{T}$}^{i}_{5}\mbox{ and }S_{k}+3k\in\mbox{$\cal{R}$})_{i=0,1,2}$
---|---
$\mbox{$\cal{G}$}_{k,2}$ | $(W_{i,\mbox{$\cal{R}$}}|W_{i,\mbox{$\cal{R}$}}\in\mbox{$\cal{T}$}^{i}_{4}\mbox{ and }S_{k}+3k\in\mbox{$\cal{R}$})_{i=0,1,2}$
$\mbox{$\cal{G}$}_{k,3}$ | $(W_{i,\mbox{$\cal{R}$}}|W_{i,\mbox{$\cal{R}$}}\in\mbox{$\cal{T}$}^{i}_{3}\mbox{ and }S_{k}+3k\in\mbox{$\cal{R}$})_{i=0,1,2}$
TABLE IV: Cache contents of user $k,k=0,1$.

Delivery: In the delivery phase, for given demands $(D_{0},D_{1})$, we first
construct an expanded demand vector $\bar{d}$ of length $6$ such that
$\bar{d}\in\mbox{$\cal{D}_{RS}$}$ defined in Definition 1. The vector
$\bar{d}$ is given by $\bar{d}=(\bar{d}^{(0)},\bar{d}^{(1)})$, where
$\bar{d}^{(k)},k=0,1$ is obtained by applying $S_{k}\ominus D_{k}$ right
cyclic shift to the vector $(0,1,2)$, where $\ominus$ denotes modulo $3$
subtraction. That is, for $k=0,1$, $d_{i}^{(k)}=i-(S_{k}-D_{k})\mod 3$. Having
defined vector $\bar{d}$, we now define symbols $Y_{\mbox{$\cal{R}$}}$ for
$\mbox{$\cal{R}$}\subset[0:5]$ and $|\mbox{$\cal{R}$}|=4,5,6$ as follows:

$\displaystyle
Y_{\mbox{$\cal{R}$}}=\bigoplus_{u\in\mbox{$\cal{R}$}}W_{d_{u},\mbox{$\cal{R}$}\setminus\\{u\\}}$

where $d_{u}$ is the $u+1$-th item in $\bar{d}$. In particular, for
$\mbox{$\cal{R}$}=[0:5]$, we have

$\displaystyle
Y_{[0:5]}=\bigoplus_{u\in[0:5]}W_{d_{u},[0:5]\setminus\\{u\\}}.$

Symbol $Y_{[0:5]}$ as defined above is a part of the main payload in the
broadcast transmission which needs $l$ bits.

To give the other parts of the broadcast, we define symbols
$W_{\mbox{$\cal{R}$}}$ and $V_{\mbox{$\cal{R}$}}$ for
$\mbox{$\cal{R}$}\subset[0:5]$ and $|\mbox{$\cal{R}$}|=4,5$ as follows:

$\displaystyle W_{\mbox{$\cal{R}$}}=(W_{0,\mbox{$\cal{R}$}}\oplus
W_{1,\mbox{$\cal{R}$}},W_{1,\mbox{$\cal{R}$}}\oplus W_{2,\mbox{$\cal{R}$}})$

and

$\displaystyle V_{\mbox{$\cal{R}$}}$ $\displaystyle=Y_{\mbox{$\cal{R}$}}\oplus
W_{\mbox{$\cal{R}$}}.$

Note that for $|\mbox{$\cal{R}$}|=4,W_{\mbox{$\cal{R}$}}$ has two parts, each
of length $2l$ bits, and $Y_{\mbox{$\cal{R}$}}$ has a length of $4l$ bits. We
further define sets $V_{4}$ and $V_{5}$ as follows:

$\displaystyle
V_{4}=\\{V_{\mbox{$\cal{R}$}}|\mbox{$\cal{R}$}\cap\\{S_{0},S_{1}+3\\}\neq\phi,|\mbox{$\cal{R}$}|=4\\}$

and

$\displaystyle V_{5}$
$\displaystyle=\\{V_{\mbox{$\cal{R}$}}||\mbox{$\cal{R}$}|=5\\}.$

Observe that $V_{4}$ and $V_{5}$ contain 14 symbols each of size $4l$ bits and
6 symbols each of size $2l$ bits, respectively. The server picks permutation
functions $\pi_{4}(\cdot)$ and $\pi_{5}(\cdot)$ uniformly at random
respectively from the symmetric group333A symmetric group defined over any set
is the group whose elements are all the bijections from the set to itself, and
whose group operation is the composition of functions. of permutations of
$[0:13]$ and $[0:5]$ and broadcasts $\pi_{4}(V_{4})$ and $\pi_{5}(V_{5})$. The
server does not fully reveal these permutation functions with any of the
users. The position of any symbol $V_{\mbox{$\cal{R}$}}\in V_{i}$, $i=4,5$ in
$\pi_{i}(V_{i})$ is privately conveyed to user $k$, if and only if
$S_{k}+3k\in\mbox{$\cal{R}$}$. This private transmission of positions is
achieved using one-time pads whose keys are deployed in the caches of
respective users in the caching phase. The main payload of the broadcast
$X^{\prime}$ can be written as

$X^{\prime}=(X_{0},X_{1},X_{2})=(Y_{[0:5]},\pi_{4}(V_{4}),\pi_{5}(V_{5})).$

Thus, the total number of transmitted bits are

$(1+6\times 2+14\times 4)l=69l.$

So, the rate of transmission is $\frac{69}{116}.$ Note that $X^{\prime}$ is
only the main payload. Along with $X^{\prime}$, the server also broadcasts
some auxiliary transmission $J=(S_{0}\ominus D_{0},S_{1}\ominus
D_{1},J^{\prime})=(\bar{S}\ominus\bar{D},J^{\prime})$. Here, $J^{\prime}$
contains the positions of various symbols in $X_{1}$ and $X_{2}$ encoded using
one-time pad as discussed above. Thus, the complete broadcast transmission is
$X=(X^{\prime},J)$.

Remark: Here, note that $V_{5}$ contains all $V_{\mbox{$\cal{R}$}}$ with
$|\mbox{$\cal{R}$}|=5$. However, $V_{4}$ does not contain all
$V_{\mbox{$\cal{R}$}}$ with $|\mbox{$\cal{R}$}|=4$. For example, if $S_{0}=0$
and $S_{1}=0$, then $V$ does not contain $V_{\\{1,2,4,5\\}}$. This is similar
to avoiding some redundant transmissions in the leader-based YMA scheme [5]
compared to the scheme in [1]. This is the main reason for getting lower rates
using this scheme compared to the rates in Theorem 2.

Decoding: For user $k\in\\{0,1\\}$, let us first consider the recovery of
segments belonging to $\mbox{$\cal{T}$}^{D_{k}}_{i}$, $i=3,4$. This is done
using symbols from $X_{1}$ and $X_{2}$. All symbols
$W_{D_{k},\mbox{$\cal{R}$}}\in\mbox{$\cal{T}$}^{D_{k}}_{i}$ such that
$S_{k}+3k\in\mbox{$\cal{R}$}$ (all symbols in set $\mbox{$\cal{G}$}_{k,6-i}$)
are cached at user $k$. User $k$ decodes the remaining symbols in
$\mbox{$\cal{T}$}^{D_{k}}_{i}$, i.e., $W_{D_{k},\mbox{$\cal{R}$}}$ such that
$|\mbox{$\cal{R}$}|=i,S_{k}+3k\notin\mbox{$\cal{R}$}$ and
$\mbox{$\cal{R}$}\subset[0:5]$ as follows:

$\displaystyle\widehat{W}_{D_{k},\mbox{$\cal{R}$}}=V_{\mbox{$\cal{R}$}^{+}}\oplus
W_{\mbox{$\cal{R}$}^{+}}\oplus\left(\bigoplus_{u\in{\mbox{$\cal{R}$}}}W_{d_{u},\mbox{$\cal{R}$}^{+}\setminus\\{u\\}}\right)$
(16)

where $\mbox{$\cal{R}$}^{+}=\\{S_{k}+3k\\}\cup\mbox{$\cal{R}$}$. Here,
$V_{\mbox{$\cal{R}$}^{+}}$ is a part of $\pi_{i+1}(V_{i+1})$ and its position
in $\pi_{i+1}(V_{i+1})$ has been revealed to user $k$ since
$S_{k}+3k\in\mbox{$\cal{R}$}^{+}$. The symbols $W_{\mbox{$\cal{R}$}^{+}}$ and
$W_{d_{u},\mbox{$\cal{R}$}^{+}\setminus\\{u\\}}$ in (16) can be recovered from
her cache. Substituting for $V_{\mbox{$\cal{R}$}^{+}}$ in (16) yields

$\displaystyle\widehat{W}_{D_{k},\mbox{$\cal{R}$}}$
$\displaystyle=Y_{\mbox{$\cal{R}$}^{+}}\oplus W_{\mbox{$\cal{R}$}^{+}}\oplus
W_{\mbox{$\cal{R}$}^{+}}\oplus\left(\bigoplus_{u\in{\mbox{$\cal{R}$}}}W_{d_{u},\mbox{$\cal{R}$}^{+}\setminus\\{u\\}}\right)$
$\displaystyle=\bigoplus_{u\in\mbox{$\cal{R}$}^{+}}W_{d_{u},\mbox{$\cal{R}$}^{+}\setminus\\{u\\}}\oplus\left(\bigoplus_{u\in{\mbox{$\cal{R}$}}}W_{d_{u},\mbox{$\cal{R}$}^{+}\setminus\\{u\\}}\right)$
$\displaystyle=W_{d_{S_{k}+3k},\mbox{$\cal{R}$}}$
$\displaystyle=W_{D_{k},\mbox{$\cal{R}$}}.$ (17)

Since user $k$ has all segments in $\mbox{$\cal{T}$}^{D_{k}}_{3}$ and
$\mbox{$\cal{T}$}^{D_{k}}_{4}$, we consider the recovery of symbols in
$\mbox{$\cal{T}$}^{D_{k}}_{5}$. In the first part $\mbox{$\cal{G}$}_{k,1}$ of
cache, user $k$ does not have one segment of $\mbox{$\cal{T}$}^{D_{k}}_{5}$,
namely $W_{D_{k},[0:5]\setminus\\{S_{k}+3k\\}}$ . User $k$ decodes this
segment as

$\displaystyle\widehat{W}_{D_{k},[0:5]\setminus\\{S_{k}+3k\\}}=Y_{[0:5]}\oplus\left(\bigoplus_{u\in{[0:5]\setminus\\{S_{k}+3k\\}}}W_{d_{u},[0:5]\setminus\\{u\\}}\right).$

Observe that $Y_{[0:5]}$ is broadcasted by the server while each symbol
$W_{d_{u},[0:5]\setminus\\{u\\}}$ is a part of $\mbox{$\cal{G}$}_{k,1}$, and
hence a part of the cache of user $k$. Thus, user $k$ can compute
$\widehat{W}_{D_{k},[0:5]\setminus\\{S_{k}+3k\\}}$. Using (17), it can be
shown that
$\widehat{W}_{D_{k},[0:5]\setminus\\{S_{k}+3k\\}}=W_{D_{k},[0:5]\setminus\\{S_{k}+3k\\}}$.
Thus, user $k$ can retrieve all symbols belonging to each of the three groups
of file $W_{D_{k}}$ and she can recover this file by concatenating these
symbols.

Privacy: To show the demand-privacy for user $k\in\\{0,1\\}$, we first define
$\tilde{k}=(k+1)$ mod $2$. Since $I(D_{\tilde{k}};Z_{k},D_{k})=0$, the privacy
condition $I(D_{\tilde{k}};X,Z_{k},D_{k})=0$ follows by showing that
$I(X;D_{\tilde{k}}|Z_{k},D_{k})=0$. To that end, we divide all symbols that
are a part of the main payload into two sets, $X^{\prime}_{k}$ and
$\tilde{X}^{\prime}_{k}$ which are defined as follows:

$\displaystyle X^{\prime}_{k}$
$\displaystyle=\\{Y_{[0:NK-1]}\\}\cup\\{V_{\mbox{$\cal{R}$}}|S_{k}+3k\in\mbox{$\cal{R}$},V_{\mbox{$\cal{R}$}}\in
X^{\prime}\\},$ $\displaystyle\tilde{X}^{\prime}_{k}$
$\displaystyle=X^{\prime}\setminus X^{\prime}_{k}.$

Note that the positions in $X^{\prime}$ of all symbols belonging to
$X^{\prime}_{k}$ is known to user $k$ while the positions of symbols belonging
to $\tilde{X}^{\prime}_{k}$ are not known. It can be shown that all symbols in
$\tilde{X}^{\prime}_{k}$ appear like a sequence of random bits to user $k$.
This is because for some set $\cal{R}$,
$\mbox{$\cal{R}$}\subset[0:5],|\mbox{$\cal{R}$}|=4,5$, the server broadcasts
$V_{\mbox{$\cal{R}$}}$ instead of $Y_{\mbox{$\cal{R}$}}$. The symbol
$W_{\mbox{$\cal{R}$}}$ essentially hides the message $Y_{\mbox{$\cal{R}$}}$
from all users that do not belong to set $\cal{R}$. Further, it can also be
shown that

$\displaystyle H(X^{\prime}_{k}|W_{D_{k}},Z_{k},\bar{S}\ominus\bar{D})=0.$
(18)

It is easy to see that, $(W_{D_{k}},Z_{k},\bar{S}\ominus\bar{D})$ does not
reveal any information about $D_{\tilde{k}}$ which in combination with (18)
ensures privacy.

###  III-D Comparison of our schemes

Figure 3: Comparison of different schemes for $N=15$ and $K=10$. The region
given by the lower convex envelop (LCE) of the the points in Theorem 3 and
Theorem 4 is larger than the region given by the LCE of the points in Theorem
2.

Now we give a comparison of our schemes. From numerical simulations we observe
that, a combination of Schemes B and C outperforms Scheme A for $K<N$, and
Scheme A outperforms both Schemes B and C for $N\leq K$, i.e., for $K<N$, the
region given by the lower convex envelop (LCE) of the the points in Theorem 3
and Theorem 4, is larger than the region given by the LCE of the points in
Theorem 2. Whereas, we observe the opposite for $N\leq K$, i.e., the region
given by the LCE of the points in Theorem 2 is larger than the region given by
the LCE of the points in Theorem 3 and Theorem 4. In Fig. 3, we plot the
memory-rate pairs achievable using our schemes along with the pairs of
achievable using the MDS scheme in [27] for $N=15$ and $K=10$. In Fig. 4, we
give a comparison of the memory-rate pairs achievable using different schemes
for $N=10$ and $K=15$.

Figure 4: Comparison of different schemes for $N=10$ and $K=15$. The region
given by the lower convex envelop (LCE) of the points in Theorem 2 is larger
than the region given by the LCE of the points in Theorem 3 and Theorem 4.

###  III-E Tightness of the achievable memory-rate pairs

Now we compare the memory-rate pairs achievable using our schemes with lower
bounds on the optimal rates for non-private schemes. Recall that for $N$
files, $K$ users and memory $M$, $R^{*p}_{N,K}(M)$ and $R^{*}_{N,K}(M)$ denote
the optimal private rate and non-private rate, respectively.

###### Theorem 5

Let $R^{A}_{N,K}(M)$ denote the LCE of the points in Theorem 2, and let
$R^{BC}_{N,K}(M)$ denote the LCE of the points in Theorem 3 and Theorem 4.
Then, we have

  1. 1.

For $N\leq K$,

$\displaystyle\frac{R^{A}_{N,K}(M)}{R^{*}_{N,K}(M)}\leq\begin{cases}4&\text{
if }M\leq\left(1-\frac{N}{K}\right)\\\ 8&\text{
if}\left(1-\frac{N}{K}\right)\leq M\leq\frac{N}{2}\\\ 2&\text{ if
}M\geq\frac{N}{2}.\end{cases}$ (19)

  2. 2.

For $K<N$,

$\displaystyle\frac{R^{BC}_{N,K}(M)}{R^{*}_{N,K}(M)}$
$\displaystyle\leq\begin{cases}3&\text{ if }M<\frac{N}{2}\\\ 2&\text{ if
}M\geq\frac{N}{2}.\end{cases}$ (20)

  3. 3.

For all $N$ and $K$, $R^{*p}_{N,K}(M)=R^{*}_{N,K}(M)$ if
$M\geq\frac{N(NK-K)}{NK-K+1}$.

Since $R^{A}_{N,K}(M)\geq R^{*p}_{N,K}(M)\geq R^{*}_{N,K}(M)$, the upper
bounds in (19) also hold for the ratios
$\frac{R^{A}_{N,K}(M)}{R^{*p}_{N,K}(M)}$ and
$\frac{R^{*p}_{N,K}(M)}{R^{*}_{N,K}(M)}$. Similarly, the upper bounds in (20)
also hold for the ratios $\frac{R^{BC}_{N,K}(M)}{R^{*p}_{N,K}(M)}$ and
$\frac{R^{*p}_{N,K}(M)}{R^{*}_{N,K}(M)}$.

The proof of Theorem 5 is presented in Subsection IV-E. Theorem 5 shows that a
combination of our schemes gives rates that are always within a constant
multiplicative factor from the optimal, i.e., the order optimality result is
shown for all cases. We also note that the order optimality result is also
obtained in [27] for all regimes except for the case when $K<N$ and $M<N/K$.
The constant factors in (19) and also the factor $2$ for the regime $K<N,M\geq
N/2$ are obtained in [27]. In contrast, the constant factor $3$ in (20) for
the regime $K<N,M<N/2$ shows the order optimality for the case $K<N,M<N/K$,
and improves the previously known factor $4$ for the case $K<N,M\leq N/K<N/2$.

One natural question that arises in demand-private coded caching is how much
cost it incurs due to the extra constraint of demand privacy. It follows from
Theorem 5 that the extra cost is always within a constant factor. However, we
note that the extra cost may not be a constant factor for all the regimes
under the stronger privacy condition (12). For example, when $K<N$ and $M=0$,
the optimal non-private rate is $K$. However, for this case, the optimal
private rate under the stronger privacy condition (12) is shown to be $N$ in
[30], whereas the optimal private rate under the privacy condition (9) is $K$
(Theorem 3). Such a difference in rates under these two notions of privacy
conditions also extends for very small memory regimes when $K<N$.

###  III-F Exact trade-off for $N\geq K=2$

For $N=K=2$, the exact trade-off under no privacy was shown in [1]. Tian
characterized the exact trade-off under no privacy for $N>K=2$ in [34]. For
$N=K=2$, the non-private trade-off region is characterized by three lines.
Whereas, if $N>2,K=2$, then the non-private trade-off region is given by two
lines. We characterize the exact trade-off for $N\geq K=2$ under demand
privacy in the following theorem. The characterization shows that the exact
trade-off region of private schemes for $N\geq K=2$ is always given by three
lines.

Figure 5: The figure on the left gives the exact trade-off with demand privacy
for $N=K=2$ and the region given by other known schemes. The figure on the
right gives the exact trade-off with demand privacy for $N=2,3,4$ and $K=2$.

###### Theorem 6

  1. 1.

Any memory-rate pair $(M,R)$ is achievable with demand privacy for $N=K=2$ if
and only if

$\displaystyle 2M+R\geq 2,\quad 3M+3R\geq 5,\quad M+2R\geq 2.$ (21)

  2. 2.

Any memory-rate pair $(M,R)$ is achievable with demand privacy for $N>K=2$ if
and only if

$\displaystyle 3M+NR\geq 2N,\quad 3M+(N+1)R\geq 2N+1,\quad M+NR\geq N.$ (22)

Next we give some outlines of the achievability schemes and the converse to
obtain Theorem 6.

Outline of converse: Any $(M,R)$ pair that is achievable under no privacy
requirement needs to satisfy the first and third inequalities in (21) for
$N=K=2$ [1]. Similarly, for $N>K=2$, any $(M,R)$ pair satisfies the first and
third inequalities in (IV-G2) under no privacy [34]. Since any converse bound
with no privacy requirement is also a converse bound with privacy. So, to
prove the converse result, we need to show only the second inequality in
(IV-G2) and in (21). Furthermore, observe that substituting $N=2$ in the
second inequality in (IV-G2) gives the second inequality in (21). So, to show
the converse of Theorem 6, we prove that for $N\geq K=2$, any $(M,R)$ pair
under privacy satisfies the second inequality in (IV-G2). Full proof of the
converse can be found in Subsection IV-F.

Outline of achievability: To show the achievability of the region in (21), we
use a particular non-private scheme from [34]. Using this particular non-
private scheme, we can show that for any $(M,R)$ pair in the region by (21),
there exists an $(2,4,M,R)$-$\cal{D}_{RS}$-non-private scheme. Then, the
achievability follows from Theorem 1. Details can be found in Subsection IV-G.

To prove the achievability of the region given by (IV-G2) for $K=2$ and $N>2$,
we show the achievability of two corner points $(\frac{N}{3},1)$ and
$(\frac{N^{2}}{2N-1},\frac{N-1}{2N-1})$. The corner points of the memory-rate
curve given by (IV-G2) are
$(0,2),(\frac{N}{3},1),(\frac{N^{2}}{2N-1},\frac{N-1}{2N-1})$ and $(N,0)$. The
achievability of the points $(0,2)$ and $(N,0)$ follows from Theorem 3. We
propose two schemes, Scheme D and Scheme E which achieve the pairs
$(\frac{N}{3},1)$ and $(\frac{N^{2}}{2N-1},\frac{N-1}{2N-1})$, respectively.
Scheme D achieves memory-rate pair $(\frac{N}{3},1)$ using uncoded prefetching
while Scheme E achieves memory-rate pair
$(\frac{N^{2}}{2N-1},\frac{N-1}{2N-1})$ using coded prefetching. In Example 4,
we describe Scheme D for $N=3,K=2,M=1$. Then in Example 5, we describe Scheme
E for $N=3,K=2,M=2/5$. General versions of both these schemes for $N>2$ and
$K=2$ are provided in Subsection IV-G.

###### Example 4

We describe Scheme D for $N=3$ and $K=2$ which achieves rate $1$ for
$M=\frac{N}{3}=1$. File $W_{i},i\in[0:2]$ is divided into 3 disjoint parts of
equal size, i.e., $W_{i}=(W_{i,0},W_{i,1},W_{i,2})$.

Caching: The server picks 2 independent permutations $\pi_{0}$ and $\pi_{1}$
uniformly at random from the symmetric group of permutations of [0:2]. The
server places $\pi_{0}(W_{0,0},W_{1,0},W_{2,0})$ and
$\pi_{1}(W_{0,1},W_{1,1},W_{2,1})$ in the caches of user 0 and user 1,
respectively. Each of these permutation functions $\pi_{0}$ and $\pi_{1}$ are
unknown to both the users. Some additional random bits are also shared with
each user in the caching phase.

Delivery: The server picks permutation $\pi_{2}$ uniformly at random from the
symmetric group of permutations of [0:2] which is independent of $\pi_{0}$,
$\pi_{1}$. The main payload $X^{\prime}$ is given by

$\displaystyle X^{\prime}=\begin{cases}\pi_{2}(W_{D_{0},1}\oplus
W_{D_{1},0},W_{D_{0},2},W_{D_{1},2})\qquad\qquad\qquad\text{if }D_{0}\neq
D_{1}\\\ \pi_{2}(W_{D_{0},1}\oplus W_{m,0},W_{D_{0},2},W_{D_{1},0}\oplus
W_{m,1})\qquad\quad\text{if }D_{0}=D_{1}\end{cases}$

where $m=(D_{0}+1)$ mod $3$. To enable decoding at each user, the server also
transmits some auxiliary transmission $J=(J_{1},J_{2},J_{3})$ of negligible
rate. Each $J_{j},j=1,2,3$ can be further divided into 2 parts, i.e.,
$J_{j}=(J_{j,0},J_{j,1})$, where $J_{j,k},k\in\\{0,1\\}$ is meant for user $k$
for all $j=1,2,3$. Using a one-time pad which uses the pre-shared random bits,
the server ensures that $J_{j,k}$ can be decoded only by user $k$ and it is
kept secret from the other user. These parts are used as follows:

  1. 1.

$J_{1,k}$ conveys the position of $W_{D_{k},k}$ in user $k$’s cache.

  2. 2.

$J_{2,k}$ gives the positions of the coded and uncoded parts of $X^{\prime}$
involving $W_{D_{k}}$ to user $k$. Specifically, $J_{2,k}$ reveals the
positions of $W_{D_{0},1}\oplus W_{D_{1},0}$ and $W_{D_{k},2}$ to user $k$
when $D_{0}\neq D_{1}$, and the positions of $W_{D_{k},\tilde{k}}\oplus
W_{m,k}$ and $W_{D_{k},2}$ when $D_{0}=D_{1}$, where $\tilde{k}=(k+1)$ mod 2.

  3. 3.

$J_{3,k}$ discloses the position of $W_{D_{\tilde{k}},k}$ if $D_{0}\neq D_{1}$
and $W_{m,k}$ if $D_{0}=D_{1}$ in her cache to user $k$.

Decoding: User $k$ decodes $W_{D_{k}}$ as follows. $W_{D_{k},k}$ can be
obtained from the cache since she knows its position from $J_{1,k}$. User $k$
recovers $W_{D_{k},2}$ from the delivery since she knows its position in
$X^{\prime}$ from $J_{2,k}$. The remaining segment $W_{D_{k},\tilde{k}}$ is
available in coded form in $X^{\prime}$. The segment that
$W_{D_{k},\tilde{k}}$ is XOR-ed with, is available in the cache of user $k$,
and its position in the cache is revealed by $J_{3,k}$. Thus, user $k$
retrieves all three segments of file $W_{D_{k}}$.

Privacy: Now we give an outline of how $D_{1}$ is kept secret from user 0.
From the transmission, we can observe that for both the cases, i.e.,
$D_{0}\neq D_{1}$ and $D_{0}=D_{1}$, user 0 receives $W_{D_{0},2}$ in the
uncoded form and $W_{D_{0},1}$ coded with another symbol. Also, in both the
cases, the remaining symbol is like a sequence of $\frac{F}{3}$ random bits to
user 0, because it contains either $W_{D_{1},2}$ or $W_{m,1}$ which she
doesn’t have access to. Thus, even though the structure of the broadcast is
different in the two cases, any user cannot differentiate between them.
Further, given $J_{1,0}$, any of the remaining 2 symbols can occupy the
remaining 2 positions in the cache with equal likelihood. Thus, although user
0 can use one of these symbols, i.e., the symbol XOR-ed with $W_{D_{0},1}$,
for decoding with the help of $J_{3,0}$, the identity of the symbol is not
known because $J_{3,0}$ only discloses the position of that symbol in user 0’s
cache. Due to the symmetry of the scheme, similar privacy arguments apply for
user 1.

###### Example 5

Now we describe Scheme E for $N=3$ and $K=2$ which achieves rate
$\frac{N-1}{2N-1}=\frac{2}{5}$, for $M=\frac{N^{2}}{2N-1}=\frac{9}{5}$. File
$W_{i},i\in[0:2]$ is partitioned into $2N-1=5$ parts of equal size, i.e.,
$W_{i}=(W_{i,1},W_{i,2},W_{i,3},W_{i,4},W_{i,5})$. We encode each file $W_{i}$
using a $(3N-2,2N-1)=(7,5)$ MDS code (i.e. each file is split into $5$ pieces
of size $\frac{F}{5}$ bits each, which are then encoded using $(7,5)$ MDS code
such that each of $7$ MDS coded symbols has $\frac{F}{5}$ bits). Each file can
be reconstructed using any $5$ MDS symbols. The $7$ symbols of file $W_{i}$
are denoted by $F_{i,0},F_{i,0,0},F_{i,0,1},F_{i,1,0},F_{i,1,1},F_{i,2,0}$ and
$F_{i,2,1}$. Further, we define tuples
$\mbox{$\cal{L}$}_{0},\mbox{$\cal{L}$}_{1}$ and $\mbox{$\cal{L}$}_{2}$ as
follows:

$\mbox{$\cal{L}$}_{j}=(F_{i,0},F_{i,j,0},F_{i,j,1})_{i\in[0:2]},\quad\forall
j\in[0:2].\\\ $

Caching: The server picks 2 independent permutation functions $\pi_{0}$ and
$\pi_{1}$ uniformly at random from the symmetric group of permutations of
[0:8]. The server also picks a random number $U_{0}$ which is uniformly
distributed in $\\{0,1,2\\}$ and places $\pi_{0}(\mbox{$\cal{L}$}_{U_{0}})$ in
the cache of user 0. Similarly, the server picks random number $U_{1}$ which
is uniformly distributed in $\\{0,1,2\\}\backslash\\{U_{0}\\}$ and places
$\pi_{1}(\mbox{$\cal{L}$}_{U_{1}})$ in user 1’s cache. Similar to Scheme D,
each of these permutation functions $\pi_{0}$ and $\pi_{1}$ are private to
both the users. Unlike the permutation functions, $U_{k}$ is shared with user
$k\in\\{0,1\\}$ by placing it in her cache and thus kept secret from the other
user.

Delivery: The main payload, $X^{\prime}$ is given by

$X^{\prime}=\left\\{\begin{array}[]{lcl}(F_{D_{0},U_{1},0}\oplus
F_{D_{1},U_{0},0},F_{D_{0},U_{1},1}\oplus F_{D_{1},U_{0},1})&\text{if
}D_{0}\neq D_{1}\\\ \\\ (F_{D_{0},V,0}\oplus F_{m_{1},0},F_{D_{0},V,1}\oplus
F_{m_{2},0})&\text{if }D_{0}=D_{1}\end{array}\right.$

where, $m_{t}=(D_{0}+t)$ mod $3$, and $V=[0:2]\backslash\\{U_{0},U_{1}\\}$.

To enable decoding at each user, the server also transmits some auxiliary
transmission $J=(J_{1},J_{2},J_{3})$ of negligible rate. Each $J_{j},j=1,2,3$
can be further divided into 2 parts, i.e., $J_{j}=(J_{j,0},J_{j,1})$. where
$J_{j,k},k\in\\{0,1\\}$ is meant for user $k$ for all $j=1,2,3$. Using a one-
time pad, the server ensures that $J_{j,k}$ can be decoded only by user $k$
and it is kept secret from the other user. These parts are used as follows:

  1. 1.

$J_{1,k}$ conveys the positions of $F_{D_{k},0},F_{D_{k},U_{k},0}$ and
$F_{D_{k},U_{k},1}$ in user $k$’s cache.

  2. 2.

$J_{2,k}$ discloses the positions of symbols $F_{D_{\tilde{k}},U_{k},0}$ and
$F_{D_{\tilde{k}},U_{k},1}$ in user $k$’s cache if $D_{0}\neq D_{1}$, where
$\tilde{k}=(k+1)$ mod 2. If $D_{0}=D_{1}$, then $J_{2,k}$ reveals the
positions of $F_{m_{1},0}$ and $F_{m_{2},0}$ in the cache for user $k$.

  3. 3.

$J_{3,k}$ gives the value of the random variable $T_{k}$ which takes the value
$U_{\tilde{k}}$ if $D_{0}\neq D_{1}$, and $V$ if $D_{0}=D_{1}$.

Decoding: Let us consider the decoding of $W_{D_{k}}$ at user $k$. First, the
user retrieves $F_{D_{k},0},F_{D_{k},U_{k},0}$ and $F_{D_{k},U_{k},1}$
directly from the cache since its positions are obtained from $J_{1,k}$. The
positions of $F_{D_{\tilde{k}},U_{k},0}$ and $F_{D_{\tilde{k}},U_{k},1}$ when
$D_{0}\neq D_{1}$, and the positions of $F_{m_{1},0}$ and $F_{m_{2},0}$ when
$D_{0}=D_{1}$, are available through $J_{2,k}$. Thus, using $X^{\prime}$ user
$k$ can recover $F_{D_{k},U_{\tilde{k}},0}$ and $F_{D_{k},U_{\tilde{k}},1}$,
or $F_{D_{k},V,0}$ and $F_{D_{k},V,1}$, accordingly. Note that because user
$k$ does not know whether $D_{0}\neq D_{1}$ or $D_{0}=D_{1}$, she also does
not know whether she has recovered $F_{D_{k},U_{\tilde{k}},0}$ and
$F_{D_{k},U_{\tilde{k}},1}$ or $F_{D_{k},V,0}$ and $F_{D_{k},V,1}$. This
information is available through $J_{3,k}$ which gives the value of $T_{k}$.
Thus, user $k$ has knowledge of $F_{D_{k},T_{k},0}$ and $F_{D_{k},T_{k},1}$.
Since $T_{k}\neq U_{k}$, user $k$ has access to 5 distinct symbols of the MDS
code namely,
$F_{D_{k},0},F_{D_{k},U_{k},0},F_{D_{k},U_{k},1},F_{D_{k},T_{k},0}$ and
$F_{D_{k},T_{k},1}$. Thus, the file $W_{D_{k}}$ can be retrieved.

Privacy: Now we describe how $D_{1}$ remains private to user 0. It is
important to note that, from the knowledge of the tuple $(U_{0},D_{0},T_{0})$,
user 0 cannot find out the demand of user 1. For example, if
$(U_{0},D_{0},T_{0})=(0,0,1)$, $(U_{1},D_{1})$ can take 3 distinct values
namely, $(1,1)$, $(1,2)$ and $(2,0)$, all 3 possibilities being equally
likely, implying that even after knowing $(U_{0},D_{0},T_{0})$, $D_{1}$ can
take all 3 values with equal likelihood. Since $\pi_{0}$ is not shared with
user 0, and since the other auxiliary transmissions ($J_{1,0}$ and $J_{2,0}$)
reveal only the positions of the 5 relevant symbols in user 0’s cache, they
are independent of $D_{1}$ and can take any of the $9\choose{5}$ possible
values depending on $\pi_{0}$. Hence, it is clear that they do not reveal the
demand of user 1. These arguments are crucial in ensuring the demand-privacy
of user 1 and similar arguments hold for the other user as well due to the
symmetry of this scheme.

##  IV Proofs

###  IV-A Proof of Theorem 1

Let us consider any $(N,NK,M,R)$ $\cal{D}_{RS}$-non-private scheme. Let
$C_{k}^{(np)},k\in[0:NK-1]$ be the cache encoding functions, $E^{(np)}$ be the
broadcast encoding function, and $G_{k}^{(np)},k\in[0:NK-1]$ be the decoding
functions for the given $(N,NK,M,R)$ $\cal{D}_{RS}$-non-private scheme. We now
present a construction of an $(N,K,M,R)$-private scheme from the given
$(N,NK,M,R)$ $\cal{D}_{RS}$-non-private scheme.

Caching: For $k\in[0:K-1]$ and $S_{k}\in[0:N-1]$, the $k$-th user’s cache
encoding function is given by

$\displaystyle C_{k}(S_{k},\bar{W}):=C_{kN+S_{k}}^{(np)}(\bar{W}).$ (23)

The $k$-th user’s cache encoding function is taken to be the same as that of
the $S_{k}$-th user in the $k$-th stack in the corresponding $(N,NK)$ caching
problem. The cache content is given by $Z_{k}=(C_{k}(S_{k},\bar{W}),S_{k})$.

Delivery: To define the broadcast encoding, we need some new notations and
definitions. Let $\Psi:[0:N-1]^{N}\rightarrow[0:N-1]^{N}$ denote the cyclic
shift operator, such that
$\Psi(t_{1},t_{2},\ldots,t_{N})=(t_{N},t_{1},\ldots,t_{N-1})$. Let us denote a
vector $\mathbb{I}:=(0,1,\ldots,N-1)$. Let us also define

$\displaystyle\bar{S}\ominus\bar{D}:=(S_{0}\ominus D_{0},S_{1}\ominus
D_{1},\ldots,S_{K-1}\ominus D_{K-1})$

where $S_{k}\ominus D_{k}$ denotes the difference of $S_{k}$ and $D_{k}$
modulo $N$. For a given $\bar{D}\in[0:N-1]^{K}$, we define an expanded demand
vector for the non-private problem as:

$\displaystyle\bar{D}^{(np)}(\bar{D},\bar{S})=(\Psi^{S_{0}\ominus
D_{0}}(\mathbb{I}),\ldots,\Psi^{S_{K-1}\ominus D_{K-1}}(\mathbb{I}))$

where $\Psi^{i}$ denotes the $i$-times cyclic shift operator.

The broadcast encoding function for the $(N,K,M,R)$-private scheme is defined
by

$\displaystyle
E(\bar{W},\bar{D},\bar{S}):=E^{(np)}(\bar{W},\bar{D}^{(np)}(\bar{D},\bar{S})).$
(24)

Let us denote $X_{1}=E(\bar{W},\bar{D},\bar{S})$. In the private scheme, the
server transmits $X=(X_{1},\bar{S}\ominus\bar{D})$.

Decoding: User $k\in[0:K-1]$ uses the decoding function of the $(kN+S_{k})$-th
user in the non-private scheme, i.e.,

$\displaystyle G_{k}(D_{k},S_{k},\bar{S}\ominus\bar{D},X_{1},Z_{k})$
$\displaystyle:=G_{kN+S_{k}}^{(np)}(\bar{D}^{(np)}(\bar{D},\bar{S}),X_{1},Z_{k}).$
(25)

Here the decoder computes $\bar{D}^{(np)}(\bar{D},\bar{S})$ from
$\bar{S}\ominus\bar{D}$.

From (23), (24), and (25), it is clear that the decoder of the $k$-th user
outputs the same file requested by the $S_{k}$-th virtual user of the $k$-th
stack in the non-private scheme. The index of the output file is the
$(kN+S_{k})$-th component in $\bar{D}^{(np)}(\bar{D},\bar{S})$, i.e.,
$S_{k}\ominus(S_{k}\ominus D_{k})=D_{k}$. Thus, the $k$-th user recovers its
desired file.

Proof of privacy: The proof of privacy essentially follows from the fact that
$S_{i}$ acts as one-time pad for $D_{i}$ which prevents any user $j\neq i$
getting any information about $D_{i}$. We now show that the derived
$(N,K,M,R)$-private scheme satisfies the privacy condition (9). First we show
that $I({\bar{D}_{\tilde{k}}};Z_{k},D_{k},X{}|\bar{W})=0$.

$\displaystyle I({\bar{D}_{\tilde{k}}};Z_{k},D_{k},X{}|\bar{W})$
$\displaystyle=H(Z_{k},D_{k},X{}|\bar{W})-H(Z_{k},D_{k},X{}|\bar{W},{\bar{D}_{\tilde{k}}})$
$\displaystyle\overset{(a)}{=}H(S_{k},D_{k},\bar{S}\ominus\bar{D},\bar{D}^{(np)}(\bar{D},\bar{S})|\bar{W})-H(S_{k},D_{k},\bar{S}\ominus\bar{D},\bar{D}^{(np)}(\bar{D},\bar{S})|\bar{W},{\bar{D}_{\tilde{k}}})$
$\displaystyle\overset{(b)}{=}H(S_{k},D_{k},\bar{S}\ominus\bar{D}|\bar{W})-H(S_{k},D_{k},\bar{S}\ominus\bar{D}|\bar{W},{\bar{D}_{\tilde{k}}})$
$\displaystyle\overset{(c)}{=}H(S_{k},D_{k},\bar{S}\ominus\bar{D})-H(S_{k},D_{k},\bar{S}\ominus\bar{D}|{\bar{D}_{\tilde{k}}})$
$\displaystyle\overset{(d)}{=}H(S_{k},D_{k},\bar{S}\ominus\bar{D})-H(S_{k},D_{k},\bar{S}\ominus\bar{D})$
$\displaystyle=0.$ (26)

Here, $(a)$ follows since
$X=(X_{1},\bar{S}\ominus\bar{D}),Z_{k}=(C_{k}(S_{k},\bar{W}),S_{k})$, and also
due to (24). In $(b)$, we used that
$H(\bar{D}^{(np)}(\bar{D},\bar{S})|\bar{S}\ominus\bar{D})=0$, and $(c)$
follows since $(S_{k},D_{k},\bar{S}\ominus\bar{D},{\bar{D}_{\tilde{k}}})$ is
independent of $\bar{W}$. We get $(d)$ since $S_{i}\ominus D_{i}$ is
independent of $D_{i}$ for all $i\in[0:K-1]$. Using the fact that demands and
files are independent, we get the following from (26)

$\displaystyle I({\bar{D}_{\tilde{k}}};Z_{k},D_{k},X{},\bar{W})$
$\displaystyle=I({\bar{D}_{\tilde{k}}};\bar{W})+I({\bar{D}_{\tilde{k}}};Z_{k},D_{k},X{}|\bar{W})$
$\displaystyle=0.$

This shows the derived scheme satisfies the privacy condition
$I({\bar{D}_{\tilde{k}}};Z_{k},D_{k},X{})=0$.

The size of the cache in the $(N,K,M,R)$-private scheme differs only by the
size of the shared key from the $(N,NK,M,R)$ $\cal{D}_{RS}$-non-private
scheme. For large enough file size $2^{F}$, this difference is negligible.
Furthermore, we can observe that the rate of transmission in
$(N,K,M,R)$-private scheme is the same as that of the $(N,NK,M,R)$
$\cal{D}_{RS}$-non-private scheme. This proves Theorem 1.

###  IV-B Proof of Lemma 1

Consider any

$\displaystyle(M,R)=\left(\frac{Nr}{NK-K+1},\frac{{NK-K+1\choose
r+1}-{NK-K+1-N\choose r+1}}{{NK-K+1\choose r}}\right),\quad\text{ for
}r\in\\{0,1,\ldots,NK-K\\}$

which is achievable for $N$ files and $NK-K+1$ users by the YMA scheme. We
will construct an $(N,NK,M,R)$ $\cal{D}_{RS}$-non-private scheme with these
$(M,R)$ pairs. We denote the set of $NK$ users by
$\mbox{$\cal{U}$}=\mbox{$\cal{U}$}_{1}\cup\mbox{$\cal{U}$}_{2}$, where

$\displaystyle\mbox{$\cal{U}$}_{1}:=\\{u^{\prime}_{1},u^{\prime}_{2},\ldots,u^{\prime}_{K-1}\\},$

and

$\displaystyle\mbox{$\cal{U}$}_{2}:=\\{u_{0},u_{1},\ldots,u_{NK-K}\\}.$

The users are partitioned into $K$ subsets/stacks
$\mbox{$\cal{K}$}_{i},i\in[0:K-1]$ as given below.

$\displaystyle\mbox{$\cal{K}$}_{0}$ $\displaystyle=\\{u_{j}|j\in[0:N-1]\\},$
$\displaystyle\mbox{$\cal{K}$}_{i}$ $\displaystyle=\\{u_{j}|i(N-1)+1\leq
j\leq(i+1)N-1\\}\cup\\{u^{\prime}_{i}\\}\quad\mbox{ for }1\leq i\leq K-1.$

The stacks of users are shown in Fig. 6. We denote the demand of
$u_{i}\in\mbox{$\cal{U}$}_{2}$ by $d_{i}$, and the demand of
$u^{\prime}_{i}\in\mbox{$\cal{U}$}_{1}$ by $d^{\prime}_{i}$. Similarly, we
denote the cache of $u_{i}\in\mbox{$\cal{U}$}_{2}$ by $Z_{i}$, and the cache
of user $u^{\prime}_{i}\in\mbox{$\cal{U}$}_{1}$ by $Z^{\prime}_{i}$. We
further define

$\displaystyle\mbox{$\cal{K}$}^{\prime}_{i}$
$\displaystyle:=\\{j|u_{j}\in\mbox{$\cal{K}$}_{i}\\}\quad\text{for
}i=0,1,2,\ldots,K-1.$ $\displaystyle\mbox{$\cal{V}$}_{i}$
$\displaystyle:=\mbox{$\cal{K}$}^{\prime}_{0}\cup\mbox{$\cal{K}$}^{\prime}_{i},\quad\text{for
}i=1,2,\ldots,K-1.$

Figure 6: The stacks of users are shown vertically. The users from
$\mbox{$\cal{U}$}_{2}$ are shown in black color, whereas those from
$\mbox{$\cal{U}$}_{1}$ are shown in red color.

Caching: The users in $\mbox{$\cal{U}$}_{2}$ has the same prefetching as that
of the users in the YMA scheme. Let $Z_{m}^{\text{YMA}},m=0,\ldots,NK-K$
denote the cache content of $m$-th user in the YMA scheme. The cache content
of user $u_{j}\in\mbox{$\cal{U}$}_{2}$ is given by

$\displaystyle Z_{j}=Z_{j}^{\text{YMA}}.$

To explain the prefetching of users in $\mbox{$\cal{U}$}_{1}$, let

$\displaystyle\mbox{$\cal{T}$}:=[0:NK-K].$

In the YMA scheme, each file is divided into ${NK-K+1\choose r}$ subfiles and
file $W_{i},i\in[0:N-1]$ is given by

$W_{i}=(W_{i,\mbox{$\cal{R}$}})_{\mbox{$\cal{R}$}\subset\mbox{$\cal{T}$},|\mbox{$\cal{R}$}|=r}.$

For $\mbox{$\cal{S}$}\subset\mbox{$\cal{T}$}$ such that
$|\mbox{$\cal{S}$}|=r-1$, we define

$\displaystyle
Z^{j}_{i,\mbox{$\cal{S}$}}:=\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\setminus\mbox{$\cal{S}$}\cap\mbox{$\cal{V}$}_{i}}W_{j,\\{u\\}\cup\mbox{$\cal{S}$}},\text{
for }i\in[0:K-1]\setminus\\{0\\},\;j\in[0:N-1].$ (27)

The cache content of user $u^{\prime}_{i}\in\mbox{$\cal{U}$}_{1}$ is given by

$\displaystyle
Z^{\prime}_{i}=\left(Z^{j}_{i,\mbox{$\cal{S}$}}|\mbox{$\cal{S}$}\subset\mbox{$\cal{T}$}\setminus\\{0\\},|\mbox{$\cal{S}$}|=r-1\right)_{j\in[0:N-1]}.$

Since the size of one $Z^{j}_{i,\mbox{$\cal{S}$}}$ is $\frac{F}{{NK-K+1\choose
r}}$ and since there are ${NK-K\choose r-1}$ possible sets $\cal{S}$, the
number of bits stored at user $u^{\prime}_{i}$ is given by

$\displaystyle len(Z^{\prime}_{i})$ $\displaystyle=\frac{NF{NK-K\choose
r-1}}{{NK-K+1\choose r}}$ $\displaystyle=\frac{NFr}{NK-K+1}$
$\displaystyle=FM.$

Delivery: For a given $\bar{d}\in\mbox{$\cal{D}_{RS}$}$, let
$\bar{d}_{1}=(d^{\prime}_{i})_{u^{\prime}_{i}\in\mbox{$\cal{U}$}_{1}}$ and
$\bar{d}_{2}=(d_{i})_{u_{i}\in\mbox{$\cal{U}$}_{2}}$. The server chooses the
transmission of the YMA scheme for $\mbox{$\cal{U}$}_{2}$ under demand
$\bar{d}_{2}$. The broadcast transmission is described using

$\displaystyle
Y_{\mbox{$\cal{R}$}}=\bigoplus_{u\in\mbox{$\cal{R}$}}W_{d_{u},\mbox{$\cal{R}$}\setminus\\{u\\}},\quad\mbox{$\cal{R}$}\subset\mbox{$\cal{T}$}\text{
such that }|\mbox{$\cal{R}$}|=r+1.$ (28)

The broadcast transmission $X$ is given by

$\displaystyle
X=\\{Y_{\mbox{$\cal{R}$}}|\mbox{$\cal{R}$}\cap\mbox{$\cal{K}$}_{0}\neq\phi\\}.$

Note that in the above broadcast transmission, stack of users
$\mbox{$\cal{K}$}_{0}$ corresponds to the set of “leaders” described in the
YMA scheme since each file $W_{i},i\in[0:N-1]$ is demanded by exactly one user
in $\mbox{$\cal{K}$}_{0}$. The size of each symbol $Y_{\mbox{$\cal{R}$}}\in X$
is $\frac{F}{{NK-K+1\choose r}}$ and $X$ contains ${NK-K+1\choose
r+1}-{NK-K+1-N\choose r+1}$ such symbols. Thus,

$\displaystyle len(X)$ $\displaystyle=\frac{\left({NK-K+1\choose
r+1}-{NK-K+1-N\choose r+1}\right)F}{{NK-K+1\choose r}}$ $\displaystyle=RF.$

Decoding:  For all user in $\mbox{$\cal{U}$}_{2}$, the decodability follows
from the decodability of the YMA scheme. The decoding of users in
$\mbox{$\cal{U}$}_{1}$ is as follows.

###### Remark 4

From the YMA scheme, we know that all symbols $Y_{\mbox{$\cal{R}$}}$ such that
$\mbox{$\cal{R}$}\subset[0:NK-1]$ and $|\mbox{$\cal{R}$}|=r+1$ can be
recovered from $X$. Similarly the following lemma states that although all
symbols $Z^{j}_{i,\mbox{$\cal{S}$}}$ given in (27) are not a part of the cache
of user $u^{\prime}_{i}\in\mbox{$\cal{U}$}_{1}$, each of these symbols can
still be recovered from the cache contents.

###### Lemma 2

For $i\in[0:K-1]\setminus\\{0\\}$, all symbols $Z^{j}_{i,\mbox{$\cal{S}$}}$,
where $\mbox{$\cal{S}$}\subset\mbox{$\cal{T}$},\;|\mbox{$\cal{S}$}|=r-1$, and
$j\in[0:N-1]$, can be recovered from the cache content $Z^{\prime}_{i}$ of
user $u^{\prime}_{i}$.

###### Proof.

See Appendix A. ∎

Next we show how user $u^{\prime}_{i}\in\mbox{$\cal{U}$}_{1}$ obtains
$W_{d^{\prime}_{i},{\mbox{$\cal{R}$}}}$ for all $\cal{R}$ satisfying
$\mbox{$\cal{R}$}\subset\mbox{$\cal{T}$}$ and $|\mbox{$\cal{R}$}|=r$. Each
$W_{d^{\prime}_{i},{\mbox{$\cal{R}$}}}$ can be written as

$\displaystyle W_{d^{\prime}_{i},{\mbox{$\cal{R}$}}}$
$\displaystyle\overset{\mathrm{(a)}}{=}\bigoplus_{u\in\mbox{$\cal{V}$}_{i}}W_{d_{u},\mbox{$\cal{R}$}}$
$\displaystyle=\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}W_{d_{u},\mbox{$\cal{R}$}}\oplus\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}W_{d_{u},\mbox{$\cal{R}$}}$
$\displaystyle\overset{\mathrm{(b)}}{=}\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}W_{d_{u},\mbox{$\cal{R}$}}\oplus\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}\bigg{\\{}Y_{\\{u\\}\cup{\mbox{$\cal{R}$}}}\oplus\bigoplus_{t\in{\mbox{$\cal{R}$}}}W_{d_{t},\\{u\\}\cup{\mbox{$\cal{R}$}}\backslash\\{t\\}}\bigg{\\}}$
$\displaystyle=\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}W_{d_{u},\mbox{$\cal{R}$}}\oplus\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}Y_{\\{u\\}\cup{\mbox{$\cal{R}$}}}\oplus\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}\;\bigoplus_{t\in{\mbox{$\cal{R}$}}}W_{d_{t},\\{u\\}\cup{\mbox{$\cal{R}$}}\backslash\\{t\\}}$
$\displaystyle=\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}W_{d_{u},\mbox{$\cal{R}$}}\oplus\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}Y_{\\{u\\}\cup{\mbox{$\cal{R}$}}}\oplus\bigoplus_{t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}\;\bigoplus_{u\in{\mbox{$\cal{R}$}}}W_{d_{u},\\{t\\}\cup{\mbox{$\cal{R}$}}\backslash\\{u\\}}$
$\displaystyle=\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}W_{d_{u},\mbox{$\cal{R}$}}\oplus\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}Y_{\\{u\\}\cup{\mbox{$\cal{R}$}}}$
$\displaystyle\quad\oplus\bigoplus_{t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}\;\bigg{\\{}\bigoplus_{u\in{\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}}W_{d_{u},\\{t\\}\cup{\mbox{$\cal{R}$}}\backslash\\{u\\}}\oplus\bigoplus_{u\in{\mbox{$\cal{R}$}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}}W_{d_{u},\\{t\\}\cup{\mbox{$\cal{R}$}}\backslash\\{u\\}}\bigg{\\}}$
$\displaystyle=\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}W_{d_{u},\mbox{$\cal{R}$}}\oplus\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}Y_{\\{u\\}\cup{\mbox{$\cal{R}$}}}\oplus\bigoplus_{t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}\;\bigoplus_{u\in{\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}}W_{d_{u},\\{t\\}\cup{\mbox{$\cal{R}$}}\backslash\\{u\\}}$
$\displaystyle\quad\oplus\bigoplus_{t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}\;\bigoplus_{u\in{\mbox{$\cal{R}$}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}}W_{d_{u},\\{t\\}\cup{\mbox{$\cal{R}$}}\backslash\\{u\\}}$
$\displaystyle=\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}W_{d_{u},\mbox{$\cal{R}$}}\oplus\bigoplus_{u\in{\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}}\;\bigoplus_{t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}W_{d_{u},\\{t\\}\cup{\mbox{$\cal{R}$}}\backslash\\{u\\}}\oplus\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}Y_{\\{u\\}\cup{\mbox{$\cal{R}$}}}$
$\displaystyle\quad\oplus\bigoplus_{u\in{\mbox{$\cal{R}$}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}}\;\bigoplus_{t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}W_{d_{u},\\{t\\}\cup{\mbox{$\cal{R}$}}\backslash\\{u\\}}$
$\displaystyle=\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}\bigg{\\{}W_{d_{u},\mbox{$\cal{R}$}}\oplus\bigoplus_{t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}W_{d_{u},\\{t\\}\cup{\mbox{$\cal{R}$}}\backslash\\{u\\}}\bigg{\\}}\oplus\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}Y_{\\{u\\}\cup{\mbox{$\cal{R}$}}}$
$\displaystyle\quad\oplus\bigoplus_{u\in{\mbox{$\cal{R}$}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}}\;\bigoplus_{t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap(\mbox{$\cal{R}$}\backslash\\{u\\})}W_{d_{u},\\{t\\}\cup{\mbox{$\cal{R}$}}\backslash\\{u\\}}$
$\displaystyle=\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}\bigg{\\{}\bigoplus_{t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap(\mbox{$\cal{R}$}\backslash\\{u\\})}W_{d_{u},\\{t\\}\cup{\mbox{$\cal{R}$}}\backslash\\{u\\}}\bigg{\\}}\oplus\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}Y_{\\{u\\}\cup{\mbox{$\cal{R}$}}}$
$\displaystyle\quad\oplus\bigoplus_{u\in{\mbox{$\cal{R}$}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}}\;\bigoplus_{t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap(\mbox{$\cal{R}$}\backslash\\{u\\})}W_{d_{u},\\{t\\}\cup{\mbox{$\cal{R}$}}\backslash\\{u\\}}$
$\displaystyle\overset{\mathrm{(c)}}{=}\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}Z^{d_{u}}_{i,\mbox{$\cal{R}$}\backslash\\{u\\}}\oplus\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}Y_{\\{u\\}\cup{\mbox{$\cal{R}$}}}\quad\oplus\bigoplus_{u\in{\mbox{$\cal{R}$}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}}}Z^{d_{u}}_{i,\mbox{$\cal{R}$}\backslash\\{u\\}}$

where $(a)$ follows since all
$W_{d_{u},\mbox{$\cal{R}$}},u\in\mbox{$\cal{V}$}_{i}$ but
$W_{d^{\prime}_{i},\mbox{$\cal{R}$}}$ appear twice in the summation on the RHS
of $(a)$ which is due to the structure of demands in $\cal{D}_{RS}$. Further,
$(b)$ follows from the definition of $Y_{\\{u\\}\cup\mbox{$\cal{R}$}}$. The
symbols in the first and third terms of $(c)$ can be obtained from the cache
of the user due to Lemma 2, and the symbols in the second term can be obtained
from the delivery part because of Remark 4. Hence, the decodability of user
$u^{\prime}_{i}\in\mbox{$\cal{U}$}_{1}$ follows. This completes the proof of
Theorem 1.

###  IV-C Proof of Theorem 3

In the placement phase, the caches of all users are populated with the same
$M/N$ fraction of each file. Let each file $W_{i}$ be split in two parts:
cached part $W^{(c)}_{i}$ of length $FM/N$, and uncached part $W^{(u)}_{i}$ of
length $F(1-M/N)$. The cache contents of all the users are the same, and given
by $Z_{k}=(Z^{(0)},Z^{(1)},\ldots,Z^{(N-1)})$, where

$\displaystyle Z^{(i)}=W^{(c)}_{i},\quad\text{for }i=0,1,\ldots,N-1.$

To describe the delivery phase, we consider two cases:

Case 1: $N\leq K$

For $N\leq K$, the server broadcasts the remaining $(1-M/N)$ fraction of each
file. This scheme achieves privacy because the transmission does not depend on
the demands of the users.

Case 2: $K<N$

Let $D_{0},D_{1},\ldots,D_{K-1}$ be the demands of the users. The transmission
$X$ has two parts $(X^{\prime},J)$, where
$X^{\prime}=(X^{\prime}_{0},X^{\prime}_{1},\ldots,X^{\prime}_{K-1})$ is the
main payload, and $J$ is the auxiliary transmission of negligible rate which
helps each user find the corresponding decoding function. For each $i$,
$X^{\prime}_{i}$ is either $W^{(u)}_{D_{j}}$ for some $j$ or random bits of
the same length. In particular, the position of $W^{(u)}_{D_{j}}$ in
$X^{\prime}$ is denoted by a random variable $P_{j}\in[0:K-1]$. The random
variables $P_{0},P_{1},\ldots,P_{K-1}$ are defined inductively as

$\displaystyle P_{i}=$ $\displaystyle\begin{cases}P_{j}&\text{if
}D_{i}=D_{j}\text{ for some }j<i\\\ \sim
unif([0:K-1]\setminus\\{P_{0},P_{1},\ldots,P_{i-1}\\})&\text{if }D_{i}\neq
D_{j}\text{ for all }j<i.\end{cases}$

Note that each demanded (uncached) file is transmitted only in one component
of the transmission so that one user can not possibly detect the same file (as
its own demand) being transmitted in another component and thus infer that the
corresponding other user also has the same demand.

The keys $S_{0},S_{1},\ldots,S_{K-1}\in[0:K-1]$ are chosen i.i.d. and
uniformly distributed. The transmission is then given by

$\displaystyle X^{\prime}_{j}=\begin{cases}W^{(u)}_{D_{i}}&\text{ if
}j=P_{i}\text{ for some }i\in[0:K-1]\\\ \sim
unif\left(\\{0,1\\}^{F(1-M/N)}\right)&\text{ otherwise}\end{cases}$

and

$\displaystyle
J=(P_{0}\oplus_{K}S_{0},P_{1}\oplus_{K}S_{1},\ldots,P_{K-1}\oplus_{K}S_{K-1})$

where $\oplus_{K}$ denotes the addition modulo $K$ operation. Since user $k$
knows $S_{k}$, it can find $P_{k}$ from $J$. It then can find
$X^{\prime}_{P_{k}}=W^{(u)}_{D_{k}}$, and thus
$W_{D_{k}}=(Z^{(D_{k})},X^{\prime}_{P_{k}})$.

Next we show that this scheme also satisfies the privacy condition. Let us
denote $Q_{i}=P_{i}\oplus_{K}S_{i}$ for the ease of writing.

$\displaystyle I({\bar{D}_{\tilde{k}}};X,D_{k},Z_{k})$
$\displaystyle=I({\bar{D}_{\tilde{k}}};X^{\prime}_{0},\ldots,X^{\prime}_{K-1},Q_{0},Q_{1},\ldots,Q_{K-1},D_{k},S_{k},W^{(c)}_{0},\ldots,W^{(c)}_{N-1})$
$\displaystyle\overset{(a)}{=}I({\bar{D}_{\tilde{k}}};Q_{0},\ldots,Q_{K-1},D_{k},S_{k})$
$\displaystyle=I({\bar{D}_{\tilde{k}}};Q_{0},\ldots,Q_{k-1},Q_{k+1},\ldots,Q_{K-1},D_{k},S_{k},P_{k})$
$\displaystyle\overset{(b)}{=}0$

where $(a)$ follows because
$(X^{\prime}_{0},\ldots,X^{\prime}_{K-1},W^{(c)}_{0},\ldots,W^{(c)}_{N-1})$ is
uniformly distributed in $\\{0,1\\}^{MF+FK(1-M/N)}$, and is independent of
$({\bar{D}_{\tilde{k}}},Q_{0},\ldots,Q_{K-1},D_{k},S_{k})$, and $(b)$ follows
because all the random variables in the mutual information are independent. In
this scheme, the number of bits broadcasted is $FK(1-M/N)$ as the bits
transmitted for communicating $J$ is negligible for large $F$. Thus, the
scheme achieves rate $K(1-M/N)$.

###  IV-D Proof of Theorem 4

First we explain the scheme that achieves the memory-rate pairs given in
Theorem 4 . We further show that this scheme also preserves privacy.

For $t\in\\{1,2,\ldots,NK-1\\}$, we partition file $W_{i},i\in[0:N-1]$ into
$\sum_{l=t}^{NK-1}{NK\choose l}$ segments of $(NK-t)$ different sizes. These
segments are grouped into $(NK-t)$ groups such that all segments in the same
group have the same size. The segments are labelled by some subsets of
$[0:NK-1]$. The segments of $W_{i}$ are $W_{i,\mbox{$\cal{R}$}}$;
$\mbox{$\cal{R}$}\subset[0:NK-1],|\mbox{$\cal{R}$}|\in\\{t,t+1,\ldots,NK-1\\}$.
These $(NK-t)$ groups are given as

$\displaystyle\mbox{$\cal{T}$}_{|\mbox{$\cal{R}$}|}^{i}=\\{W_{i,\mbox{$\cal{R}$}}|\mbox{$\cal{R}$}\subset[0:NK-1]\\}\quad\text{
for }t\leq|\mbox{$\cal{R}$}|\leq NK-1.$

Thus, file $W_{i},i\in[0:N-1]$ is given as

$\displaystyle
W_{i}=\left(\mbox{$\cal{T}$}_{|\mbox{$\cal{R}$}|}^{i}\right)_{t\leq|\mbox{$\cal{R}$}|\leq
NK-1}.$

All elements of each file in one group have same size and elements of
different groups have different sizes. For
$|\mbox{$\cal{R}$}_{1}|<|\mbox{$\cal{R}$}_{2}|$, size of an element in
$\mbox{$\cal{T}$}_{|\mbox{$\cal{R}$}_{1}|}^{i}$ is
$r^{|\mbox{$\cal{R}$}_{2}|-|\mbox{$\cal{R}$}_{1}|}$ times the size of an
element in $\mbox{$\cal{T}$}_{|\mbox{$\cal{R}$}_{2}|}^{i}$ for parameter
$r\in[1,N-1]$. Hence, for $i\in[0:N-1]$ and
$\mbox{$\cal{R}$}\subset[0:NK-1],t\leq|\mbox{$\cal{R}$}|\leq NK-1$, we have

$len(W_{i,\mbox{$\cal{R}$}})=\frac{r^{NK-|\mbox{$\cal{R}$}|-1}}{\sum_{s=t}^{NK-1}{NK\choose
s}r^{NK-s-1}}F.$

Sum of all these segments is $F$ since for any $r>0$, we have

$\displaystyle len(W_{i})$
$\displaystyle=\sum_{|\mbox{$\cal{R}$}|=t}^{NK-1}\frac{{NK\choose|\mbox{$\cal{R}$}|}r^{NK-|\mbox{$\cal{R}$}|-1}}{\sum_{s=t}^{NK-1}{NK\choose
s}r^{NK-s-1}}F$
$\displaystyle=\frac{\sum_{|\mbox{$\cal{R}$}|=t}^{NK-1}{NK\choose|\mbox{$\cal{R}$}|}r^{NK-|\mbox{$\cal{R}$}|-1}}{\sum_{s=t}^{NK-1}{NK\choose
s}r^{NK-s-1}}F$ $\displaystyle=F.$

Caching: The cache content $Z_{k}$ of user $k\in[0:K-1]$ has two components:
the main load $Z^{\prime}_{k}$ and sub load $Z^{\prime\prime}_{k}$. The main
load $Z^{\prime}_{k}$ is grouped into $NK-t$ groups similar to the way we
partition the file. The groups are indexed by the cardinality of
$\mbox{$\cal{R}$}\subset[0:NK-1]$, where $t\leq|\mbox{$\cal{R}$}|\leq NK-1$.
The group indexed by $|\mbox{$\cal{R}$}|$ of user $k$ is denoted by
$\mbox{$\cal{G}$}_{k,|\mbox{$\cal{R}$}|}$. Its content is determined by random
variable $S_{k}\sim unif[0:N-1]$ which is shared between user $k$ and the
server, and it is given by

$\displaystyle\mbox{$\cal{G}$}_{k,|\mbox{$\cal{R}$}|}=\\{W_{i,\mbox{$\cal{R}$}}|W_{i,\mbox{$\cal{R}$}}\in\mbox{$\cal{T}$}_{|\mbox{$\cal{R}$}|}^{i}\text{
and }S_{k}+kN\in\mbox{$\cal{R}$}\\}_{i\in[0:N-1]}.$

Then the main load $Z^{\prime}_{k}$ is given by

$\displaystyle
Z^{\prime}_{k}:=(\mbox{$\cal{G}$}_{k,|\mbox{$\cal{R}$}|})_{t\leq|\mbox{$\cal{R}$}|\leq
NK-1}.$

Since there are $N{NK-1\choose|\mbox{$\cal{R}$}|-1}$ elements in
$\mbox{$\cal{G}$}_{k,|\mbox{$\cal{R}$}|}$, we obtain the size of the main load
as

$\displaystyle len(Z^{\prime}_{k})$
$\displaystyle=\sum_{|\mbox{$\cal{R}$}|=t}^{NK-1}|\mbox{$\cal{G}$}_{k,|\mbox{$\cal{R}$}|}|\frac{r^{NK-|\mbox{$\cal{R}$}|-1}F}{\sum_{s=t}^{NK-1}{NK\choose
s}r^{NK-s-1}}$ $\displaystyle=\frac{N\sum_{s=t}^{NK-1}{NK-1\choose
s-1}r^{NK-s-1}F}{\sum_{s=t}^{NK-1}{NK\choose s}r^{NK-s-1}}$
$\displaystyle=MF.$

Now we define the sub load $Z^{\prime\prime}_{k}$ which is of negligible size
compared to the file size $F$. To this end, we first define

$\mbox{$\cal{L}$}:=\\{kN+S_{k}|0\leq k\leq K-1\\},$

and

$\tau:=\\{\mbox{$\cal{R}$}|\mbox{$\cal{R}$}\subset[0:NK-1],\mbox{$\cal{R}$}\cap\mbox{$\cal{L}$}\neq\phi,\text{
and }t+1\leq|\mbox{$\cal{R}$}|\leq NK-1\\}.$

The server generates independent symbols $S^{\prime}_{\mbox{$\cal{R}$}}$ for
all $\mbox{$\cal{R}$}\in\tau$, where each $S^{\prime}_{\mbox{$\cal{R}$}}\sim
unif\\{[0:\kappa_{|\mbox{$\cal{R}$}|}-1]\\}$, with $\kappa_{s}$ defined as

$\displaystyle\kappa_{s}={NK\choose s}-{NK-K\choose s},\quad\mbox{ for
}s\in\\{t+1,t+2,\ldots,NK-1\\}.$

For all $\mbox{$\cal{R}$}\in\tau$, $S^{\prime}_{\mbox{$\cal{R}$}}$ is cached
at user $k$ if and only if $k\in\mbox{$\cal{R}$}$. Then, the sub load
$Z^{\prime\prime}_{k}$ is given by

$\displaystyle
Z^{\prime\prime}_{k}:=\left(\\{S^{\prime}_{\mbox{$\cal{R}$}}|\mbox{$\cal{R}$}\in\tau\text{
and }(kN+S_{k})\cap\mbox{$\cal{R}$}\neq\phi\\},S_{k}\right).$ (29)

The cache content $Z_{k}$ is the concatenation of $Z^{\prime}_{k}$ and
$Z^{\prime\prime}_{k}$, i.e., $Z_{k}=(Z^{\prime}_{k},Z^{\prime\prime}_{k})$.

Delivery: For a given demand vector $(D_{0},\ldots,D_{K-1})$, the server first
constructs an expanded demand vector $\bar{d}$ of $NK$-length. We write it as
$K$ vectors of $N$ length each, as follows:

$\displaystyle\bar{d}=\left[\bar{d}^{(0)},\bar{d}^{(1)},\ldots,\bar{d}^{(K-1)}\right]$
(30)

where $\bar{d}^{(k)},k\in[0:K-1]$ is the vector obtained by applying
$S_{k}\ominus D_{k}$ cyclic shift to the vector $(0,1,\ldots,N-1)$. Here
$\ominus$ denotes modulo $N$ subtraction. That is, for $k\in[0:K-1]$,
$d_{i}^{(k)}=i-(S_{k}-D_{k})\mod N$. We also define

$\displaystyle\bar{S}\ominus\bar{D}:=\left(S_{0}\ominus D_{0},S_{1}\ominus
D_{1},\ldots,S_{K-1}\ominus D_{K-1}\right).$ (31)

To explain the broadcast transmission, we define symbols
$Y_{\mbox{$\cal{R}$}}$ for $\mbox{$\cal{R}$}\subset[0:NK-1]$ and
$t+1\leq|\mbox{$\cal{R}$}|\leq NK$ as follows:

$\displaystyle
Y_{\mbox{$\cal{R}$}}:=\bigoplus_{u\in\mbox{$\cal{R}$}}W_{d_{u},\mbox{$\cal{R}$}\setminus\\{u\\}}$

where $d_{u}$ is the $(u+1)$-th item of $\bar{d}$, and for all
$\mbox{$\cal{R}$}\in\tau$, we define symbols $W_{\mbox{$\cal{R}$}}$

$W_{\mbox{$\cal{R}$}}:=(W_{0,\mbox{$\cal{R}$}}\oplus
W_{1,\mbox{$\cal{R}$}},W_{1,\mbox{$\cal{R}$}}\oplus
W_{2,\mbox{$\cal{R}$}},\ldots,W_{N-2,\mbox{$\cal{R}$}}\oplus
W_{N-1,\mbox{$\cal{R}$}}).$ (32)

If the size of $W_{\mbox{$\cal{R}$}}$ is $F^{\prime}$ bits, we denote the
first $rF^{\prime}/(N-1)$ bits of $W_{\mbox{$\cal{R}$}}$ by
$W^{r}_{\mbox{$\cal{R}$}}$, where $r\in[1,N-1]$. Further, we also define

$\displaystyle V_{\mbox{$\cal{R}$}}$
$\displaystyle:=Y_{\mbox{$\cal{R}$}}\oplus
W^{r}_{\mbox{$\cal{R}$}},\quad\text{ for
}r\in[1,N-1],\enspace\mbox{$\cal{R}$}\in\tau,$ (33)

and

$\displaystyle V_{|\mbox{$\cal{R}$}|}$
$\displaystyle:=\\{V_{\mbox{$\cal{R}$}}|\mbox{$\cal{R}$}\in\tau\\}.$ (34)

Also, set $V$ is defined as the concatenation of all sets defined in (34),
i.e.,

$\displaystyle V$ $\displaystyle:=(V_{s})_{t+1\leq s\leq NK-1}.$

The server picks permutation functions
$\left(\pi_{t+1}(\cdot),\pi_{t+2}(\cdot),\ldots,\pi_{NK-1}(\cdot)\right)$,
where $\pi_{i}(\cdot)$ is picked uniformly at random from the symmetric group
of permutations of $[0:\kappa_{i}-1]$ for $i\in\\{t+1,t+2,\ldots,NK-1\\}$.
These permutation functions are not fully shared with any of the users. The
main payload is given by

$X^{\prime}=(X^{\prime}_{t+1},X^{\prime}_{t+2},\ldots,X^{\prime}_{NK-1},Y_{[0:NK-1]})=(\pi_{t+1}(V_{t+1}),\pi_{t+2}(V_{t+2}),\ldots,\pi_{NK-1}(V_{NK-1}),Y_{[0:NK-1]}).$

Rate of transmission is calculated as follows. For
$t+1\leq|\mbox{$\cal{R}$}|\leq NK-1$, the server transmits
${NK\choose|\mbox{$\cal{R}$}|}-{NK-K\choose|\mbox{$\cal{R}$}|}$ number of
symbols $V_{\mbox{$\cal{R}$}}$, and the server also transmits $Y_{[0:NK-1]}$.
Then, the total number of bits transmitted in the main payload are given by

$\displaystyle len(X^{\prime})$
$\displaystyle=\sum_{s=t+1}^{NK}\frac{[{NK\choose s}-{NK-K\choose
s}]r^{NK-s}F}{\sum_{s=t}^{NK-1}{NK\choose s}r^{NK-s-1}}$ $\displaystyle=RF.$

Along with $X^{\prime}$, the server also broadcasts some auxiliary
transmission $J$ of negligible rate, given by

$\displaystyle J$
$\displaystyle=(\\{S^{\prime}_{\mbox{$\cal{R}$}}\oplus\alpha_{|\mbox{$\cal{R}$}|,\mbox{$\cal{R}$}}|\mbox{$\cal{R}$}\in\tau\\},\bar{S}\ominus\bar{D})$
$\displaystyle=(J^{\prime},\bar{S}\ominus\bar{D}).$ (35)

Here, $\alpha_{|\mbox{$\cal{R}$}|,\mbox{$\cal{R}$}}$ denotes the position of
$V_{\mbox{$\cal{R}$}}$ in $\pi_{|\mbox{$\cal{R}$}|}(V_{|\mbox{$\cal{R}$}|})$
for $\mbox{$\cal{R}$}\in\tau$. The private keys ensure that the location of
any symbol $V_{\mbox{$\cal{R}$}}$ is shared with user $k$ if and only if
$S_{k}+kN\in\mbox{$\cal{R}$}$. For large file sizes, the size of the auxiliary
transmission is negligible. The broadcasted message, $X$ can thus be given as
$X=(X^{\prime},J)$.

Decoding: Now we explain how user $k\in[0:K-1]$ decodes the segments that are
missing from each group in her cache. We can observe that the group
$\mbox{$\cal{G}$}_{k,NK-1}$ in the cache of user $k$ has all the elements of
$\mbox{$\cal{T}$}_{NK-1}^{D_{k}}$ except one. This missing element
$W_{D_{k},[0:NK-1]\setminus\\{S_{k}+kN\\}}$ can be decoded as

$\displaystyle\widehat{W}_{D_{k},[0:NK-1]\setminus\\{S_{k}+kN\\}}=Y_{[0:NK-1]}\oplus\left(\bigoplus_{u\in{[0:NK-1]\setminus\\{S_{k}+kN\\}}}W_{d_{u},{[0:NK-1]}\setminus\\{u\\}}\right).$

Observe that $Y_{[0:NK-1]}$ is broadcasted by the server while each symbol
$W_{d_{u},[0:NK-1]\setminus\\{u\\}}$ is a part of $\mbox{$\cal{G}$}_{k,NK-1}$
and hence a part of the cache of user $k$. Thus, user $k$ can compute
$\widehat{W}_{D_{k},[0:NK-1]\setminus\\{S_{k}+3k\\}}$. It follows that

$\displaystyle\widehat{W}_{D_{k},[0:NK-1]\setminus\\{S_{k}+kN\\}}$
$\displaystyle=Y_{[0:NK-1]}\oplus\left(\bigoplus_{u\in{[0:NK-1]\setminus\\{S_{k}+kN\\}}}W_{d_{u},{[0:NK-1]}\setminus\\{u\\}}\right)$
$\displaystyle=\bigoplus_{u\in[0:NK-1]}W_{d_{u},[0:NK-1]\setminus\\{u\\}}\oplus\left(\bigoplus_{u\in{[0:NK-1]\setminus\\{S_{k}+kN\\}}}W_{d_{u},{[0:NK-1]}\setminus\\{u\\}}\right)$
$\displaystyle=W_{d_{S_{k}+kN},[0:NK-1]\setminus\\{S_{k}+kN\\}}$
$\displaystyle\overset{(a)}{=}W_{D_{k},[0:NK-1]\setminus\\{S_{k}+kN\\}}.$

Here $(a)$ follows because $d_{S_{k}+kN}=(S_{k}+kN-(S_{k}-D_{k}))$ mod $N$
$=D_{k}$. Since user $k$ has all the segments in
$\mbox{$\cal{T}$}^{D_{k}}_{NK-1}$, we explain how user $k$ can obtain all
symbols in any set $\mbox{$\cal{T}$}^{D_{k}}_{j}$, where $t\leq j\leq NK-2$.
All symbols $W_{D_{k},\mbox{$\cal{R}$}}\in\mbox{$\cal{T}$}^{D_{k}}_{j}$ such
that $S_{k}+kN\in\mbox{$\cal{R}$}$ form the group $\mbox{$\cal{G}$}_{k,j}$ and
hence are a part of her cache. All the remaining symbols
$W_{D_{k},\mbox{$\cal{R}$}}\in\mbox{$\cal{T}$}^{D_{k}}_{j}$ satisfying
$S_{k}+kN\notin\mbox{$\cal{R}$}$ can be decoded by user $k$ as follows:

$\displaystyle\widehat{W}_{D_{k},{\mbox{$\cal{R}$}}}$
$\displaystyle=X^{\prime}_{{|\mbox{$\cal{R}$}^{+}|},t}\oplus
W^{r}_{\mbox{$\cal{R}$}^{+}}\oplus\left(\bigoplus_{u\in{\mbox{$\cal{R}$}}}W_{d_{u},\mbox{$\cal{R}$}^{+}\setminus\\{u\\}}\right)$

where $\mbox{$\cal{R}$}^{+}=\\{S_{k}+kN\\}\cup{\mbox{$\cal{R}$}}$,
$t=\alpha_{{|\mbox{$\cal{R}$}^{+}|},\mbox{$\cal{R}$}^{+}}$ and
$X^{\prime}_{{|\mbox{$\cal{R}$}^{+}|},t}$ denotes the symbol in the $t$-th
position of $X^{\prime}_{{|\mbox{$\cal{R}$}^{+}|}}$. Here,
$X^{\prime}_{{|\mbox{$\cal{R}$}^{+}|}}$ is a part of the broadcast. User $k$
can recover $t$ using the auxiliary transmission as
$t=S^{\prime}_{\mbox{$\cal{R}$}^{+}}\oplus(S^{\prime}_{\mbox{$\cal{R}$}^{+}}\oplus\alpha_{|\mbox{$\cal{R}$}^{+}|,\mbox{$\cal{R}$}^{+}})$
because $S^{\prime}_{\mbox{$\cal{R}$}^{+}}$ is part of her cache. All symbols
in the second and third terms can also be recovered from the cache of user
$k$. Thus, user $k$ can compute $\widehat{W}_{D_{k},{\mbox{$\cal{R}$}}}$.
Thus, we obtain

$\displaystyle\widehat{W}_{D_{k},{\mbox{$\cal{R}$}}}$
$\displaystyle=X^{\prime}_{{|\mbox{$\cal{R}$}^{+}|},t}\oplus
W^{r}_{\mbox{$\cal{R}$}^{+}}\oplus\left(\bigoplus_{u\in{\mbox{$\cal{R}$}}}W_{d_{u},\mbox{$\cal{R}$}^{+}\setminus\\{u\\}}\right)$
$\displaystyle=V_{\\{S_{k}+kN\\}\cup\mbox{$\cal{R}$}}\oplus
W^{r}_{\\{S_{k}+kN\\}\cup\mbox{$\cal{R}$}}\oplus\left(\bigoplus_{u\in{\mbox{$\cal{R}$}}}W_{d_{u},\\{S_{k}+kN\\}\cup{\mbox{$\cal{R}$}}\setminus\\{u\\}}\right)$
$\displaystyle=Y_{\\{S_{k}+kN\\}\cup\mbox{$\cal{R}$}}\oplus
W^{r}_{\\{S_{k}+kN\\}\cup\mbox{$\cal{R}$}}\oplus
W^{r}_{\\{S_{k}+kN\\}\cup\mbox{$\cal{R}$}}\oplus\left(\bigoplus_{u\in{\mbox{$\cal{R}$}}}W_{d_{u},\\{S_{k}+kN\\}\cup{\mbox{$\cal{R}$}}\setminus\\{u\\}}\right)$
$\displaystyle=\bigoplus_{u\in\\{S_{k}+kN\\}\cup{\mbox{$\cal{R}$}}}W_{d_{u},\\{S_{k}+kN\\}\cup{\mbox{$\cal{R}$}}\setminus\\{u\\}}\oplus\left(\bigoplus_{u\in{\mbox{$\cal{R}$}}}W_{d_{u},\\{S_{k}+kN\\}\cup{\mbox{$\cal{R}$}}\setminus\\{u\\}}\right)$
$\displaystyle=W_{D_{k},\mbox{$\cal{R}$}}$

which shows that user $k$ can recover all symbols in
$\mbox{$\cal{T}$}^{D_{k}}_{j}$ for $t\leq j\leq NK-1$. This completes the
proof for decodability.

Proof of privacy: We show that

$\displaystyle I(X;{\bar{D}_{\tilde{k}}}|Z_{k},D_{k})=0,\quad\forall
k\in[0:K-1]$ (36)

which implies the privacy condition
$I({\bar{D}_{\tilde{k}}};X,Z_{k},D_{k})=0$, since
$I({\bar{D}_{\tilde{k}}};Z_{k},D_{k})=0$. To show (36), we first define

$\displaystyle
B_{k}:=\\{\alpha_{|\mbox{$\cal{R}$}|,\mbox{$\cal{R}$}}|\mbox{$\cal{R}$}\subset[0:NK-1],kN+S_{k}\cap\mbox{$\cal{R}$}\neq\phi,t+1\leq|\mbox{$\cal{R}$}|\leq
NK-1\\}.$ (37)

We also divide $J^{\prime}$ given in (35) into two parts,
$J^{\prime}=(J^{\prime}_{k},\tilde{J^{\prime}}_{k})$, where $J^{\prime}_{k}$
is the part $J$ which can be accessed by user $k$ while
$\tilde{J^{\prime}}_{k}$ is the remaining part. These are defined as follows:

$\displaystyle J^{\prime}_{k}$
$\displaystyle:=\\{S^{\prime}_{\mbox{$\cal{R}$}}\oplus\alpha_{|\mbox{$\cal{R}$}|,\mbox{$\cal{R}$}}|\mbox{$\cal{R}$}\in\tau,kN+S_{k}\in\mbox{$\cal{R}$}\\},$
$\displaystyle\tilde{J^{\prime}}_{k}$ $\displaystyle:=J^{\prime}\setminus
J^{\prime}_{k}.$

Then, we have

$\displaystyle I(X;{\bar{D}_{\tilde{k}}}|Z_{k},D_{k})$
$\displaystyle=I(X^{\prime},J;{\bar{D}_{\tilde{k}}}|Z_{k},D_{k})$
$\displaystyle=I(X^{\prime},J^{\prime}_{k},\tilde{J^{\prime}}_{k},\bar{S}\ominus\bar{D};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k})$
$\displaystyle\overset{(a)}{=}I(X^{\prime},\bar{S}\ominus\bar{D},J^{\prime}_{k},B_{k};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k})$
$\displaystyle\overset{(b)}{=}I(X^{\prime},\bar{S}\ominus\bar{D},B_{k};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k})$
$\displaystyle=I(\bar{S}\ominus\bar{D},B_{k};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k})+I(X^{\prime};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},\bar{S}\ominus\bar{D},B_{k})$
$\displaystyle\overset{(c)}{=}I(X^{\prime};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},\bar{S}\ominus\bar{D},B_{k})$
$\displaystyle=I(Y_{[0:NK-1]},\pi_{t+1}(V_{t+1}),\pi_{t+2}(V_{t+2}),\ldots,\pi_{NK-1}(V_{NK-1});{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D})$
$\displaystyle\overset{(d)}{=}I(Y_{[0:NK-1]},V;{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D}).$
(38)

Here, $(a)$ follows since $B_{k}$ is a function of $(Z_{k},J^{\prime}_{k})$
and $\tilde{J^{\prime}}_{k}$ is independent of all other random variables on
the RHS of $(a)$, and $(b)$ follows since $J^{\prime}_{k}$ is a function of
$(Z_{k},B_{k})$. Further, $(c)$ follows since $(\bar{S}\ominus\bar{D},B_{k})$
is independent of other random variables, and $(d)$ follows due to the fact
that the permutations
$\left(\pi_{t+1}(\cdot),\pi_{t+2}(\cdot),\ldots,\pi_{NK-1}(\cdot)\right)$ are
independent of all other random variables. Next we show that the RHS of (38)
is zero. To this end, we first divide the set $V$, defined in (34), into two
parts: the first part $X_{k}$ contains the symbols in $V$ whose positions are
known to user $k$, and the second part $\tilde{X}_{k}$ contains the remaining
symbols in $V$, i.e.,

$\displaystyle X_{k}$
$\displaystyle:=\\{V_{\mbox{$\cal{R}$}}|(kN+S_{k})\cap\mbox{$\cal{R}$}\neq\phi,\mbox{$\cal{R}$}\in\tau\\},$
$\displaystyle\tilde{X}_{k}$ $\displaystyle:=V\setminus X_{k}.$

Set $\tilde{X}_{k}$ can be further divided into more groups labelled by
$\tilde{X}_{k,|\mbox{$\cal{R}$}|}$, where $t+1\leq|\mbox{$\cal{R}$}|\leq
NK-1$, as follows:

$\tilde{X}_{k,|\mbox{$\cal{R}$}|}=\\{V_{\mbox{$\cal{R}$}}|(kN+S_{k})\cap\mbox{$\cal{R}$}=\phi,\mbox{$\cal{R}$}\in\tau\\}.$

Then, we get

$\displaystyle
I(Y_{[0:NK-1]},V;{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D})$
(39)
$\displaystyle=I(Y_{[0:NK-1]},X_{k},\tilde{X}_{k};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D})$
$\displaystyle=I(Y_{[0:NK-1]},X_{k};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D})+I(\tilde{X}_{k};{\bar{D}_{\tilde{k}}}|Y_{[0:NK-1]},X_{k},Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D}).$
$\displaystyle\overset{(a)}{=}I(Y_{[0:NK-1]},X_{k},W_{D_{k}};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D})+I(\tilde{X}_{k};{\bar{D}_{\tilde{k}}}|Y_{[0:NK-1]},X_{k},Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D},W_{D_{k}}).$
$\displaystyle\overset{(b)}{=}I(W_{D_{k}};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D})+I(\tilde{X}_{k};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D},W_{D_{k}}).$
$\displaystyle=I(W_{D_{k}};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D})+\sum_{i=t+1}^{NK-1}I(\tilde{X}_{k,i};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D},W_{D_{k}},\tilde{X}_{k,t+1},\ldots,\tilde{X}_{k,i-1})$
(40)

where in (40), we used $\tilde{X}_{k,i}=\phi$ for $i<t+1$. Here, $(a)$ follows
because we have seen in the decodability section that $W_{D_{k}}$ can be
recoverd from $(\bar{S}\ominus\bar{D},Z_{k},X_{k},Y_{[0:NK-1]})$, and $(b)$
follows since each $V_{\mbox{$\cal{R}$}}\in X_{k}$ can be written as

$\displaystyle V_{\mbox{$\cal{R}$}}$ $\displaystyle=Y_{\mbox{$\cal{R}$}}\oplus
W^{r}_{\mbox{$\cal{R}$}}$
$\displaystyle=\bigoplus_{u\in\mbox{$\cal{R}$}}W_{d_{u},\mbox{$\cal{R}$}\backslash\\{u\\}}\oplus
W^{r}_{\mbox{$\cal{R}$}}$
$\displaystyle=\bigoplus_{u\in\mbox{$\cal{R}$}\backslash(S_{k}+kN)}W_{d_{u},\mbox{$\cal{R}$}\backslash\\{u\\}}\oplus
W_{d_{S_{k}+kN},\mbox{$\cal{R}$}\backslash\\{S_{k}+kN\\}}\oplus
W^{r}_{\mbox{$\cal{R}$}}.$

Here, the first and third terms can be recovered from $Z_{k}$ and the second
term is a part of $W_{D_{k}}$ since $d_{S_{k}+kN}=D_{k}$. Similarly, we have

$\displaystyle Y_{[0:NK-1]}$
$\displaystyle=\bigoplus_{u\in{[0:NK-1]}}W_{d_{u},{[0:NK-1]}\backslash\\{u\\}}$
$\displaystyle=\bigoplus_{u\in{[0:NK-1]\backslash(S_{k}+kN)}}W_{d_{u},{[0:NK-1]}\backslash\\{u\\}}\oplus
W_{d_{S_{k}+kN},[0:NK-1]\backslash\\{S_{k}+kN\\}}.$

Here, all symbols in the first term are a part of $Z_{k}$ while the second
term is a part of $W_{D_{k}}$ because $d_{S_{k}+kN}=D_{k}$. Thus,
$(X_{k},Y_{[0:NK-1]})$ is a function of
$(\bar{S}\ominus\bar{D},Z_{k},W_{D_{k}})$ which completes the argument for
$(b)$.

Next, we show that each term on the RHS of (40) is zero. First, we consider
the terms
$I(\tilde{X}_{k,i};Z_{k},B_{k},\bar{S}\ominus\bar{D},{\bar{D}_{\tilde{k}}},W_{D_{k}}|Y_{[0:NK-1]},X_{k},\tilde{X}_{k,i-1},\ldots,\tilde{X}_{k,t+1})$
for $t+1\leq i\leq NK-1$. For simplicity of notation, we define set
$\tau_{k,i}$ as follows:

$\tau_{k,i}=\\{\mbox{$\cal{R}$}\in\tau,\mbox{$\cal{R}$}\cap(kN+S_{k})=\phi,|\mbox{$\cal{R}$}|=i\\}.$

For $k\in[0:K-1]$ and $t+1\leq i\leq NK-1$, we get

$\displaystyle
I(\tilde{X}_{k,i};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D},W_{D_{k}},\tilde{X}_{k,t+1},\ldots\tilde{X}_{k,i-1})$
$\displaystyle=I((V_{\mbox{$\cal{R}$}})_{\mbox{$\cal{R}$}\in\tau_{k,i}};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D},W_{D_{k}},\tilde{X}_{k,t+1},\ldots\tilde{X}_{k,i-1})$
$\displaystyle=I((Y_{\mbox{$\cal{R}$}}\oplus
W_{\mbox{$\cal{R}$}})_{\mbox{$\cal{R}$}\in\tau_{k,i}};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D},W_{D_{k}},\tilde{X}_{k,t+1},\ldots\tilde{X}_{k,i-1})$
$\displaystyle=I((Y_{\mbox{$\cal{R}$}}\oplus(W_{0,\mbox{$\cal{R}$}}\oplus
W_{1,\mbox{$\cal{R}$}},...,W_{N-2,\mbox{$\cal{R}$}}\oplus
W_{N-1,\mbox{$\cal{R}$}}))_{\mbox{$\cal{R}$}\in\tau_{k,i}};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D},W_{D_{k}},\tilde{X}_{k,t+1},\ldots\tilde{X}_{k,i-1})$
$\displaystyle=0.$ (41)

Here, (41) follows because each symbol $(W_{i,\mbox{$\cal{R}$}})$,
$i\in[0:N-1]$ is non-overlapping with
$(\tilde{X}_{k,t+1},\ldots,\tilde{X}_{k,i-1},Y_{k,i})$ and because $W_{D_{k}}$
contains only one symbol in $W_{\mbox{$\cal{R}$}}$, namely
$W_{D_{k},\mbox{$\cal{R}$}}$. We can also see that the first term on the RHS
of (40) is zero, i.e.,

$\displaystyle
I(W_{D_{k}};{\bar{D}_{\tilde{k}}}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D})=0.$
(42)

because $W_{D_{k}}$ is independent of ${\bar{D}_{\tilde{k}}}$. Thus, from (42)
and (41), we obtain

$\displaystyle
I(Y_{[0:NK-1]},V;\bar{D}|Z_{k},D_{k},B_{k},\bar{S}\ominus\bar{D})=0.$

This together with (38) implies (36).

###  IV-E Proof of Theorem 5

To prove the theorem, we first give some notations and inequalities. For
parameter $r_{2}=\frac{KM}{N}$, let

$\displaystyle R^{\text{YMA}}_{N,K}\left(\frac{Nr_{2}}{K}\right)$
$\displaystyle=\frac{{K\choose r_{2}+1}-{K-\min(N,K)\choose
r_{2}+1}}{{K\choose r_{2}}},\quad\mbox{ for }r_{2}\in\\{0,1,\ldots,K\\},$ (43)
$\displaystyle R^{\text{MAN}}_{N,K}\left(M\right)$
$\displaystyle=K\left(1-\frac{M}{N}\right)\min\left(\frac{1}{1+\frac{KM}{N}},\frac{N}{K}\right),\quad\mbox{
for }M\in\\{0,N/K,2N/K,\ldots,N\\}.$ (44)

Furthermore, let $R^{\text{YMA, c}}_{N,K}(M)$ and $R^{\text{MAN, c}}_{N,K}(M)$
denote the lower convex envelop of the points in (43) and (44), respectively.
Recall that $R^{*p}_{N,K}(M)$ and $R^{*}_{N,K}(M)$ denote the optimal rate
with privacy and without privacy as defined in (10) and (5), respectively.
Then we have the following inequalities which hold for all $M\geq 0$:

$\displaystyle
R^{*}_{N,K}(M)\stackrel{{\scriptstyle(a)}}{{\leq}}R^{*p}_{N,K}(M)\stackrel{{\scriptstyle(b)}}{{\leq}}R^{A}_{N,K}(M)=R^{\text{YMA,
c}}_{N,NK-K+1}(M)\leq R^{\text{YMA,
c}}_{N,NK}(M)\stackrel{{\scriptstyle(c)}}{{\leq}}R^{\text{MAN, c}}_{N,NK}(M)$
(45)

where $(a)$ follows from the fact that the optimal rate required with demand
privacy is larger than that of without privacy, $(b)$ follows since an
achievable rate is lower-bounded by the optimal rate, and $(c)$ was shown in
[5].

####  IV-E1 Proof of Part 1), ($N\leq K$)

We first prove that

$\displaystyle\frac{R^{A}_{N,K}(M)}{R^{*}_{N,K}(M)}\leq\begin{cases}4&\text{
if }M\leq\left(1-\frac{N}{K}\right)\\\ 8&\text{
if}\left(1-\frac{N}{K}\right)\leq M\leq\frac{N}{2}.\end{cases}$ (46)

To this end, we show that

$\displaystyle\frac{R^{\text{MAN,
c}}_{N,NK}(M)}{R^{*}_{N,K}(M)}\leq\begin{cases}4&\text{ if
}M\leq\left(1-\frac{N}{K}\right)\\\ 8&\text{ if}\left(1-\frac{N}{K}\right)\leq
M\leq\frac{N}{2}.\end{cases}$ (47)

Then the result follows from (45). We first consider the ratio
$\frac{R^{\text{MAN}}_{N,NK}(M)}{R^{\text{MAN}}_{N,K}(M)}$ for
$M\in\\{0,N/K,2N/K,\ldots,N\\}$. We have

$\displaystyle\frac{R^{\text{MAN}}_{N,NK}(M)}{R^{\text{MAN}}_{N,K}(M)}=\frac{N\min\left(\frac{1}{1+KM},\frac{1}{K}\right)}{\min\left(\frac{1}{1+\frac{KM}{N}},\frac{N}{K}\right)},\quad
M\in\\{0,N/K,2N/K,\ldots,N\\}.$ (48)

We consider the following three cases.

Case 1: $M\in[0,1-\frac{N}{K}]$

We first find $\min\left(\frac{1}{1+KM},\frac{1}{K}\right)$ and
$\min\left(\frac{1}{1+\frac{KM}{N}},\frac{1}{K}\right)$.

$\displaystyle\frac{1}{1+KM}$ $\displaystyle\geq\frac{1}{1+K(1-N/K)}$
$\displaystyle=\frac{1}{K-N+1}$ $\displaystyle>\frac{1}{K},\quad\mbox{ for
}N>1.$

So, $\min\left(\frac{1}{1+KM},\frac{1}{K}\right)=\frac{1}{K}$. Further,

$\displaystyle\frac{1}{1+\frac{KM}{N}}$
$\displaystyle\geq\frac{1}{1+\frac{K}{N}(1-N/K)}$ $\displaystyle=\frac{N}{K}.$

Thus, $\min\left(\frac{1}{1+\frac{KM}{N}},\frac{N}{K}\right)=\frac{N}{K}$.
Hence (48) gives 1.

Case 2: $M\in[1-\frac{N}{K},1-\frac{1}{K}]$

In this case, we get

$\displaystyle\min\left(\frac{1}{1+KM},\frac{1}{K}\right)=\frac{1}{K},$

and

$\displaystyle\min\left(\frac{1}{1+\frac{KM}{N}},\frac{N}{K}\right)=\frac{1}{1+\frac{KM}{N}}.$

Then from (48), it follows that

$\displaystyle\frac{R^{\text{MAN}}_{N,K}(M)}{R^{\text{MAN}}_{N,K}\left(M\right)}$
$\displaystyle=\frac{N}{K}\left(1+\frac{KM}{N}\right)$
$\displaystyle=\frac{N}{K}+M$ $\displaystyle\leq 2$

where the last inequality follows since $\frac{N}{K}\leq 1$ and $M\leq 1$.

Case 3: $M\in[1-\frac{1}{K},N]$

In this case, we obtain

$\displaystyle\min\left(\frac{1}{1+KM},\frac{1}{K}\right)=\frac{1}{1+KM},\quad\mbox{
if }1-\frac{1}{K}\leq M\leq N$

and

$\displaystyle\min\left(\frac{1}{1+\frac{KM}{N}},\frac{N}{K}\right)=\frac{1}{1+\frac{KM}{N}},\quad\mbox{
if }1-\frac{1}{K}\leq M\leq N.$

Then from (48), we get the following

$\displaystyle\frac{R^{\text{MAN}}_{N,NK}(M)}{R^{\text{MAN}}_{N,K}(M)}$
$\displaystyle=\frac{N}{1+KM}\left(1+\frac{KM}{N}\right)$
$\displaystyle=\frac{N+KM}{1+KM}$ $\displaystyle=\frac{N-1}{1+KM}+1.$ (49)

Further,

$\displaystyle M\geq 1-\frac{1}{K}$ $\displaystyle\implies KM\geq K-1,$
$\displaystyle\implies KM\geq N-1\;(\text{Since $K\geq N$}),$
$\displaystyle\implies KM+1\geq N-1,$
$\displaystyle\implies\frac{N-1}{1+KM}\leq 1.$

Then, we obtain $\frac{R^{\text{MAN}}_{N,NK}(M)}{R^{\text{MAN}}_{N,K}(M)}\leq
2$ from (49).

Let $R^{\text{MAN, lin}}_{N,K}(M)$ denote the region obtained by linearly
interpolating the adjacent memory points given in (44). Similarly,
$R^{\text{MAN, lin}}_{N,NK}(M)$ denotes the linear interpolation of the points
$R^{\text{MAN}}_{N,NK}(M),M\in\\{0,N/K,2N/K,\ldots,N\\}$. Then, it follows
from the above three cases that

$\displaystyle\frac{R^{\text{MAN,
lin}}_{N,NK}(M)}{R^{\text{MAN,lin}}_{N,K}(M)}\leq\begin{cases}1&\text{ if
}M\leq\left(1-\frac{N}{K}\right)\\\ 2&\text{ if}\left(1-\frac{N}{K}\right)\leq
M\leq\frac{N}{2}.\end{cases}$ (50)

Next we need the following lemma.

###### Lemma 3

For $N\leq K$, the following holds:

$\displaystyle\frac{R^{\text{MAN, lin}}_{N,K}(M)}{R^{*}_{N,K}(M)}\leq
4,\quad\mbox{for }0\leq M\leq\frac{N}{2}.$ (51)

###### Proof.

See Appendix B. ∎

Since $R^{\text{MAN, c}}_{N,NK}(M)\leq R^{\text{MAN, lin}}_{N,NK}(M)$, (47)
follows from (50) and (51). This further implies (46).

Now it remains to prove

$\displaystyle\frac{R^{A}_{N,K}(M)}{R^{*}_{N,K}(M)}$ $\displaystyle\leq
2,\quad\text{ if }M\geq\frac{N}{2}.$

By substituting $r_{2}=\lfloor{NK/2}\rfloor$ in (43) for $N$ files and $NK$
users, we get

$\displaystyle
R^{\text{YMA}}_{N,NK}\left(\frac{\lfloor{NK/2}\rfloor}{K}\right)$
$\displaystyle\leq\frac{{NK\choose\lfloor{NK/2}\rfloor+1}}{{NK\choose\lfloor{NK/2}\rfloor}}$
$\displaystyle=\frac{NK-\lfloor{NK/2}\rfloor}{\lfloor{NK/2}\rfloor+1}$
$\displaystyle=\frac{NK+1}{\lfloor{NK/2}\rfloor+1}-1$
$\displaystyle\leq\frac{NK+1}{NK/2-1/2+1}-1$ $\displaystyle=1.$

Since $\frac{\lfloor{NK/2}\rfloor}{K}\leq\frac{N}{2}$, we have $R^{\text{YMA,
c}}_{N,NK}(N/2)\leq 1$. Also, $R^{\text{YMA, c}}_{N,NK}(N)=0$. Thus, for
$N/2\leq M\leq N$, it follows that

$R^{\text{YMA, c}}_{N,NK}(M)\leq 2\left(1-\frac{M}{N}\right).$ (52)

The cutset bounds on the rates without privacy gives that

$R^{*}_{N,K}(M)\geq\left(1-\frac{M}{N}\right).$ (53)

From (52) by (53), we obtain

$\displaystyle\frac{R^{\text{YMA, c}}_{N,NK}(M)}{R^{*}_{N,K}(M)}\leq
2,\quad\text{ for }M\geq\frac{N}{2}.$

From (45), we have $R^{A}_{N,K}(M)\leq R^{\text{YMA, c}}_{N,NK}(M)$ which then
implies that

$\displaystyle\frac{R^{A}_{N,K}(M)}{R^{*}_{N,K}(M)}\leq 2,\quad\text{ for
}M\geq\frac{N}{2}.$

This completes the proof of Part 1).

####  IV-E2 Proof of Part 2), $K<N$

We denote the memory corresponding to parameters $r=r_{0}$ and $t=t_{0}$ in
(15) by $M_{r_{0},t_{0}}$. First we consider the memory regime $M\leq N/2$.
Substituting $t=1$ in (15), we get the achievability of the following memory-
rate pairs

$\displaystyle(M_{r,1},R)$
$\displaystyle=\left(\frac{N\sum_{s=1}^{NK-1}{NK-1\choose
s-1}r^{NK-s-1}}{\sum_{s=1}^{NK-1}{NK\choose
s}r^{NK-s-1}},\frac{\sum_{s=2}^{NK}[{NK\choose s}-{NK-K\choose
s}]r^{NK-s}}{\sum_{s=1}^{NK-1}{NK\choose s}r^{NK-s-1}}\right)$
$\displaystyle=\left(\frac{N\sum_{s=1}^{NK-1}{NK-1\choose
s-1}r^{NK-s}}{\sum_{s=1}^{NK-1}{NK\choose
s}r^{NK-s}},\frac{\sum_{s=2}^{NK}{NK\choose
s}r^{NK-s+1}-\sum_{s=2}^{NK}{NK-K\choose
s}r^{NK-s+1}}{\sum_{s=1}^{NK-1}{NK\choose s}r^{NK-s}}\right)$
$\displaystyle=\left(\frac{N\sum_{s=0}^{NK-2}{NK-1\choose
s}r^{NK-s-1}}{\sum_{s=1}^{NK-1}{NK\choose
s}r^{NK-s}},\frac{\sum_{s=2}^{NK}{NK\choose
s}r^{NK-s+1}-\sum_{s=2}^{NK}{NK-K\choose
s}r^{NK-s+1}}{\sum_{s=1}^{NK-1}{NK\choose s}r^{NK-s}}\right)$
$\displaystyle=\left(\frac{N(\sum_{s=0}^{NK-1}{NK-1\choose
s}r^{NK-s-1}-1)}{\sum_{s=0}^{NK}{NK\choose
s}r^{NK-s}-r^{NK}-1},\frac{\sum_{s=0}^{NK}{NK\choose
s}r^{NK-s+1}-\sum_{s=0}^{NK}{NK-K\choose
s}r^{NK-s+1}-Kr^{NK}}{\sum_{s=1}^{NK-1}{NK\choose s}r^{NK-s}}\right)$
$\displaystyle=\left(\frac{N((r+1)^{NK-1}-1)}{(r+1)^{NK}-r^{NK}-1},\frac{r((r+1)^{NK}-Kr^{NK-1}-(r+1)^{NK-K}r^{K})}{((r+1)^{NK}-r^{NK}-1)}\right).$
(54)

We first show that $M_{r,1}$ in (54) satisfies the following

$\displaystyle M_{r,1}$
$\displaystyle=\frac{N((r+1)^{NK-1}-1)}{(r+1)^{NK}-r^{NK}-1}$
$\displaystyle=\frac{N}{r+1}\left(1-\frac{r-r^{NK}}{(r+1)^{NK}-r^{NK}-1}\right)$
$\displaystyle\geq\frac{N}{r+1}$ (55)

where the last inequality follows since
$\left(1-\frac{r-r^{NK}}{(r+1)^{NK}-r^{NK}-1}\right)\geq 1$. Using the fact
that all points on the line joining $(0,K)$ and $(M_{r,1},R)$ are also
achievable, for $M\leq M_{r,1}$ we get

$\displaystyle R^{BC}_{N,K}(M)$
$\displaystyle\leq\left(\frac{R-K}{M_{r,1}}\right)M+K$ (56)
$\displaystyle=\left(\frac{(r+1)^{NK}r-(r+1)^{NK-K}r^{K+1}-K(r+1)^{NK}+K}{N((r+1)^{NK-1}-1)}\right)M+K.$
(57)

Now we substitute $r=K/s-1$ for some integer $s$ in the interval
$[1,\lfloor{K/2}\rfloor]$. Note that, $Ns/K=N/(r+1)\leq M_{r,1}$, where the
inequality follows from (55). Thus, (57) holds for $M=Ns/K$ and we obtain

$\displaystyle R^{BC}_{N,K}(Ns/K)$
$\displaystyle\leq\left(\frac{(\frac{K}{s})^{NK}\left(\frac{K}{s}-1\right)-(\frac{K}{s})^{NK-K}\left(\frac{K}{s}-1\right)^{K+1}-K(\frac{K}{s})^{NK}+K}{N((\frac{K}{s})^{NK-1}-1)}\right)\frac{Ns}{K}+K$
$\displaystyle=\left(\frac{K^{NK}(K-s)-K^{NK-K}(K-s)^{K+1}-sK^{NK+1}+Ks^{NK+1}}{N(K^{NK-1}s-s^{NK})}\right)\frac{N}{K}+K$
$\displaystyle=\left(\frac{K^{NK-1}(K-s)-K^{NK-K-1}(K-s)^{K+1}-sK^{NK}+s^{NK+1}}{(K^{NK-1}s-s^{NK})}\right)+K$
$\displaystyle=\left(\frac{K^{NK-1}(K-s)-K^{NK-K-1}(K-s)^{K+1}-Ks^{NK}+s^{NK+1}}{(K^{NK-1}s-s^{NK})}\right).$
(58)

Note that $R^{\text{YMA}}_{N,K}(Ns/K)=(K-s)/(s+1)$. Dividing (58) by
$R^{\text{YMA}}_{N,K}(Ns/K)$ yields

$\displaystyle\frac{R^{BC}_{N,K}(Ns/K)}{R^{\text{YMA}}_{N,K}(Ns/K)}$
$\displaystyle=(s+1)\left(\frac{K^{NK-1}(K-s)-K^{NK-K-1}(K-s)^{K+1}-Ks^{NK}+s^{NK+1}}{(K^{NK-1}s-s^{NK})(K-s)}\right)$
$\displaystyle=(s+1)\left(\frac{K^{NK-1}-K^{NK-K-1}(K-s)^{K}-s^{NK}}{(K^{NK-1}s-s^{NK})}\right)$
$\displaystyle\leq\frac{(s+1)}{s}\left(\frac{K^{NK-1}-K^{NK-K-1}(K-s)^{K}-s^{NK-1}}{(K^{NK-1}-s^{NK-1})}\right)$
$\displaystyle=\frac{(s+1)}{s}\left(1-\frac{K^{NK-K-1}(K-s)^{K}}{(K^{NK-1}-s^{NK-1})}\right)$
$\displaystyle\leq\frac{(s+1)}{s}\left(1-\frac{K^{NK-K-1}(K-s)^{K}}{K^{NK-1}}\right)$
$\displaystyle=\frac{(s+1)}{s}\left(1-\left(1-\frac{s}{K}\right)^{K}\right).$
(59)

Now we need to compute the maximum value of the expression on the RHS of (59)
for $K\geq 2$ and $1\leq s\leq\lfloor{K/2}\rfloor$. Note that both $s$ and $K$
are integers. For $s$ fixed, $K\geq 2s$ satisfies all constarints. Observe
that for $s$ fixed the function $(1-\frac{s}{K})^{K}$ is increasing in $K$.
Thus, the RHS of (59) is decreasing in $K$. Since we want to compute the
maxima, we substitute $K=2s$. Thus, it follows that

$\displaystyle\frac{R^{BC}_{N,K}(Ns/K)}{R^{\text{YMA}}_{N,K}(Ns/K)}$
$\displaystyle\leq\frac{(s+1)}{s}\left(1-\left(\frac{1}{2}\right)^{2s}\right).$
(60)

The expression on the RHS of (60) takes value $3/2$ when $s=1$. For $s\geq 2$,
$(s+1)/s\leq 3/2$. So the maxima is $3/2$ and attained at $s=1,K=2$. Thus, we
have

$\frac{R^{BC}_{N,K}(Ns/K)}{R^{\text{YMA}}_{N,K}(Ns/K)}\leq 3/2\qquad\forall
s\in\\{1,2,\ldots,\lfloor{K/2}\rfloor\\}.$ (61)

Substituting $t=1$ and $r=1$ in (15), we get the following memory-rate pair

$(M_{1,1},R)=\left(\frac{N}{2},\frac{2^{NK}-2^{NK-K}-K}{2^{NK}-2}\right).$

We know that $R^{\text{YMA}}_{N,K}(N/2)\geq K/(K+2)$. Thus,

$\displaystyle\frac{R^{BC}_{N,K}(N/2)}{R^{\text{YMA}}_{N,K}(N/2)}$
$\displaystyle\leq\frac{(K+2)(2^{NK}-2^{NK-K}-K)}{K(2^{NK}-2)}$
$\displaystyle\leq\frac{(K+2)}{K}\left(\frac{(2^{NK}-2^{NK-K}-2)}{(2^{NK}-2)}\right)$
$\displaystyle=\frac{(K+2)}{K}\left(1-\frac{2^{NK-K}}{(2^{NK}-2)}\right)$
$\displaystyle\leq\frac{(K+2)}{K}\left(1-\frac{1}{2^{K}}\right).$ (62)

The maximum value of the expression on the RHS of (62)) is 3/2 and is attained
at $K=2$. The analysis for computing this maxima is exactly the same as the
one we used for (60). Thus,

$\frac{R^{BC}_{N,K}(N/2)}{R^{\text{YMA}}_{N,K}(N/2)}\leq 3/2.$ (63)

It was shown in [5] that

$\frac{R^{\text{YMA}}_{N,K}(M)}{R^{*}_{N,K}(M)}\leq 2.$ (64)

For $M\leq N/2$, $R^{\text{YMA}}_{N,K}(M)$ is the linear extrapolation of the
points $R^{\text{YMA}}_{N,K}(M^{\prime})$ where
$M^{\prime}\in\\{0,N/K,2N/K,\ldots,N/2\\}$. Thus, using (61), (63) and (64),
we conclude that,

$\frac{R^{BC}_{N,K}(M)}{R^{*p}_{N,K}(M)}\leq 3\quad\text{for }M\leq N/2.$ (65)

Now let us consider the memory regime $M\geq N/2$. All memory-rate points on
the line joining $(N/2,R^{BC}_{N,K}(M)(N/2))$ and $(N,0)$ are achievable.
Moreover from (IV-E2), it is clear that $R^{BC}_{N,K}(N/2)\leq 1$. So,

$R^{BC}_{N,K}(M)(M)\leq 2-\frac{2}{N}M,\quad\text{for }M\geq N/2.$ (66)

Using the cut-set bounds, we have the lower bound on the non-private rate

$R^{*}_{N,K}(M)\geq\left(1-\frac{M}{N}\right).$ (67)

Since $R^{*p}_{N,K}(M)\geq R^{*}_{N,K}(M)$, from (66) and (67), it follows
that

$\frac{R^{BC}_{N,K}(M)}{R^{*p}_{N,K}(M)}\leq 2,\quad\text{for }M\geq N/2.$

This completes the proof of Part 2).

####  IV-E3 Proof of Part 3)

On substituting $r=NK-K$ and $r=NK-K+1$ in (1) we get memory-rate trade-off
points $(\frac{N(NK-K)}{NK-K+1},\frac{1}{NK-K+1})$ and $(N,0)$, respectively.
Observe that both these points lie on the line given by (67). This shows that
$R^{*p}_{N,K}(M)=R^{*}_{N,K}(M)$ for $M\geq\frac{N(NK-K)}{NK-K+1}$.

###  IV-F Proof of Converse for Theorem 6

As discussed in Section III, any $(M,R)$ pair that is achievable under no
privacy requirement needs to satisfy the first and third inequalities in (21)
for $N=K=2$ [1]. Similarly, for $N>2$ and $K=2$, any feasible $(M,R)$ pair
under no privacy constraint is required to satisfy the first and third
inequalities in (IV-G2) [34]. Substituting $N=2$ in the second inequality of
(IV-G2) gives us the second inequality of (21). Thus, we only need to prove
that the inequality $3M+(N+1)R\geq 2N+1$ holds for $N\geq 2$ and $K=2$ and we
give a proof for the same in this subsection. To show that any feasible
$(M,R)$ pair satisfies this inequality, we use the following lemma on some
conditional distributions.

###### Lemma 4

Let $\tilde{k}=(k+1)\mod 2$ for $k=0,1$. Then for all
$i\in[0:N-1],i^{\prime}\in[0:N-1]$ and $j\in[0:N-1]$ any demand-private scheme
for $K=2$ satisfies the following for user $k$, with $k\in\\{0,1\\}$ :

$\displaystyle(X,Z_{k},W_{j}|D_{k}=j)$
$\displaystyle\sim(X,Z_{k},W_{j}|D_{\tilde{k}}=i,D_{k}=j)$
$\displaystyle\sim(X,Z_{k},W_{j}|D_{\tilde{k}}=i^{\prime},D_{k}=j).$ (68)

###### Proof.

See Appendix C. ∎

Throughout this proof, for simplicity, we denote $(X|D_{0}=d_{0},D_{1}=d_{1})$
by $X_{d_{0},d_{1}}$. We also define
$W_{[0:N-1]}=(W_{0},W_{1},\ldots,W_{N-1})$, $j_{i}=(j\oplus i)$ mod $N$ and
$X^{\prime}_{j}=(X_{j,j_{1}},X_{j,j_{2}},\ldots,X_{j,j_{N-1}})$. Then, we have

$\displaystyle\sum_{j=0}^{N-1}(NH(Z_{0})+H(Z_{1})+2H(X_{j,j})+\sum_{i\neq
j}H(X_{j,i}))$
$\displaystyle\geq\sum_{j=0}^{N-1}(H(Z_{0},X_{j,j})+H(Z_{1},X_{j,j})+\sum_{i\neq
j}H(X_{j,i},Z_{0}))$
$\displaystyle\overset{\mathrm{(a)}}{=}\sum_{j=0}^{N-1}(H(Z_{0},X_{j,j},W_{j})+H(Z_{1},X_{j,j},W_{j})+\sum_{i\neq
j}H(X_{j,i},Z_{0},W_{j}))$
$\displaystyle=\sum_{j=0}^{N-1}(H(Z_{1},X_{j,j},W_{j})+H(X_{j,j}|Z_{0},W_{j})+\sum_{i\neq
j}H(X_{j,i}|Z_{0},W_{j})+NH(Z_{0},W_{j}))$
$\displaystyle\geq\sum_{j=0}^{N-1}(H(Z_{1},X_{j,j},W_{j})+H(X^{\prime}_{j},X_{j,j},Z_{0},W_{j})+(N-1)H(Z_{0},W_{j}))$
$\displaystyle=\sum_{j=0}^{N-1}(H(Z_{1}|X_{j,j},W_{j})+H(X^{\prime}_{j},Z_{0}|X_{j,j},W_{j})+(N-1)H(Z_{0},W_{j})+2H(X_{j,j},W_{j}))$
$\displaystyle\geq\sum_{j=0}^{N-1}(H(X^{\prime}_{j},Z_{0},Z_{1},X_{j,j},W_{j})+(N-1)H(Z_{0},W_{j})+H(X_{j,j},W_{j}))$
$\displaystyle\overset{\mathrm{(b)}}{=}\sum_{j=0}^{N-1}(H(X^{\prime}_{j},Z_{0},Z_{1},X_{j,j},W_{[0:N-1]})+(N-1)H(Z_{0},W_{j})+H(X_{j_{1},j},W_{j}))$
$\displaystyle\geq\sum_{j=0}^{N-1}(H(W_{[0:N-1]})+(N-2)H(Z_{0},W_{j})+H(Z_{0}|W_{j})+H(X_{j_{1},j}|W_{j})+2H(W_{j}))$
$\displaystyle\geq\sum_{j=0}^{N-1}(H(W_{[0:N-1]})+(N-2)H(Z_{0},W_{j})+H(Z_{0},X_{j_{1},j},W_{j})+H(W_{j}))$
$\displaystyle\overset{\mathrm{(c)}}{\geq}\sum_{j=0}^{N-1}(H(W_{[0:N-1]})+(N-2)H(Z_{0},W_{j})+H(Z_{0},W_{j},W_{j_{1}})+H(W_{j}))$
$\displaystyle=N(N+1)F+\sum_{j=0}^{N-1}(N-2)H(Z_{0},W_{j})+\sum_{j=0}^{N-1}H(Z_{0},W_{j},W_{j_{1}})$
$\displaystyle\overset{\mathrm{(d)}}{=}N(N+1)F+\sum_{j=0}^{N-1}\sum_{i=2}^{N-1}H(Z_{0},W_{j_{i}})+\sum_{j=0}^{N-1}H(Z_{0},W_{j},W_{j_{1}})$
$\displaystyle\geq
N(N+1)F+\sum_{j=0}^{N-1}(\sum_{i=2}^{N-1}H(W_{j_{i}}|Z_{0})+H(W_{j},W_{j_{1}}|Z_{0})+(N-1)H(Z_{0})))$
$\displaystyle\geq N(N+1)F+\sum_{j=0}^{N-1}(H(W_{[0:N-1]})+(N-2)H(Z_{0}))$
$\displaystyle=N(2N+1)F+N(N-2)H(Z_{0})$ (69)

where (a) and (c) follow from the decodability criteria; (b) follows from
decodability criteria and Lemma 4; (d) follows by rearranging the terms of
first summation and the definition $j_{i}=(j\oplus i)$ mod $N$. Cancelling out
the common terms of $H(Z_{0})$ from both sides in (69), we obtain

$\displaystyle 2NH(Z_{0})+NH(Z_{1})+\sum_{j=0}^{N-1}(2H(X_{j,j})+\sum_{i\neq
j}H(X_{j,i}))\geq N(2N+1)F$

which implies that

$\displaystyle 3M+(N+1)R\geq 2N+1.$

This follows since $H(Z_{i})\leq MF$ and $H(X_{j,i})\leq RF$ for
$i\in[0:N-1]$, $j\in[0:N-1]$ by definition. The proof is thus complete.

###  IV-G Proof of Achievability for Theorem 6

####  IV-G1 Achievability of the region in (21) for $N=K=2$

We show that any memory-rate pair $(M,R)$ satisfying the below inequalities is
achievable under demand privacy for $N=K=2$:

$\displaystyle 2M+R\geq 2,\quad 3M+3R\geq 5,\quad M+2R\geq 2.$

To this end, we use the concept of _demand type_ introduced in [34].

######  Definition 2 (Demand Types)

In $(N,K)$-non-private coded caching problem, for a given demand vector
$\bar{d}$, let $t_{i}$ denote the number of users requesting file $i$, where
$i=0,\ldots,N-1$. Demand type of $\bar{d}$, denoted by $T(\bar{d})$, is
defined as the $N$-length vector $T(\bar{d}):=\bar{t}=(t_{1},\ldots,t_{N})$.
The type class of $\bar{t}$ is defined as
$\mbox{$\cal{D}$}_{\bar{t}}=\\{\mbox{$\bar{d}$}|T(\mbox{$\bar{d}$})=\bar{t}\\}$.

Clearly, the restricted demand subset $\cal{D}_{RS}$ defined in Definition 1
is a subset of the type class $(K,K,\ldots,K)$, i.e.,

$\displaystyle\mbox{$\cal{D}_{RS}$}\subseteq\mbox{$\cal{D}$}_{(K,K,\ldots,K)}.$
(70)

Indeed, for $\mbox{$\cal{D}$}_{1}\subset\mbox{$\cal{D}$}_{2}$, a
$\mbox{$\cal{D}$}_{2}$-non-private scheme is also a
$\mbox{$\cal{D}$}_{1}$-non-private scheme. Thus, we have the following
proposition.

###### Proposition 1

If there exists an $(N,NK,M,R)$ $\mbox{$\cal{D}$}_{(K,K,\ldots,K)}$-non-
private scheme, then there exists an $(N,K,M,R)$-private scheme.

###### Proof.

As mentioned before, we have
$\mbox{$\cal{D}_{RS}$}\subseteq\mbox{$\cal{D}$}_{(K,K,\ldots,K)}$. So, an
$(N,NK,M,R)$ $\mbox{$\cal{D}$}_{(K,K,\ldots,K)}$-non-private scheme is also an
$(N,NK,M,R)$ $\cal{D}_{RS}$-non-private scheme. Then, the proposition follows
from Theorem 1. ∎

It was shown in [34, Proposition 7] that the region given by (21) is an
achievable for Type $(2,2)$ for the $N=2,K=4$ coded caching problem without
demand privacy. So it follows from Proposition 1 that the same region is
achievable under demand privacy for $N=K=2$.

###### Remark 5

The corner points of the region in (21) are $(0,2)$
$(\frac{1}{3},\frac{4}{3})$, $(\frac{4}{3},\frac{1}{3})$ and $(2,0)$. The
achievability of the pairs $(0,2)$ and $(2,0)$ for Type $(2,2)$ in $N=2,K=4$
non-private coded caching problem is trivial. The achievability of the pairs
$(\frac{1}{3},\frac{4}{3})$ and $(\frac{4}{3},\frac{1}{3})$ were shown in
[34]. In Example 1, we showed that using the non-private scheme that achieves
the memory-rate pair $(\frac{1}{3},\frac{4}{3})$, we can achieve the same pair
with demand privacy for $N=K=2$. Similarly, we can also achieve the pair
$(\frac{4}{3},\frac{1}{3})$. We further note that the pair
$(\frac{4}{3},\frac{1}{3})$ is also achievable by the MDS scheme in [27].

####  IV-G2 Achievability of the region in (IV-G2) for $N>K=2$

We show that any rate-memory pair satisfying the below inequalities is
achievable under demand privacy for $N>2$ and $K=2$:

$\displaystyle 3M+NR\geq 2N,\quad 3M+(N+1)R\geq 2N+1,\quad M+NR\geq N.$

The corner points of this rate-memory curve are
$(0,2),(\frac{N}{3},1),(\frac{N^{2}}{2N-1},\frac{N-1}{2N-1})$ and $(N,0)$. The
achievability of $(0,2)$ and $(N,0)$ was shown in Theorem 3 while that of
$(\frac{N}{3},1)$ and $(\frac{N^{2}}{2N-1},\frac{N-1}{2N-1})$ is proved next.
The achievability of the entire region then follows by memory sharing.
Throughout this subsection, for simplicity we define $\tilde{k}=(k+1)$ mod 2,
where $k\in\\{0,1\\}$.

Achievability of $(\frac{N}{3},1)$: Now we describe Scheme D for $N>2$ files
and 2 users which generalizes the ideas discussed in Example 4. Scheme D
achieves rate 1 for memory $\frac{N}{3}$. We first give an outline of Scheme D
before describing it in detail.

In Scheme D, the server partitions each file into three symbols of equal size.
The first symbols of all files are cached at user 0 and the second symbols are
cached at user 1. So, each user has $N$ symbols of $F/3$ bits in her cache.
The server randomly permutes all these $N$ symbols before caching at each
user. Thus, the users do not know the position of each symbol in their own
cache. In the delivery phase, the server reveals the position of the symbol of
the demanded file that is available in her cache, through auxiliary
transmission. Thus, she needs two more symbols to recover the entire file,
which are obtained from the broadcast. The main payload of the broadcast
consists of three symbols each of size $F/3$ bits. Each user uses two out of
these three symbols to recover its demanded file in the two cases of
$D_{0}=D_{1}$ and $D_{0}\neq D_{1}$. Out of the two symbols that each user
uses to recover the file, one symbol is coded (XOR-ed with a symbol available
in the cache) and the other one is uncoded in both the cases. The remaining
symbol in the broadcast, which the user does not use for decoding, appears as
a sequence of random bits to the user. This symmetry helps in achieving the
privacy. Next we formally describe Scheme D.

Caching: The server breaks each file $W_{i},i\in[0:N-1]$ into 3 disjoint parts
of equal size, i.e., $W_{i}=(W_{i,0},W_{i,1},W_{i,2})$. We define
$Z^{\prime}_{0}$ and $Z^{\prime}_{1}$ as follows:

$\displaystyle Z^{\prime}_{0}$ $\displaystyle:=(W_{i,0})_{i\in[0:N-1]}$
$\displaystyle Z^{\prime}_{1}$ $\displaystyle:=(W_{i,1})_{i\in[0:N-1]}.$

Let $\pi_{0}$ and $\pi_{1}$ be two permutation functions which are independent