$\displaystyle X_{\mathcal{S}}$
$\displaystyle=\sum_{k\in{\mathcal{S}}}C_{d_{k},{\mathcal{S}}\setminus\\{k\\}},\quad\forall{\mathcal{S}}\in\Omega_{{\mathcal{I}}}^{t+1}.$
(53)

If the server were to broadcast all the multicast signals in (53), the load
would be
$\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t+1}/\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}$.
Let $r=\mathsf{rank}\big{(}d_{{\mathcal{I}}}\big{)}$; there are
$\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-r}{t+1}$
out of
$\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t+1}$
redundant multicast signals in (53), which need not be sent (akin to the YMA
delivery). For the largest possible
$r={\mathsf{r}}^{\prime}=\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})$,
the load is ${\mathsf{R}}^{\text{\rm HT1}}_{t}$ as in Theorem IV.1.

##### Correctness

By leveraging the received multicast signal and the local cache content, that
is, user $k\in{\mathcal{I}}$ knows
$\big{\\{}C_{d_{k},{\mathcal{Q}}}:{\mathcal{Q}}\in\Omega_{{\mathcal{I}}}^{t}\big{\\}}$,
user $k\in{\mathcal{I}}$ has the following system of equations

$\displaystyle\begin{bmatrix}C_{d_{k},{\mathcal{Q}}_{1}}\\\
C_{d_{k},{\mathcal{Q}}_{2}}\\\ \vdots\\\
C_{d_{k},{\mathcal{Q}}_{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}}}\end{bmatrix}$
$\displaystyle={\mathbf{G}}[\Omega_{{\mathcal{I}}}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}]\
\begin{bmatrix}F_{d_{k},{\mathcal{W}}_{1}}\\\ F_{d_{k},{\mathcal{W}}_{2}}\\\
\vdots\\\
F_{d_{k},{\mathcal{W}}_{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}}}\end{bmatrix},$
(54)

where
${\mathbf{G}}[\Omega_{{\mathcal{I}}}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}]$
is square and invertible by the properties the MDS code; thus, each active
user obtains its desired file.

##  Appendix B Proof of Theorem IV.2

We start with the details of the case of two files to easy the reader into the
notation. We aim to show the achievability of the corner point

$\displaystyle({\mathsf{M}},{\mathsf{R}})=(1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},\
2(1-1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}})),$
(55)

which satisfies with equality the cut-set bound in Lemma 2 with $s=2$, namely
${\mathsf{R}}\geq 2(1-{\mathsf{M}})$, thereby showing that the segment
connecting the trivial corner point $({\mathsf{M}},{\mathsf{R}})=(0,2)$ with
this corner point is optimal.

##### Placement Phase

The caches are populated as

$\displaystyle Z_{k}=\mathbf{G}_{k}(F_{1}+F_{2}),\ \forall
k\in[{\mathsf{K}}],$ (56)

where $\mathbf{G}_{k}$ is the ‘cache-coding’ matrix of user $k$ which is of
dimension
${\mathsf{B}}/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\times{\mathsf{B}}$,
thus
${\mathsf{M}}=1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.

##### Delivery Phase

Consider a demand vector with $n_{1}$ active users demanding file $F_{1}$ and
$n_{2}$ active users demanding file $F_{2}$, with
$n_{1}+n_{2}={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\geq
2$. When $n_{1}=0$ (or $n_{2}=0$), the server sends $F_{1}$ (or $F_{2}$) which
has load ${\mathsf{R}}=1\leq 2(1-1/{\mathsf{K}})$.

Next we consider the case where both $n_{1}$ and $n_{2}$ are strictly
positive. Let ${\mathcal{I}}_{1}\subseteq\Omega_{[{\mathsf{K}}]}^{n_{1}}$ be
the set of users demanding file $F_{1}$ and
${\mathcal{I}}_{2}\subseteq\Omega_{[{\mathsf{K}}]\setminus{\mathcal{I}}_{1}}^{n_{2}}$
be the set of users demanding file $F_{2}$. The delivery has two steps.

  1. 1.

In the first step, the server’s transmissions aim to ‘decode’ the caches of
the active users

$\displaystyle X_{\text{step1}}=[$ $\displaystyle\mathbf{G}_{j}F_{1}:\forall
j\in{\mathcal{I}}_{2},$ (57) $\displaystyle\mathbf{G}_{i}F_{2}:\forall
i\in{\mathcal{I}}_{1}].$ (58)

There are
$n_{1}+n_{2}={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
sub-messages in $X_{\text{step1}}$, each of size
${\mathsf{B}}/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.
The net result of this first step is that the active users have now a
‘decoded’ cache containing

$\displaystyle Z_{i}^{\prime}$ $\displaystyle=(\mathbf{G}_{u}F_{1},\ \forall
u\in{\mathcal{I}}_{2}\cup\\{i\\}),\ \forall i\in{\mathcal{I}}_{1},$ (59)
$\displaystyle Z_{j}^{\prime}$ $\displaystyle=(\mathbf{G}_{u}F_{2},\ \forall
u\in{\mathcal{I}}_{1}\cup\\{j\\}),\ \forall j\in{\mathcal{I}}_{2}.$ (60)

  2. 2.

In the second step, the server creates MAN-type multicast messages to serve
pairs of active users requesting the same file. For any two users in
${\mathcal{I}}_{1}$ (or in ${\mathcal{I}}_{2}$), we face a classical MAN
problem with $(t,r)=(1,1)$ where each subfile is cached exclusively by one
user and all the users request the same file. Thus, with
$u^{\star}_{n}=\min\\{u:u\in{\mathcal{I}}_{n}\\}$ being the ‘leader’ user for
file $n\in[2]$, we have

$\displaystyle X_{\text{step2}}=[$
$\displaystyle\mathbf{G}_{u^{\star}_{1}}F_{1}+\mathbf{G}_{i}F_{1}:\forall
i\in{\mathcal{I}}_{1}\setminus\\{u^{\star}_{1}\\},$ (61)
$\displaystyle\mathbf{G}_{u^{\star}_{2}}F_{2}+\mathbf{G}_{j}F_{2}:\forall
j\in{\mathcal{I}}_{2}\setminus\\{u^{\star}_{2}\\}].$ (62)

There are
$n_{1}-1+n_{2}-1={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-2$
sub-messages in $X_{\text{step2}}$, each of size
${\mathsf{B}}/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.

In total the server has sent
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-2+{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=2({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1)$
sub-messages, each of size
${\mathsf{B}}/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.
The load is thus
${\mathsf{R}}=2(1-1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}})$,
as claimed.

##### Correctness

We still need to show that each active user can decode its demanded file. At
the end of the delivery phase, each active user
$k\in{\mathcal{I}}_{1}\cup{\mathcal{I}}_{2}$ (recall
$|{\mathcal{I}}_{1}\cup{\mathcal{I}}_{2}|={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$)
has the following set of equations

$\displaystyle\underbrace{[\mathbf{G}_{u}:\forall
u\in{\mathcal{I}}_{1}\cup{\mathcal{I}}_{2}]}_{\text{${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\frac{{\mathsf{B}}}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}\times{\mathsf{B}}$
matrix}}\underbrace{F_{d_{k}}}_{\text{${\mathsf{B}}\times 1$ vector}}$ (63)

which can be inverted if the collection of cache-encoding matrices
$\\{\mathbf{G}_{1},\mathbf{G}_{2},\ldots\mathbf{G}_{{\mathsf{K}}}\\}$ has the
following MDS-like property: every
$[\mathbf{G}_{{\mathcal{S}}}:\forall{\mathcal{S}}\in\Omega_{[{\mathsf{K}}]}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}]$
is full rank. Such matrices exists.

We aim to show the achievability of the corner point

$\displaystyle({\mathsf{M}},{\mathsf{R}})=(1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},\
{\mathsf{N}}(1-1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}})).$
(64)

##### Placement Phase

The caches are populated as

$\displaystyle Z_{k}=\mathbf{G}_{k}(F_{1}+F_{2}+\ldots+F_{{\mathsf{N}}}),\
\forall k\in[{\mathsf{K}}],$ (65)

where $\mathbf{G}_{k}$ is the ‘cache-coding’ matrix of user $k$ which is of
dimension
${\mathsf{B}}/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\times{\mathsf{B}}$,
thus
${\mathsf{M}}=1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.

##### Delivery Phase

Consider a demand vector with $n_{j}$ active users demanding file $F_{j}$ for
$j\in[{\mathsf{N}}]$, with
$n_{1}+n_{2}+\ldots+n_{{\mathsf{N}}}={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\geq{\mathsf{N}}$.
When at least one of the $n_{j}$ is zero, the server sends all the demanded
files, which has load
${\mathsf{R}}\leq{\mathsf{N}}-1\leq{\mathsf{N}}(1-1/{\mathsf{K}})$.

Next we consider the case where all $n_{j}$’s are strictly positive. Let
${\mathcal{I}}_{j}\subseteq\Omega_{[{\mathsf{K}}]}^{n_{j}}$ be the set of
active users demanding file $F_{j}$, where the ${\mathcal{I}}_{j}$’s are
disjoint and $|{\mathcal{I}}_{j}|=n_{j}$ for $j\in[{\mathsf{N}}]$. The
delivery has two steps.

  1. 1.

In the first step, the server’s transmissions aim to ‘decode’ the caches of
the active users

$\displaystyle X_{\text{step1}}=[$ $\displaystyle\mathbf{G}_{u}F_{n}:\forall
u\in{\mathcal{I}}_{1},\ n\in[{\mathsf{N}}]\setminus\\{1\\},$ (66)
$\displaystyle\mathbf{G}_{u}F_{n}:\forall u\in{\mathcal{I}}_{2},\
n\in[{\mathsf{N}}]\setminus\\{2\\},$ (67) $\displaystyle\vdots$ (68)
$\displaystyle\mathbf{G}_{u}F_{n}:\forall u\in{\mathcal{I}}_{{\mathsf{N}}},\
n\in[{\mathsf{N}}]\setminus\\{{\mathsf{N}}\\}].$ (69)

There are
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}({\mathsf{N}}-1)$
sub-messages in $X_{\text{step1}}$, each of size
${\mathsf{B}}/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.

Let ${\mathcal{I}}=\cup_{j\in[{\mathsf{N}}]}{\mathcal{I}}_{j}$, with
$|{\mathcal{I}}|=n_{1}+n_{2}+\ldots+n_{{\mathsf{N}}}={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.
The net result of this first step is that the active users have now an
‘unlocked’ cache containing

$\displaystyle Z_{i}^{\prime}$ $\displaystyle=(\mathbf{G}_{u}F_{\ell},\
\forall u\in({\mathcal{I}}\setminus{\mathcal{I}}_{\ell})\cup\\{i\\}),\forall
i\in{\mathcal{I}}_{\ell},\ \ell\in[{\mathsf{N}}],$ (70)

  2. 2.

In the second step, the server creates MAN-type multicast messages to serve
pairs of active users requesting the same file. For any two users in
${\mathcal{I}}_{n}$, we face a classical MAN problem where each subfile is
cached exclusively by one user in ${\mathcal{I}}_{n}$ and all the users in
${\mathcal{I}}_{n}$ request the same file $F_{n}$, for $n\in[{\mathsf{N}}]$.
Thus, with $u^{\star}_{n}=\min\\{u:u\in{\mathcal{I}}_{n}\\}$ being the
‘leader’ user for file $n\in[{\mathsf{N}}]$, we have

$\displaystyle X_{\text{step2}}=[$
$\displaystyle\mathbf{G}_{u^{\star}_{1}}F_{1}+\mathbf{G}_{j}F_{1}:\forall
j\in{\mathcal{I}}_{1}\setminus\\{u^{\star}_{1}\\},$ (71)
$\displaystyle\mathbf{G}_{u^{\star}_{2}}F_{2}+\mathbf{G}_{j}F_{2}:\forall
j\in{\mathcal{I}}_{2}\setminus\\{u^{\star}_{2}\\},$ (72) $\displaystyle\vdots$
(73)
$\displaystyle\mathbf{G}_{u^{\star}_{{\mathsf{N}}}}F_{{\mathsf{N}}}+\mathbf{G}_{j}F_{{\mathsf{N}}}:\forall
j\in{\mathcal{I}}_{{\mathsf{N}}}\setminus\\{u^{\star}_{{\mathsf{N}}}\\}].$
(74)

There are
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-{\mathsf{N}}$
sub-messages in $X_{\text{step2}}$, each of size
${\mathsf{B}}/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.

In total the server has sent
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}({\mathsf{N}}-1)+{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-{\mathsf{N}}={\mathsf{N}}({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1)$
sub-messages, each of size
${\mathsf{B}}/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.
The load is thus
${\mathsf{N}}(1-1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}})$,
as claimed.

##### Correctness

At the end of the delivery phase, each active user $k\in{\mathcal{I}}$ has the
following set of equations

$\displaystyle\underbrace{[\mathbf{G}_{u}:\forall
u\in{\mathcal{I}}]}_{\text{${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\frac{{\mathsf{B}}}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}\times{\mathsf{B}}$
matrix}}\underbrace{F_{d_{k}}}_{\text{${\mathsf{B}}\times 1$ vector}}$ (75)

which can be inverted if the collection of cache-encoding matrices
$\\{\mathbf{G}_{1},\mathbf{G}_{2},\ldots\mathbf{G}_{{\mathsf{K}}}\\}$ has the
following MDS-like property: every
$[\mathbf{G}_{{\mathcal{S}}}:\forall{\mathcal{S}}\in\Omega_{[{\mathsf{K}}]}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}]$
is full rank. Such matrices exists on a large enough finite field.

##  Appendix C Proof of Lemma 1

Given a
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
hotplug system, let
$t\in[2:{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1]$,
and fix ${\mathsf{L}}_{t}$ such that

$\displaystyle{\mathsf{L}}_{t}<\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>(76)

##### Cache Placement

For each user $k\in[{\mathsf{K}}]$, we define
${\mathbf{E}}_{k}\in\mathbb{F}_{\mathsf{q}}^{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{t-1}\times{\mathsf{L}}_{t}}$
as the encoding matrix for user $k$. The cache $Z_{k}$ is populated from
${\mathbf{E}}_{k}$ as

$\displaystyle
Z_{k}=(({\mathbf{E}}_{k}\otimes{\mathbf{I}}_{{\mathsf{B}}/{\mathsf{L}}_{t}})F_{i}:i\in[{\mathsf{N}}]),\quad\forall
k\in[{\mathsf{K}}].$ (77)

Thus, the memory size
${\mathsf{M}}={\mathsf{N}}\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{t-1}/{\mathsf{L}}_{t}>(t-1)/t$.
We require the concatenation of all encoding matrices,
$[{\mathbf{E}}_{1};\ldots;{\mathbf{E}}_{{\mathsf{K}}}]$ to be a MDS matrix of
size
${\mathsf{K}}\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{t-1}\times{\mathsf{L}}_{t}$.

##### Delivery Phase

The server knows the active user set ${\mathcal{I}}$ and the demands
$d_{{\mathcal{I}}}$; it transmits the multicast messages

$\displaystyle
X_{\mathcal{S}}=\sum_{j\in{\mathcal{S}}}\alpha_{{\mathcal{S}},j}\left({\mathbf{p}}_{j,{\mathcal{S}}\setminus\\{j\\}}\otimes{\mathbf{I}}_{{\mathsf{B}}/{\mathsf{L}}_{t}}\right)F_{d_{j}},\forall{\mathcal{S}}\in\Omega_{{\mathcal{I}}}^{t+1},$
(78)

where $\alpha_{{\mathcal{S}},j}\in\mathbb{F}_{\mathsf{q}}$ is a coefficient
chosen as in [8, 28],
${\mathbf{p}}_{j,{\mathcal{S}}\setminus\\{j\\}}\in\mathbb{F}_{\mathsf{q}}^{{\mathsf{L}}_{t}}$
is a ‘decoding vector.’ We denote the decoding matrix for user
$j\in[{\mathcal{I}}]$ as ${\mathbf{P}}_{j}$, which is a concatenation of
$\\{{\mathbf{p}}_{j,{\mathcal{T}}}:{\mathcal{T}}\in\Omega_{[{\mathcal{I}}]\setminus\\{j\\}}^{t}\\}$.
Then ${\mathbf{P}}_{j}$ is of dimension
$\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{t}\times{\mathsf{L}}_{t}$.

We require that every decoding vector ${\mathbf{p}}_{j,{\mathcal{T}}}$ is in
the span of ${\mathbf{E}}_{k}$ when $k\in{\mathcal{T}}$, i.e.

$\displaystyle{\mathbf{p}}_{j,{\mathcal{T}}}\in\\{{\mathbf{E}}_{k}^{T}\lambda:\lambda\in\mathbb{F}_{\mathsf{q}}^{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{t-1}}\\},\forall
k\in{\mathcal{T}}.$ (79)

We will prove that such decoding vectors exist later.

##### Correctness

We can rewrite $X_{\mathcal{S}}$ in (78) as follows: for
$\ell\in{\mathcal{S}}$

$\displaystyle X_{\mathcal{S}}$
$\displaystyle=\alpha_{{\mathcal{S}},\ell}\left({\mathbf{p}}_{\ell,{\mathcal{S}}\setminus\\{\ell\\}}\otimes{\mathbf{I}}_{{\mathsf{B}}/{\mathsf{L}}_{t}}\right)F_{d_{\ell}}+\underbrace{\sum_{j\in{\mathcal{S}}\setminus\\{\ell\\}}\alpha_{{\mathcal{S}},j}\left({\mathbf{p}}_{j,{\mathcal{S}}\setminus\\{j\\}}\otimes{\mathbf{I}}_{{\mathsf{B}}/{\mathsf{L}}_{t}}\right)F_{d_{j}}}_{\text{can
be computed by user $\ell$ as every
}{\mathbf{p}}_{j,{\mathcal{S}}\setminus\\{j\\}}\in\mathsf{Span}({\mathbf{E}}_{\ell})}.$
(80)

Thus, for $j\in{\mathcal{I}}$,
$\\{{\mathbf{E}}_{j};{\mathbf{P}}_{j}\\}\in\mathbb{F}_{\mathsf{q}}^{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}\times{\mathsf{L}}_{t}}$
is known by user $j$. Since
$\\{{\mathbf{E}}_{1},\ldots,{\mathbf{E}}_{\mathsf{K}}\\}$ is a MDS matrix, if
$\\{{\mathbf{E}}_{j};{\mathbf{P}}_{j}\\}$ s full rank $F_{d_{j}}$ can be
recovered by user $j$.

##### Existence of Decoding Vectors

WLOG, let ${\mathcal{T}}=[t]$, then we can find
$\\{\lambda_{j}\in\mathbb{F}_{\mathsf{q}}^{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{t-1}}:j\in{\mathcal{T}}\\}$,
such that

$\displaystyle{\mathbf{E}}_{1}^{T}\lambda_{1}={\mathbf{E}}_{2}^{T}\lambda_{2}={\mathbf{E}}_{3}^{T}\lambda_{3}\ldots={\mathbf{E}}_{t}^{T}\lambda_{t},$
(81)

i.e. we have a linear system equation as follows,

$\displaystyle\underbrace{\begin{bmatrix}({\mathbf{E}}_{1})^{T}&-({\mathbf{E}}_{2})^{T}&&&\\\
\vdots&&\ddots&\\\
({\mathbf{E}}_{1})^{T}&&&-({\mathbf{E}}_{t})^{T}\end{bmatrix}}_{:={\mathbf{G}},\
\mathsf{dim}({\mathbf{G}})={\mathsf{L}}_{t}(t-1)\times\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{t-1}t}\begin{bmatrix}\lambda_{1}\\\
\vdots\\\ \lambda_{t}\end{bmatrix}=0.$ (82)

Each row of ${\mathbf{G}}$ is linearly independent as the concatenation of
$\\{{\mathbf{E}}_{j}:j\in[t]\\}$ is a MDS code. To ensure
$\\{\lambda_{1};\ldots;\lambda_{t}\\}\neq 0$, ${\mathbf{G}}$ must be a fat
matrix, i.e.

$\displaystyle{\mathsf{L}}_{t}(t-1)<\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{t-1}t\,\Longleftrightarrow\,{\mathsf{L}}_{t}<\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{t-1}\frac{t}{t-1},$
(83)

which already holds in (76). Thus, such decoding vectors do exist.

##  Appendix D Proof of Theorem V.1

We continue to use the notation of bilinear product in (21).

##### File Partition

Fix
$t\in[{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}]$
and partition the files into
${\mathsf{L}}_{t}=\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}$
equal-length subfiles. Then, code the subfiles of each file with the MDS
generator matrix ${\mathbf{G}}$, where any
$\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}$
columns of ${\mathbf{G}}$ are linearly independent: for all
$n\in[{\mathsf{N}}]$

$\displaystyle
C_{n,{\mathcal{T}}_{\ell}}:=\sum_{j\in\left[\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}\right]}F_{n,{\mathcal{W}}_{j}}\
g_{\ell,j}={\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{g}}_{\ell})\in\mathbb{F}_{\mathsf{q}}^{{\mathsf{B}}/\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}},$
(84)
$\displaystyle{\mathbf{g}}_{\ell}:=(g_{\ell,1},\ldots,g_{\ell,\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}})^{T}\in\mathbb{F}_{\mathsf{q}}^{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}},\
\forall\ell\in\left[\binom{{\mathsf{K}}}{t}\right],$ (85)
$\displaystyle{\mathbf{G}}:=[{\mathbf{g}}_{1};\cdots;{\mathbf{g}}_{\binom{{\mathsf{K}}}{t}}]\in\mathbb{F}_{\mathsf{q}}^{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>(86)

Note the slight abuse of notation in (84): the definition of $T(\cdot,\cdot)$
in (21) assumes subpacketization level $\binom{{\mathsf{K}}}{t}$, while here
the subpacketization level is
$\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}$;
we decided not to introduce a new notation in (84) as we essentially use
$T(\cdot,\cdot)$ to denote a linear combination of subfiles whose
subpacketization level is clear from the context.

##### Cache Placement

For each user $j\in[{\mathsf{K}}]$, the server generates an i.i.d uniformly
random vector ${\mathbf{p}}_{j}\in\mathbb{F}_{\mathsf{q}}^{\mathsf{N}}$ such
that $\sum_{i=1}^{\mathsf{N}}p_{j,i}={\mathsf{q}}-1$, and places it into
$Z_{j}$, together with the MAN-like content

$\displaystyle\\{{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{g}}_{\mathcal{T}}):n\in[{\mathsf{N}}],{\mathcal{T}}\in\Omega_{[{\mathsf{K}}]}^{t},j\in{\mathcal{T}}\\}.$
(87)

To guarantee privacy, we also need to store (inspired by the PK scheme in
(23b)) the privacy keys
$\\{{\mathrm{T}}({\mathbf{p}}_{j},{\mathbf{g}}_{\mathcal{W}}):{\mathcal{W}}\in\Omega_{[{\mathsf{K}}]\setminus\\{j\\}}^{t}\\}$
in the cache of user $j\in[{\mathsf{K}}]$. It would therefore seem that we
need to store
${\mathsf{N}}\binom{{\mathsf{K}}-1}{t-1}+\binom{{\mathsf{K}}-1}{t}$ subfiles
as in the PK scheme. The privacy keys are however MDS coded, so we only need
to store
$\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}$
of them to recover all possible $\binom{{\mathsf{K}}}{t}$. Now, from the MAN-
like content in (87) and the local randomness ${\mathbf{p}}_{j}$, we can
locally compute (similarly to (27d))

$\displaystyle{\mathrm{T}}({\mathbf{p}}_{j},{\mathbf{g}}_{\mathcal{T}})=\sum_{n\in[{\mathsf{N}}]}p_{j,n}{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{g}}_{\mathcal{T}}):{\mathcal{T}}\in\Omega_{[{\mathsf{K}}]}^{t},j\in{\mathcal{T}},$
(88)

this implies that if
$\binom{{\mathsf{K}}-1}{t-1}\geq\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}$
we are good; otherwise we need to store additional
$\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}-\binom{{\mathsf{K}}-1}{t-1}$
privacy keys that are linearly independent of those in (88).

The memory size is thus $\displaystyle{\mathsf{M}}^{\text{\rm(new)}}_{t}$
$\displaystyle=\begin{cases}{\mathsf{N}}\frac{\binom{{\mathsf{K}}-1}{t-1}}{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}}&\binom{{\mathsf{K}}-1}{t-1}\geq\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}\\\
1+\frac{t}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}\frac{\binom{{\mathsf{K}}-1}{t-1}}{\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{t-1}}({\mathsf{N}}-1)&\binom{{\mathsf{K}}-1}{t-1}<\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>(89a)

Let
$\eta_{t}:=\left[\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t}-\binom{{\mathsf{K}}-1}{t-1}\right]^{+}$.
The cache for user $j\in[{\mathsf{K}}]$ is

$\displaystyle Z_{j}$
$\displaystyle=\left\\{{\mathrm{T}}({\mathbf{e}}_{i},{\mathbf{g}}_{\\{j\\}\cup{\mathcal{Q}}}):i\in[{\mathsf{N}}],{\mathcal{Q}}\in\Omega_{[{\mathsf{K}}]\setminus\\{j\\}}^{t-1}\right\\}$
(90a) $\displaystyle\cup\
\left\\{{\mathrm{T}}({\mathbf{p}}_{j},\xi_{j,\ell}):\ell\in\left[\eta_{t}\right]\right\\}\cup\\{{\mathbf{p}}_{j}\\},$
(90b)

where $\\{\xi_{j,\ell}:\ell\in[\eta_{t}]\\}$ is a subset of
$\\{{\mathbf{g}}_{{\mathcal{T}}}:{\mathcal{T}}\in\Omega_{[{\mathsf{K}}]\setminus\\{j\\}}^{t}\\}$
that is linearly independent w.r.t.
$\\{{\mathbf{g}}_{\\{j\\}\cup{\mathcal{Q}}}:{\mathcal{Q}}\in\Omega_{[{\mathsf{K}}]\setminus\\{j\\}}^{t-1}\\}$.

##### Delivery Phase

Given the active users indexed by
${\mathcal{I}}\in\Omega_{[{\mathsf{K}}]}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$
where user $j\in{\mathcal{I}}$ demands $F_{d_{j}}$, we let
${\mathbf{q}}_{j}={\mathbf{p}}_{j}+{\mathbf{e}}_{d_{j}}$ as in the PK scheme.
As the sum entries of ${\mathbf{e}}_{d_{j}}$ is always 1, the sum entries of
${\mathbf{q}}_{j}$ thus is 0. Let
${\mathbf{Q}}=[{\mathbf{q}}_{i}:i\in{\mathcal{I}}]\in\mathbb{F}_{\mathsf{q}}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$,
the maximal rank of ${\mathbf{Q}}$ is
$\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}}-1)$.
The server sends

$\displaystyle X$
$\displaystyle=\\{X_{\mathcal{S}}:{\mathcal{S}}\in\Omega_{{\mathcal{I}}}^{t+1}\\}\cup\\{{\mathbf{Q}},{\mathcal{I}}\\}.$
(91)

##### Proof of Correctnes

We write $\displaystyle X_{\mathcal{S}}$
$\displaystyle=\sum_{j\in{\mathcal{S}}}\alpha_{j,{\mathcal{S}}\setminus\\{j\\}}{\mathrm{T}}({\mathbf{q}}_{j},{\mathbf{g}}_{{\mathcal{S}}\setminus\\{j\\}})$
(92a)
$\displaystyle=\alpha_{v,{\mathcal{S}}\setminus\\{v\\}}\left(\underbrace{{\mathrm{T}}({\mathbf{e}}_{d_{v}},{\mathbf{g}}_{{\mathcal{S}}\setminus\\{v\\}})}_{\text{demanded
by
user~{}$v$}}+\underbrace{{\mathrm{T}}({\mathbf{p}}_{v},{\mathbf{g}}_{{\mathcal{S}}\setminus\\{v\\}})}_{\text{from
cache $Z_{v}$ in~{}\eqref{eq:LMDC:ZjPK}}}\right)$ (92b)
$\displaystyle+\sum_{j\in{\mathcal{S}}\setminus\\{v\\}}\alpha_{j,{\mathcal{S}}\setminus\\{j\\}}\underbrace{{\mathrm{T}}({\mathbf{q}}_{j},{\mathbf{g}}_{{\mathcal{S}}\setminus\\{j\\}})}_{\text{from
cache $Z_{v}$ in~{}\eqref{eq:LMDC:ZjMAN} and ${\mathbf{Q}}$
in~{}\eqref{eq:LayerMDSmessages:X}}},\ \forall v\in{\mathcal{S}}.$ (92c)

Note that $\alpha_{j,{\mathcal{S}}\setminus\\{j\\}}\in\\{+1,-1\\}$ are
encoding coefficients as shown in [28]. As in the PK scheme, some multicast
messages in (91) need not be sent (similarly to the PK scheme), resulting in
the load

$\displaystyle{\mathsf{R}}^{\text{\rm
HT1+PK}}_{t}=\bigl{[}\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{t+1}-\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}}-1)}{t+1}\bigr{]}/\binom{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>(93)

##### Proof of Privacy

We prove that our scheme satisfies the privacy constraint in (8). Fix
${\mathcal{B}}\subseteq{\mathcal{I}}$, then

$\displaystyle
I(d_{{\mathcal{I}}\setminus{\mathcal{B}}};X,d_{{\mathcal{B}}},Z_{{\mathcal{B}}}\mid{{\mathcal{I}}},F_{[{\mathsf{N}}]})$
$\displaystyle\stackrel{{\scriptstyle\rm{(a)}}}{{=}}I(d_{{\mathcal{I}}\setminus{\mathcal{B}}};{\mathbf{q}}_{{\mathcal{I}}},d_{\mathcal{B}},Z_{\mathcal{B}}\mid{{\mathcal{I}}},F_{[{\mathsf{N}}]})$
$\displaystyle\stackrel{{\scriptstyle\rm{(b)}}}{{=}}I(d_{{\mathcal{I}}\setminus{\mathcal{B}}};{\mathbf{q}}_{{\mathcal{I}}},d_{\mathcal{B}},{\mathbf{p}}_{\mathcal{B}}\mid{{\mathcal{I}}},F_{[{\mathsf{N}}]})$
$\displaystyle\stackrel{{\scriptstyle\rm{(c)}}}{{=}}I(d_{{\mathcal{I}}\setminus{\mathcal{B}}};{\mathbf{q}}_{{\mathcal{I}}\setminus{\mathcal{B}}},d_{\mathcal{B}},{\mathbf{p}}_{\mathcal{B}}\mid{{\mathcal{I}}},F_{[{\mathsf{N}}]})$
$\displaystyle=I(d_{{\mathcal{I}}\setminus{\mathcal{B}}};d_{\mathcal{B}},{\mathbf{p}}_{\mathcal{B}}\mid{{\mathcal{I}}},F_{[{\mathsf{N}}]})+I(d_{{\mathcal{I}}\setminus{\mathcal{B}}};{\mathbf{q}}_{{\mathcal{I}}\setminus{\mathcal{B}}}\mid
d_{\mathcal{B}},{\mathbf{p}}_{\mathcal{B}},{{\mathcal{I}}},F_{[{\mathsf{N}}]})$
$\displaystyle\stackrel{{\scriptstyle\rm{(d)}}}{{=}}0+I(d_{{\mathcal{I}}\setminus{\mathcal{B}}};{\mathbf{q}}_{{\mathcal{I}}\setminus{\mathcal{B}}}\mid
d_{\mathcal{B}},{\mathbf{p}}_{\mathcal{B}},{{\mathcal{I}}},F_{[{\mathsf{N}}]})$
$\displaystyle\stackrel{{\scriptstyle\rm{(e)}}}{{=}}0,$

where the equality follows because: (a) $X$ in (91) is a function of
$(F_{[{\mathsf{N}}]},{\mathbf{q}}_{\mathcal{I}})$; (b) $Z_{\mathcal{B}}$ in
(90) is function of $(F_{[{\mathsf{N}}]},{\mathbf{p}}_{\mathcal{B}})$; (c)
since
${\mathbf{q}}_{{\mathcal{B}}}={\mathbf{e}}_{d_{\mathcal{B}}}+{\mathbf{p}}_{{\mathcal{B}}}$
and thus can be dropped; (d) the user demands are independent, and independent
of the local randomness; and (e)
$(d_{\mathcal{B}},{\mathbf{p}}_{\mathcal{B}},d_{{\mathcal{I}}\setminus{\mathcal{B}}},{\mathbf{q}}_{{\mathcal{I}}\setminus{\mathcal{B}}})$
are independent.

##  Appendix E Proof of Theorem V.2

##### File Partition

We partition each file into
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
equal-length subfiles as

$\displaystyle
F_{n}=(F_{n,\ell}:\ell\in[{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}]),\
\forall n\in[{\mathsf{N}}].$ (94)

With a notation similar to (21), we let
$F_{n,\ell}={\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{e}}_{\ell}),n\in[{\mathsf{N}}],\ell\in[{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}]$.

##### Cache Placement

We consider the generator matrix
${\mathbf{G}}_{j}=[{\mathbf{g}}_{j,1};\cdots;{\mathbf{g}}_{j,{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}]$
of size
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1)\times{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$,
and a vector $\xi_{j}$ of size
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
for every user $j\in[{\mathsf{K}}]$. For each user $j\in[{\mathsf{K}}]$, we
also generate i.i.d uniformly at randomly a vector
${\mathbf{p}}_{j}\in\mathbb{F}_{{\mathsf{q}}}^{{\mathsf{N}}}$ such that
$\sum_{i\in[{\mathsf{N}}]}p_{j,i}={\mathsf{q}}-1$. We populate the caches as

$\displaystyle Z_{j}$
$\displaystyle=\left\\{{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{g}}_{j,\ell}):n\in[{\mathsf{N}}],\ell\in[{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1]\right\\}$
(95a)
$\displaystyle\cup\left\\{{\mathrm{T}}({\mathbf{p}}_{j},\xi_{j})\right\\}\cup\left\\{{\mathbf{p}}_{j}\right\\},\
\forall j\in[{\mathsf{K}}],$ (95b)

and the memory size is

$\displaystyle{\mathsf{M}}={\mathsf{N}}\frac{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}+\frac{1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}=1+\frac{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}({\mathsf{N}}-1).$
(96)

More conditions on
$\\{{\mathbf{G}}_{1},\ldots,{\mathbf{G}}_{\mathsf{K}},\xi_{1},\ldots,\xi_{\mathsf{K}}\\}$
will be needed to insure decodability and will be listed next.

##### Delivery Phase

Given the set of active users
${\mathcal{I}}\in\Omega_{[{\mathsf{K}}]}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$
where user $j\in{\mathcal{I}}$ demands $F_{d_{j}}$, let
${\mathbf{q}}_{j}={\mathbf{p}}_{j}+{\mathbf{e}}_{d_{j}}$ as in PK scheme. The
server sends

$\displaystyle X$
$\displaystyle=(X_{\mathcal{I}},{\mathbf{q}}_{{\mathcal{I}}},{\mathcal{I}}),$
(97a) $\displaystyle X_{\mathcal{I}}$
$\displaystyle=\sum_{j\in{\mathcal{I}}}{\mathrm{T}}({\mathbf{q}}_{j},\phi^{({\mathcal{I}})}_{j}),$
(97b)

where the vectors $\phi^{({\mathcal{I}})}_{j}$ are to be chosen so as to
insure users can recover their demanded linear combination of files from
$X_{\mathcal{I}}$, as we shall specify later.

##### Proof of Correctness

As for the PK scheme, we rewrite $X_{\mathcal{I}}$ as

$\displaystyle X_{\mathcal{I}}$
$\displaystyle=\underbrace{{\mathrm{T}}({\mathbf{e}}_{d_{v}},\phi^{({\mathcal{I}})}_{v})}_{\text{desired
by
user~{}$v$}}+\underbrace{{\mathrm{T}}({\mathbf{p}}_{v},\phi^{({\mathcal{I}})}_{v})}_{\text{from
cached content in $Z_{v}$}}$ (98a)
$\displaystyle+\sum_{j\in{\mathcal{I}}\setminus\\{v\\}}\underbrace{{\mathrm{T}}({\mathbf{q}}_{j},\phi^{({\mathcal{I}})}_{j})}_{\text{from
cached content in $Z_{v}$ and ${\mathbf{q}}_{{\mathcal{I}}}$}},\ \forall
v\in{\mathcal{I}},$ (98b)

where in the underlines we clarified how we intend to remove from
$X_{\mathcal{I}}$ the ‘interfering’ terms for any user $v\in{\mathcal{I}}$. We
will describe next how to remove the ‘interfering’ terms, thus also
identifying additional properties we require of the generator matrices;
assuming that it is indeed possible, the load is
${\mathsf{R}}=1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$.

##### Proof of Privacy

Privacy can be proved similarly to the proof of Theorem V.1 in Appendix D.

##### Conditions for Decodability

  * •

Condition 1: $[{\mathbf{G}}_{v};\xi_{v}]$ is full rank for all
$v\in[{\mathsf{K}}]$.

Reason: The second term in (98a) can be computed from the cache content
$Z_{v}$ as follows: if $[{\mathbf{G}}_{v};\xi_{v}]$ is full rank, then any
$\tilde{{\mathbf{a}}}\in\mathbb{F}_{\mathsf{q}}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$
can be obtained as

$\displaystyle\tilde{{\mathbf{a}}}$
$\displaystyle=\sum_{\ell\in[{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1]}a_{\ell}{\mathbf{g}}_{j,\ell}+a_{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}\xi_{j},$
(99)

for some
${\mathbf{a}}=[a_{1},\ldots,a_{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}]$,
thus user $v$ can compute

$\displaystyle{\mathrm{T}}({\mathbf{p}}_{v},\tilde{{\mathbf{a}}})=\sum_{\ell\in[{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1]}a_{\ell}\left(\sum_{n\in[{\mathsf{N}}]}p_{v,n}{\mathrm{T}}({\mathbf{e}}_{n},{\mathbf{g}}_{j,\ell})\right)+a_{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}{\mathrm{T}}({\mathbf{p}}_{v},\xi_{v}),$
(100)

for any $\tilde{{\mathbf{a}}}$, and thus in particular for
$\tilde{{\mathbf{a}}}=\phi^{({\mathcal{I}})}_{v}$.

  * •

Condition 2: $[{\mathbf{G}}_{v};\phi^{({\mathcal{I}})}_{v}]$ is full rank for
all $v\in[{\mathsf{K}}]$ and all
${\mathcal{I}}\in\Omega_{[{\mathsf{K}}]}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$.

Reason: Let us assume for now that the term in (98b) can also be computed from
the cache content $Z_{v}$, thus user $v\in{\mathcal{I}}$ has recovered
${\mathrm{T}}({\mathbf{q}}_{v},\phi^{({\mathcal{I}})}_{v})$. From Condition 1,
user $v$ further computes
${\mathrm{T}}({\mathbf{p}}_{v},\phi^{({\mathcal{I}})}_{v})$ and thus attains
${\mathrm{T}}({\mathbf{e}}_{d_{j}},\phi^{({\mathcal{I}})}_{v})$ Thus we need
$[{\mathbf{G}}_{v};\phi^{({\mathcal{I}})}_{v}]$ to be full rank as well, in
order for the recovered $F_{d_{v}}$.

  * •

Condition 3: For $i,j\in[{\mathsf{K}}],i\neq j$,
$[{\mathbf{G}}_{i},{\mathbf{G}}_{j}]$ is a full rank matrix.

Reason: We finally need to show under which conditions the term in (98b) can
be computed from the cache content of user $v\in{\mathcal{I}}$. The server
sents ${\mathbf{q}}_{\mathcal{I}}$ to all users as shows in (97a),
equivalently, user $v\in[{\mathcal{I}}]$ can compute
$\\{{\mathrm{T}}({\mathbf{q}}_{j},{\mathbf{g}}_{v,\ell}):\ell\in[{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1]\\}$
for all $j\in{\mathcal{I}}$. Then
$\\{\phi^{({\mathcal{I}})}_{j}:j\in{\mathcal{I}}\setminus\\{v\\}\\}$ in (98b)
should be computable from the cache of user $v$, that is, there should exist a
vector ${\mathbf{x}}_{v,j}$ of length
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1$
such that

$\displaystyle\phi^{({\mathcal{I}})}_{j}={\mathbf{G}}_{v}{\mathbf{x}}_{v,j},\
\forall j,v\in{\mathcal{I}},v\not=j.$ (101)

As an example consider
${\mathcal{I}}=[{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}]$
and rewrite the condition in (101) for
$j={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
as

$\displaystyle\underbrace{\begin{bmatrix}{\mathbf{G}}_{1}&{\mathbf{G}}_{2}&&\\\
\vdots&&\ddots&\\\
{\mathbf{G}}_{1}&&&{\mathbf{G}}_{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}\\\
\end{bmatrix}}_{=\widetilde{{\mathbf{G}}}_{j}\in\mathbb{F}_{\mathsf{q}}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-2)\times({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1)^{2}}}\underbrace{\begin{bmatrix}-{\mathbf{x}}_{1,j}\\\
\vdots\\\
{\mathbf{x}}_{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1,j}\end{bmatrix}}_{=\widetilde{{\mathbf{x}}}_{j}}=0,\
j={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},$
(102)

where $\widetilde{{\mathbf{G}}}_{j}$ is a ‘fat matrix’, i.e.,
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-2)<({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1)^{2}$;
to ensure a non-zero solution for $\widetilde{{\mathbf{x}}}_{j}$ we need
$\widetilde{{\mathbf{G}}}_{j}$ to be full rank. For (101) to hold, it suffices
that any matrix $[{\mathbf{G}}_{j}:j\in{\mathcal{I}}]$ is an MDS matrix for
all
${\mathcal{I}}\in\Omega_{[{\mathsf{K}}]}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$.

  * •

For sufficiently large enough finite field size ${\mathsf{q}}$, if
$[{\mathbf{G}}_{1},\ldots,{\mathbf{G}}_{{\mathsf{K}}}]$ is an MDS code, then
the above three conditions are satisfied.

##  Appendix F Proof of Theorem IV.4

In this section we are going to use the following results.

######  Lemma 2 (Cut-set Bound from [3, Theorem 2]).

For the classical coded caching system with with
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
users and ${\mathsf{N}}$ files, the memory-load pair
$({\mathsf{M}},{\mathsf{R}})$ is lower bounded by

$\displaystyle{\mathsf{R}}\geq
s-\frac{s}{\lfloor{\mathsf{N}}/s\rfloor}{\mathsf{M}},\quad\forall
s\in[\min\\{{\mathsf{N}},{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>(103)

######  Lemma 3 ([3, Appendix]).

For the classical coded caching system with with
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=2$
users and ${\mathsf{N}}=2$ files, the optimal memory-load is

$\displaystyle{\mathsf{R}}^{\star}=\max\left\\{2-2{\mathsf{M}},\frac{3}{2}-{\mathsf{M}},1-\frac{{\mathsf{M}}}{2}\right\\}.$
(104)

######  Lemma 4 ([12, Theorem 3]).

For the classical coded caching system with with
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=2$
users and ${\mathsf{N}}\geq 3$ files, the optimal memory-load is

$\displaystyle{\mathsf{R}}^{\star}=\max\left\\{2-\frac{3{\mathsf{M}}}{{\mathsf{N}}},1-\frac{{\mathsf{M}}}{{\mathsf{N}}}\right\\}.$
(105)

######  Lemma 5 ([6, Theorem 2]).

For the classical coded caching system with with
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
users and ${\mathsf{N}}$ files, the memory-load pair
$({\mathsf{M}},{\mathsf{R}})$ is lower bounded by

$\displaystyle{\mathsf{R}}\geq s-1+\alpha-\frac{s(s-1)-\ell(\ell-1)+2\alpha
s}{2({\mathsf{N}}-\ell+1)}{\mathsf{M}},$ (106)

for any
$s\in[\min\\{{\mathsf{N}},{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\\}]$,
$\alpha\in[0,1]$, and where $\ell\in[s]$ is the minimum value such that

$\displaystyle\frac{s(s-1)-\ell(\ell-1)}{2}+\alpha
s\leq({\mathsf{N}}-\ell+1)\ell.$ (107)

###  F-A Case 1:
$\min\\{{\mathsf{N}},{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\\}=1$

In Theorem IV.1, there are two (trivial) corner points $(0,1)$ and
$({\mathsf{N}},0)$. The line connecting these two points meets the lower bound
in (103) in Lemma 2 for $s=1$, namely ${\mathsf{R}}\geq
1-{\mathsf{M}}/{\mathsf{N}}$. This optimal performance does not depend on the
value of ${\mathsf{K}}$.

###  F-B Case 2: constant gap

By Theorem III.3, we have

$\displaystyle{\mathsf{R}}^{\star}({\mathsf{M}})$
$\displaystyle\leq{\mathsf{R}}^{\text{\rm(YMA+)}}({\mathsf{M}})\leq{\mathsf{R}}^{\text{\rm(decen+)}}({\mathsf{M}})$
(108)
$\displaystyle=\left.\frac{1-\mu}{\mu}\Big{(}1-(1-\mu)^{\min({\mathsf{N}},{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}})}\Big{)}\right|_{\mu:={{\mathsf{M}}}/{{\mathsf{N}}}}$
(109) $\displaystyle\stackrel{{\scriptstyle\text{
\cite[cite]{[\@@bibref{}{yu2018characterizing}{}{}, Lemma 1]}
}}}{{\leq}}2.00884\ {\mathsf{R}}^{\text{Lemma~{}\ref{lem: converse lemma
YMA}}},$ (110)

where ${\mathsf{R}}^{\text{Lemma~{}\ref{lem: converse lemma YMA}}}$ denotes
the lower convex envelope of the region identified by Lemma 5.

###  F-C Case 3:
${\mathsf{N}}=2={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=2$

The achievability is proved in Section VI-A and the converse is Lemma 3.

###  F-D Case 4: ${\mathsf{N}}\geq
3,{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}=2$

In Theorem IV.1, there are three corner points points $(0,2)$,
$({\mathsf{N}},0)$ and $({\mathsf{N}}/2,1/2)$. Their lower convex envelop
equals the lower bound in (105) in Lemma 4. This optimal performance does not
depend on the value of ${\mathsf{K}}$.

###  F-E Case 5: small memory and many files
(${\mathsf{N}}>{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}+1)/2$)

When
${\mathsf{N}}\geq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}+1)/2$,
the inequality in (107) holds for any
$s\in[{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}]$,
$\alpha=1$ and $\ell=1$; so, if we let
$s={\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
and
${\mathsf{M}}={\mathsf{N}}/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
in (106), we obtain the lower bound

$\displaystyle{\mathsf{R}}\geq{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-\frac{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}+1)}{2}\
\frac{{\mathsf{M}}}{{\mathsf{N}}}.$ (111)

The segment connecting the corner points $({\mathsf{M}}^{\text{\rm
HT1}}_{0},{\mathsf{R}}^{\text{\rm
HT1}}_{0})=(0,{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}})$
and $({\mathsf{M}}^{\text{\rm HT1}}_{1},{\mathsf{R}}^{\text{\rm
HT1}}_{1})=\biggl{(}\frac{{\mathsf{N}}}{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}},\frac{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}-1}{2}\biggr{)}$
satisfies (111) with equality. This optimal performance does not depend on the
value of ${\mathsf{K}}$.

###  F-F Case 6: small memory and much fewer files than users

The corner point $({\mathsf{M}}^{\text{\rm HT2}},{\mathsf{R}}^{\text{\rm
HT2}})=(1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},\
{\mathsf{N}}(1-1/{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}})),$
satisfies with equality the cut-set bound in Lemma 2 with $s={\mathsf{N}}$,
namely ${\mathsf{R}}\geq{\mathsf{N}}(1-{\mathsf{M}})$, thereby showing that
the segment connecting the trivial corner point
$({\mathsf{M}},{\mathsf{R}})=(0,{\mathsf{N}})$ with this corner point is
optimal. This optimal performance does not depend on the value of
${\mathsf{K}}$.

###  F-G Case 7: large memory

The segment connecting the corner points
$({\mathsf{M}},{\mathsf{R}})^{\text{HT3}}=({\mathsf{N}}\frac{{\mathsf{K}}-1}{{\mathsf{K}}},\frac{1}{{\mathsf{K}}})$
and $({\mathsf{M}},{\mathsf{R}})=({\mathsf{N}},0)$ satisfies ${\mathsf{R}}\geq
1-{\mathsf{M}}/{\mathsf{N}}$, which is Lemma 2 for $s=1$.

##  Appendix G Proof of the general virtual-users idea for hotplug with
privacy

For a given
$({\mathsf{N}}{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}}{\mathsf{K}},{\mathsf{N}})$-hotplug-
NONprivate scheme, let

  * •

${C}_{k}^{(np)}$ be the cache encoding function for user $k$, that is

$Z_{k}^{(np)}={C}_{k}^{(np)}\big{(}F_{[{\mathsf{N}}]}\big{)},\forall
k\in[{\mathsf{N}}{\mathsf{K}}];$

  * •

${E}^{(np)}$ be the server encoding function, that is, for every active user
set
${\mathcal{I}}^{(np)}\in\Omega_{[{\mathsf{N}}{\mathsf{K}}]}^{{\mathsf{N}}{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$,
and their demands
$d^{(np)}_{{\mathcal{I}}}\in[{\mathsf{N}}]^{{\mathsf{N}}{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$
we have

$X^{(np)}={E}^{(np)}\big{(}{\mathcal{I}}^{(np)},d^{(np)}_{{\mathcal{I}}},F_{[{\mathsf{N}}]}\big{)};$

  * •

${G}_{k}^{(np)}$ be the decoding function for user
$k\in[{\mathsf{N}}{\mathsf{K}}]$, that is, for every
$k\in{\mathcal{I}}^{(np)}$ we have

$F_{d_{k}}={G}_{k}^{(np)}\big{(}d^{(np)}_{k},Z_{k}^{(np)},X^{(np)}\big{)},\forall
k\in{\mathcal{I}}^{(np)},\ d^{(np)}_{k}\in[{\mathsf{N}}];$

  * •

this non-private scheme achievs $({\mathsf{M}}^{(np)},{\mathsf{R}}^{(np)})$
where $H(Z_{k}^{(np)})\leq{\mathsf{B}}{\mathsf{M}}^{(np)}$ and
$H(X^{(np)})\leq{\mathsf{B}}{\mathsf{R}}^{(np)}$ for ${\mathsf{B}}$ the file
length.

We will now present a construction of an
$({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$-hotplug-
private scheme that achieves $({\mathsf{M}}^{(np)},{\mathsf{R}}^{(np)})$ from
the given
$({\mathsf{N}}{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}}{\mathsf{K}},{\mathsf{N}})$-hotplug-
NONprivate scheme.

##### Cache Placement

For each user $k$ with local i.i.d uniform randomness
$\tau_{k}\in[{\mathsf{N}}]$, the cache content is

$\displaystyle
Z_{k}=\left({C}_{(k-1){\mathsf{N}}+\tau_{k}}^{(np)}(F_{[{\mathsf{N}}]}),\,\tau_{k}\right),\forall
k\in[{\mathsf{K}}].$

Since storing $\tau_{k}$ requires $\log_{\mathsf{q}}({\mathsf{N}})$ symbols,
which is not a function of file length ${\mathsf{B}}$, the case size in the
private scheme is the same as the cache size in the NONprivate scheme.

##### Delivery

Let $\Psi:[{\mathsf{N}}]^{\mathsf{N}}\rightarrow[{\mathsf{N}}]^{\mathsf{N}}$
denote the cyclic shift operator, such that
$\Psi(t_{1},t_{2},\cdots,t_{\mathsf{N}})=(t_{\mathsf{N}},t_{1},\cdots,t_{{\mathsf{N}}-1})$.
Let us denote a vector $\mathbb{I}_{\mathsf{N}}:=(1,\cdots,{\mathsf{N}})$. For
a given active user set

${\mathcal{I}}=\\{j_{1},\ldots,j_{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}\\}\in\Omega_{[{\mathsf{N}}]}^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$

and their demands
$d_{{\mathcal{I}}}\in[{\mathsf{N}}]^{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}$,
we define: an ‘expanded demand vector’ of length
${\mathsf{N}}{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
as

$\displaystyle\widetilde{{\mathbf{d}}}:=\left(\Psi^{\tau_{j_{1}}\ominus
d_{j_{1}}}(\mathbb{I}_{\mathsf{N}}),\cdots,\Psi^{\tau_{j_{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}\ominus
d_{j_{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}}(\mathbb{I}_{\mathsf{N}})\right),$

where the operator $\Psi^{i}$ denotes the $i$-times cyclic shift operator,
which is the operator $\Psi$ applied $i$ times, and $\tau_{j}\ominus d_{j}$
denotes the difference of $\tau_{j}$ and $d_{j}$ modulo ${\mathsf{N}}$; an
‘expanded active user set’ of size
${\mathsf{N}}{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
as

$\displaystyle\widetilde{{\mathcal{I}}}:=\left((j-1){\mathsf{N}}+\ell:j\in{\mathcal{I}},\ell\in[3]\right);$

and

$\displaystyle\tau_{\mathcal{I}}\ominus
d_{\mathcal{I}}:=\left(\tau_{j_{1}}\ominus
d_{j_{1}},\cdots,\tau_{j_{{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}}\ominus
d_{j_{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}}\right).$

The server sends

$\displaystyle X$ $\displaystyle=\big{(}X_{1},X_{2}\big{)}:$ $\displaystyle
X_{1}={E}^{(np)}\big{(}\widetilde{{\mathcal{I}}},\widetilde{{\mathbf{d}}},F_{[{\mathsf{N}}]}\big{)},$
$\displaystyle X_{2}=\Big{(}\tau_{\mathcal{I}}\ominus
d_{\mathcal{I}},{\mathcal{I}}\Big{)}.$

Since sending $X_{2}$ does not scale with the file length ${\mathsf{B}}$, thus
the load in the private scheme is the same as the load size in the NONprivate
scheme for sending $X_{1}$.

##### Proof of Correctness

Active user $k\in{\mathcal{I}}$ computes $\widetilde{{\mathbf{d}}}$ and
$\widetilde{{\mathcal{I}}}$ as a function of $X_{2}$, and uses the
$((k-1){\mathsf{N}}+\tau_{k})$-th decoding function in the NONprivate scheme
to compute

$\displaystyle
F_{d_{k}}={G}_{(k-1){\mathsf{N}}+\tau_{k}}^{(np)}(d_{k},Z_{k},X_{1}).$

It is clear that the decoder of the $k$-th user outputs the same file
requested by the $\tau_{k}$-th virtual user of the $k$-th stack in the
NONprivate scheme, so the desired file is retrieved.

##### Proof of Privacy

The proof follows from the fact that, for every $i\in[{\mathsf{K}}]$,
$\tau_{i}$ acts as one-time pad for $d_{i}$, which prevents any user
$j\in{\mathcal{I}}$ but $j\neq i$ from getting any information about $d_{i}$.
Fix ${\mathcal{B}}\subseteq{\mathcal{I}}$, then

$\displaystyle
I(d_{{\mathcal{I}}\setminus{\mathcal{B}}};X,d_{{\mathcal{B}}},Z_{\mathcal{B}}\mid{{\mathcal{I}}},F_{[{\mathsf{N}}]})$
$\displaystyle\stackrel{{\scriptstyle\rm(a)}}{{=}}I(d_{{\mathcal{I}}\setminus{\mathcal{B}}};X,d_{{\mathcal{B}}}\mid{{\mathcal{I}}},F_{[{\mathsf{N}}]})$
$\displaystyle\stackrel{{\scriptstyle\rm(b)}}{{=}}I(d_{{\mathcal{I}}\setminus{\mathcal{B}}};\tau_{\mathcal{I}}\ominus
d_{\mathcal{I}},d_{{\mathcal{B}}}\mid{{\mathcal{I}}},F_{[{\mathsf{N}}]})$
$\displaystyle=I(d_{{\mathcal{I}}\setminus{\mathcal{B}}};d_{{\mathcal{B}}}\mid{{\mathcal{I}}},F_{[{\mathsf{N}}]})+I(d_{{\mathcal{I}}\setminus{\mathcal{B}}};\tau_{\mathcal{I}}\ominus
d_{\mathcal{I}}\mid d_{{\mathcal{B}}},{{\mathcal{I}}},F_{[{\mathsf{N}}]})$
$\displaystyle\stackrel{{\scriptstyle\rm(c)}}{{=}}0$

where the equality follows because (a) $Z_{\mathcal{B}}$ is a function of
$F_{[{\mathsf{N}}]}$; (b) $X$ is a function of
$(F_{[{\mathsf{N}}]},\tau_{\mathcal{I}}\ominus
d_{\mathcal{I}},{\mathcal{I}})$; (c) the user demands and user randomness are
independent. This shows that the derived scheme satisfies the privacy
condition.

##  Appendix H Proof of Constant Gap for Hotplug with Privacy

The main idea is to leverage the following chain of inequalities

$\displaystyle\frac{1}{\mathsf{ClassicalGap}}\cdot\underbrace{{\mathsf{R}}({\mathsf{M}};{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})}_{\text{achievable
classical
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
users}}\leq\underbrace{{\mathsf{R}}^{\star}({\mathsf{M}};{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})}_{\text{optimal
classical
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$
users}}\leq\underbrace{{\mathsf{R}}^{\star}({\mathsf{M}};{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})}_{\text{optimal
hotplug}}\leq\underbrace{{\mathsf{R}}({\mathsf{M}};{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})}_{\text{achievable
hotplug}},$

and bound

$\displaystyle\mathsf{HotplugGap}=\sup\frac{{\mathsf{R}}({\mathsf{M}};{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})}{{\mathsf{R}}^{\star}({\mathsf{M}};{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})}\leq\mathsf{ClassicalGap}\cdot\sup\frac{{\mathsf{R}}({\mathsf{M}};{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})}{{\mathsf{R}}({\mathsf{M}};{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})}.$

If we can find a hotpulog scheme for which the achevable load
${\mathsf{R}}({\mathsf{M}};{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})$
is not a function of ${\mathsf{K}}$, then we conclude
$\mathsf{HotplugGap}=\mathsf{ClassicalGap}$.

For the case without privacy, we used "decen+"
${\mathsf{R}}({\mathsf{M}};{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{K}},{\mathsf{N}})=\frac{1-\mu}{\mu}\Big{(}1-(1-\mu)^{\min({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}},{\mathsf{N}})}\Big{)}$,
to prove that the gap with hotplug is the same as in the classical (not
hotplug) case, as in Appendix F-B.

For the case with privacy we can use PK+" in Theorem III.5 to show to prove
that the gap with hotplug is the same as in the classical (not hotplug) case
in Theorem III.4. To notice is that the load with hotplug is increasing in
${\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\mathsf{A}}$,
so the classical case is the “worst case”. Details are not reported for
brevity.

## References

  * [1] Y. Ma and D. Tuninetti, “On coded caching systems with offline users,” in 2022 IEEE International Symposium on Information Theory (ISIT), pp. 1133–1138, IEEE, 2022.
  * [2] Y. Ma and D. Tuninetti, “Demand privacy in hotplug caching systems,” in 2023 IEEE International Symposium on Information Theory (ISIT), pp. 424–429, IEEE, 2023.
  * [3] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE Transactions on Information Theory, vol. 60, no. 5, pp. 2856–2867, 2014.
  * [4] 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, 2017.
  * [5] K. Wan, D. Tuninetti, and P. Piantanida, “An index coding approach to caching with uncoded cache placement,” IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1318–1332, 2020.
  * [6] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Characterizing the rate-memory tradeoff in cache networks within a factor of 2,” IEEE Transactions on Information Theory, vol. 65, no. 1, pp. 647–663, 2018.
  * [7] K. Wan, D. Tuninetti, M. Ji, G. Caire, and P. Piantanida, “Fundamental limits of decentralized data shuffling,” IEEE Transactions on Information Theory, vol. 66, no. 6, pp. 3616–3637, 2020.
  * [8] Y. Ma and D. Tuninetti, “A general coded caching scheme for scalar linear function retrieval,” IEEE Journal on Selected Areas in Information Theory, vol. 3, no. 2, pp. 321–336, 2022.
  * [9] Z. Chen, P. Fan, and K. B. Letaief, “Fundamental limits of caching: Improved bounds for users with small buffers,” IET Communications, vol. 10, no. 17, pp. 2315–2318, 2016.
  * [10] C. Tian and J. Chen, “Caching and delivery via interference elimination,” IEEE Transactions on Information Theory, vol. 64, no. 3, pp. 1548–1560, 2018.
  * [11] 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, 2018.
  * [12] C. Tian, “Symmetry, outer bounds, and code constructions: A computer-aided investigation on the fundamental limits of caching,” Entropy, vol. 20, no. 8, p. 603, 2018.
  * [13] Y. Ma and D. Tuninetti, “Coded caching with linear coded placement: Exact tradeoff for the three user case,” in 2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton), IEEE, 2023.
  * [14] C.-Y. Wang, S. S. Bidokhti, and M. Wigger, “Improved converses and gap results for coded caching,” IEEE Transactions on Information Theory, vol. 64, no. 11, pp. 7051–7062, 2018.
  * [15] A. Sengupta and R. Tandon, “Improved approximation of storage-rate tradeoff for caching with multiple demands,” IEEE Transactions on Communications, vol. 65, no. 5, pp. 1940–1955, 2017.
  * [16] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, “Private information retrieval,” in Proceedings of IEEE 36th Annual Foundations of Computer Science, pp. 41–50, IEEE, 1995.
  * [17] K. Wan and G. Caire, “On coded caching with private demands,” IEEE Transactions on Information Theory, vol. 67, no. 1, pp. 358–372, 2020.
  * [18] F. Engelmann and P. Elia, “A content-delivery protocol, exploiting the privacy benefits of coded caching,” in 2017 15th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), pp. 1–6, IEEE, 2017.
  * [19] S. Kamath, “Demand private coded caching,” arXiv preprint arXiv:1909.03324, 2019.
  * [20] 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), pp. 1–6, IEEE, 2020.
  * [21] K. K. Namboodiri and B. S. Rajan, “Optimal demand private coded caching for users with small buffers,” in 2021 IEEE International Symposium on Information Theory (ISIT), pp. 706–711, IEEE, 2021.
  * [22] Q. Yan and D. Tuninetti, “Fundamental limits of caching for demand privacy against colluding users,” IEEE Journal on Selected Areas in Information Theory, vol. 2, no. 1, pp. 192–207, 2021.
  * [23] Ç. Yapar, K. Wan, R. F. Schaefer, and G. Caire, “On the optimality of d2d coded caching with uncoded cache placement and one-shot delivery,” IEEE Transactions on Communications, vol. 67, no. 12, pp. 8179–8192, 2019.
  * [24] H. Ghasemi and A. Ramamoorthy, “Asynchronous coded caching with uncoded prefetching,” IEEE/ACM Transactions on Networking, vol. 28, no. 5, pp. 2146–2159, 2020.
  * [25] A. T. Milad Abolpour, MohammadJavad Salehi, “Cache-aided communications in miso networks with dynamic user behavior: A universal solution,” in 2023 IEEE International Symposium on Information Theory (ISIT), pp. 132–137, IEEE, 2023.
  * [26] J. Liao and O. Tirkkonen, “Fundamental rate-memory tradeoff for coded caching in presence of user inactivity,” arXiv preprint arXiv:2109.14680, 2021\.
  * [27] Q. Yan and D. Tuninetti, “Robust, private and secure cache-aided scalar linear function retrieval from coded servers,” IEEE Journal on Selected Areas in Communications, vol. 40, no. 3, pp. 968–981, 2022.
  * [28] K. Wan, H. Sun, M. Ji, D. Tuninetti, and G. Caire, “On the optimal load-memory tradeoff of cache-aided scalar linear function retrieval,” IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 4001–4018, 2021.
  * [29] M. A. Maddah-Ali and U. Niesen, “Decentralized coded caching attains order-optimal memory-rate tradeoff,” IEEE/ACM Transactions On Networking, vol. 23, no. 4, pp. 1029–1040, 2014.