\section{Introduction}\label{sec:introduction}

Secure distributed matrix multiplication (SDMM) has been studied as a way to compute a matrix product using the help of worker servers such that the computation is information-theoretically secure against colluding workers. SDMM was first studied by Chang and Tandon in \cite{chang2018capacity}. Their scheme was improved by D'Oliveira \emph{et al.}\ in \cite{d2020gasp, d2021degree, d2020notes} using GASP codes. Different codes have also been introduced in \cite{kakar2019capacity, aliasgari2020private, jia2019capacity, mital2020secure, kim2019private, yu2020entangled}. Furthermore, different modes of SDMM, such as private, batch or cooperative SDMM, have been studied in \cite{chang2019upload, jia2021cross, yu2019lagrange, yu2020entangled, chen2021gcsa, zhu2021secure, li2022efficient, li2022private}. The information-theoretic capacity of SDMM has been studied in \cite{chang2018capacity, jia2019capacity, kakar2019capacity, yang2019secure}, but overall capacity results are still scarce. In addition to considering SDMM over finite fields, SDMM has also been utilized over the analog domain (real/complex numbers) in \cite{makkonen2022analog}.

The workers in an SDMM scheme are thought of as untrustworthy-but-useful, which means that some of them might not work as intended. The main robustness has been against providing security against colluding workers, which share the information they receive and try to infer the contents of the original matrices. Tools from secret sharing have been used to guarantee information-theoretic security against such colluding workers. Additionally, robustness against so-called straggling workers has been considered. Stragglers are workers that respond slowly or not at all. Such workers cause an undesired straggler effect if the computation is limited by the slowest worker.

Byzantine workers are workers that return erroneous results either intentionally or as a result of a fault. Such errors can be difficult to detect directly without further analysis. To guarantee correctness of the matrix product, it is crucial to be able to detect the errors and correct them with minimal overhead in communication and computation. Tools from classical coding theory can be used to correct errors caused by the Byzantine workers and erasures caused by stragglers.

A coded computation scheme that accounts for stragglers and Byzantine workers has been presented in \cite{yu2019lagrange} using so-called Lagrange coded computation. This scheme considers stragglers as erasures and Byzantine workers as errors in some linear codes. This means that a straggling worker requires one additional worker and a Byzantine worker requires two additional workers.

As the main contribution, this paper introduces a general framework for linear SDMM schemes that can be used to construct many SDMM schemes in a unified way. We show a strong connection between star product codes and SDMM schemes and relate the associated codes to the proofs of the security of the schemes as well as to the recovery threshold and collusion tolerance. Previously, star product codes have been successfully utilized in private information retrieval (PIR) \cite{freij2017private}. Furthermore, we present a bounded-distance decoding strategy utilizing interleaved codes, which provides robustness against stragglers and Byzantine workers. Finally, we analyze the error-correcting capabilities of the proposed strategy under some natural assumptions about the error distributions.

\section{Preliminaries on Interleaved Codes}\label{sec:preliminaries_interleaved_codes}

We write $[n] = \{1, \dots, n\}$. We consider matrices and scalars over a finite field $\ensuremath{\mathbb{F}}_q$ with $q$ elements. Vectors in $\ensuremath{\mathbb{F}}_q^n$ are considered to be row vectors. If $G$ is a matrix, then $G^{\leq m}$ and $G^{> m}$ denote the first $m$ rows and the the rest of the rows. Furthermore, if $\mathcal{I}$ is a set of indices, then $G_\mathcal{I}$ is the submatrix of $G$ with the columns indexed by $\mathcal{I}$.

Interleaved codes have been used to correct burst errors in a stream of codewords in many applications. Burst errors are errors where multiple consecutive symbols are affected instead of single symbol errors distributed randomly.

\begin{definition}[Homogeneous interleaved codes]
Let $\mathcal{C}$ be a linear code over the field $\ensuremath{\mathbb{F}}_q$. Then the $\ell$-interleaved code of $\mathcal{C}$ is the code
\begin{align*}
    \mathcal{IC}^{(\ell)} = \left\{ \begin{pmatrix}c_1 \\ \vdots \\ c_\ell \end{pmatrix} \colon c_i \in \mathcal{C}~\forall i \in [\ell] \right\}.
\end{align*}
\end{definition}

The codewords in an interleaved code are matrices, where each row is a codeword in the code $\mathcal{C}$. Instead of the Hamming weight as the measure of the size of an error, the column weight is used. The column weight of an error matrix is defined to be the number of nonzero columns.

When many codewords need to be transmitted, they can be sent such that first the first symbol of each codeword is sent, then the second symbol of each codeword, and so on. If a burst error occurs, then multiple codewords are affected, but only a small number of symbols is affected in a codeword. This transforms the burst error into single symbol errors in the individual codewords, which means that regular error correction algorithms can be used to correct up to half the minimum distance of errors.

Even more efficient error correction algorithms can be performed for interleaved codes by considering collaborative decoding, where all of the codewords in the interleaved code are considered at the same time. This is advantageous, since the error locations in each of the codewords are the same. Collaborative decoding algorithms have been studied in \cite{krachkovsky2003reed, schmidt2009collaborative} and more recently in \cite{holzbaur2021success}. Collaborative decoding algorithms can achieve beyond half the minimum distance decoding by correcting the errors as a system of simultaneous equations.

\section{Examples of SDMM Schemes}\label{sec:examples_of_SDMM_schemes}

In this section we recall some examples of previous SDMM schemes adopting the presentation typically used in the literature. Later, we will show how these schemes arise as special cases from the general framework proposed in this paper.

The goal is to compute the matrix product of the matrices $A \in \ensuremath{\mathbb{F}}_q^{t \times s}$ and $B \in \ensuremath{\mathbb{F}}_q^{s \times r}$ using a total of $N$ workers, while protecting against any $X$ colluding workers. Furthermore, we denote by $S$ the number of stragglers and by $B$ the number of Byzantine workers. These should not be confused with any matrices. The \emph{recovery threshold} defined as the number of responses from workers that are required in order to decode the intended product.

The schemes are based on different matrix partitioning techniques. The most popular partitionings are the \emph{inner product partitioning} (IPP) and \emph{outer product partitioning} (OPP). In IPP the matrices are partitioned into $p$ pieces such that 
\begin{align*}
    A = \begin{pmatrix} A_1 & \dots & A_p \end{pmatrix}, \quad B = \begin{pmatrix} B_1 \\ \vdots \\ B_p \end{pmatrix}.
\end{align*}
Then the product can be expressed as $AB = \sum_{j=1}^p A_j B_j$. In OPP the matrices are partitioned into $m$ and $n$ pieces, respectively, such that
\begin{align*}
    A = \begin{pmatrix} A_1 \\ \vdots \\ A_m \end{pmatrix}, \quad B = \begin{pmatrix} B_1 & \dots & B_n \end{pmatrix}.
\end{align*}
Then the product can be expressed as
\begin{align*}
    AB = \begin{pmatrix}
    A_1B_1 & \dots & A_1B_n \\
    \vdots & \ddots & \vdots \\
    A_mB_1 & \dots & A_mB_n
    \end{pmatrix}.
\end{align*}
It is also possible to consider combinations of these partitions. 

\textit{Secure MatDot:} A well-known example of an SDMM scheme is the secure MatDot scheme introduced in \cite{aliasgari2020private}. The secure MatDot scheme uses the inner product partitioning to partition the matrices to $p$ pieces. Define the polynomials
\begin{align*}
    f(x) &= \sum_{j=1}^p A_j x^{j-1} + \sum_{k=1}^X R_k x^{p+k-1} \\
    g(x) &= \sum_{j'=1}^p B_{j'} x^{p-j'-1} + \sum_{k'=1}^X S_{k'}x^{p+k'-1},
\end{align*}
where $R_1, \dots, R_X$ and $S_1, \dots, S_X$ are matrices of appropriate size that are chosen uniformly at random from matrices over $\ensuremath{\mathbb{F}}_q$. Let $\alpha_1, \dots, \alpha_N \in \ensuremath{\mathbb{F}}_q^\times$ be distinct nonzero points. Evaluate the polynomials $f(x)$ and $g(x)$ at these points to get the encoded matrices
\begin{align*}
    \widetilde{A}_i = f(\alpha_i), \quad \widetilde{B}_i = g(\alpha_i).
\end{align*}
These encoded matrices can be sent to each worker node. The worker nodes compute the matrix products $\widetilde{C}_i = \widetilde{A}_i \widetilde{B}_i$ and return these  to the user. The user receives evaluations of the polynomial $h(x) = f(x)g(x)$ from each worker node. Using the definition of $f(x)$ and $g(x)$ we can write out the coefficients of $h(x)$ as
\begin{align*}
    h(x) &= f(x)g(x) \\
    &= \sum_{j=1}^p \sum_{j'=1}^p A_jB_{j'} x^{p+j-j'-1} + (\text{terms of degree $\geq p$}).
\end{align*}
The degree of $h(x)$ is at most $2p + 2X - 2$. Furthermore, the coefficient of the term $x^{p-1}$ is exactly the product $AB$, which we wish to recover. Using polynomial interpolation we can compute the required coefficient, given that we have at least $2p + 2X - 1$ evaluations. The recovery threshold for the secure MatDot code is $K = 2p + 2X - 1$.

\textit{GASP code:} Another SDMM scheme that has been widely researched is the GASP scheme, which was first presented in \cite{d2020gasp}. This scheme is also based on polynomial evaluation, but the choice of the polynomials and the evaluation points is more involved. Additionally, the matrices are partitioned according to the outer product partitioning. The following example will give an idea of the general construction described in \cite{d2020gasp, d2021degree}.

The matrices $A \in \ensuremath{\mathbb{F}}_q^{t \times s}$ and $B \in \ensuremath{\mathbb{F}}_q^{s \times r}$ are partitioned into $m = n = 3$ submatrices with the outer product partitioning. We wish to protect against $X = 2$ colluding workers. Let us define the polynomials
\begin{align*}
    f(x) &= A_1 + A_2x + A_3x^2 + R_1x^9 + R_2x^{12}, \\
    g(x) &= B_1 + B_2x^3 + B_3x^6 + S_1x^9 + S_2x^{10},
\end{align*}
where $R_1, R_2, S_1, S_2$ are matrices of appropriate size that are chosen uniformly at random from matrices over $\ensuremath{\mathbb{F}}_q$. The exponents are chosen carefully so that the total number of workers needed is as low as possible. Let $\alpha_1, \dots, \alpha_N \in \ensuremath{\mathbb{F}}_q^\times$ be distinct nonzero points. Evaluate the polynomials $f(x)$ and $g(x)$ at these points to get the encoded matrices
\begin{align*}
    \widetilde{A}_i = f(\alpha_i), \quad \widetilde{B}_i = g(\alpha_i).
\end{align*}
These encoded matrices can be sent to each worker node. The worker nodes compute the matrix products $\widetilde{C}_i = \widetilde{A}_i \widetilde{B}_i$ and send these  to the user. The user receives evaluations of the polynomial $h(x) = f(x)g(x)$ from each worker. Using the definition of $f(x)$ and $g(x)$ we can write out the coefficients of $h(x)$ as
\begin{align*}
    h(x) &= A_1B_1 + A_2B_1x + A_3B_1x^2 + A_1B_2x^3 + A_2B_2x^4 \\ 
    &+ A_2B_3x^5 + A_1B_3x^6 + A_2B_3x^7 + A_3B_3x^8 \\
    &+ (\text{terms of degree $\geq 9$}).
\end{align*}
We notice that the coefficients of the first $9$ terms are exactly the submatrices we wish to recover. We need 18 responses from the workers, since $h(x)$ has $18$ nonzero coefficients, provided that the corresponding linear equations are solvable. In this case, the recovery threshold is $K = 18$.

The general choice of the exponents in the polynomials $f(x)$ and $g(x)$ is explained in \cite{d2021degree}. A so-called degree table is used to analyze the recovery threshold of the scheme. Furthermore, the choice of the evaluation points is not as simple as with the secure MatDot code, but it has been shown that a suitable choice can be made in a large enough field.

\textit{SDMM based on FFT:} A novel SDMM scheme based on the Fourier transform over finite fields was introduced by Mital \emph{et al}.\ in \cite{mital2020secure}. This scheme is not able to protect against straggling workers. The matrices are partitioned into $p = N - 2X$ pieces with the inner product partitioning. Define the functions
\begin{align*}
    f(x) &= \sum_{j=1}^p A_j x^{j-1} + \sum_{k=1}^X R_k x^{p + k - 1} \\
    g(x) &= \sum_{j'=1}^p B_{j'} x^{-j'+1} + \sum_{k'=1}^X S_{k'} x^{-p-X-k'+1},
\end{align*}
where $R_1, \dots, R_X$ and $S_1, \dots, S_X$ are matrices of appropriate size that are chosen uniformly at random from matrices over $\ensuremath{\mathbb{F}}_q$. Let $\alpha_N \in \ensuremath{\mathbb{F}}_q^\times$ be a primitive $N$th root of unity. The functions $f(x)$ and $g(x)$ are evaluated at the points $1, \alpha_N, \alpha_N^2, \dots, \alpha_N^{N-1}$ and the results are sent to the workers such that worker $i \in [N]$ receives the encoded matrices
\begin{align*}
    \widetilde{A}_i = f(\alpha_N^{i-1}), \quad \widetilde{B}_i = f(\alpha_N^{i-1}).
\end{align*}
The workers compute the matrix products of the encoded matrices and return the results $\widetilde{C}_i = \widetilde{A}_i \widetilde{B}_i$. The user receives evaluations of the function
\begin{align*}
    h(x) = f(x)g(x) = \sum_{j=1}^p A_j B_j + (\text{non-constant terms}).
\end{align*}
The other terms have degree in $[-N + 1, N - 1]$, which means that the average of the responses equals the constant term, since $\sum_{i=1}^N (\alpha_N)^s = 0$ for $N \nmid s$. Hence, the product $AB$ can be computed as the average of all the responses. This means that no stragglers can be tolerated, since all of the responses are needed. Furthermore, the field has to be such that the appropriate $N$th root of unity exists.

\section{Linear SDMM}\label{sec:linear_SDMM}

Many SDMM schemes in the literature use concepts from coding theory and secret sharing, but are usually presented as concrete constructions based on polynomial interpolation. This makes it easy to argue that the schemes compute the desired matrix product, but the comparison of different schemes is difficult. A more general and abstract way can provide simpler comparisons between SDMM schemes and constructions that are not based on any particular SDMM scheme, while losing some detail about why each scheme works as they do. In this section we present a general linear SDMM framework that can be used to describe the earlier SDMM schemes in a compact way. Furthermore, we prove a general security result for linear SDMM schemes.

\subsection{General Linear SDMM Framework via Star Products}\label{sec:general_linear_SDMM_framework}

Linear SDMM schemes can be constructed in general with the following formula. The input matrices $A \in \ensuremath{\mathbb{F}}_q^{t \times s}$ and $B \in \ensuremath{\mathbb{F}}_q^{s \times r}$ are partitioned into block matrices of equal size  using some partitioning such that the blocks can be arranged as the vectors
\begin{equation*}
    (A_1, \dots, A_m),\quad (B_1, \dots, B_n)
\end{equation*}
of length $m$ and $n$, respectively. Matrices $R_1, \dots, R_X$ and $S_1, \dots, S_X$ are drawn uniformly at random such that the matrices $R_k$ and $S_{k'}$ have the same size as $A_j$ and $B_{j'}$, respectively. These random matrices are appended to the partition vectors to get the following vectors of matrices
\begin{equation*}
    (A_1, \dots, A_m, R_1, \dots, R_X), \quad (B_1, \dots, B_n, S_1, \dots, S_X)
\end{equation*}
of length $m + X$ and $n + X$, respectively. These vectors are encoded using $[N, m + X]$ and $[N, n + X]$ linear codes $\mathcal{C}_A$ and $\mathcal{C}_B$, respectively, where $N$ denotes the number of workers. Let $F$ and $G$ be generator matrices for $\mathcal{C}_A$ and $\mathcal{C}_B$, respectively. The associated codewords are then
\begin{align*}
    \widetilde{A} &= (\widetilde{A}_1, \dots, \widetilde{A}_N) = (A_1, \dots, A_m, R_1, \dots, R_X) F \\
    \widetilde{B} &= (\widetilde{B}_1, \dots, \widetilde{B}_N) = (B_1, \dots, B_n, S_1, \dots, S_X) G.
\end{align*}
Each worker is sent one component of both vectors, \emph{i.e.}, worker $i$ receives matrices $\widetilde{A}_i$ and $\widetilde{B}_i$. The worker then multiplies these matrices together and sends the result to the user. In coding-theoretic terms, this can be interpreted as a star product of the vectors $\widetilde{A}$ and $\widetilde{B}$. Hence, we may write
\begin{align*}
    \widetilde{C} = \widetilde{A} \star \widetilde{B} = (\widetilde{A}_1 \widetilde{B}_1, \dots, \widetilde{A}_N \widetilde{B}_N).
\end{align*}
Let $H$ be a suitable generator matrix for $\mathcal{C}_A \star \mathcal{C}_B$ and $\mathcal{I} \subseteq [N]$ the indices of the fastest responses. The result can be obtained by computing $(\widetilde{A} \star \widetilde{B})_\mathcal{I} H_\mathcal{I}^{-1}$, provided that $\mathcal{I}$ is an information set of $\mathcal{C}_A \star \mathcal{C}_B$. The generator matrix $H$ has to be chosen such that the desired product can be obtained as one of the components of the decoded vector. It is often convenient to assume that $\mathcal{C}_A \star \mathcal{C}_B$ is an MDS code, which means that any set of sufficient size is an information set.

\begin{remark}
The vectors $\widetilde{A}$, $\widetilde{B}$ and $\widetilde{C}$ are vectors of matrices that are obtained as the encoding of the partition vectors. Another way to interpret these is that $\widetilde{A}$, $\widetilde{B}$ and $\widetilde{C}$ are matrices of codewords in $\mathcal{C}_A$, $\mathcal{C}_B$ and $\mathcal{C}_A \star \mathcal{C}_B$, respectively. By abuse of notation, we denote
\begin{align*}
    \widetilde{A} \in \mathcal{C}_A,~\widetilde{B} \in \mathcal{C}_B,~\widetilde{C} \in \mathcal{C}_A \star \widetilde{C}_B.
\end{align*}
\end{remark}

\begin{remark}
This construction of linear SDMM schemes is quite abstract as it does not provide a general way of constructing new SDMM schemes from any linear codes. However, it provides a robust and general way to look at different SDMM schemes and prove general results. This general linear structure can be used to easily show the security of the schemes by checking properties of the generator matrices $F$ and $G$ as we show in Section~\ref{sec:security_linear_SDMM}.
\end{remark}

With the linear SDMM framework, an SDMM scheme can be described using the partition of the matrices and the three generator matrices $F$, $G$ and $H$. It is worth noting that $H$ is a generator matrix of $\mathcal{C}_A \star \mathcal{C}_B$ and not a parity-check matrix. 

If $\mathcal{C}_A \star \mathcal{C}_B$ is an MDS code, only a certain number of fastest responses are required for decoding. This is possible since any set that is large enough is an information set. In other words, the dimension $K$ of $\mathcal{C}_A \star \mathcal{C}_B$ is the recovery threshold of the SDMM scheme, which means that any $K$ responses are enough to decode the answer. Recovery threshold has been denoted by $R_c$ in the literature, but we choose to denote it by $K$ as it conveniently matches our coding-theoretic approach.

As an immediate consequence of \cite[Theorem 7]{mirandola2015critical} we get the following lower bound for the recovery threshold for a linear SDMM scheme.

\begin{proposition}\label{prop:recovery_thresold}
If $\mathcal{C}_A$ and $\mathcal{C}_B$ are full-support MDS codes, then the linear SDMM scheme using the codes $\mathcal{C}_A$ and $\mathcal{C}_B$ has recovery threshold
\begin{align*}
    K \geq \min\{N, (m + n) + 2X - 1\}.
\end{align*}
\end{proposition}

As a corollary of Proposition~\ref{prop:recovery_thresold} we get an upper bound on the number of colluding workers.

\begin{corollary}
The number of colluding workers a linear SDMM scheme can protect against is $X < \frac{N}{2}$, when $\mathcal{C}_A$ and $\mathcal{C}_B$ are full-support MDS codes.
\end{corollary}


\subsection{Constructing SDMM Schemes Using Linear SDMM}\label{sec:constructing_linear_SDMM_schemes}

The examples of SDMM schemes presented in Section~\ref{sec:examples_of_SDMM_schemes} can be described using the linear SDMM framework by describing the partitioning of the matrices and the associated codes $\mathcal{C}_A$ and $\mathcal{C}_B$. Here we describe only the generator matrices of $\mathcal{C}_A$ and $\mathcal{C}_B$. The generator matrix of $\mathcal{C}_A \star \mathcal{C}_B$ is also of importance, but in the interest of space we will not describe it in detail.

\textit{Secure MatDot:} The secure MatDot scheme can be described using the linear SDMM framework by the following. The matrices $A \in \ensuremath{\mathbb{F}}_q^{t \times s}$ and $B \in \ensuremath{\mathbb{F}}_q^{s \times r}$ are partitioned into $p$ pieces with the inner product partitioning such that the order of the pieces of $B$ is reversed. The generator matrices $F$ and $G$ are defined as $(p + X) \times N$ Vandermonde matrices on the distinct evaluation points $\alpha_1, \dots, \alpha_N \in \ensuremath{\mathbb{F}}_q^\times$. These matrices generate Reed-Solomon codes of dimension $p + X$ and length $N$ on the locators $\alpha = (\alpha_1, \dots, \alpha_N)$. We denote this by $\mathcal{C}_A = \RS_{p + X}(\alpha)$ and $\mathcal{C}_B = \RS_{p + X}(\alpha)$. It is easy to see that this produces the same encoding as the general description of the secure MatDot scheme. It was shown in \cite{mirandola2015critical} that the resulting star product code is then $\mathcal{C}_A \star \mathcal{C}_B = \RS_{2p + 2X - 1}(\alpha)$, provided that $N \geq 2p + 2X - 1$.

\textit{GASP code:} The GASP code can similarly be described using the linear SDMM framework. The matrices $A \in \ensuremath{\mathbb{F}}_q^{t \times s}$ and $B \in \ensuremath{\mathbb{F}}_q^{s \times r}$ are partitioned into $m$ and $n$ pieces, respectively, using the outer product partitioning. The encoding is done using a polynomial evaluation code, where the terms of the polynomials are determined by optimizing the degree table. Let $\varphi$ and $\gamma$ be the vectors that contain the exponents of the encoding polynomials $f(x)$ and $g(x)$, respectively. The generator matrices are
\begin{equation*}
    F = \begin{pmatrix}
    \alpha_1^{\varphi_1} & \dots & \alpha_N^{\varphi_1} \\
    \vdots & \ddots & \vdots  \\
    \alpha_1^{\varphi_{m + X}} & \dots & \alpha_N^{\varphi_{m + X}}
    \end{pmatrix}, \quad G = \begin{pmatrix}
    \alpha_1^{\gamma_1} & \dots & \alpha_N^{\gamma_1} \\
    \vdots & \ddots & \vdots  \\
    \alpha_1^{\gamma_{n + X}} & \dots & \alpha_N^{\gamma_{n + X}}
    \end{pmatrix}.
\end{equation*}
Thus, $\mathcal{C}_A$ is an $[N, m + X]$ code and $\mathcal{C}_B$ is an $[N, n + X]$ code.

\textit{SDMM based on FFT:} The SDMM scheme based on FFT that was first presented in \cite{mital2020secure} uses the inner product partitioning to partition the matrices to $p = N - 2X$ pieces. The generator matrices can be expressed as
\begin{align*}
    F &= \begin{pmatrix}
    1 & 1 & \dots & 1 \\
    1 & \alpha_N & \dots & \alpha_N^{N - 1} \\
    1 & \alpha_N^2 & \dots & \alpha_N^{2(N - 1)} \\
    \vdots & & \ddots & \vdots \\
    1 & \alpha_N^{p + X - 1} & \dots & \alpha_N^{(p + X - 1)(N - 1)}
    \end{pmatrix}, \quad
    G = \begin{pmatrix}
    1 & 1 & \dots & 1 \\
    1 & \alpha_N^{-1} & \dots & \alpha_N^{-(N - 1)} \\
    \vdots & & \ddots & \vdots \\
    1 & \alpha_N^{-(p - 1)} & \dots & \alpha_N^{-(p - 1)(N - 1)} \\
    1 & \alpha_N^{-(p + X)} & \dots & \alpha_N^{-(p + X)(N - 1)} \\
    \vdots & & \ddots & \vdots \\
    1 & \alpha_N^{-(p + 2X - 1)} & \dots & \alpha_N^{-(p + 2X - 1)(N - 1)}
    \end{pmatrix}.
\end{align*}
These follow directly from the general description in Section~\ref{sec:examples_of_SDMM_schemes}.

\subsection{Security of Linear SDMM Schemes}\label{sec:security_linear_SDMM}

The following theorem will highlight the usefulness of the linear SDMM framework, since the security of the schemes can be proven by checking the properties of the generator matrices. A matrix has the MDS property if and only if it generates an MDS code, \emph{i.e.}, all of its maximal submatrices are invertible. This approach has been taken in \cite{d2020gasp} in reference to GASP codes. Here we apply the theorem in a more general setting.

\begin{theorem}\label{thm:linear_SDMM_security}
Let $F$ and $G$ be the generator matrices used in the encoding of some linear SDMM scheme. Then the scheme is secure against $X$-collusion if $F^{> m}$ and $G^{> n}$ have the MDS property. 
\end{theorem}

\begin{proof}
Let $\mathcal{X} \subseteq [N]$, $|\mathcal{X}| = X$, be a set of $X$ colluding nodes. Writing the generator matrix $F$ as
\begin{equation*}
    F = \begin{pmatrix}
    F^{\leq m} \\
    F^{>m}
    \end{pmatrix}
\end{equation*}
allows us to write the shares the colluding nodes have about the encoded matrix $\widetilde{A}$ as
\begin{equation*}
    \widetilde{A}_\mathcal{X} = (A_1, \dots, A_m)F^{\leq m}_\mathcal{X} + (R_1, \dots, R_X)F^{> m}_\mathcal{X}.
\end{equation*}
If $F^{> m}$ has the MDS property, then any $X \times X$ submatrix of $F^{> m}$ is invertible. As $(R_1, \dots, R_X)$ is uniformly distributed, we get that $(R_1, \dots, R_X)F^{> m}_\mathcal{X}$ is also uniformly distributed. Therefore,
\begin{equation*}
    I(\mathbf{A}; \mathbf{\widetilde{A}}_\mathcal{X}) = 0.
\end{equation*}
The idea is that the confidential data of $A$ is hidden by adding uniformly random noise. A similar argument works for the matrix $B$. Finally, we get that 
\begin{align*}
    I(\mathbf{A}, \mathbf{B}; \mathbf{\widetilde{A}}_\mathcal{X}, \mathbf{\widetilde{B}}_\mathcal{X}) &= I(\mathbf{A}, \mathbf{B}; \mathbf{\widetilde{A}}_\mathcal{X}) + I(\mathbf{A}, \mathbf{B}; \mathbf{\widetilde{B}}_\mathcal{X} \mid \mathbf{\widetilde{A}}_\mathcal{X}) \\
    &\leq I(\mathbf{A}; \mathbf{\widetilde{A}}_\mathcal{X}) + I(\mathbf{B}; \mathbf{\widetilde{B}}_\mathcal{X}) = 0.
\end{align*}
The inequality follows from $\mathbf{\widetilde{A}}_\mathcal{X}$ being conditionally independent of $\mathbf{B}$ given $\mathbf{A}$, and $\mathbf{\widetilde{B}}_\mathcal{X}$ being conditionally independent of $\mathbf{\widetilde{A}}_\mathcal{X}$ and $\mathbf{A}$ given $\mathbf{B}$. This proves the claim.
\end{proof}

The security of the SDMM schemes presented earlier follows as simple corollaries of the above theorem.

\section{Error Correction in SDMM}\label{sec:error_correction_SDMM}

Protecting against straggling workers has been a subject of research in many SDMM schemes. Another form of robustness is protection against so-called Byzantine workers, which return erroneous responses as a result of a fault or on purpose. This error can occur during the computation or during transmission. Robustness against Byzantine workers has been studied in the context of private information retrieval (PIR) and other distributed computation systems such as Lagrange coded computation in \cite{yu2019lagrange}.

The difference between straggling workers and Byzantine workers is that a straggling worker is simple to detect, while noticing erroneous responses from a Byzantine worker is not as straightforward. In coding-theoretic terms the straggling workers correspond to erasures in codes and Byzantine workers correspond to errors. It is well-known that erasures require one additional code symbol to fix with MDS codes, while errors typically require two additional code symbols to fix. The authors of \cite{yu2019lagrange} devised a coded computation scheme, where each additional straggler requires one additional response and each Byzantine worker requires two additional responses. This disparity between the costs can be fixed using interleaved codes by utilizing the structure of the error patterns.

\subsection{Interleaved Codes in SDMM}\label{sec:interleaved_codes_SDMM}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.4\columnwidth]{drawing3x4.png}
    \caption{Diagram depicting the responses from the worker nodes. The Byzantine worker is depicted by the purple layer and the straggler by the blurred layer. Each response is a matrix, which is represented as a rectangular array in the figure. The codewords are the length $N$ vectors formed by stacking the responses and looking at the corresponding matrix entries. Hence, a Byzantine worker and stragglers can only affect their own position in the codewords.}
    \label{fig:response_diagram}
\end{figure}

The responses from the workers in a linear SDMM scheme can be seen to be codewords in the code $\mathcal{C}_A \star \mathcal{C}_B$. If this code has error correction capabilities, then we can correct possible errors in each of the codewords by considering each matrix position independently. This approach requires $N = K + 2B$ workers, where $K$ is the recovery threshold of the scheme and $B$ is the number of Byzantine workers. However, a more efficient method would be to consider all of the codewords at once, since we can use the structure of the errors to our advantage.

Figure \ref{fig:response_diagram} depicts how the responses of a linear SDMM scheme can be seen as a collection of codewords from the star product code $\mathcal{C}_A \star \mathcal{C}_B$. Each layer in the diagram depicts one of the responses from one of the workers. By collecting the matching matrix positions to a vector of length $N$ we obtain codewords in the code $\mathcal{C}_A \star \mathcal{C}_B$. If one of the workers returns an incorrect result, say worker 2 in Figure \ref{fig:response_diagram}, then the corresponding coordinate in each of the codewords is erroneous. Similarly, if one of the workers fails to return a response in time, say worker 4 in Figure \ref{fig:response_diagram}, then the corresponding coordinate is an erasure in each of the codewords. In particular, if we consider the $\ell$-interleaved code obtained by taking some collection of $\ell$ codewords in the response matrices, then the errors caused by the Byzantine workers are burst errors in the interleaved code.

There are several algorithms for decoding interleaved codes that can reach error correction capabilities that can correct up to twice as many errors as non-interleaved decoders \cite{schmidt2009collaborative, holzbaur2021success}. This is achieved by collaborative decoding, where the fact that the erroneous symbols are in the same place in each codeword is utilized.

In principle, interleaved coding techniques can be used with any linear SDMM scheme. However, many codes that are used in different SDMM constructions do not have an explicit error correction algorithm. SDMM schemes that are based on polynomial interpolation, such as the secure MatDot or $\mathrm{GASP}_\text{big}$ schemes, can be utilized, since the Reed--Solomon code has well-known error correction algorithms.

The proposed idea for correcting errors from the responses of a linear SDMM scheme is the following.
\begin{itemize}
    \item Choose some subset of $\ell$ matrix entries and collect the corresponding $\ell$ codewords of $\mathcal{C}_A \star \mathcal{C}_B$ as a codeword of an interleaved code.
    \item Find the error locations from the interleaved code using error correction algorithms for the $\ell$-interleaved code.
    \item Treat the erroneous coordinates as erasures and decode as usual.
\end{itemize}
As error correction of the interleaved codewords requires more computational power than just decoding, it is not advantageous to choose $\ell$ to be maximal, \emph{i.e.}, choosing all of the matrix entries to the interleaved codeword. On the other hand, collaborative decoding algorithms do not guarantee success with probability 1, so $\ell$ has to be chosen such that the success probability is suitably high. Furthermore, choosing a small subset of the matrix entries might lead to situations where not all of the errors are detected by the error correction algorithm.

\subsection{Analyzing Error Correction Capabilities}\label{sec:analyzing_error_correction}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.55\columnwidth]{num_errors_vs_P_unsuccessful.png}
    \caption{Probability of unsuccessful decoding as a function of the number of errors $t\leq B$, where $q = 2^{32} - 5$, $D = 19$, $B = D - 2 = 17$ and $\ell = 9$. It is clear from the figure that the probability of unsuccessful decoding is extremely small.}
    \label{fig:number_of_errors}
\end{figure}

Collaborative error correction algorithms have been designed for interleaved Reed-Solomon codes, since they are prevalent in many applications where burst errors are common. In this section we analyze the success probability of some interleaved Reed--Solomon decoders in the context of the secure MatDot and $\mathrm{GASP}_\text{big}$ schemes. The same techniques are applicable for other linear SDMM schemes based on Reed--Solomon codes.

We assume that the errors sent by the Byzantine workers are uniformly distributed, \emph{i.e.}, the Byzantine workers respond with a matrix of appropriate size whose entries are uniformly distributed over the field $\ensuremath{\mathbb{F}}_q$. This is a natural assumption if the errors occur naturally without malice. Additionally, this assumption is popular in the literature, where failure probabilities are analyzed. In the examples in this section we use a field of size $q = 2^{32} - 5$, since it is large enough to use in problems, where the elements are discretized from the real numbers.

Bounded distance decoders for interleaved Reed--Solomon codes are discussed in \cite{schmidt2009collaborative, holzbaur2021success}. These decoding algorithms generalize the Berlekamp--Massey approach of decoding Reed--Solomon codes to interleaved codes. Additionally, \cite{schmidt2009collaborative, holzbaur2021success} give bounds on the success probability of the decoders when the errors are assumed to be uniformly distributed with specified column weights. Theorem 7 of \cite{holzbaur2021success} gives an upper bound on the probability of unsuccessful decoding as
\begin{align}
    \left( \frac{q^\ell - q^{-1}}{q^\ell - 1} \right)^t \cdot \frac{q^{-(\ell + 1)(t_\text{max} - t)}}{q - 1}, \label{eq:holzbaur_upper_bound}
\end{align}
where $t_\text{max} = \frac{\ell}{\ell + 1}(D - 1)$, $D$ is the minimum distance and $t$ is the number of errors.

To analyze the probability of unsuccessful decoding we use the upper bound in \eqref{eq:holzbaur_upper_bound}. This upper bound depends only on the field size $q$, the interleaving order $\ell$, the minimum distance $D$, and the number of Byzantine workers $t$, which is bounded from above by the maximal number of Byzantine workers $B$. The upper bound of unsuccessful decoding as a function of the number of Byzantine workers is depicted in Figure \ref{fig:number_of_errors}.

From Figure \ref{fig:number_of_errors} it is clear that the decoding is successful with a strikingly high probability. This shows that $N = K + B + 1$ workers are needed to correct errors from $B$ Byzantine workers, where the scheme has recovery threshold $K$. By adding $S$ straggling workers, we require an additional $S$ responses, which means that we need at least $N = K + S + B + 1$. This is an improvement over independent decoding, which requires $N = K + 2B + S$ workers, since the number of errors can be up to $\lfloor \frac{N - K}{2} \rfloor$.

\section*{Acknowledgements}

This work has been supported by the Academy of Finland under Grant No.\ 336005.

