scheme for the $({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})$ non-secure problem.

We then consider the case where
$0<|{\mathcal{A}}_{2}|\leq{\mathsf{N}}-{\mathsf{M}}$ and from the answers of
${\mathcal{A}}_{1}$ the user cannot recover the task function. Assume the
number of linearly independent combinations of messages transmitted by the
servers in ${\mathcal{A}}_{1}$ is $\lambda_{1}$. Besides the answers of the
servers in ${\mathcal{A}}_{1}$, if the user obtains any
$h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-\lambda_{1}$ linear combinations
in ${\bf F}[W_{1};\ldots;W_{{\mathsf{N}}}]$, which are all independent of the
answers of the servers in ${\mathcal{A}}_{1}$, the user can recover ${\bf
F}[W_{1};\ldots;W_{{\mathsf{N}}}]$.999 The reason is as follows. In each of
the proposed schemes (except a special case in Scheme 3), from the answers of
any ${\mathsf{N}}_{\rm r}$ responding servers, the user can recover the
transmissions by all servers. The only special case is in Scheme 3 when the
set of responding servers contains one server in
$\left[\frac{{\mathsf{M}}}{2}\right]$ and one server in
$\left[\frac{{\mathsf{M}}}{2}+1:{\mathsf{M}}\right]$. However, if
${\mathcal{A}}_{1}$ contains such two servers, the user can directly recover
the task function; otherwise, we can find ${\mathsf{N}}_{\rm
r}-|{\mathcal{A}}_{1}|$ servers in $[{\mathsf{M}}+1:{\mathsf{N}}]$, such that
from the answers of the total ${\mathsf{N}}_{\rm r}$ servers, the user can
recover the transmissions by all servers.  In Appendix E, we will prove the
following lemma.

######  Lemma 3.

The answers in servers ${\mathcal{A}}_{2}$ contains
$h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-\lambda_{1}$ linear combinations,
independent of the answers of the servers in ${\mathcal{A}}_{1}$ with high
probability.

By Lemma 3, from the answers of servers in ${\mathcal{A}}$, the user can
recover ${\bf F}[W_{1};\ldots;W_{{\mathsf{N}}}]$.

In conclusion, we have
$h({\mathsf{N}},{\mathsf{M}})=h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})$,
which coincides with (33). We have proved that if $a_{j}$ where
$j\in[h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-1]$ is generated uniformly
i.i.d. over $\mathbb{F}_{{\mathsf{q}}}$, the user can recover the task
function with high probability. Hence, we only need to pick one realization of
them, such that we can guarantee the successful decoding.

##  V Conclusions

In this paper, we formulated the secure distributed linearly separable
computation problem, where the user should only recover the desired task
function without retrieving any other information about the datasets. It is
interesting to see that to preserve this security, we need not to increase the
communication cost if the computing scheme is based on linear coding. We then
focused on the problem where the computation cost is minimum. In this case,
while achieving the optimal communication cost, we aim to minimize the size of
the randomness variable which is independent of the datasets and is introduced
in the system to preserve the security. For this purpose, we proposed an
information theoretic converse bound on the randomness size for each possible
assignment. We then proposed a secure computing scheme with novel assignment
strategies, which outperforms the optimal computing schemes with the well-know
fractional repetition assignment and cyclic assignment in terms of the
randomness size. Exact optimality results have been obtained from the proposed
computing scheme under some system parameters. Ongoing work includes deriving
tighter converse bounds over all possible assignments and minimizing the
needed randomness size for more general case where the computation cost is not
minimum and the user requests multiple linear combinations of messages.

##  Appendix A Proof of Theorem 2

We consider the distributed linearly separable computation problem in [6]
where
${\mathsf{M}}=\frac{{\mathsf{K}}}{{\mathsf{N}}}({\mathsf{N}}-{\mathsf{N}}_{\rm
r}+{\mathsf{m}})$ for ${\mathsf{m}}\in[{\mathsf{N}}_{\rm r}]$ and the user
requests ${\mathsf{K}}_{\rm c}\in[{\mathsf{K}}]$ linearly independent
combinations of messages. We now describe on a general linear coding computing
scheme. In this scheme, we divide each message $W_{k}$ where
$k\in[{\mathsf{K}}]$ into $\ell$ non-overlapping and equal-length sub-
messages, $W_{k}=\\{W_{k,i}:i\in[\ell]\\}$. Server $n\in[{\mathsf{N}}]$ sends
$\frac{\ell T_{n}}{{\mathsf{L}}}$ linearly independent combinations of
$W_{1,1},W_{1,2},\ldots,W_{{\mathsf{K}},\ell}$.

Considering the transmitted linear combinations by all servers, the number of
linearly independent combinations is denoted by $\lambda$ and these $\lambda$
linear combinations can be expressed as ${\bf
F}[W_{1,1};W_{1,2};\ldots;W_{{\mathsf{K}},\ell}]$, where

$\displaystyle{\bf F}=\begin{bmatrix}{\mathbf{f}}_{1}\\\ \vdots\\\
{\mathbf{f}}_{\lambda}\end{bmatrix}\
=\begin{bmatrix}f_{1,1}&\cdots&f_{1,\ell{\mathsf{K}}}\\\
\vdots&\ddots&\vdots\\\
f_{\lambda,1}&\cdots&f_{\lambda,\ell{\mathsf{K}}}\end{bmatrix}.$ (43)

Notice that any linear scheme can be transformed in the above manner. Among
the linear combinations in (43),
${\mathbf{f}}_{i}[W_{1,1};W_{1,2};\ldots;W_{{\mathsf{K}},\ell}]$ where
$i\in[\ell{\mathsf{K}}_{\rm c}]$ represent the desired task function of the
user. The transmission of each server $n\in[{\mathsf{N}}]$ can be express as

$\displaystyle\mathbf{S}_{n}\ {\bf F}\
[W_{1,1};W_{1,2};\ldots;W_{{\mathsf{K}},\ell}],$ (44)

where the dimension of $\mathbf{S}_{n}$ is $\frac{\ell
T_{n}}{{\mathsf{L}}}\times\lambda$.

For any set of ${\mathsf{N}}_{\rm r}$ responding servers (denoted by
${\mathcal{A}}=\\{{\mathcal{A}}(1),\ldots,{\mathcal{A}}({\mathsf{N}}_{\rm
r})\\}$), the user receives

$\mathbf{S}_{{\mathcal{A}}}\ {\bf F}\
[W_{1,1};W_{1,2};\ldots;W_{{\mathsf{K}},\ell}]$

where $\mathbf{S}_{{\mathcal{A}}}$ represents the row-wise sub-matrix of
$\left[\mathbf{S}_{{\mathcal{A}}(1)};\ldots;\mathbf{S}_{{\mathcal{A}}({\mathsf{N}}_{\rm
r})}\right]$ which has the same rank as
$\left[\mathbf{S}_{{\mathcal{A}}(1)};\ldots;\mathbf{S}_{{\mathcal{A}}({\mathsf{N}}_{\rm
r})}\right]$. Assume $\mathbf{S}_{{\mathcal{A}}}$ contains $r_{{\mathcal{A}}}$
rows. In the decoding phase, the user multiply $\mathbf{S}_{{\mathcal{A}}}{\bf
F}[W_{1,1};W_{1,2};\ldots;W_{{\mathsf{K}},\ell}]$ by
$\mathbf{D}_{{\mathcal{A}}}$, where the dimension of
$\mathbf{D}_{{\mathcal{A}}}$ is $\ell{\mathsf{K}}_{\rm c}\times
r_{{\mathcal{A}}}$ and

$\displaystyle\mathbf{D}_{{\mathcal{A}}}\
\mathbf{S}_{{\mathcal{A}}}=[\mathbf{I}_{\ell{\mathsf{K}}_{\rm c}},{\bf
0}_{\ell{\mathsf{K}}_{\rm c}\times(r_{{\mathcal{A}}}-\ell{\mathsf{K}}_{\rm
c})}],$ (45)

where $\mathbf{I}_{n}$ represents the identity matrix with dimension $n\times
n$ and ${\bf 0}_{m\times n}$ represents the zero matrix with dimension
$m\times n$. Hence, the user can recover the desired task function from
$\mathbf{D}_{{\mathcal{A}}}\mathbf{S}_{{\mathcal{A}}}{\bf
F}[W_{1,1};W_{1,2};\ldots;W_{{\mathsf{K}},\ell}]$.

Now we take the security constraint (10) into consideration, and extend the
above general linear coding scheme. We introduce
$\lambda-\ell{\mathsf{K}}_{\rm c}$ independent randomness variables
$Q_{1},\ldots,Q_{\lambda-\ell{\mathsf{K}}_{\rm c}}$, where
$Q_{i},i\in[\lambda-\ell{\mathsf{K}}_{\rm c}]$ is uniformly i.i.d. over
$[\mathbb{F}_{{\mathsf{q}}}]^{\frac{{\mathsf{L}}}{\ell}}$. We then let ${\bf
F}^{\prime}=[{\bf F},\mathbf{S}],$ where $\mathbf{S}=[{\bf
0}_{\ell{\mathsf{K}}_{\rm c}\times(\lambda-\ell{\mathsf{K}}_{\rm
c})};\mathbf{S}^{\prime}]$ and $\mathbf{S}^{\prime}$ is full-rank with
dimension $(\lambda-\ell{\mathsf{K}}_{\rm
c})\times(\lambda-\ell{\mathsf{K}}_{\rm c})$.

We let each server $n\in[{\mathsf{N}}]$ transmit

$\displaystyle\mathbf{S}_{n}\ {\bf F}^{\prime}\
[W_{1,1};W_{1,2};\ldots;W_{{\mathsf{K}},\ell};Q_{1};\ldots;Q_{\lambda-\ell{\mathsf{K}}_{\rm
c}}],$ (46)

where $\mathbf{S}_{n}$ is the same as that in (44). It can be seen that in the
transmitted linear combinations (46), the coefficients of the sub-messages
which server $n$ cannot compute are still $0$ as the original non-secure
scheme.

For any set of ${\mathsf{N}}_{\rm r}$ responding servers ${\mathcal{A}}$, the
user receives

$\mathbf{S}_{{\mathcal{A}}}\ {\bf F}^{\prime}\
[W_{1,1};W_{1,2};\ldots;W_{{\mathsf{K}},\ell}],$

and recovers its desired task function from
$\mathbf{D}_{{\mathcal{A}}}\mathbf{S}_{{\mathcal{A}}}{\bf
F}^{\prime}[W_{1,1};W_{1,2};\ldots;W_{{\mathsf{K}},\ell};Q_{1};\ldots;Q_{\lambda-\ell{\mathsf{K}}_{\rm
c}}],$ since (45) holds.

Finally, we will prove that the above scheme is secure, i.e., the security
constraint (10) holds. From the answers of all servers, the user can only
recover totally $\lambda$ linearly independent combinations, which are

$\displaystyle{\bf F}^{\prime}\
[W_{1,1};W_{1,2};\ldots;W_{{\mathsf{K}},\ell};Q_{1};\ldots;Q_{\lambda-\ell{\mathsf{K}}_{\rm
c}}].$ (47)

In addition, $\mathbf{S}^{\prime}$ is full-rank (with rank equal to
$\lambda-\ell{\mathsf{K}}_{\rm c}$). Hence, the user can only recover the
desired task function (i.e., the first $\ell{\mathsf{K}}_{\rm c}$ linear
combinations in (47)) without $Q_{1},\ldots,Q_{\lambda-\ell{\mathsf{K}}_{\rm
c}}$, and thus the above scheme is secure.

##  Appendix B Proof of Theorem 3

By the security constraint in (10), the user can only obtain
$W_{1}+\cdots+W_{{\mathsf{K}}}$ without knowing any other information about
the messages after receiving the answers of all servers. Recall that
$X_{{\mathcal{S}}}=\\{X_{n}:n\in{\mathcal{S}}\\}$. Intuitively by [23], we
need a key with length at least
$H(X_{[{\mathsf{N}}]})-H(W_{1}+\cdots+W_{{\mathsf{K}}})$ such that except
$W_{1}+\cdots+W_{{\mathsf{K}}}$, the other information about
$W_{1},\ldots,W_{{\mathsf{K}}}$ transmitted in $X_{[{\mathsf{N}}]}$ is hidden.
More precisely, from (10) we have

$\displaystyle 0$
$\displaystyle=I\big{(}W_{1},\ldots,W_{{\mathsf{K}}};X_{[{\mathsf{N}}]}|W_{1}+W_{2}+\cdots+W_{{\mathsf{K}}}\big{)}$
(48a)
$\displaystyle=H(X_{[{\mathsf{N}}]}|W_{1}+W_{2}+\cdots+W_{{\mathsf{K}}})-H(X_{[{\mathsf{N}}]}|W_{1},\ldots,W_{{\mathsf{K}}})$
(48b) $\displaystyle\geq
H(X_{[{\mathsf{N}}]}|W_{1}+W_{2}+\cdots+W_{{\mathsf{K}}})-H(Q,W_{1},\ldots,W_{{\mathsf{K}}}|W_{1},\ldots,W_{{\mathsf{K}}})$
(48c)
$\displaystyle=H(X_{[{\mathsf{N}}]}|W_{1}+W_{2}+\cdots+W_{{\mathsf{K}}})-H(Q)$
(48d)
$\displaystyle=H(X_{[{\mathsf{N}}]})-I(X_{[{\mathsf{N}}]};W_{1}+W_{2}+\cdots+W_{{\mathsf{K}}})-H(Q)$
(48e) $\displaystyle\geq
H(X_{[{\mathsf{N}}]})-H(W_{1}+W_{2}+\cdots+W_{{\mathsf{K}}})-H(Q)$ (48f)

where (48c) comes from that the $X_{[{\mathsf{N}}]}$ is a function of
$Q,W_{1},\ldots,W_{{\mathsf{K}}}$, (48d) comes from that $Q$ is independent of
$W_{1},\ldots,W_{{\mathsf{K}}}$. Hence, from (48f) and we have

$\displaystyle\eta{\mathsf{L}}\geq H(Q)\geq
H(X_{[{\mathsf{N}}]})-H(W_{1}+\cdots+W_{{\mathsf{K}}})$ (49a)
$\displaystyle\geq H(X_{[{\mathsf{N}}]})-{\mathsf{L}}$ (49b)
$\displaystyle\geq H(X_{s_{1}},\ldots,X_{s_{v}})-{\mathsf{L}}$ (49c)
$\displaystyle=H(X_{s_{1}})+H(X_{s_{2}}|X_{s_{1}})+\cdots+H(X_{s_{v}}|X_{s_{1}},\ldots,X_{s_{v-1}})-{\mathsf{L}},$
(49d)

where (49b) comes from that the ${\mathsf{K}}$ messages are independent and
each message is uniformly i.i.d. over
$[\mathbb{F}_{{\mathsf{q}}}]^{{\mathsf{L}}}$, (49d) comes from the chain rule
of entropy.

Let us then focus on each entropy term in (49d),
$H(X_{s_{i}}|X_{s_{1}},\ldots,X_{s_{i-1}})$ where $i\in[v]$. Recall that
server $s_{i}$ can compute some message (assumed to be message $W_{j}$) which
cannot be computed by servers $s_{1},\ldots,s_{i-1}$, and that each message
cannot computed by ${\mathsf{N}}_{\rm r}-1$ servers. We assume that the set of
servers which cannot compute $W_{j}$ is $\overline{{\mathcal{A}}_{j}}$.
Obviously, $\\{s_{1},\ldots,s_{i-1}\\}\subseteq\overline{{\mathcal{A}}_{j}}$.
Now consider that the set of responding servers is
$\overline{{\mathcal{A}}_{j}}\cup\\{s_{i}\\}$, totally containing
${\mathsf{N}}_{\rm r}$ servers. As $W_{j}$ can only computed by server $s_{i}$
among the servers in $\overline{{\mathcal{A}}_{j}}\cup\\{s_{i}\\}$, and from
the answers of servers in $\overline{{\mathcal{A}}_{j}}\cup\\{s_{i}\\}$ the
user should recover $W_{1}+\cdots+W_{{\mathsf{K}}}$, we have

$\displaystyle H(X_{s_{i}}|X_{s_{1}},\ldots,X_{s_{i-1}})\geq
H(X_{s_{i}}|X_{k}:k\in\overline{{\mathcal{A}}_{j}})\geq{\mathsf{L}}.$ (50)

Hence, we take (50) into (49d) to obtain,

$\displaystyle\eta{\mathsf{L}}\geq v{\mathsf{L}}-{\mathsf{L}},$ (51)

which proves (18).

##  Appendix C Proof of Theorem 7

We first introduce the following lemma which will be proved in Appendix C-D
and will be used in the proof of Theorem 7.

######  Lemma 4.

For the $({\mathsf{K}},{\mathsf{N}},{\mathsf{N}}_{\rm r},{\mathsf{K}}_{\rm
c},{\mathsf{M}})$ secure distributed linearly separable computation problem
with ${\mathsf{M}}=\frac{{\mathsf{K}}}{{\mathsf{N}}}{\mathsf{M}}^{\prime}$,
${\mathsf{K}}_{\rm c}=1$,
$\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\geq
3$, and
$\text{Mod}\left(\frac{{\mathsf{N}}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})},\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\right)=\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}-1$,
to achieve the optimal communication cost, it must hold that

$\displaystyle\eta^{\star}\geq\left\lceil{\mathsf{N}}/{\mathsf{M}}^{\prime}\right\rceil.$
(52)

$\square$

We then start to prove Theorem 7 and focus on the
$({\mathsf{K}},{\mathsf{N}},{\mathsf{N}}_{\rm r},{\mathsf{K}}_{\rm
c},{\mathsf{M}})$ secure distributed linearly separable computation problem
where ${\mathsf{M}}=\frac{{\mathsf{K}}}{{\mathsf{N}}}{\mathsf{M}}^{\prime}$,
${\mathsf{K}}_{\rm c}=1$, and
$\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\leq
4$. Notice that when
$\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}=1$
(i.e., ${\mathsf{M}}^{\prime}$ divides ${\mathsf{N}}$), the optimality
directly comes from Theorem 4. Hence, in the following, we consider the case
where
$\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\in[2:4]$.

###  C-A
$\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}=2$

When
$\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}=2$,
it can be seen that
$\text{Mod}\left(\frac{{\mathsf{N}}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})},\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\right)=1$.
Hence, by the proposed scheme for Theorem 6, the needed randomness size is

$\displaystyle h({\mathsf{N}},{\mathsf{M}}^{\prime})-1$
$\displaystyle=h\left(\frac{{\mathsf{N}}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})},\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\right)-1$
(53a)
$\displaystyle=\left\lfloor{\mathsf{N}}/{\mathsf{M}}^{\prime}-1\right\rfloor+h(3,2)-1$
(53b)
$\displaystyle=\left\lfloor{\mathsf{N}}/{\mathsf{M}}^{\prime}-1\right\rfloor+2-1=\left\lceil{\mathsf{N}}/{\mathsf{M}}^{\prime}\right\rceil-1,$
(53c)

where (53a) comes from (29), (53b) comes from (30), (53c) comes from that
$h(3,2)=2$ and that
$\left\lfloor{\mathsf{N}}/{\mathsf{M}}^{\prime}+1\right\rfloor=\left\lceil{\mathsf{N}}/{\mathsf{M}}^{\prime}\right\rceil$
since ${\mathsf{M}}^{\prime}$ does not divide ${\mathsf{N}}$. It can be seen
that the needed randomness size (53c) coincides with the converse bound in
Corollary 2, and thus is optimal.

###  C-B
$\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}=3$

When
$\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}=3$,
it can be seen that
$\text{Mod}\left(\frac{{\mathsf{N}}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})},\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\right)\in[2]$.

For the case where
$\text{Mod}\left(\frac{{\mathsf{N}}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})},\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\right)=1$,
by the proposed scheme for Theorem 6, the needed randomness size is

$\displaystyle h({\mathsf{N}},{\mathsf{M}}^{\prime})-1$
$\displaystyle=h\left(\frac{{\mathsf{N}}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})},\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\right)-1$
(54a)
$\displaystyle=\left\lfloor{\mathsf{N}}/{\mathsf{M}}^{\prime}-1\right\rfloor+h(4,3)-1$
(54b)
$\displaystyle=\left\lfloor{\mathsf{N}}/{\mathsf{M}}^{\prime}-1\right\rfloor+2-1=\left\lceil{\mathsf{N}}/{\mathsf{M}}^{\prime}\right\rceil-1,$
(54c)

where (54a) comes from (29), (54b) comes from (30), and (54c) comes from that
$h(4,3)=2$. The needed randomness size in (54c) coincides with the converse
bound in Corollary 2, and thus is optimal.

For the case where
$\text{Mod}\left(\frac{{\mathsf{N}}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})},\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\right)=2$,
by the proposed scheme for Theorem 6, the needed randomness size is

$\displaystyle h({\mathsf{N}},{\mathsf{M}}^{\prime})-1$
$\displaystyle=h\left(\frac{{\mathsf{N}}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})},\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\right)-1$
(55a)
$\displaystyle=\left\lfloor{\mathsf{N}}/{\mathsf{M}}^{\prime}-1\right\rfloor+h(5,3)-1$
(55b)
$\displaystyle=\left\lfloor{\mathsf{N}}/{\mathsf{M}}^{\prime}-1\right\rfloor+3-1=\left\lceil{\mathsf{N}}/{\mathsf{M}}^{\prime}\right\rceil,$
(55c)

where (55a) comes from (29), (55b) comes from (30), and (55c) comes from that
$h(5,3)=3$. The needed randomness size in (55c) coincides with the converse
bound in Lemma 4, and thus is optimal.

###  C-C
$\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}=4$

When
$\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}=4$,
it can be seen that
$\text{Mod}\left(\frac{{\mathsf{N}}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})},\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\right)\in\\{1,3\\}$.

For the case where
$\text{Mod}\left(\frac{{\mathsf{N}}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})},\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\right)=1$,
by the proposed scheme for Theorem 6, the needed randomness size is

$\displaystyle h({\mathsf{N}},{\mathsf{M}}^{\prime})-1$
$\displaystyle=h\left(\frac{{\mathsf{N}}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})},\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\right)-1$
(56a)
$\displaystyle=\left\lfloor{\mathsf{N}}/{\mathsf{M}}^{\prime}-1\right\rfloor+h(5,4)-1$
(56b)
$\displaystyle=\left\lfloor{\mathsf{N}}/{\mathsf{M}}^{\prime}-1\right\rfloor+2-1=\left\lceil{\mathsf{N}}/{\mathsf{M}}^{\prime}\right\rceil-1,$
(56c)

where (56a) comes from (29), (56b) comes from (30), and (56c) comes from that
$h(5,4)=2$. The needed randomness size in (56c) coincides with the converse
bound in Corollary 2, and thus is optimal.

For the case where
$\text{Mod}\left(\frac{{\mathsf{N}}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})},\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\right)=3$,
by the proposed scheme for Theorem 6, the needed randomness size is

$\displaystyle h({\mathsf{N}},{\mathsf{M}}^{\prime})-1$
$\displaystyle=h\left(\frac{{\mathsf{N}}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})},\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\right)-1$
(57a)
$\displaystyle=\left\lfloor{\mathsf{N}}/{\mathsf{M}}^{\prime}-1\right\rfloor+h(7,4)-1$
(57b)
$\displaystyle=\left\lfloor{\mathsf{N}}/{\mathsf{M}}^{\prime}-1\right\rfloor+3-1=\left\lceil{\mathsf{N}}/{\mathsf{M}}^{\prime}\right\rceil,$
(57c)

where (57a) comes from (29), (57b) comes from (30), and (57c) comes from that
$h(7,4)=3$. The needed randomness size in (57c) coincides with the converse
bound in Lemma 4, and thus is optimal.

###  C-D Proof of Lemma 4

Recall that
${\mathsf{M}}=\frac{{\mathsf{K}}}{{\mathsf{N}}}{\mathsf{M}}^{\prime}$, and
that
$\text{Mod}\left(\frac{{\mathsf{N}}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})},\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\right)=\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}-1$.
For the ease of notation, we let
${\mathsf{a}}:=\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}$.
By the constraints in Lemma 4, we have ${\mathsf{a}}\geq 3$.

We assume that
${\mathsf{N}}=(2{\mathsf{a}}-1+{\mathsf{a}}{\mathsf{b}})\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})$,
where ${\mathsf{b}}$ is a non-negative integer. To prove (52), it is
equivalent to prove

$\eta\geq\left\lceil{\mathsf{N}}/{\mathsf{M}}^{\prime}\right\rceil=\left\lceil
2+{\mathsf{b}}-\frac{1}{{\mathsf{a}}}\right\rceil={\mathsf{b}}+2.$

In the following we use the induction method to prove that for any assignment,
there must exist some ordered set of ${\mathsf{b}}+3$ servers satisfying the
constraint in (17).

Proof step 1. We first consider the case where ${\mathsf{b}}=0$, and aim to
prove that for any possible assignment, we can always find an ordered set of
three servers ${\mathbf{s}}=(s_{1},s_{2},s_{3})$ such that server $s_{2}$ has
some dataset not assigned to server $s_{1}$ and server $s_{3}$ has some
dataset not assigned to servers $s_{1},s_{2}$.

In this case,
${\mathsf{N}}=2{\mathsf{M}}^{\prime}-\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})$.
For any possible assignment, each dataset is assigned to
${\mathsf{M}}^{\prime}$ servers, and each server has (recall that
${\mathsf{a}}:=\frac{{\mathsf{M}}^{\prime}}{\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}\geq
3$)

${\mathsf{M}}=\frac{{\mathsf{K}}}{{\mathsf{N}}}{\mathsf{M}}^{\prime}=\frac{{\mathsf{M}}^{\prime}{\mathsf{K}}}{2{\mathsf{M}}^{\prime}-\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})}=\frac{{\mathsf{a}}{\mathsf{K}}}{2{\mathsf{a}}-1}$

datasets. It can be seen that
$\frac{{\mathsf{K}}}{2}<{\mathsf{M}}<\frac{2}{3}{\mathsf{K}}$. We can prove
that there exist two servers (assumed to be server $s_{1},s_{2}$) such that
${\mathcal{Z}}_{s_{1}}\neq{\mathcal{Z}}_{s_{2}}$ and
${\mathcal{Z}}_{s_{1}}\cup{\mathcal{Z}}_{s_{2}}\neq[{\mathsf{K}}]$.101010 As
$\frac{{\mathsf{K}}}{2}<{\mathsf{M}}<\frac{2}{3}{\mathsf{K}}$, there must be
three servers with three different sets of obtained datasets. We denote these
three servers by servers $n_{1},n_{2},n_{3}$. We then prove by contradiction
that there exist two servers in $\\{n_{1},n_{2},n_{3}\\}$, where some dataset
is not assigned to any of them. Assume that
${\mathcal{Z}}_{n_{1}}\cup{\mathcal{Z}}_{n_{2}}=[{\mathsf{K}}]$,
${\mathcal{Z}}_{n_{1}}\cup{\mathcal{Z}}_{n_{3}}=[{\mathsf{K}}]$, and
${\mathcal{Z}}_{n_{2}}\cup{\mathcal{Z}}_{n_{3}}=[{\mathsf{K}}]$. Hence, each
dataset must be assigned to at least two servers in $\\{n_{1},n_{2},n_{3}\\}$,
and thus there are at least $2{\mathsf{K}}/3$ datasets assigned to each
server, which contradicts ${\mathsf{M}}<\frac{2}{3}{\mathsf{K}}$.  Assumed
that dataset $D_{k}$ is not assigned to server $s_{1},s_{2}$. We then pick one
server which has dataset $D_{k}$ (assumed to be server $s_{3}$). It can be see
that the ordered set of servers $(s_{1},s_{2},s_{3})$ satisfies the constraint
in (17).

Proof step 2. We then focus on the case where ${\mathsf{b}}=1$. In this case,

$\displaystyle{\mathsf{N}}=(3{\mathsf{a}}-1)\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})=3{\mathsf{M}}^{\prime}-\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime}),$
$\displaystyle{\mathsf{K}}=\frac{{\mathsf{K}}}{{\mathsf{N}}}{\mathsf{N}}=3\frac{{\mathsf{K}}}{{\mathsf{N}}}{\mathsf{M}}^{\prime}-\frac{{\mathsf{K}}}{{\mathsf{N}}}\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})=3{\mathsf{M}}-\frac{{\mathsf{K}}}{{\mathsf{N}}}\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime}).$

Hence,
${\mathsf{K}}-{\mathsf{M}}=2{\mathsf{M}}-\frac{{\mathsf{K}}}{{\mathsf{N}}}\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})>2{\mathsf{M}}-\frac{{\mathsf{K}}}{{\mathsf{N}}}{\mathsf{M}}^{\prime}={\mathsf{M}}$.
WLOG, we assume that server $1$ has datasets $D_{1},\ldots,D_{{\mathsf{M}}}$.
Let us then focus on the datasets
$D_{{\mathsf{M}}+1},\ldots,D_{{\mathsf{K}}}$, and consider the following two
cases:

  * •

Case 1: among
${\mathcal{Z}}_{2}\cap[{\mathsf{M}}+1:{\mathsf{K}}],\ldots,{\mathcal{Z}}_{{\mathsf{N}}}\cap[{\mathsf{M}}+1:{\mathsf{K}}]$,
there are at least three different non-empty sets. As shown before, there must
exist an ordered set of three servers in $[2:{\mathsf{N}}]$, which is assumed
to be $(s_{1},s_{2},s_{3})$, satisfying the constraint in (17). In addition,
server $1$ does not have any datasets in $[{\mathsf{M}}+1:{\mathsf{K}}]$.
Hence, the ordered set of servers $(1,s_{1},s_{2},s_{3})$ also satisfies the
constraint in (17).

  * •

Case 2: among
${\mathcal{Z}}_{2}\cap[{\mathsf{M}}+1:{\mathsf{K}}],\ldots,{\mathcal{Z}}_{{\mathsf{N}}}\cap[{\mathsf{M}}+1:{\mathsf{K}}]$,
there are only two different non-empty sets. In this case, there are
${\mathsf{M}}^{\prime}$ servers (assumed to be ${\mathcal{V}}_{1}$) whose
obtained datasets in $[{\mathsf{M}}+1:{\mathsf{K}}]$ are non-empty and the
same; there are other ${\mathsf{M}}^{\prime}$ servers (assumed to be
${\mathcal{V}}_{2}$) whose obtained datasets in
$[{\mathsf{M}}+1:{\mathsf{K}}]$ are non-empty and the same. We then consider
the sets ${\mathcal{Z}}_{n}$ where
$n\in({\mathcal{V}}_{1}\cup{\mathcal{V}}_{2})$. It is not possible that there
are only two different sets among them, because the datasets in
$[{\mathsf{M}}]$ are only assigned to the servers in
$[{\mathsf{N}}]\setminus({\mathcal{V}}_{1}\cup{\mathcal{V}}_{2})$ where
$|[{\mathsf{N}}]\setminus({\mathcal{V}}_{1}\cup{\mathcal{V}}_{2})|<{\mathsf{M}}^{\prime}$.
Hence, there must exist at least three different sets among
${\mathcal{Z}}_{n}$ where $n\in({\mathcal{V}}_{1}\cup{\mathcal{V}}_{2})$. Thus
there must be an ordered set of three servers in
$({\mathcal{V}}_{1}\cup{\mathcal{V}}_{2})$ satisfying the constraint in (17),
which is assumed to be $(s_{1},s_{2},s_{3})$. In addition, in the union set of
the assigned datasets to these three servers, there are at most
$2{\mathsf{M}}-({\mathsf{K}}-{\mathsf{M}})<{\mathsf{M}}$ datasets in
$[{\mathsf{M}}]$. Hence, the ordered set of servers $(s_{1},s_{2},s_{3},1)$
also satisfies the constraint in Theorem 3

Proof step 3. Finally, we assume when ${\mathsf{b}}\in[x]$, there exists some
ordered set of servers $(s_{1},\ldots,s_{{\mathsf{b}}+3})$ satisfying the
constraint in Theorem 3. We will show that when ${\mathsf{b}}=x+1$, there
exists some ordered set of servers $(s_{1},\ldots,s_{x+4})$ satisfying the
constraint in Theorem 3.

In this case,

$\displaystyle{\mathsf{N}}=((3+x){\mathsf{a}}-1)\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})=(3+x){\mathsf{M}}^{\prime}-\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime}),$
$\displaystyle{\mathsf{K}}=\frac{{\mathsf{K}}}{{\mathsf{N}}}{\mathsf{N}}=(3+x)\frac{{\mathsf{K}}}{{\mathsf{N}}}{\mathsf{M}}^{\prime}-\frac{{\mathsf{K}}}{{\mathsf{N}}}\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})=(3+x){\mathsf{M}}-\frac{{\mathsf{K}}}{{\mathsf{N}}}\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime}).$

Hence, we have $(x+2){\mathsf{M}}<{\mathsf{K}}<(x+3){\mathsf{M}}$. As there
are ${\mathsf{K}}$ datasets, each of which is assigned to
${\mathsf{M}}^{\prime}$ servers, and the number of datasets assigned to each
server is ${\mathsf{M}}$, we can find $x+1$ servers where each server has some
dataset not assigned to other $x$ servers.

If there exists some server $j\in[x+1]$ where at least
$\frac{{\mathsf{K}}}{{\mathsf{N}}}\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})+1$
datasets assigned to server $j$ have also been assigned to some other server
in $[x+1]\setminus\\{j\\}$, it can be seen that there are at least

${\mathsf{K}}-(x+1){\mathsf{M}}+\frac{{\mathsf{K}}}{{\mathsf{N}}}\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})+1=2{\mathsf{M}}+1$

datasets not assigned to $[x+1]$; thus we can find three servers which has
some dataset not assigned to the servers in $[x+1]$ nor the other two servers.
Hence, we can find an ordered set of $x+4$ servers satisfying the constraint
in (17).

Hence, in the following we consider that at most
$\frac{{\mathsf{K}}}{{\mathsf{N}}}\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})$
datasets assigned to each server in $[x+1]$ have also been assigned to some
other server in $[x+1]$. There are totally at most $(x+1){\mathsf{M}}$
different datasets to these $x+1$ servers, and thus there remains at least
${\mathsf{K}}-(x+1){\mathsf{M}}=2{\mathsf{M}}-\frac{{\mathsf{K}}}{{\mathsf{N}}}\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})$
datasets which are not assigned to these $x+1$ servers. WLOG, we assume that
the $x+1$ servers are in $[x+1]$ and these
$2{\mathsf{M}}-\frac{{\mathsf{K}}}{{\mathsf{N}}}\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})$
datasets are $D_{(x+1){\mathsf{M}}+1},\ldots,D_{{\mathsf{K}}}$.

We then consider two cases:

  * •

Case 1: among
${\mathcal{Z}}_{x+2}\cap[(x+1){\mathsf{M}}+1:{\mathsf{K}}],\ldots,{\mathcal{Z}}_{{\mathsf{N}}}\cap[(x+1){\mathsf{M}}+1:{\mathsf{K}}]$,
there are at least three different non-empty sets. As shown before, there must
exist an ordered set of three servers in $[x+2:{\mathsf{N}}]$, which is
assumed to be $(s_{1},s_{2},s_{3})$, satisfying the constraint in (17). In
addition, servers in $[x+1]$ do not have any datasets in
$[{\mathsf{M}}+1:{\mathsf{K}}]$. Hence, the ordered set of servers
$(1,2,\ldots,x+1,s_{1},s_{2},s_{3})$ also satisfies the constraint in (17).

  * •

Case 2: among
${\mathcal{Z}}_{x+2}\cap[(x+1){\mathsf{M}}+1:{\mathsf{K}}],\ldots,{\mathcal{Z}}_{{\mathsf{N}}}\cap[(x+1){\mathsf{M}}+1:{\mathsf{K}}]$,
there are only two different non-empty sets. In this case, there are
${\mathsf{M}}^{\prime}$ servers (assumed to be ${\mathcal{V}}_{1}$) whose
obtained datasets in $[(x+1){\mathsf{M}}+1:{\mathsf{K}}]$ are non-empty and
the same; there are other ${\mathsf{M}}^{\prime}$ servers (assumed to be
${\mathcal{V}}_{2}$) whose obtained datasets in
$[(x+1){\mathsf{M}}+1:{\mathsf{K}}]$ are non-empty and the same. We then
consider the sets ${\mathcal{Z}}_{n}$ where
$n\in({\mathcal{V}}_{1}\cup{\mathcal{V}}_{2})$.

    * –

If there are two different sets among them, we have completely assigned
$2{\mathsf{M}}$ datasets to $2{\mathsf{M}}^{\prime}$ servers, each of which
has ${\mathsf{M}}$ datasets. Hence, if we focus on the assignment for the
servers in $[{\mathsf{N}}]\setminus({\mathcal{V}}_{1}\cup{\mathcal{V}}_{2})$,
the assignment is equivalent to the problem where we assign
${\mathsf{K}}_{1}={\mathsf{K}}-2{\mathsf{M}}$ datasets to
${\mathsf{N}}_{1}={\mathsf{N}}-2{\mathsf{M}}^{\prime}=(2{\mathsf{a}}-1+(x-1){\mathsf{a}})\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})$
servers, where each dataset is assigned to ${\mathsf{M}}^{\prime}$ servers and
the number of assigned datasets to each server is ${\mathsf{M}}$. Therefore,
we can use the induction assumption to find an ordered set of $(x-1)+3=x+2$
servers satisfying the constraint in (17), which are assumed to be servers
$(s_{1},\ldots,s_{x+2})$. In addition, we can pick two server in
${\mathcal{V}}_{1}\cup{\mathcal{V}}_{2}$ with different sets of datasets,
which are assumed to be servers $s_{x+3},s_{x+4}$. In summary, the ordered set
of servers $(s_{1},\ldots,s_{x+4})$ also satisfies the constraint in (17).

    * –

If there are at least three different sets among them, we can find an ordered
set of three servers in $({\mathcal{V}}_{1}\cup{\mathcal{V}}_{2})$ satisfying
the constraint in (17), which is assumed to be $(s_{1},s_{2},s_{3})$. In
addition, in the union set of the assigned datasets to these three servers,
there are at most
$2{\mathsf{M}}-({\mathsf{K}}-(x+1){\mathsf{M}})=\frac{{\mathsf{K}}}{{\mathsf{N}}}\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})$
datasets in $[(x+1){\mathsf{M}}]$. In addition, each server in $[x+1]$ has
${\mathsf{M}}\geq
3\frac{{\mathsf{K}}}{{\mathsf{N}}}\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})$
datasets and at most
$\frac{{\mathsf{K}}}{{\mathsf{N}}}\text{GCD}({\mathsf{N}},{\mathsf{M}}^{\prime})$
datasets assigned to each server in $[x+1]$ have also been assigned to some
other server in $[x+1]$. As a result, the ordered set of servers
$(s_{1},s_{2},s_{3},1,2,\ldots,x+1)$ satisfies the constraint in (17).

In conclusion, by the induction method, we proved Lemma 4.

##  Appendix D Proof of Decodability of Scheme 4

###  D-A Proof of Lemma 1

Recall that for each server $n\in[{\mathsf{y}}+1:{\mathsf{M}}]$, it computes a
linear combination ${\bf
s}_{n}\left[a{\mathbf{f}}_{1}-{\mathbf{f}}_{2};{\mathbf{f}}_{3};\ldots;{\mathbf{f}}_{\frac{{\mathsf{M}}+5}{2}-{\mathsf{y}}}\right]$,
where ${\bf s}_{n}$ is a random linear combination of the two linearly
independent vectors in the left-hand side nullspace of
$\frac{{\mathsf{M}}-1}{2}-{\mathsf{y}}$ neighbouring columns in ${\bf
F}^{\prime}_{3}$. We aim to prove that for any set
${\mathcal{V}}\subseteq[{\mathsf{y}}+1:{\mathsf{M}}]$ where
$|{\mathcal{V}}|=\frac{{\mathsf{M}}+3}{2}-{\mathsf{y}}$, the vectors
${\mathbf{s}}_{n}$ where $n\in{\mathcal{V}}$ are linearly independent.

As the field size ${\mathsf{q}}$ is large enough, following the decodability
proof in [3, Appendix C] (which also proves that the transmission vectors by a
set of servers are linearly independent with high probability) based on the
Schwartz-Zippel lemma [24, 25, 26], we only need to find out one specific
realization of

${\bf F}^{\prime}_{3}=\begin{bmatrix}\ a&a&\ldots&a\\\ *&*&\ldots&*\\\
\vdots&\vdots&\vdots&\vdots\\\ *&*&\ldots&*\end{bmatrix},$

such that the vectors ${\mathbf{s}}_{n}$ where $n\in{\mathcal{V}}$ are
linearly independent.

We sort the servers in ${\mathcal{V}}$ in an increasing order,
${\mathcal{V}}=\\{v_{1},\ldots,v_{\frac{{\mathsf{M}}+3}{2}-{\mathsf{y}}}\\}$,
where $v_{i}<v_{j}$ if $i<j$. For each
$i\in[\frac{{\mathsf{M}}+1}{2}-{\mathsf{y}}]$, we let the $(i+1)^{\text{th}}$
row of ${\bf F}^{\prime}_{3}$ be

$\displaystyle[*,*,\cdots,*,0,0,\cdots,0,*,*,\cdots,*],$

where each $0$ corresponds to one distinct message which server $v_{i}$ cannot
compute.

By the construction of ${\bf F}^{\prime}_{3}$, we let the transmission vector
${\mathbf{s}}_{v_{i}}$ of each server $v_{i}$ where
$i\in[\frac{{\mathsf{M}}+1}{2}-{\mathsf{y}}]$ be as follows,111111 Notice that
${\bf F}^{\prime}_{3}$ contains $\frac{{\mathsf{M}}+3}{2}-{\mathsf{y}}$ rows,
and server $v_{i}$ cannot compute $\frac{{\mathsf{M}}-1}{2}-{\mathsf{y}}$
messages in $W_{{\mathsf{M}}+1},\ldots,W_{{\mathsf{N}}}$; thus we need to fix
two positions in ${\mathbf{s}}_{v_{i}}$ and then to determine the other
elements ${\mathbf{s}}_{v_{i}}$ by solving linear equations. More precisely,
we let the first element is $0$ and the $(i+1)^{th}$ element be $1$. With the
above construction, by the proof in [3, Appendix D], the remaining elements in
${\mathbf{s}}_{v_{i}}$ are obtained by solving linear equations, which are all
$0$.

$\displaystyle{\mathbf{s}}_{v_{i}}=[0,\cdots,0,1,0,\cdots,0],$

where ${\mathbf{s}}_{v_{i}}$ has $\frac{{\mathsf{M}}+3}{2}-{\mathsf{y}}$
elements and the $(i+1)^{th}$ element is $1$.

Let us then design the transmission vector
${\mathbf{s}}_{v_{\frac{{\mathsf{M}}+3}{2}-{\mathsf{y}}}}$ of server
$v_{\frac{{\mathsf{M}}+3}{2}-{\mathsf{y}}}$ by letting its first element be
$1$ and second element be $0$. By the proof in [3, Appendix D], the remaining
elements in ${\mathbf{s}}_{v_{\frac{{\mathsf{M}}+3}{2}-{\mathsf{y}}}}$ are
obtained by solving linear equations (but not necessary be all $0$). Hence, by
construction
${\mathbf{s}}_{v_{1}},\ldots,{\mathbf{s}}_{v_{\frac{{\mathsf{M}}+3}{2}-{\mathsf{y}}}}$
are linearly independent.

###  D-B Proof of Lemma 2

Recall that ${\mathcal{L}}_{1}$ contains
$\frac{{\mathsf{M}}+1}{2}-{\mathsf{y}}$ linearly independent combinations of
$F_{2},\ldots,f_{\frac{{\mathsf{M}}+5}{2}-{\mathsf{y}}}$, and one linear
combination $F_{1}-F_{2}$. The coefficients in these linear combinations are
independent of $a$.

Let us focus on the servers in $[{\mathsf{y}}+1:{\mathsf{M}}]$ and the servers
in $[{\mathsf{M}}+1:{\mathsf{N}}]$. Recall that the transmission of each
server $n\in[{\mathsf{y}}+1:{\mathsf{M}}]$ is

$\displaystyle{\mathbf{s}}_{n}\
\left[a{\mathbf{f}}_{1}-{\mathbf{f}}_{2};{\mathbf{f}}_{3};\ldots;{\mathbf{f}}_{\frac{{\mathsf{M}}+5}{2}-{\mathsf{y}}}\right]\
[W_{1};\ldots;W_{{\mathsf{N}}}].$

Server $n$ can compute $\frac{{\mathsf{M}}+1}{2}$ neighbouring messages in
$W_{{\mathsf{M}}+1},\ldots,W_{{\mathsf{N}}}$, which are

$\displaystyle
W_{\text{Mod}(n-{\mathsf{y}},{\mathsf{N}}-{\mathsf{M}})+{\mathsf{M}}},W_{\text{Mod}(n-{\mathsf{y}}+1,{\mathsf{N}}-{\mathsf{M}})+{\mathsf{M}}},\ldots,W_{\text{Mod}\left(n-{\mathsf{y}}+\frac{{\mathsf{M}}-1}{2},{\mathsf{N}}-{\mathsf{M}}\right)+{\mathsf{M}}}.$
(58)

The transmission vector ${\mathbf{s}}_{n}$ of server $n$ is in the left-hand
side null space of the column-wise sub-matrix of ${\bf F}^{\prime}_{3}$,
including the columns corresponding to the
${\mathsf{N}}-{\mathsf{M}}-\frac{{\mathsf{M}}+1}{2}=\frac{{\mathsf{M}}-1}{2}-{\mathsf{y}}$
messages in $W_{{\mathsf{M}}+1},\ldots,W_{{\mathsf{N}}}$ which server $n$
cannot compute. Notice that this null space contains
$\frac{{\mathsf{M}}+1}{2}-{\mathsf{y}}+1-\frac{{\mathsf{M}}-1}{2}-{\mathsf{y}}=2$
linearly independent vectors, and ${\mathbf{s}}_{n}$ is a random combination
of them.

It can be seen that the number of servers in $[{\mathsf{y}}+1:{\mathsf{M}}]$
is the same as the number of servers in $[{\mathsf{M}}+1:{\mathsf{N}}]$, which
are both equal to ${\mathsf{N}}-{\mathsf{M}}={\mathsf{M}}-{\mathsf{y}}$. In
addition, for each $n\in[{\mathsf{y}}+1:{\mathsf{M}}]$, server
$n+({\mathsf{M}}-{\mathsf{y}})$ (which is in $[{\mathsf{M}}+1:{\mathsf{N}}]$)
can compute the messages

$W_{\text{Mod}(n-{\mathsf{y}},{\mathsf{N}}-{\mathsf{M}})+{\mathsf{M}}},W_{\text{Mod}(n-{\mathsf{y}}+1,{\mathsf{N}}-{\mathsf{M}})+{\mathsf{M}}},\ldots,W_{\text{Mod}\left(n-{\mathsf{y}}+\frac{{\mathsf{M}}-1}{2}-1,{\mathsf{N}}-{\mathsf{M}}\right)+{\mathsf{M}}}$

among the messages in $[{\mathsf{M}}+1:{\mathsf{N}}]$. Hence, compared to the
set of messages in $[{\mathsf{M}}+1:{\mathsf{N}}]$ that server
$n+({\mathsf{M}}-{\mathsf{y}})$ can compute, it can be seen from (58) that
server $n$ additionally has
$W_{\text{Mod}\left(n-{\mathsf{y}}+\frac{{\mathsf{M}}-1}{2},{\mathsf{N}}-{\mathsf{M}}\right)+{\mathsf{M}}}$.

Let us then prove Lemma 2 by the Schwartz-Zippel lemma [24, 25, 26], as in [3,
Appendix C]. More precisely, for any set of
$\frac{{\mathsf{M}}+1}{2}-{\mathsf{y}}$ servers in
$[{\mathsf{M}}+1:{\mathsf{N}}]$ (denoted by ${\mathcal{A}}_{1}$) and any set
of $\frac{{\mathsf{M}}+1}{2}-{\mathsf{y}}$ servers in
$[{\mathsf{y}}+1:{\mathsf{M}}]$ (denoted by ${\mathcal{A}}_{2}$), we aim to
find one specific realization of $a$ and ${\bf
F}^{(\left[3:\frac{{\mathsf{M}}+5}{2}-{\mathsf{y}}\right])_{\rm r}}_{3}$ such
that there exists one server in ${\mathcal{A}}_{2}$ whose transmission is
linearly independent of the linear combinations in ${\mathcal{L}}_{1}$.

We sort the servers in ${\mathcal{A}}_{1}$ in an increasing order,
${\mathcal{A}}_{1}(1)<\cdots<{\mathcal{A}}_{1}\left(\frac{{\mathsf{M}}+1}{2}-{\mathsf{y}}\right)$.
For each $i\in\left[\frac{{\mathsf{M}}+1}{2}-{\mathsf{y}}\right]$, we let the
$i^{\text{th}}$ row of ${\bf
F}^{(\left[3:\frac{{\mathsf{M}}+5}{2}-{\mathsf{y}}\right])_{\rm r}}_{3}$ be

$[*,*,\cdots,*,0,0,\cdots,0,*,*,\cdots,*],$

where each $0$ corresponds to one distinct message which server
${\mathcal{A}}_{1}(i)$ cannot compute. After determining such ${\bf
F}^{(\left[3:\frac{{\mathsf{M}}+5}{2}-{\mathsf{y}}\right])_{\rm r}}_{3}$, as
shown in [3, Appendix D], the transmission of server ${\mathcal{A}}_{1}(i)$ is
${\mathbf{s}}_{{\mathcal{A}}_{1}(i)}\left[{\mathbf{f}}_{2};\ldots;{\mathbf{f}}_{\frac{{\mathsf{M}}+5}{2}-{\mathsf{y}}}\right][W_{1};\ldots;W_{{\mathsf{N}}}]$,
where

${\mathbf{s}}_{{\mathcal{A}}_{1}(i)}=[0,\cdots,0,1,0,\cdots,0].$

Notice that ${\mathbf{s}}_{{\mathcal{A}}_{1}(i)}$ contains
$\frac{{\mathsf{M}}+3}{2}-{\mathsf{y}}$ elements and $1$ is located at the
$(i+1)^{\text{th}}$ position.

In other words, it can be seen that the transmissions of the
$\frac{{\mathsf{M}}+1}{2}-{\mathsf{y}}$ servers in
$[{\mathsf{M}}+1:{\mathsf{N}}]$ are
$F_{3},\ldots,F_{\frac{{\mathsf{M}}+5}{2}-{\mathsf{y}}}.$ In addition, the
transmission of each server in $[{\mathsf{y}}]$ is $F_{1}-F_{2}$.

Let us then determine the transmissions of the servers in
${\mathcal{A}}_{2}\subseteq[{\mathsf{y}}+1:{\mathsf{M}}]$. It can be easily
proved that among the servers in ${\mathcal{A}}_{2}$, there must exist one
server (assumed to be $n^{\prime}$) the set of whose available messages in
$W_{{\mathsf{M}}+1},\ldots,W_{{\mathsf{N}}}$, is a super set of the available
messages in $W_{{\mathsf{M}}+1},\ldots,W_{{\mathsf{N}}}$ to some server
(assumed to be $n^{\prime\prime}$) in
$[{\mathsf{M}}+1:{\mathsf{N}}]\setminus{\mathcal{A}}_{1}$.121212 The proof is
as follows. For any
${\mathsf{N}}-{\mathsf{M}}-|{\mathcal{A}}_{1}|=\frac{{\mathsf{M}}-1}{2}$
servers in $[{\mathsf{M}}+1:{\mathsf{N}}]$, there are at least
$\frac{{\mathsf{M}}-1}{2}+2$ servers in $[{\mathsf{y}}+1:{\mathsf{M}}]$ the
set of whose obtained datasets is a super set of the set of the obtained
datasets by some of these $\frac{{\mathsf{M}}-1}{2}$ servers. Hence,
${\mathcal{A}}_{2}$ contains $\frac{{\mathsf{M}}+1}{2}-{\mathsf{y}}$ servers
in $[{\mathsf{y}}+1:{\mathsf{M}}]$, which must contain some of these
$\frac{{\mathsf{M}}-1}{2}+2$ servers because
$\frac{{\mathsf{M}}+1}{2}-{\mathsf{y}}+\frac{{\mathsf{M}}-1}{2}+2={\mathsf{M}}-{\mathsf{y}}+2>{\mathsf{M}}-{\mathsf{y}}$.
The transmission of $n^{\prime\prime}$ is assumed to be

$\displaystyle{\mathbf{s}}_{n^{\prime\prime}}\
[{\mathbf{f}}_{2};\ldots;{\mathbf{f}}_{\frac{{\mathsf{M}}+5}{2}-{\mathsf{y}}}]\
[W_{1};\ldots;W_{{\mathsf{N}}}],$

where ${\mathbf{s}}_{n^{\prime\prime}}$ is the vector in the left-hand side
null space (which contains two independent vectors) of the column-wise sub-
matrix of ${\bf
F}^{(\left[2:\frac{{\mathsf{M}}+5}{2}-{\mathsf{y}}\right])_{\rm r}}_{3}$
corresponding the unavailable messages in $[{\mathsf{M}}+1:{\mathsf{N}}]$ to
server $n^{\prime\prime}$. By the proof in [3, Appendix C], the first element
of ${\mathbf{s}}_{n^{\prime\prime}}$ is not $0$ with high probability; thus
${\mathbf{s}}_{n^{\prime\prime}}$ is linearly independent of the transmissions
of the servers in ${\mathcal{A}}_{1}$ with high probability. Recall that the
transmission vector of server $n^{\prime}$ is a random vector in the left-hand
side null space (which contains two independent vectors) of the column-wise
sub-matrix of ${\bf F}^{\prime}_{3}$ corresponding the unavailable messages in
$[{\mathsf{M}}+1:{\mathsf{N}}]$ to server $n^{\prime}$. In addition, the set
of available messages in $[{\mathsf{M}}+1:{\mathsf{N}}]$ to server
$n^{\prime}$ is a super set of that to server $n^{\prime\prime}$. Hence,
${\mathbf{s}}_{n^{\prime\prime}}$ can be also the transmission vector of
server $n^{\prime}$; that is, server $n^{\prime}$ transmits

$\displaystyle{\mathbf{s}}_{n^{\prime}}\
\left[a{\mathbf{f}}_{1}-{\mathbf{f}}_{2};{\mathbf{f}}_{3};\ldots;{\mathbf{f}}_{\frac{{\mathsf{M}}+5}{2}-{\mathsf{y}}}\right]\
[W_{1};\ldots;W_{{\mathsf{N}}}],$ (59)

where ${\mathbf{s}}_{n^{\prime}}$ is obtained by replacing the first element
of ${\mathbf{s}}_{n^{\prime\prime}}$ (assumed to be $s$) by $\frac{s}{a-1}$.

Recall that ${\mathcal{L}}_{1}$ contains
$F_{3},\ldots,F_{\frac{{\mathsf{M}}+5}{2}-{\mathsf{y}}}$ and $F_{1}-F_{2}$. As
$a$ is uniformly over $F_{{\mathsf{q}}}\setminus\\{0,1\\}$, it can be seen
that the transmission in (59) is independent of the linear combinations in
${\mathcal{L}}_{1}$ with high probability.

##  Appendix E Proof of Lemma 3

We will prove Lemma 3 by the Schwartz-Zippel lemma [24, 25, 26]. Hence, we
need to find one specific realization of
$a_{1},\ldots,a_{h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-1}$, such that the
answers of any $h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-\lambda_{1}$
servers in ${\mathcal{A}}_{2}$ are linearly independent of the answers of the
servers in ${\mathcal{A}}_{1}$.131313 It holds that $|{\mathcal{A}}_{2}|\geq
h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-\lambda_{1}$. This is because, as
shown in Footnote 9, if from ${\mathcal{A}}_{1}$ the user cannot recover the
task function, then there must exist ${\mathsf{N}}_{\rm
r}=|{\mathcal{A}}_{1}|+|{\mathcal{A}}_{2}|$ servers in $[{\mathsf{M}}]$
containing the servers in ${\mathcal{A}}_{1}$, such that the answers of these
${\mathsf{N}}_{\rm r}$ servers contain
$h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})$ linearly independent
combinations. Recall that the number of linearly independent combinations
transmitted by the servers in ${\mathcal{A}}_{1}$ is $\lambda$. Hence, we have
$|{\mathcal{A}}_{2}|\geq
h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-\lambda_{1}$.

Without loss of generality, we assume a possible set of
$h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-\lambda_{1}$ linearly independent
transmission vectors is,

$\displaystyle\left[({\bf
S}^{\prime}_{1})_{\left(h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-\lambda_{1}\right)\times\lambda_{1}},\mathbf{I}_{h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-\lambda_{1}}\right],$
(60)

where the $h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-\lambda_{1}$ linear
combinations in $\left[{\bf
S}^{\prime}_{1},\mathbf{I}_{h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-\lambda_{1}}\right]{\bf
F}[W_{1};\ldots;W_{{\mathsf{N}}}]$ are linearly independent of the answers of
the servers in ${\mathcal{A}}_{1}$.

We now prove that there exist a matrix
$[1;a_{1};\ldots;a_{h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-1}]$, whose
left-hand side null space contains all row vectors in (60). This can be proved
by randomly choosing the values of $a_{1},\ldots,a_{\lambda_{1}-1}$, and then
determining the values in
$[a_{\lambda_{1}};\ldots;a_{h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-1}]$ as
follows,

$\displaystyle\begin{bmatrix}\ a_{\lambda_{1}}\\\ \vdots\\\
a_{h({\mathsf{M}},2{\mathsf{M}}-{\mathsf{N}})-1}\end{bmatrix}=-{\bf
S}^{\prime}_{1}\begin{bmatrix}\ 1\\\ a_{1}\\\ \vdots\\\
a_{\lambda_{1}-1}\end{bmatrix}.$

## References

  * [1] R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis, “Gradient coding: Avoiding stragglers in distributed learning,” _in Advances in Neural Information Processing Systems (NIPS)_ , p. 3368–3376, 2017.
  * [2] S. Dutta, V. Cadambe, and P. Grover, “Short-dot: Computing large linear transforms distributedly using coded short dot products,” _in Advances in Neural Information Processing Systems (NIPS)_ , pp. 2100–2108, 2016.
  * [3] K. Wan, H. Sun, M. Ji, and G. Caire, “Distributed linearly separable computation,” _available at arXiv:2007.00345_ , Jul. 2020.
  * [4] M. Ye and E. Abbe, “Communication computation efficient gradient coding,” _in Advances in Neural Information Processing Systems (NIPS)_ , pp. 5610–5619, 2018.
  * [5] H. Cao, Q. Yan, and X. Tang, “Adaptive gradient coding,” _arXiv:2006.04845_ , Jun. 2020.
  * [6] K. Wan, H. Sun, M. Ji, and G. Caire, “On the tradeoff between computation and communication costs for distributed linearly separable computation,” _available at arXiv:2010.01633_ , Oct. 2020.
  * [7] M. Ben-Or, S. Goldwasser, , and A. Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation,” _in Proceedings of the twentieth annual ACM symposium on Theory of computing_ , pp. 1–10, 1988.
  * [8] D. Chaum, C. Crépeau, and I. Damgard, “Multiparty unconditionally secure protocols,” _in Proceedings of the twentieth annual ACM symposium on Theory of computing_ , pp. 11–19, 1988.
  * [9] K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical secure aggregation for federated learning on user-held data,” _available at arXiv:1611.04482_ , Nov. 2016.
  * [10] ——, “Practical secure aggregation for privacy-preserving machine learning,” _in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , pp. 1175–1191, 2017.
  * [11] Q. Yu, S. Li, N. Raviv, S. M. M. Kalan, M. Soltanolkotabi, and S. A. Avestimehr, “Lagrange coded computing: Optimal design for resiliency, security, and privacy,” _in Proceedings of Machine Learning Research (PMLR)_ , pp. 1215–1225, Apr. 2019.
  * [12] W. T. Chang and R. Tandon, “On the upload versus download cost for secure and private matrix multiplication,” _arXiv:1906.10684_ , Jun. 2019.
  * [13] M. Aliasgari, O. Simeone, and J. Kliewer, “Private and secure distributed matrix multiplication with flexible communication load,” _arXiv:1909.00407_ , Sep. 2019.
  * [14] Z. Jia and S. A. Jafar, “On the capacity of secure distributed matrix multiplication,” _arXiv:1908.06957_ , Aug. 2019.
  * [15] J. Kakar, A. Khristoforov, S. Ebadifar, and A. Sezgin, “Uplink-downlink tradeoff in secure distributed matrix multiplication,” _available at arXiv:1910.13849_ , Oct. 2019.
  * [16] Q. Yu and A. S. Avestimehr, “Entangled polynomial codes for secure, private, and batch distributed matrix multiplication: Breaking the cubic barrier,” _arXiv:2001.05101_ , Jan. 2020.
  * [17] Z. Chen, Z. Jia, Z. Wang, , and S. A. Jafar, “GCSA codes with noise alignment for secure coded multi-party batch matrix multiplication,” _arXiv:2002.07750_ , Feb. 2020.
  * [18] J. Zhu and X. Tang, “Secure batch matrix multiplication from grouping lagrange encoding,” _IEEE Communications Letters_ , Dec. 2020.
  * [19] W. Halbawi, N. Azizan-Ruhi, F. Salehi, and B. Hassibi, “Improving distributed gradient descent using reed-solomon codes,” _available at arXiv:1706.05436_ , Jun. 2017.
  * [20] N. Raviv, R. Tandon, A. Dimakis, and I. Tamo, “Gradient coding from cyclic MDS codes and expander graphs,” _in Proc. Int. Conf. on Machine Learning (ICML)_ , pp. 4302–4310, Jul. 2018.
  * [21] Y. Yang, M. Interlandi, P. Grover, S. Kar, S. Amizadeh, and M. Weimer, “Coded elastic computing,” _in IEEE International Symposium on Information Theory (ISIT)_ , pp. 2654–2658, Jul. 2019.
  * [22] A. Behrouzi-Far and E. Soljanin, “Efficient replication for straggler mitigation in distributed computing,” _available at arXiv:2006.02318_ , Jun. 2020.
  * [23] C. E. Shannon, “Communication theory of secrecy systems,” _in The Bell System Technical Journal_ , vol. 28, no. 4, pp. 656–715, Oct. 1949.
  * [24] J. T. Schwartz, “Fast probabilistic algorithms for verification of polynomial identities,” _Journal of the ACM (JACM)_ , vol. 27, no. 4, pp. 701–717, 1980\.
  * [25] R. Zippel, “Probabilistic algorithms for sparse polynomials,” in _International symposium on symbolic and algebraic manipulation_. Springer, 1979, pp. 216–226.
  * [26] R. A. Demillo and R. J. Lipton, “A probabilistic remark on algebraic program testing,” _Information Processing Letters_ , vol. 7, no. 4, pp. 193–195, 1978.