and uniformly distributed in the symmetric group of permutations of $[0:N-1]$.
Further, for $k\in\\{0,1\\}$, let

$\displaystyle Z^{\prime\prime}_{k}$
$\displaystyle:=(Z^{\prime\prime}_{k,0},Z^{\prime\prime}_{k,1},\ldots,Z^{\prime\prime}_{k,N-1})$
$\displaystyle=\pi_{k}(Z^{\prime}_{k}).$

The server places $Z^{\prime\prime}_{k}$ in the cache of user $k\in\\{0,1\\}$
along with 4 symbols $(S_{k,1},S_{k,2},P_{k,1},P_{k,2})$ of negligible size,
where

$\displaystyle S_{k,j}\sim unif\\{[0:N-1]\\},$ $\displaystyle P_{k,j}\sim
unif\\{[0:2]\\},\quad\text{for }k\in\\{0,1\\},\;j=1,2.$

These 4 symbols are used in the delivery phase. Thus, the cache of user $k$,
$Z_{k}$ is given by

$Z_{k}=(Z^{\prime\prime}_{k},S_{k,1},S_{k,2},P_{k,1},P_{k,2}).$

Observe that $Z^{\prime}_{k}$ consists of $N$ symbols each containing
$\frac{F}{3}$ bits, which gives444 where $o(F)$ is some function of $F$ such
that $\lim_{F\to\infty}\frac{o(F)}{F}=0$.

$\displaystyle len(Z_{k})$ $\displaystyle=\frac{NF}{3}+o(F)$
$\displaystyle=MF+o(F).$

Note that in this caching scheme, the server does not fully reveal the
permutation functions $\pi_{0}$ and $\pi_{1}$ with any user.

Delivery: To describe the delivery, we first define

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

where $m=(D_{0}+1)$ mod $N$. The server picks a permutation function $\pi_{2}$
uniformly at random from the symmetric group of permutations of $[0:2]$ and
includes $\pi_{2}(X^{\prime})$ in the transmission. The permutation $\pi_{2}$
is not fully revealed to any of the users. In addition to
$\pi_{2}(X^{\prime})$, to recover the demanded files, users need some more
information, which can be delivered with negligible rate. The entire broadcast
is given by

$\displaystyle X$ $\displaystyle=(\pi_{2}(X^{\prime}),J_{1},J_{2},J_{3})$
$\displaystyle=(X^{\prime\prime},J_{1},J_{2},J_{3})$
$\displaystyle=(X^{\prime\prime}_{0},X^{\prime\prime}_{1},X^{\prime\prime}_{2},J_{1},J_{2},J_{3}).$

Here, $(J_{1},J_{2},J_{3})$ are auxiliary transmissions which contain the
extra information. The auxiliary transmission $J_{1}$ is given by
$J_{1}=(J_{1,0},J_{1,1})$, where $J_{1,k}$ is defined as

$\displaystyle J_{1,k}:=S_{k,1}\oplus\pi_{k}(D_{k}).$ (71)

Recall that $\pi_{k}(D_{k})$ gives the position of $W_{D_{k},k}$ in
$Z^{\prime\prime}_{k}$ while $S_{k,1}$, $k\in\\{0,1\\}$ is a part of $Z_{k}$.

To define auxiliary transmission $J_{2}$, we first define random variables
$T_{k,j}$ for $k\in\\{0,1\\}$, $j\in\\{1,2\\}$ as follows:

$\displaystyle(T_{0,1},T_{0,2},T_{1,1},T_{1,2}):=\left\\{\begin{array}[]{lcl}(\pi_{2}(0),\pi_{2}(1),\pi_{2}(0),\pi_{2}(2))&\text{if
}D_{0}\neq D_{1}\\\ \\\ (\pi_{2}(0),\pi_{2}(1),\pi_{2}(2),\pi_{2}(1))&\text{if
}D_{0}=D_{1}.\end{array}\right.$ (75)

Note that $\pi_{2}(i)$ gives the position of the $i$-th symbol of $X^{\prime}$
in $\pi_{2}(X^{\prime})$. Auxiliary transmission $J_{2}$ is given by
$J_{2}=(J_{2,0},J_{2,1})=(J_{2,0,0},J_{2,0,1},J_{2,1,0},J_{2,1,1})$, where
$J_{2,k,j}$, $j\in\\{0,1\\}$ is defined as

$\displaystyle J_{2,k,j}$ $\displaystyle:=P_{k,j+1}\oplus T_{k,j+1}.$ (76)

Recall that symbols $P_{k,1}$ and $P_{k,2}$ are part of $Z_{k}$.

Auxiliary transmission $J_{3}$ is given by $J_{3}=(J_{3,0},J_{3,1})$, where
$J_{3,k}$ is defined as

$\displaystyle J_{3,k}:=S_{k,2}\oplus\pi_{k}(p_{k})$ (77)

and $p_{k}$ is given as

$\displaystyle p_{k}:=\left\\{\begin{array}[]{lcl}D_{\tilde{k}}&\text{if
}D_{0}\neq D_{1}\\\ \\\ m&\text{if }D_{0}=D_{1}.\end{array}\right.$ (81)

Recall that $m=(D_{0}+1)$ mod $N$, and $S_{0,2}$ and $S_{1,2}$ are part of
$Z_{0}$ and $Z_{1}$, respectively.

Observe that $X^{\prime}$ contains 3 symbols, each of size $\frac{F}{3}$ bits,
which gives

$\displaystyle len(X)$ $\displaystyle=\frac{3F}{3}+o(F)$
$\displaystyle=RF+o(F).$

Decoding: We discuss the decoding of file $W_{D_{k}}$ for user $k=0,1$. User
$k$ first recovers $\pi_{k}(D_{k}),T_{k,1},T_{k,2}$ and $\pi_{k}(p_{k})$ from
$J_{1},J_{2}$ and $J_{3}$ as follows:

$\displaystyle J_{1,k}\oplus S_{k,1}=\pi_{k}(D_{k})\oplus S_{k,1}\oplus
S_{k,1}=\pi_{k}(D_{k})\qquad\text{(using \eqref{eq:s1J1})}$ $\displaystyle
J_{2,k,0}\oplus P_{k,1}=T_{k,1}\oplus P_{k,1}\oplus
P_{k,1}=T_{k,1}\qquad\qquad\text{(using \eqref{eq:s1J2})}$ $\displaystyle
J_{2,k,1}\oplus P_{k,2}=T_{k,2}\oplus P_{k,2}\oplus
P_{k,2}=T_{k,2}\qquad\qquad\text{(using \eqref{eq:s1J2})}$ $\displaystyle
J_{3,k}\oplus S_{k,2}=\pi_{k}(p_{k})\oplus S_{k,2}\oplus
S_{k,2}=\pi_{k}(p_{k})\qquad\enspace\text{(using \eqref{eq:s1J3})}.$

User $k$ decodes the 3 parts of $W_{D_{k}}$ as follows:

$\displaystyle\widehat{W}_{D_{k},k}=Z^{\prime\prime}_{k,\pi_{k}(D_{k})}$
$\displaystyle\widehat{W}_{D_{k},2}=X^{\prime\prime}_{T_{k,2}}$
$\displaystyle\widehat{W}_{D_{k},\tilde{k}}=X^{\prime\prime}_{T_{k,1}}\oplus
Z^{\prime\prime}_{k,\pi_{k}(p_{k})}.$

User $k$ can recover each of $\widehat{W}_{D_{k},k},\widehat{W}_{D_{k},2}$ and
$\widehat{W}_{D_{k},\tilde{k}}$, where $\tilde{k}=(k+1)$ mod 2, because she
has access to each symbol $X^{\prime\prime}_{i}$, $i\in[0:2]$ from the
broadcast while all symbols $Z^{\prime\prime}_{k,j}$, $j\in[0:N-1]$ are
available in her cache.

Observe that $\widehat{W}_{D_{k},k}={W}_{D_{k},k}$ and
$\widehat{W}_{D_{k},2}={W}_{D_{k},2}$ by definition of $\pi_{k}(D_{k})$ and
$T_{k,2}$, respectively. We show that
$\widehat{W}_{D_{k},\tilde{k}}=W_{D_{k},\tilde{k}}$ by considering the
following two cases:

Case 1: $D_{0}\neq D_{1}$

$\displaystyle\widehat{W}_{D_{k},\tilde{k}}$
$\displaystyle=X^{\prime\prime}_{T_{k,1}}\oplus
Z^{\prime\prime}_{k,\pi_{k}(p_{k})}$
$\displaystyle=X^{\prime\prime}_{T_{k,1}}\oplus
Z^{\prime\prime}_{k,\pi_{k}(D_{\tilde{k}})}\qquad\text{(using
\eqref{eq:impobsT})}$ $\displaystyle=W_{D_{k},\tilde{k}}\oplus
W_{D_{\tilde{k}},k}\oplus W_{D_{\tilde{k}},k}$
$\displaystyle=W_{D_{k},\tilde{k}}.$

Case 2: $D_{0}=D_{1}$

$\displaystyle\widehat{W}_{D_{k},\tilde{k}}$
$\displaystyle=X^{\prime\prime}_{T_{k,1}}\oplus
Z^{\prime\prime}_{k,\pi_{k}(p_{k})}$
$\displaystyle=X^{\prime\prime}_{T_{k,1}}\oplus
Z^{\prime\prime}_{k,\pi_{k}(m)}\qquad\text{(using \eqref{eq:impobsT})}$
$\displaystyle=W_{D_{k},\tilde{k}}\oplus W_{m,k}\oplus W_{m,k}$
$\displaystyle=W_{D_{k},\tilde{k}}.$

Having retrieved these 3 segments of $W_{D_{k}}$, user $k$ recovers
$W_{D_{k}}$ by concatenating $W_{D_{k},0},W_{D_{k},1}$ and $W_{D_{k},2}$ in
that order.

Proof of privacy: We now prove that Scheme D is demand-private for user
$k\in\\{0,1\\}$, i.e., (9) holds true for this scheme. Recall that $\tilde{k}$
is defined as $\tilde{k}=(k+1)$ mod 2. Then the following sequence of
equalities holds true:

$\displaystyle I(D_{\tilde{k}};X,Z_{k},D_{k})$
$\displaystyle=I(D_{\tilde{k}};X|Z_{k},D_{k})+I(D_{\tilde{k}};Z_{k}|D_{k})+I(D_{k};D_{\tilde{k}})$
$\displaystyle\overset{\mathrm{(a)}}{=}I(X;D_{\tilde{k}}|Z_{k},D_{k})$
$\displaystyle=I(\pi_{2}(X^{\prime}),J_{1},J_{2},J_{3};D_{\tilde{k}}|\pi_{k}(Z^{\prime}_{k}),S_{k,1},S_{k,2},P_{k,1},P_{k,2},D_{k})$
$\displaystyle\overset{\mathrm{(b)}}{=}I(J_{1},J_{2},J_{3};D_{\tilde{k}}|S_{k,1},S_{k,2},P_{k,1},P_{k,2},D_{k})$
$\displaystyle=I(J_{1,0},J_{1,1},J_{2,0},J_{2,1},J_{3,0},J_{3,1};D_{\tilde{k}}|S_{k,1},S_{k,2},P_{k,1},P_{k,2},D_{k})$
$\displaystyle\overset{\mathrm{(c)}}{=}I(J_{1,k},J_{2,k},J_{3,k};D_{\tilde{k}}|S_{k,1},S_{k,2},P_{k,1},P_{k,2},D_{k})$
$\displaystyle=I((S_{k,1}\oplus\pi_{k}(D_{k})),(P_{k,1}\oplus
T_{k,1},P_{k,2}\oplus
T_{k,2}),(S_{k,2}\oplus\pi_{k}(p_{k}));D_{\tilde{k}}|S_{k,1},S_{k,2},P_{k,1},P_{k,2},D_{k})$
$\displaystyle=I(\pi_{k}(D_{k}),T_{k,1},T_{k,2},\pi_{k}(p_{k});D_{\tilde{k}}|S_{k,1},S_{k,2},P_{k,1},P_{k,2},D_{k})$
$\displaystyle\overset{\mathrm{(d)}}{=}I(\pi_{k}(D_{k}),T_{k,1},T_{k,2},\pi_{k}(p_{k});D_{\tilde{k}}|D_{k})$
(82)

where (a) follows because $Z_{k}$ is independent of $(D_{0},D_{1})$ and also
$D_{0}$ and $D_{1}$ are independent; for (b) note that for any fixed value of
$(J_{1},J_{2},J_{3},D_{k},D_{\tilde{k}},S_{k,1},S_{k,2},P_{k,1},P_{k,2})$, we
have

$\displaystyle(X^{\prime},Z^{\prime}_{k}|J_{1},J_{2},J_{3},D_{k},D_{\tilde{k}},S_{k,1},S_{k,2},P_{k,1},P_{k,2})\sim
unif\\{0,1\\}^{\left(1+\frac{N}{3}\right)F}$

which holds because for both cases $D_{0}\neq D_{1}$ and $D_{0}=D_{1}$, the
symbols in $X^{\prime}$ and $Z_{k}$ are independent. Hence, $X^{\prime},Z_{k}$
and $(J_{1},J_{2},J_{3},D_{k},D_{\tilde{k}},S_{k,1},S_{k,2},P_{k,1},P_{k,2})$
are independent which gives (b); (c) follows because
$(S_{\tilde{k},1},S_{\tilde{k},2},$ $P_{\tilde{k},1},P_{\tilde{k},2})$ which
are one-time pads for symbols in
$(J_{1,\tilde{k}},J_{2,\tilde{k}},J_{3,\tilde{k}})$ are independent of all
other random variables; (d) follows because
$(S_{k,1},S_{k,2},P_{k,1},P_{k,2})$ are independent of all other random
variables.

Now we show that the RHS of (82) is 0. From the definition in (81), we have
that, for all fixed values of $D_{0}$, $D_{1}$, $\pi_{0}$, $\pi_{1}$, and
$t_{1},t_{2}\in[0:2]$,

$\Pr(T_{k,1}=t_{1},T_{k,2}=t_{2}|D_{0},D_{1},\pi_{0},\pi_{1})=\Pr(T_{k,1}=t_{1},T_{k,2}=t_{2})=\left\\{\begin{array}[]{lr}\frac{1}{6},&\text{if
}t_{1}\neq t_{2}\\\ \\\ 0,&\text{if }t_{1}=t_{2}.\\\ \end{array}\right.$ (83)

Hence, $(T_{k,1},T_{k,2})$ is independent of $(D_{0},D_{1},\pi_{0},\pi_{1})$.
Also, from definition we know that $(\pi_{k}(D_{k}),\pi_{k}(p_{k}))$ is a
function of $(D_{0},D_{1},\pi_{k})$, which implies the independence of
$(T_{k,1},T_{k,2})$ and $(\pi_{k}(D_{k}),\pi_{k}(p_{k}),D_{0},D_{1})$. Then,
it follows from (82) that

$\displaystyle I(D_{\tilde{k}};X,Z_{k},D_{k})$
$\displaystyle=I(\pi_{k}(D_{k}),\pi_{k}(p_{k});D_{\tilde{k}}|D_{k})$
$\displaystyle=I(\pi_{k}(p_{k});D_{\tilde{k}}|D_{k},\pi_{k}(D_{k})+I(\pi_{k}(D_{k});D_{\tilde{k}}|D_{k})$
$\displaystyle\overset{\mathrm{(a)}}{=}0$

where (a) follows because for any fixed value of
$(D_{k},D_{\tilde{k}},\pi_{k}(D_{k}))$, we have

$\displaystyle(\pi_{k}(p_{k})|D_{k},D_{\tilde{k}},\pi_{k}(D_{k}))\sim(\pi_{k}(p_{k})|D_{k},\pi_{k}(D_{k}))\sim
unif\\{[0:N-1]\setminus\\{\pi_{k}(D_{k})\\}\\}$

and

$\displaystyle(\pi_{k}(D_{k})|D_{k},D_{\tilde{k}})\sim(\pi_{k}(D_{k})|D_{k})\sim
unif\\{[0:N-1]\\}.$

This completes the proof of privacy.

Achievability of $(\frac{N^{2}}{2N-1},\frac{N-1}{2N-1})$: Now we describe
Scheme E for $N>2$ files and 2 users which achieves rate $\frac{N-1}{2N-1}$
for memory $\frac{N^{2}}{2N-1}$. File $W_{i}$, $i\in[0:N-1]$ is partitioned
into $2N-1$ disjoint parts of equal size, i.e., $W_{i}$ is given by
$W_{i}=(W_{i,0},W_{i,1},\ldots,W_{i,2N-2})$. File $W_{i}$ is then encoded
using a $(3N-2,2N-1)$ MDS code such that each of $(3N-2)$ coded symbols has
$\frac{F}{2N-1}$ bits. Each file can be reconstructed using any $(2N-1)$ coded
symbols. One of the $(3N-2)$ coded symbols of file $W_{i}$ is denoted by
$F_{i,0}$ while the remaining $(3N-3)$ symbols are denoted by $F_{i,j,k}$,
where $j\in[0:2]$ and $k\in[0:N-2]$. Next we give an outline of Scheme E.

In Scheme E, $N$ out of $3N-2$ symbols of each file are cached at each user.
Out of these $N$ symbols, one symbol is common with the other user and
remaining $N-1$ symbols are distinct from the other user. Similar to Scheme D,
the server randomly permutes these $N^{2}$ symbols before caching at each
user. The main payload of the broadcast consists of $N-1$ symbols. To decode
the demanded file, each user needs $2N-1$ symbols. The server reveals the
positions of the $N$ symbols of the requested file that are available in the
cache of each user, through auxiliary transmission. Both users obtain
additional $N-1$ symbols from the broadcast in the two cases of $D_{0}=D_{1}$
and $D_{0}\neq D_{1}$. This symmetry is a crucial point in preserving privacy.
We formally describe Scheme E next.

Caching: To give the cache contents of the users, we first 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,1},F_{i,j,2},\ldots,F_{i,j,N-1})_{i\in[0:N-1]},\quad\forall
j\in[0:2].$

The server randomly picks any 2 of $\mbox{$\cal{L}$}_{0},\mbox{$\cal{L}$}_{1}$
and $\mbox{$\cal{L}$}_{2}$ and places one of them in the cache of user 0 after
applying a random permutation, and places the other in the cache of user 1
after applying another independent permutation. To describe this process
formally, we first define

$\displaystyle U_{0}\sim unif\\{[0:2]\\}$ $\displaystyle U_{1}\sim
unif\\{[0:2]\backslash\\{U_{0}\\}\\}.$

Let $\pi_{0}$ and $\pi_{1}$ be two independent and uniformly distributed
permutation functions in the symmetric group of permutations of $[0:N^{2}-1]$.
Further, for $k\in\\{0,1\\}$, let

$\displaystyle Z^{\prime}_{k}$
$\displaystyle=(Z^{\prime}_{k,0},Z^{\prime}_{k,1},\ldots,Z^{\prime}_{k,N^{2}-1})=\pi_{k}(\mbox{$\cal{L}$}_{U_{k}}).$
(84)

The server places $Z^{\prime}_{k}$ and $U_{k}$ in the cache of user $k$ and
also the symbols $(S_{k,1},S_{k,2},\ldots,S_{k,2N-1},P_{k})$, where

$\displaystyle S_{k,j}$ $\displaystyle\sim unif\\{[0:N^{2}-1]\\},$
$\displaystyle P_{k}$ $\displaystyle\sim unif\\{[0:2]\\},\qquad\forall
k\in\\{0,1\\},\enspace j\in[0:2N-1]\backslash\\{0\\}.$

These symbols are used in the delivery phase. Thus, the cache of user $k$,
$Z_{k}$ is given by

$Z_{k}=(Z^{\prime}_{k},S_{k,1},S_{k,2},\ldots,S_{k,2N-1},P_{k},U_{k}).$

Note that the main payload consists of $N$ coded symbols of each file and each
symbol has $\frac{F}{2N-1}$ bits. Thus, we have

$\displaystyle len(Z_{k})$ $\displaystyle=\frac{N^{2}F}{2N-1}+o(F)$
$\displaystyle=MF+o(F).$

Delivery: To describe the delivery phase, we first define

$\displaystyle
X^{\prime}=(X^{\prime}_{0},X^{\prime}_{1},\ldots,X^{\prime}_{N-2})=\left\\{\begin{array}[]{lcl}(F_{D_{0},U_{1},t}\oplus
F_{D_{1},U_{0},t})_{t\in[0:N-1]\backslash\\{0\\}}&\text{if }D_{0}\neq D_{1}\\\
\\\ (F_{D_{0},V,t}\oplus F_{m_{t},0})_{t\in[0:N-1]\backslash\\{0\\}}&\text{if
}D_{0}=D_{1}\end{array}\right.$ (88)

where $m_{t}=(D_{0}+t)$ mod $N$, and $V=[0:2]\backslash\\{U_{0},U_{1}\\}$. The
transmitted message $X$ is given by

$X=(X^{\prime},J_{1},J_{2},J_{3})$

where $(J_{1},J_{2},J_{3})$ are the auxiliary transmissions. Next we describe
these auxiliary transmissions.

To describe $J_{1}$, we define

$\displaystyle C^{k}_{i,j}:=\pi_{k}(Ni+j),\quad\forall
i\in[0:N-1],\;j\in[0:N-1],\;k\in\\{0,1\\}.$ (89)

Thus, $C^{k}_{i,0}$ and $C^{k}_{i,j}$ respectively give the positions of
$F_{i,0}$ and $F_{i,U_{k},j}$ in $Z^{\prime}_{k}$. The auxiliary transmission
$J_{1}$ is given by $J_{1}=(J_{1,0},J_{1,1})$, where

$\displaystyle J_{1,k}$
$\displaystyle=(J_{1,k,j})_{j\in[0:N-1]}:=(S_{k,j+1}\oplus
C^{k}_{D_{k},j})_{j\in[0:N-1]},\quad k\in\\{0,1\\}.$ (90)

Here, $\oplus$ denotes addition modulo $N^{2}$ and also note that $S_{k,j+1}$
are part of $Z_{k}$.

Auxiliary transmission $J_{2}$ is defined as $J_{2}=(J_{2,0},J_{2,1})$, where

$\displaystyle J_{2,k}=(J_{2,k,j})_{j\in[0:N-2]}:=(S_{k,N+1+j}\oplus
H_{k,j+1})_{j\in[0:N-2]},\quad k\in\\{0,1\\}$ (91)

with $H_{k,j}\in[0:N^{2}-1]$ defined by

$\displaystyle
H_{k,j}:=\left\\{\begin{array}[]{lcl}C^{k}_{D_{\tilde{k}},j}&\text{if
}D_{0}\neq D_{1}\\\ \\\ C^{k}_{m_{j},0}&\text{if
}D_{0}=D_{1}.\end{array}\right.$ (95)

Note that, for $k\in\\{0,1\\}$ and $j\in[0:N-1]\backslash\\{0\\}$,
$S_{k,N+1+j}\in[0:N^{2}-1]$ are part of $Z_{k}$.

Finally, the auxiliary transmission $J_{3}$ is defined as
$J_{3}=(J_{3,0},J_{3,1})$, where

$\displaystyle J_{3,k}$ $\displaystyle:=(P_{k}\oplus T_{k}).$ (96)

Here, $P_{k}$ is a part of $Z_{k}$, and $(T_{0},T_{1})$ is defined as

$(T_{0},T_{1}):=\left\\{\begin{array}[]{lcl}(U_{1},U_{0})&\text{if }D_{0}\neq
D_{1}\\\ \\\ (V,V)&\text{if }D_{0}=D_{1}.\end{array}\right.$

Observe that the main payload $X^{\prime}$ consists of $(N-1)$ symbols of
$\frac{F}{2N-1}$ bits each. Thus, we have

$\displaystyle len(X)$ $\displaystyle=\frac{(N-1)F}{2N-1}+o(F)$
$\displaystyle=RF+o(F).$

Decoding: Now we describe the decoding of file $W_{D_{k}}$ at user
$k\in\\{0,1\\}$. For $i\in[0:N-1],j\in[0:N-1]\backslash\\{0\\}$, user $k$
recovers $(C^{k}_{D_{k},0},C^{k}_{D_{k},1},\ldots,C^{k}_{D_{k},N-1})$,
$(H_{k,1},H_{k,2},\ldots,H_{k,N-1})$ and $T_{k}$ from $J_{1},J_{2}$ and
$J_{3}$, respectively as follows:

$\displaystyle J_{1,k,i}\oplus S_{k,i+1}=C^{k}_{D_{k},i}\oplus S_{k,i+1}\oplus
S_{k,i+1}=C^{k}_{D_{k},i}\qquad\quad\enspace\text{(using~{}\eqref{eq:J1})}$
$\displaystyle J_{2,k,j-1}\oplus S_{k,N+j}=H_{k,j}\oplus S_{k,N+j}\oplus
S_{k,N+j}=H_{k,j}\qquad\text{(using~{}\eqref{eq:J2})}$ $\displaystyle
J_{3,k}\oplus P_{k}=T_{k}\oplus P_{k}\oplus
P_{k}=T_{k}\qquad\qquad\qquad\qquad\qquad\enspace\hskip
2.27621pt\text{(using~{}\eqref{eq:J3})}.$

The coded symbols of $W_{D_{k}}$, namely, $F_{D_{k},0}$ and
$F_{D_{k},U_{k},j},j\in[0:N-1]\setminus\\{0\\}$ are stored in the cache of
user $k$, but their positions are unknown to the user. Using
$(C^{k}_{D_{k},0},C^{k}_{D_{k},1},\ldots,C^{k}_{D_{k},N-1})$, user $k$ can
recover these symbols as

$\displaystyle\widehat{F}_{D_{k},0}$
$\displaystyle=Z^{\prime}_{k,C^{k}_{D_{k},0}},$
$\displaystyle\widehat{F}_{D_{k},U_{k},j}$
$\displaystyle=Z^{\prime}_{k,C^{k}_{D_{k},j}},\quad\text{for
}j\in[0:N-1]\backslash\\{0\\}.$

Observe that, by the definition of $C^{k}_{D_{k},0}$ and $C^{k}_{D_{k},j}$, we
get $\widehat{F}_{D_{k},0}={F}_{D_{k},0}$ and
$\widehat{F}_{D_{k},U_{k},j}={F}_{D_{k},U_{k},j}$. Now that user $k$ has
recovered $N$ coded symbols of $W_{D_{k}}$, we show how it recovers $(N-1)$
more symbols namely, $F_{D_{k},T_{k},j}$, $j\in[0:N-1]\setminus\\{0\\}$.
Symbol $F_{D_{k},T_{k},j}$ can be recovered from the main payload using
$(H_{k,1},H_{k,2},\ldots,H_{k,N-1})$ as follows:

$\widehat{F}_{D_{k},T_{k},j}=X^{\prime}_{j-1}\oplus
Z^{\prime}_{k,H_{k,j}},\quad\text{for }j\in[0:N-1]\backslash\\{0\\}.$

To show that $\widehat{F}_{D_{k},T_{k},j}={F}_{D_{k},T_{k},j}$, we consider
the following two cases:
Case 1: $D_{0}\neq D_{1}$

$\displaystyle\widehat{F}_{D_{k},T_{k},j}$
$\displaystyle=X^{\prime}_{j-1}\oplus Z^{\prime}_{k,H_{k,j}}$
$\displaystyle=F_{D_{0},U_{1},j}\oplus F_{D_{1},U_{0},j}\oplus
Z^{\prime}_{k,C^{k}_{D_{\tilde{k}},j}}\qquad\text{(using \eqref{eq:X'} and
\eqref{eq:defh})}$ $\displaystyle=F_{D_{0},U_{1},j}\oplus
F_{D_{1},U_{0},j}\oplus F_{D_{\tilde{k}},U_{k},j}\qquad\text{(using
\eqref{eq:pos} and \eqref{eq:cache})}$
$\displaystyle=F_{D_{k},U_{\tilde{k}},j}$ $\displaystyle=F_{D_{k},T_{k},j}.$

Case 2: $D_{0}=D_{1}$

$\displaystyle\widehat{F}_{D_{k},T_{k},j}$
$\displaystyle=X^{\prime}_{j-1}\oplus Z^{\prime}_{k,H_{k,j}}$
$\displaystyle=F_{D_{0},V,j}\oplus F_{m_{j},0}\oplus
Z^{\prime}_{k,C^{k}_{m_{j},0}}\qquad\text{(using \eqref{eq:X'} and
\eqref{eq:defh})}$ $\displaystyle=F_{D_{0},V,j}\oplus F_{m_{j},0}\oplus
F_{m_{j},0}\qquad\quad\text{(using \eqref{eq:pos} and \eqref{eq:cache})}$
$\displaystyle=F_{D_{0},V,j}$ $\displaystyle=F_{D_{k},T_{k},j}.$

Since $T_{k}\neq U_{k}$, user $k$ has retrieved $2N-1$ distinct symbols of the
MDS code. Using these, user $k$ can decode file $W_{D_{k}}$.

Proof of privacy:  Now we prove that Scheme E is demand-private for user
$k=0,1$, i.e., (9) holds true for this scheme. Recall that $\tilde{k}$ is
defined as $\tilde{k}=(k+1)$ mod 2. Then the following sequence of equalities
holds true:

$\displaystyle I(D_{\tilde{k}};X,Z_{k},D_{k})$
$\displaystyle=I(D_{\tilde{k}};X|Z_{k},D_{k})+I(D_{\tilde{k}};Z_{k}|D_{k})+I(D_{k};D_{\tilde{k}})$
$\displaystyle\overset{\mathrm{(a)}}{=}I(X;D_{\tilde{k}}|Z_{k},D_{k})$
$\displaystyle=I(X^{\prime},J_{1},J_{2},J_{3};D_{\tilde{k}}|\pi_{k}(\mbox{$\cal{L}$}_{U_{k}}),S_{k,1},S_{k,2},\ldots,S_{k,2N-1},P_{k},U_{k},D_{k})$
$\displaystyle\overset{\mathrm{(b)}}{=}I(J_{1},J_{2},J_{3};D_{\tilde{k}}|S_{k,1},S_{k,2},\ldots,S_{k,2N-1},P_{k},U_{k},D_{k})$
$\displaystyle=I(J_{1,0},J_{1,1},J_{2,0},J_{2,1},J_{3,0},J_{3,1};D_{\tilde{k}}|S_{k,1},S_{k,2},\ldots,S_{k,2N-1},P_{k},U_{k},D_{k})$
$\displaystyle\overset{\mathrm{(c)}}{=}I(J_{1,k},J_{2,k},J_{3,k};D_{\tilde{k}}|S_{k,1},S_{k,2},\ldots,S_{k,2N-1},P_{k},U_{k},D_{k})$
$\displaystyle=I(C^{k}_{D_{k},0},C^{k}_{D_{k},1},\ldots,C^{k}_{D_{k},N-1},H_{k,1},H_{k,2},\ldots,H_{k,N-1},T_{k};D_{\tilde{k}}|S_{k,1},S_{k,2},\ldots,S_{k,2N-1},P_{k},U_{k},D_{k})$
$\displaystyle\overset{\mathrm{(d)}}{=}I(C^{k}_{D_{k},0},C^{k}_{D_{k},1},\ldots,C^{k}_{D_{k},N-1},H_{k,1},H_{k,2},\ldots,H_{k,N-1},T_{k};D_{\tilde{k}}|U_{k},D_{k})$
(97)

where (a) follows because $Z_{k}$ is independent of $(D_{0},D_{1})$ and also
$D_{0}$ and $D_{1}$ are independent; (b) follows because for any fixed value
of
$(J_{1},J_{2},J_{3},S_{k,1},S_{k,2},\ldots,S_{k,2N-1},P_{k},U_{k},D_{k},D_{\tilde{k}})$,
we have

$\displaystyle(X^{\prime},\mbox{$\cal{L}$}_{U_{k}}|J_{1},J_{2},J_{3},S_{k,1},S_{k,2},\ldots\,S_{k,2N-1},P_{k},U_{k},D_{k},D_{\tilde{k}})\sim
unif\\{0,1\\}^{F\frac{(N^{2}+N-1)}{(2N-1)}};$

(c) follows because $(J_{1,\tilde{k}},J_{2,\tilde{k}},J_{3,\tilde{k}})$ are
encoded using one-time pads which are only available with user $\tilde{k}$;
(d) follows because $(S_{k,1},S_{k,2},\ldots,S_{k,2N-1},P_{k})$ are one-time
pads which are independent of all other random variables.

Next we show that the RHS of (97) is 0. To this end, we need the following.
For all $C^{k}_{D_{k},i}$ and $H_{k,j}$ distinct, observe that:

  1. (i)

For $d_{0}\in[0:N-1],d_{1}\in[0:N-1]$, $d_{0}\neq d_{1}$ and any fixed values
of $(U_{0},U_{1})$,

$\displaystyle\Pr(C^{k}_{D_{k},0},C^{k}_{D_{k},1},\ldots,C^{k}_{D_{k},N-1},H_{k,1},H_{k,2},\ldots,H_{k,N-1}|D_{0}=d_{0},D_{1}=d_{1},U_{0},U_{1})$
$\displaystyle\overset{\mathrm{(e)}}{=}\Pr(C^{k}_{d_{k},0},C^{k}_{d_{k},1},\ldots,C^{k}_{d_{k},N-1},C^{k}_{d_{\tilde{k}},1},C^{k}_{d_{\tilde{k}},2},\ldots,C^{k}_{d_{\tilde{k}},N-1}|D_{0}=d_{0},D_{1}=d_{1},U_{0},U_{1})$
$\displaystyle\overset{\mathrm{(f)}}{=}\Pr(C^{k}_{d_{k},0},C^{k}_{d_{k},1},\ldots,C^{k}_{d_{k},N-1},C^{k}_{d_{\tilde{k}},1},C^{k}_{d_{\tilde{k}},2},\ldots,C^{k}_{d_{\tilde{k}},N-1})$
$\displaystyle=\frac{(N^{2}-2N+1)!}{(N^{2})!}.$ (98)

  2. (ii)

For $d_{0}\in[0:N-1],d_{1}\in[0:N-1]$, $d_{0}=d_{1}$ and any fixed values of
$(U_{0},U_{1})$,

$\displaystyle\Pr(C^{k}_{D_{k},0},C^{k}_{D_{k},1},\ldots,C^{k}_{D_{k},N-1},H_{k,1},H_{k,2},\ldots,H_{k,N-1}|D_{0}=d_{0},D_{1}=d_{1},U_{0},U_{1})$
$\displaystyle\overset{\mathrm{(g)}}{=}\Pr(C^{k}_{d_{k},0},C^{k}_{d_{k},1},\ldots,C^{k}_{d_{k},N-1},C^{k}_{m_{1},0},C^{k}_{m_{2},0},\ldots,C^{k}_{m_{N-1},0}|D_{0}=d_{0},D_{1}=d_{1},U_{0},U_{1})$
$\displaystyle\overset{\mathrm{(h)}}{=}\Pr(C^{k}_{d_{k},0},C^{k}_{d_{k},1},\ldots,C^{k}_{d_{k},N-1},C^{k}_{m_{1},0},C^{k}_{m_{2},0},\ldots,C^{k}_{m_{N-1},0})$
$\displaystyle=\frac{(N^{2}-2N+1)!}{(N^{2})!}.$ (99)

Here, (e) and (g) follow from (95); (f) follows because
$(C^{k}_{d_{k},0},C^{k}_{d_{k},1},\ldots,C^{k}_{d_{k},N-1},C^{k}_{d_{\tilde{k}},1},C^{k}_{d_{\tilde{k}},2},\ldots,C^{k}_{d_{\tilde{k}},N-1})$
only depends on $\pi_{k}$ which is independent of $(D_{0},D_{1},U_{0},U_{1})$;
(h) follows for similar reasons as (f). Note that by definition $T_{k}$ is a
function of $(D_{0},D_{1},U_{0},U_{1})$.

Now using (98) and (99), we conclude that
$(C^{k}_{D_{k},0},C^{k}_{D_{k},1},\ldots,C^{k}_{D_{k},N-1},H_{k,1},H_{k,2},\ldots,H_{k,N-1})$
is independent of $(D_{0},D_{1},T_{k},U_{k})$. Thus, it follows from (97) that

$\displaystyle
I(C^{k}_{D_{k},0},C^{k}_{D_{k},1},\ldots,C^{k}_{D_{k},N-1},H_{k,1},H_{k,2},\ldots,H_{k,N-1},T_{k};D_{\tilde{k}}|U_{k},D_{k})=I(T_{k};D_{\tilde{k}}|U_{k},D_{k}).$
(100)

For
$d_{0}\in[0:N-1],d_{1}\in[0:N-1],u_{k}\in[0:2],t\in[0:2]\setminus\\{u_{k}\\}$,

$\displaystyle\Pr(T_{k}=t|D_{0}=d_{0},D_{1}=d_{1},U_{k}=u_{k})=\begin{cases}\Pr(U_{\tilde{k}}=t|D_{0}=d_{0},D_{1}=d_{1},U_{k}=u_{k})=\frac{1}{2},\quad&\text{if
}d_{0}\neq d_{1}\\\ \\\
\Pr(V=t|D_{0}=d_{0},D_{1}=d_{1},U_{k}=u_{k})=\frac{1}{2},\quad&\text{if
}d_{0}=d_{1}.\end{cases}$ (101)

From (101), we obtain that $T_{k}$ is independent of
$(U_{k},D_{k},D_{\tilde{k}})$. It thus follows from (100) and (97) that

$\displaystyle
I(D_{\tilde{k}};X,Z_{k},D_{k})=I(T_{k};D_{\tilde{k}}|U_{k},D_{k})=0.$

This completes the proof for privacy.

##  Appendix A Proof of Lemma 2

To prove this lemma, we need to show that user $u^{\prime}_{i}$ can recover
all $Z^{i}_{j,\mbox{$\cal{S}$}}$ such that
$\mbox{$\cal{R}$}^{-}\subset\mbox{$\cal{T}$},|\mbox{$\cal{R}$}^{-}|=r-1$, and
$0\in\mbox{$\cal{S}$}$. For
$\mbox{$\cal{A}$}:=\mbox{$\cal{S}$}\setminus\\{0\\}$, it follows from the
definition that

$\displaystyle Z^{j}_{i,\mbox{$\cal{S}$}}$
$\displaystyle=\bigoplus_{t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{S}$}}W_{j,\mbox{$\cal{S}$}\cup\\{t\\}}$
$\displaystyle=\bigoplus_{t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{R}$}^{-}}W_{j,\mbox{$\cal{A}$}\cup\\{0,t\\}}.$
(102)

For
$t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{S}$}$,
we can write

$\displaystyle Z^{j}_{i,\mbox{$\cal{A}$}\cup\\{t\\}}$
$\displaystyle=\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap(\mbox{$\cal{A}$}\cup\\{t\\})}W_{j,\mbox{$\cal{A}$}\cup\\{t,u\\}}$
$\displaystyle\overset{(a)}{=}W_{j,\mbox{$\cal{A}$}\cup\\{0,t\\}}\oplus\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap(\mbox{$\cal{S}$}\cup\\{t\\})}W_{j,\mbox{$\cal{A}$}\cup\\{t,u\\}}$

where, $(a)$ follows because
$\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap(\mbox{$\cal{A}$}\cup\\{t\\})=\left(\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap(\mbox{$\cal{S}$}\cup\\{t\\})\right)\cup\\{0\\}$.
Thus, we have

$\displaystyle W_{j,\mbox{$\cal{A}$}\cup\\{0,t\\}}$
$\displaystyle=Z^{j}_{i,\mbox{$\cal{A}$}\cup\\{t\\}}\oplus\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap(\mbox{$\cal{S}$}\cup\\{t\\})}W_{j,\mbox{$\cal{A}$}\cup\\{t,u\\}}.$

Substituting the above expression of $W_{j,\mbox{$\cal{A}$}\cup\\{0,t\\}}$ in
(102), we get

$\displaystyle Z^{j}_{i,\mbox{$\cal{S}$}}$
$\displaystyle=\bigoplus_{t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{S}$}}Z^{j}_{i,\mbox{$\cal{A}$}\cup\\{t\\}}\oplus\bigoplus_{t\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap\mbox{$\cal{S}$}}\;\bigoplus_{u\in\mbox{$\cal{V}$}_{i}\backslash\mbox{$\cal{V}$}_{i}\cap(\mbox{$\cal{S}$}\cup\\{t\\})}W_{j,\mbox{$\cal{A}$}\cup\\{t,u\\}}.$

Observe that $Z^{j}_{i,\mbox{$\cal{A}$}\cup\\{t\\}}$ is cached at the user
while the second term is zero because every term
$W_{j,\mbox{$\cal{A}$}\cup\\{t,u\\}}$ appears twice in the double summation.
This shows that $Z^{j}_{i,\mbox{$\cal{S}$}}$ can be recovered using only the
cache contents. This completes the proof of Lemma 2.

##  Appendix B Proof of Lemma 3

To prove the lemma, we follow the proof of [6, Theorem 2], where a lower bound
on the optimal rate that is tighter than the cut-set bound was obtained. We
also use that $R^{\text{MAN,lin}}_{N,K}(M)$ is monotonically non-increasing
for all $M\geq 0$ which can be shown as follows. Let $g_{1}(M)=N-M$,
$g_{2}(M)=K(1-M/N)\frac{1}{1+\frac{KM}{N}}$ and
$t_{0}=\frac{KM}{N}\in\\{0,1,\ldots,K\\}$. It is easy to see that, for
$t^{\prime}_{0},t^{\prime\prime}_{0}\in\\{0,1,\ldots,K\\}$,

$\displaystyle g_{1}\left(\frac{t^{\prime}_{0}N}{K}\right)\leq
g_{1}\left(\frac{t^{\prime\prime}_{0}N}{K}\right),\quad\mbox{if
}t^{\prime}_{0}>t^{\prime\prime}_{0},\;.$ (103)

We also have

$\displaystyle g_{2}\left(\frac{t^{\prime}_{0}N}{K}\right)\leq
g_{2}\left(\frac{t^{\prime\prime}_{0}N}{K}\right),\quad\mbox{if
}t^{\prime}_{0}>t^{\prime\prime}_{0}$ (104)

since

$\displaystyle
g_{2}\left(\frac{t_{0}N}{K}\right)-g_{2}\left(\frac{(t_{0}+1)N}{K}\right)$
$\displaystyle=\frac{K-t_{0}}{1+t_{0}}-\frac{K-(t_{0}+1)}{2+t_{0}}$
$\displaystyle=\frac{K+1}{(1+t_{0})(2+t_{0})}$ $\displaystyle\geq 0.$

From (103) and (104), it follows that

$\displaystyle\min\left(g_{1}\left(\frac{t^{\prime}_{0}N}{K}\right),g_{2}\left(\frac{t^{\prime}_{0}N}{K}\right)\right)$
$\displaystyle\leq\min\left(g_{1}\left(\frac{t^{\prime\prime}_{0}N}{K}\right),g_{2}\left(\frac{t^{\prime\prime}_{0}N}{K}\right)\right),\quad\mbox{for
}t^{\prime}_{0}>t^{\prime\prime}_{0}.$ (105)

Since $R^{\text{MAN,lin}}_{N,K}(M)$ is the linear interpolation of
$\min\left(g_{1}\left(\frac{t_{0}N}{K}\right),g_{2}\left(\frac{t_{0}N}{K}\right)\right)$
for $t_{0}\in\\{0,1,\ldots,K\\}$, (105) implies that
$R^{\text{MAN,lin}}_{N,K}(M)$ is monotonically non-increasing in $M$.

Now we consider the two memory regions studied in the proof of [6, Theorem 2].
For $N\leq K$, the two regions are as follows:

Region I: $0\leq M\leq 1$:  Since $R^{\text{MAN,lin}}_{N,K}(0)=N$, and also
that $R^{\text{MAN, lin}}_{N,K}(M)$ is monotonically non-increasing in $M$, we
get

$\displaystyle R^{\text{MAN, lin}}_{N,K}(M)\leq N.$

For this regime, it was shown [6, Theorem 2] that $R^{*}_{N,K}(M)\geq N/4$.
Then, we have

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

Region II: $1\leq M\leq N/2$:  Let us define
$f_{1}(M):=\frac{N}{M}-\frac{1}{2}$. For $t_{0}\geq 1$ and
$\frac{Nt_{0}}{K}\leq M\leq\frac{N(t_{0}+1)}{K}$, it was shown [6, Theorem 2]
that

$\displaystyle R^{\text{MAN,
lin}}_{N,K}\left(\frac{Nt_{0}}{K}\right)=\frac{K-t_{0}}{t_{0}+1}\leq f_{1}(M)$
(106)

and also that

$\displaystyle\frac{f_{1}(M)}{R^{*}_{N,K}(M)}\leq 4.$ (107)

Since $R^{\text{MAN, lin}}_{N,K}(M)$ is non-increasing, we get

$\displaystyle R^{\text{MAN, lin}}_{N,K}(M)\leq R^{\text{MAN,
lin}}_{N,K}\left(\frac{Nt_{0}}{K}\right).$ (108)

It thus follows from (106), (107) and (108) that

$\displaystyle\frac{R^{\text{MAN,lin}}_{N,K}(M)}{R^{*}_{N,K}(M)}\leq 4.$ (109)

This completes the proof of Lemma 3.

##  Appendix C Proof of Lemma 4

We prove (68) for $k=1$. Other cases follow similarly. Any $(N,K,M,R)$-private
scheme satisfies that $I(D_{0};Z_{1},D_{1},X)=0$. Since
$H(W_{D_{1}}|X,Z_{1},D_{1})=0$, we have that
$I(D_{0};Z_{1},D_{1},X,W_{D_{1}})=0$. Then it follows that

$\displaystyle\Pr(D_{0}=i|X=x,Z_{1}=z^{\prime},W_{j}=w_{j},D_{1}=j)=\Pr(D_{0}=i^{\prime}|X=x,Z_{1}=z^{\prime},W_{j}=w_{j},D_{1}=j).$

Multiplying both sides by $\Pr(X=x,Z_{1}=z^{\prime},W_{j}=w_{j}|D_{1}=j)$
gives

$\displaystyle\Pr(D_{0}=i,X=x,Z_{1}=z^{\prime},W_{j}=w_{j}|D_{1}=j)=\Pr(D_{0}=i^{\prime},X=x,Z_{1}=z^{\prime},W_{j}=w_{j}|D_{1}=j).$

Then it follows that

$\displaystyle\Pr(D_{0}=i|D_{1}=j)\times\Pr(X=x,Z_{1}=z^{\prime},W_{j}=w_{j}|D_{0}=i,D_{1}=j)$
$\displaystyle=\Pr(D_{0}=i^{\prime}|D_{1}=j)\times\Pr(X=x,Z_{1}=z^{\prime},W_{j}=w_{j}|D_{0}=i^{\prime},D_{1}=j).$

Since the demands are equally likely and they are independent of each other,
we get

$\displaystyle\Pr(X=x,Z_{1}=z^{\prime},W_{j}=w_{j}|D_{0}=i,D_{1}=j)$
$\displaystyle=\Pr(X=x,Z_{1}=z^{\prime},W_{j}=w_{j},|D_{0}=i^{\prime},D_{1}=j).$
(110)

Further, we also have

$\displaystyle\Pr(X=x,Z_{1}=z^{\prime},W_{j}=w_{j}|D_{1}=j)$
$\displaystyle=\sum_{t=0}^{N-1}\Pr(D_{0}=t)\times\Pr(X=x,Z_{1}=z^{\prime},W_{j}=w_{j},|D_{0}=t,D_{1}=j).$
(111)

Eq. (110) and (111) together prove (68) for $k=1$.

## References

  * [1] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” _IEEE Transactions on Information Theory_ , vol. 60, no. 5, pp. 2856–2867, May 2014\.
  * [2] ——, “Decentralized coded caching attains order-optimal memory-rate tradeoff,” _IEEE/ACM Transactions On Networking_ , vol. 23, no. 4, pp. 1029–1040, 2014.
  * [3] M. Mohammadi Amiri and D. Gunduz, “Fundamental limits of coded caching: Improved delivery rate-cache capacity tradeoff,” _IEEE Transactions on Communications_ , vol. 65, no. 2, pp. 806–815, Feb 2017.
  * [4] J. Gómez-Vilardebó, “Fundamental limits of caching: Improved rate-memory tradeoff with coded prefetching,” _IEEE Transactions on Communications_ , vol. 66, no. 10, pp. 4488–4497, Oct 2018.
  * [5] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “The exact rate-memory tradeoff for caching with uncoded prefetching,” _IEEE Transactions on Information Theory_ , vol. 64, no. 2, pp. 1281–1296, Feb. 2018.
  * [6] H. Ghasemi and A. Ramamoorthy, “Improved lower bounds for coded caching,” _IEEE Transactions on Information Theory_ , vol. 63, no. 7, pp. 4388–4413, July 2017.
  * [7] C. Wang, S. Saeedi Bidokhti, and M. Wigger, “Improved converses and gap results for coded caching,” _IEEE Transactions on Information Theory_ , vol. 64, no. 11, pp. 7051–7062, Nov 2018.
  * [8] Q. Yan, M. Cheng, X. Tang, and Q. Chen, “On the placement delivery array design for centralized coded caching scheme,” _IEEE Transactions on Information Theory_ , vol. 63, no. 9, pp. 5821–5833, 2017.
  * [9] L. Tang and A. Ramamoorthy, “Coded caching schemes with reduced subpacketization from linear block codes,” _IEEE Transactions on Information Theory_ , vol. 64, no. 4, pp. 3099–3120, 2018.
  * [10] H. H. Suthan Chittoor, M. Bhavana, and P. Krishnan, “Coded caching via projective geometry: A new low subpacketization scheme,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , 2019, pp. 682–686.
  * [11] U. Niesen and M. A. Maddah-Ali, “Coded caching with nonuniform demands,” _IEEE Transactions on Information Theory_ , vol. 63, no. 2, pp. 1146–1158, 2017.
  * [12] M. Ji, A. M. Tulino, J. Llorca, and G. Caire, “Order-optimal rate of caching and coded multicasting with random demands,” _IEEE Transactions on Information Theory_ , vol. 63, no. 6, pp. 3923–3949, 2017.
  * [13] J. Zhang, X. Lin, and X. Wang, “Coded caching under arbitrary popularity distributions,” _IEEE Transactions on Information Theory_ , vol. 64, no. 1, pp. 349–366, 2018.
  * [14] H. Ghasemi and A. Ramamoorthy, “Asynchronous coded caching with uncoded prefetching,” _IEEE/ACM Transactions on Networking_ , vol. 28, no. 5, pp. 2146–2159, 2020.
  * [15] Q. Yang, M. Mohammadi Amiri, and D. Gunduz, “Audience-retention-rate-aware caching and coded video delivery with asynchronous demands,” _IEEE Transactions on Communications_ , vol. 67, no. 10, pp. 7088–7102, 2019.
  * [16] K. Shanmugam, N. Golrezaei, A. G. Dimakis, A. F. Molisch, and G. Caire, “Femtocaching: Wireless content delivery through distributed caching helpers,” _IEEE Transactions on Information Theory_ , vol. 59, no. 12, pp. 8402–8413, 2013.
  * [17] N. Karamchandani, U. Niesen, M. A. Maddah-Ali, and S. N. Diggavi, “Hierarchical coded caching,” _IEEE Transactions on Information Theory_ , vol. 62, no. 6, pp. 3212–3229, 2016.
  * [18] M. Ji, G. Caire, and A. F. Molisch, “Fundamental limits of caching in wireless d2d networks,” _IEEE Transactions on Information Theory_ , vol. 62, no. 2, pp. 849–869, 2016.
  * [19] M. A. Maddah-Ali and U. Niesen, “Coding for caching: Fundamental limits and practical challenges,” _IEEE Communications Magazine_ , vol. 54, no. 8, pp. 23–29, 2016.
  * [20] Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol, “Index coding with side information,” _IEEE Transactions on Information Theory_ , vol. 57, no. 3, pp. 1479–1494, March 2011.
  * [21] V. Narayanan, J. Ravi, V. K. Mishra, B. K. Dey, N. Karamchandani, and V. M. Prabhakaran, “Private index coding,” in _2018 IEEE International Symposium on Information Theory (ISIT)_ , June 2018, pp. 596–600.
  * [22] S. H. Dau, V. Skachek, and Y. M. Chee, “On the security of index coding with side information,” _IEEE Transactions on Information Theory_ , vol. 58, no. 6, pp. 3975–3988, June 2012.
  * [23] M. Karmoose, L. Song, M. Cardone, and C. Fragouli, “Privacy in index coding: $k$ -limited-access schemes,” _IEEE Transactions on Information Theory_ , vol. 66, no. 5, pp. 2625–2641, 2020.
  * [24] H. Sun and S. A. Jafar, “The capacity of private information retrieval,” _IEEE Transactions on Information Theory_ , vol. 63, no. 7, pp. 4075–4088, 2017.
  * [25] A. Sengupta, R. Tandon, and T. C. Clancy, “Fundamental limits of caching with secure delivery,” _IEEE Transactions on Information Forensics and Security_ , vol. 10, no. 2, pp. 355–370, Feb. 2015.
  * [26] V. Ravindrakumar, P. Panda, N. Karamchandani, and V. M. Prabhakaran, “Private coded caching,” _IEEE Transactions on Information Forensics and Security_ , vol. 13, no. 3, pp. 685–694, Mar. 2018.
  * [27] K. Wan and G. Caire, “On coded caching with private demands,” _IEEE Transactions on Information Theory_ , vol. 67, no. 1, pp. 358–372, Jan. 2021.
  * [28] S. Kamath, “Demand private coded caching,” arXiv:1909.03324 [cs.IT], Sep. 2019.
  * [29] V. R. Aravind, P. K. Sarvepalli, and A. Thangaraj, “Subpacketization in coded caching with demand privacy,” in _2020 National Conference on Communications (NCC)_ , Kharagpur, India, Feb. 2020.
  * [30] Q. Yan and D. Tuninetti, “Fundamental limits of caching for demand privacy against colluding users,” arXiv:2008.03642 [cs.IT], Aug. 2020.
  * [31] K. Wan, H. Sun, M. Ji, D. Tuninetti, and G. Caire, “Fundamental limits of device-to-device private caching with trusted server,” arXiv: 1912.09985 [cs:IT], Jan. 2020.
  * [32] V. R. Aravind, P. K. Sarvepalli, and A. Thangaraj, “Coded caching with demand privacy: Constructions for lower subpacketization and generalizations,” arXiv: 2007.07475 [cs.IT], Jul. 2020.
  * [33] S. Kamath, J. Ravi, and B. K. Dey, “Demand-private coded caching and the exact trade-off for N=K=2,” in _2020 National Conference on Communications (NCC)_ , Kharagpur, India, Feb. 2020.
  * [34] C. Tian, “Symmetry, outer bounds, and code constructions: A computer-aided investigation on the fundamental limits of caching,” _Entropy_ , vol. 20, no. 8, pp. 603.1–603.43, Aug. 2018.
  * [35] S. Shao, J. Gómez-Vilardebó, K. Zhang, and C. Tian, “On the fundamental limit of coded caching systems with a single demand type,” in _2019 IEEE Information Theory Workshop (ITW)_ , 2019, pp. 1–5.