Flexible Field Sizes in Secure Distributed Matrix Multiplication via Efficient Interference Cancellation
Okko Makkonen






Flexible Field Sizes in Secure Distributed Matrix Multiplication via Efficient Interference Cancellation
    
    Okko Makkonen

    Department of Mathematics and Systems Analysis

    Aalto University

    Espoo, Finland

    Email: okko.makkonen@aalto.fi

    Received / accepted 
========================================================================================================================================================




In this paper, we propose a new secure distributed matrix multiplication (SDMM) scheme using the inner product partitioning.
We construct a scheme with a minimal number of workers and no redundancy, and another scheme with redundancy against stragglers.
Unlike previous constructions in the literature, we do not utilize algebraic methods such as locally repairable codes or algebraic geometry codes.
Our construction, which is based on generalized Reed–Solomon codes, improves the flexibility of the field size as it does not assume any divisibility constraints among the different parameters.
We achieve a minimal number of workers by efficiently canceling all interference terms with a suitable orthogonal decoding vector.
Finally, we discuss how the MDS conjecture impacts the smallest achievable field size for SDMM schemes and show that our construction almost achieves the bound given by the conjecture.




§ INTRODUCTION



Secure distributed matrix multiplication (SDMM) is a way of distributing the computation of a matrix product to a distributed system of worker nodes, while providing resiliency against slow and unresponsive workers (stragglers) and data security against colluding workers.
SDMM was first introduced by Chang and Tandon in <cit.> and has seen a number of papers improving on their construction <cit.>.
SDMM schemes utilize many techniques from coding theory and secret sharing, which means that they naturally operate over finite fields.

The way to distribute the computation is to break the problem down to smaller problems.
This is done by partitioning the two matrices to smaller pieces such that the entire product can be assembled from the smaller products.
In this paper we focus on the so-called inner product partitioning where the product can be computed as an inner product of the partition vectors.

If all responses from the worker nodes are needed, then just one node being slow or unresponsive will slow down the whole computation.
This problem, known as the straggler problem, can be reduced by making the system sufficiently redundant such that some of the workers' responses may be ignored.
This redundancy is provided through methods in coding theory, where these straggling workers may be seen as erasures in the codewords.
Coding theory can also be used to protect against errors in the responses coming from so-called Byzantine workers, which have been addressed <cit.>.

In case the matrices contain sensitive information, it is important for the distribution process not to leak any secret information to the worker nodes.
This is achieved through secret sharing, where coded randomness is inserted to the computation such that any sufficiently few nodes will not be able to decode the original matrices.
In particular, information-theoretic security is required for secure distributed matrix multiplication.

Many constructions in the literature use techniques from algebraic coding theory, such as locally repairable codes in <cit.>, algebraic geometry codes over Hermitian curves and Kummer extensions in <cit.> and <cit.>, and so-called discrete Fourier transform (DFT) codes in <cit.>.
These constructions assume certain properties of the finite fields, such as the existence of primitive Nth roots of unity in <cit.>, or large field extensions in <cit.>.
Furthermore, the authors of <cit.> are interested in finding SDMM schemes over small fields by using codes over high genus algebraic curves.
In this paper, we construct SDMM schemes without relying on assumptions on the field, other than that the field has to be sufficiently large (q ≥ N, where N is the number of workers) for the existence of certain MDS codes.
Our construction is enabled by efficient interference cancellation, where all noise terms are removed with a single linear combination, as well as the observation that computing any non-degenerate bilinear form is sufficient for the inner product partitioning.
This method does not increase the encoding or decoding complexity.
We also discuss how the field size has to be roughly N due to the MDS conjecture.

This paper is organized as follows.
In <ref>, we give some preliminaries on linear codes and generalized Reed–Solomon codes.
In <ref>, we introduce the system model for secure distributed matrix multiplication and give some examples.
In <ref>, we provide our construction utilizing Reed–Solomon codes with flexibility in the chosen finite field.
Finally, in <ref>, we compare our construction against some competing schemes in the literature.




§ PRELIMINARIES



Let _q denote the finite field with q elements, _q^* = _q ∖{0}, and [n] = {1, …, n}.
We consider elements of _q^n as row vectors.



 §.§ Linear Codes



For a vector x ∈_q^n we define the support and weight by (x) = {i ∈ [n] : x_i ≠ 0} and (x) = | 0.1em (x) |.
A k-dimensional subspace 𝒞 of _q^n is said to be an [n, k] linear code.
If G is a k × n matrix whose rows span the subspace 𝒞, then G is said the be a generator matrix of 𝒞.
The minimum distance of a code 𝒞 is

    d_min = min{(c) : c ∈𝒞∖{0}}.

The famous Singleton bound states that d_min≤ n - k + 1 and codes that meet this bound with equality are said to be maximum distance separable (MDS).
Another characterization of MDS codes is that any k × k submatrix of the generator matrix G is invertible.
Simple examples of MDS codes are the [n, 1] repetition code and the [n, n - 1] single parity check code.
The following proposition states that for k ≥ q + 1, the longest possible MDS codes are single parity check codes.



Let 𝒞 be a linear [n, k] MDS code over _q with k ≥ q + 1.
Then, n ≤ k + 1.


The following conjecture, which was stated by Segre in 1955 <cit.>, states that the longest possible (non-trivial) linear MDS codes have length roughly equal to the alphabet size.
Several special cases of the conjecture have been proven, see <cit.>.



Let 𝒞 be a linear [n, k] MDS code over _q with 2 ≤ k ≤ q.
Then n ≤ q + 1, except if q is even and k = 3 or k = q - 1, in which case n ≤ q + 2.


The star product of two length n linear codes 𝒞 and 𝒟 is the linear code generated by the coordinatewise products of their codewords, i.e.,

    𝒞⋆𝒟 = { c ⋆ d | c ∈𝒞, d ∈𝒟},

where (c ⋆ d)_i = c_id_i.

The dual of a linear code 𝒞 is a linear code 𝒞^⊥ whose codewords are orthogonal to all the codewords in 𝒞 with respect to the standard inner product, i.e.,

    𝒞^⊥ = {x ∈_q^n : x · c = 0 ∀ c ∈𝒞}.

If 𝒞 is k-dimensional, then 𝒞^⊥ is (n - k)-dimensional and 𝒞 = (𝒞^⊥)^⊥.
Furthermore, if 𝒞 is MDS, then 𝒞^⊥ is also MDS.




 §.§ Generalized Reed–Solomon Codes



A famous class of linear MDS codes can be constructed from evaluations of polynomials.
In particular, let α∈_q^n contain distinct entries, ν∈ (_q^*)^n, and let _q[x]^< k denote the vector space of polynomials of degree < k.
The k-dimensional generalized Reed–Solomon (GRS) code is defined as

    _k(α, ν) = {(ν_1 f(α_1), …, ν_n f(α_n)) | f(x) ∈_q[x]^< k}.

It is well-known that GRS codes are MDS.
The elements of α and ν are known as evaluation points and column multipliers, respectively.
If 1 is the all-ones vector, then we write _k(α) = _k(α, 1).
The length of a GRS code is n ≤ q due to the fact that the evaluation points have to be distinct points of _q.
Therefore, these codes do not quite achieve the bound of n ≤ q + 1 (or n ≤ q + 2) given by the MDS conjecture.

The star product of GRS codes defined on the same evaluation points can be computed with

    _k(α, ν) ⋆_ℓ(α, μ) = _min{k + ℓ - 1, n}(α, ν⋆μ).

The dual of an (n - 1)-dimensional Reed–Solomon code is a one-dimensional MDS code, i.e., generated by some full-weight ω∈_q^n.
The dual of a Reed–Solomon code can be computed from the following equation

    (_k(α) ⋆_n-k(α))^⊥ = _n-1(α)^⊥ = {ω}.

Therefore,

    0 = ∑_i=1^Nω_i (c ⋆ d)_i = ∑_i=1^N c_i (ω_i d_i),

where c ∈_k(α) and d ∈_n - k(α).
Hence, _k(α)^⊥ = _n-k(α, ω).
Notice that ω only depends on the evaluation points α and not the dimension k.
In fact, the column multipliers may be written explicitly as ω_i = (∏_j=1, j ≠ i^n (α_i - α_j))^-1.




§ SECURE DISTRIBUTED MATRIX MULTIPLICATION



The aim of secure distributed matrix multiplication is to distribute the computation of a matrix product to workers such that the workers do not gain any information about the secret matrices.
The computation should be made redundant such that the responses from some of the workers may be ignored, which will mitigate the so-called straggler problem.



 §.§ System Model



We wish to compute the product AB for matrices A ∈_q^t × s and B ∈_q^s × r.
We begin by partitioning these matrices to P equal pieces such that

    A = [ A_1   ⋯ A_P ],    B = [ B_1;   ⋮; B_P ].

Then, the product can be expressed as

    AB = ∑_j=1^P A_jB_j.

This way of partitioning the matrices is known as the inner product partition, since the product is expressed as the inner product of the block vectors.
Other ways to partition the matrices have also been considered in the literature, but we will not focus on these in this paper.

Each of the N workers, indexed by i ∈ [N], is sent two matrices Ã_i and B̃_i.
These encoded matrices depend on the blocks of A and B, as well as some randomness.
The workers compute Ã_i B̃_i and return this to the user who decodes the product AB from the responses.
The recovery threshold of the scheme is the minimal number R such that the product can be decoded from any R of the responses.
In some cases, it may be possible to decode the product from some fewer number of responses.

Let 𝒳⊆ [N], |𝒳|≤ X, be a set of colluding workers and Ã_𝒳 = {Ã_i : i ∈𝒳}, B̃_𝒳 = {B̃_i : i ∈𝒳} be the collections of the shares of the matrices A and B held by these workers.
The encoded pieces should have the property that

    I(A, B; Ã_𝒳, B̃_𝒳) = 0,

where the mutual information is computed over the randomness in the encoding process.
The parameter X denotes the security level of the system as the security condition describes that any X workers should gain no information about the matrices A and B from their encoded pieces.
If the above condition holds, then we call the SDMM scheme X-secure.

The following examples will show how SDMM schemes have been constructed using polynomial evaluation.

[DFT scheme <cit.>]

Consider the functions

    f(x)    = ∑_j=1^P A_j x^j - 1 + ∑_k=1^X R_k x^P + k - 1, 
    
        g(x)    = ∑_j'=1^P B_j' x^-j' + 1 + ∑_k'=1^X S_k' x^-P - X - k' + 1,

where R_1, …, R_X and S_1, …, S_X are matrices of suitable size chosen uniformly at random.
Each worker is sent Ã_i = f(α_i) and B̃_i = g(α_i).
The workers compute h(α_i) = f(α_i)g(α_i), where

    h(x) = f(x)g(x) = ∑_j=1^P A_jB_j + (non-constant terms).

The terms in the polynomial (in x and x^-1) have degrees in -(P + 2X) + 1, …, P + X - 1.
Let N = P + 2X and choose the evaluation points α_i to be distinct Nth roots of unity.
It is well known that

    ∑_i=1^N α_i^ℓ = 
            N     if N |ℓ
    
            0     otherwise
        .

Therefore,

    1/N∑_i=1^N h(α_i) = ∑_j=1^P A_j B_j = AB,

since the non-constant terms add up to zero.
The existence of the Nth roots of unity requires that N | (q - 1).


[Secure MatDot <cit.>]

Let β_1, …, β_P and α_1, …, α_q - P be distinct points in _q.
Choose polynomials f(x), g(x) ∈_q[x] of degree < P + X such that

    f(β_j)    = A_j,    g(β_j) = B_j,    j ∈ [P] 
    
        f(α_k)    = R_k,    g(α_k) = S_k,    k ∈ [X].

Let N = q - P.
Worker i ∈ [N] receives Ã_i = f(α_i) and B̃_i = g(α_i).
They compute h(α_i) = f(α_i)g(α_i), where h(x) = f(x)g(x) and (h(x)) < 2P + 2X - 1.
Let γ = (β_1, …, β_P, α_1, …, α_q - P) be a vector whose entries are all the elements in _q.
Then,

    _2P + 2X - 1(γ)^⊥ = _q - 2P - 2X + 1(γ).

Let H(x) ∈_q[x] be such that (H(x)) < q - 2P - 2X + 1, H(β_1) = … = H(β_P) = μ≠ 0, and H(x) has many zeros in _q.
The evaluation vector of H(x) on the evaluation points γ is contained in _q - 2P - 2X + 1(γ), so

    ∑_j=1^P h(β_j)H(β_j) + ∑_i=1^N h(α_i)H(α_i) = 0

due to the orthogonality relation.
Thus,

    AB = ∑_j=1^P A_j B_j = ∑_j=1^P h(β_j) = -1/μ∑_i=1^N h(α_i)H(α_i).

If H(α_i) = 0 for many of the α_i, then only a few of the h(α_i) are needed to compute the above sum.
On the other hand, as h(x) has degree < 2P + 2X - 1, any 2P + 2X - 1 responses are sufficient to interpolate h(x) and compute the sum.
The authors of <cit.> construct suitable polynomials H(x) under several assumptions of the field size dividing some of the parameters.




 §.§ Linear SDMM



A general framework for SDMM schemes utilizing linear codes, called linear SDMM, was formulated in <cit.>.
Most of the SDMM schemes presented in the literature can be expressed in terms of this framework, including <ref>.
The encodings are computed using generator matrices F and G of [N, P + X] linear codes 𝒞_A and 𝒞_B, respectively.
In particular,

    (Ã_1, …, Ã_N)    = (A_1, …, A_P, R_1, …, R_X)F, 
    
        (B̃_1, …, B̃_N)    = (B_1, …, B_P, S_1, …, S_X)G,

where R_1, …, R_X and S_1, …, S_X are random matrices of suitable size chosen uniformly at random.
The responses from the workers are

    (Ã_1 B̃_1, …, Ã_N B̃_N) ∈𝒞_A ⋆𝒞_B.

The subcodes of 𝒞_A and 𝒞_B that correspond to the random parts are denoted as 𝒞_A^ and 𝒞_B^.
These codes are generated by the lowest X rows of the generator matrices F and G, respectively.
The following well-known proposition is used to show the security of most SDMM schemes in the literature <cit.>.



A linear SDMM scheme is X-secure if 𝒞_A^ and 𝒞_B^ are [N, X] MDS codes.


By <cit.>, N ≥ P + 2X for any linear SDMM scheme with 𝒞_A^ and 𝒞_B^ MDS codes.
If X ≥ q + 1, then N ≤ X + 1, which is a contradiction, so X ≤ q.
Assuming that the MDS conjecture holds and X ≥ 2, then q ≥ N - 1 (or q ≥ N - 2), where q is the field size and N is the number of workers.
According to this, it would not be possible to construct X-secure SDMM schemes over field sizes significantly smaller than the number of workers[
The scheme in <cit.> is proposed to work over small field sizes (even sublinear in N) if the MDS condition in their generator matrices is fulfilled.
However, this seems to not be possible in generality, assuming the MDS conjecture holds.
].
For X = 1, it may still be possible to reduce the field size due to the fact that the [N, 1] repetition code is MDS over any field.



§ CONSTRUCTION



Denote the length P row vectors whose entries are the matrix partitions by a = (A_1, …, A_P) and b = (B_1, …, B_P).
We have that ab^T = AB due to the inner product partitioning.
If M is an invertible P × P matrix and we are able to compute aMb^T for all a and b, then we may simply compute (aM^-1)Mb^T = ab^T = AB.
This corresponds to first doing a linear transformation on the partitions of matrix A.
This allows us to consider the simpler problem of computing aMb^T for some fixed, but arbitrary, invertible P × P matrix M.

Let q ≥ N and α∈_q^N be a vector with distinct entries.
Consider the encoding polynomials

    f(x)    = ∑_k=1^X R_k x^k - 1 + ∑_j=1^P A_j x^X + j - 1, 
    
        g(x)    = ∑_k'=1^X S_k' x^k' - 1 + ∑_j'=1^P B_j' x^X + j' - 1,

where R_1, …, R_X and S_1, …, S_X are matrices of the same size as the partitions A_j and B_j' chosen uniformly at random.
We define Ã_i = f(α_i), B̃_i = g(α_i) for i ∈ [N].
By definition of Reed–Solomon codes, we have that

    Ã∈𝒞_A = _P + X(α),   B̃∈𝒞_B = _P + X(α).

Furthermore, the security codes are

    𝒞_A^ = 𝒞_B^ = _X(α).

As these codes are MDS, we know that this scheme is X-secure according to <ref>.

The workers compute Ã_i B̃_i, which means that we receive evaluations of the polynomial h(x) = f(x)g(x).
These response vectors are contained in the star product code

    𝒞_A ⋆𝒞_B = _min{2P + 2X - 1, N}(α).

The interference terms of h(x) (those including random parts) are contained in the terms of degree 0, …, P + 2X - 2.
Therefore,

    h(x) = (terms of degree < P + 2X - 1) + ∑_j=1^P∑_j'=1^P A_j B_j' x^2X + j + j' - 2

Let us choose a decoding vector λ∈_P + 2X - 1(α)^⊥, i.e.,

    ∑_i=1^Nλ_i α_i^ℓ = 0

for ℓ = 0, …, P + 2X - 2.
Then,

    ∑_i=1^Nλ_i h(α_i)    = ∑_j=1^P ∑_j'=1^P A_j B_j'∑_i=1^Nλ_i α_i^2X + j + j' - 2,

as all terms of degree < P + 2X - 1 add up to zero according to the definition of λ.
We call this interference cancellation.

We can further write the above sum as aMb^T, where the P × P matrix M is defined by

    M_j,j' = ∑_i=1^Nλ_i α_i^2X + j + j' - 2.



If λ∈_P + 2X - 1(α)^⊥∖_P + 2X(α)^⊥, then the matrix M is invertible.



Notice that M_j, j' only depends on j + j', so let m_j + j' = M_j, j'.
As λ∈_P + 2X - 1(α)^⊥, we have that m_ℓ = 0 for ℓ < P + 1.
Therefore, the matrix M has the following form

    M = [       0         m_P + 1;               ⋰        ; m_P + 1               ⋆ ].

Thus, M is invertible if and only if m_P + 1≠ 0.
If m_P + 1 = 0, then ∑_i=1^Nλ_i α_i^ℓ = 0 for ℓ = 0, …, P + 2X - 1, which implies that λ∈_P + 2X(α)^⊥.
This is a contradiction to the definition of λ, which means that m_P + 1≠ 0.
Therefore, M is invertible.


Using the above lemma, we can compute

    ∑_i=1^Nλ_i h(α_i) = aMb^T,

where M is invertible.
The only requirement on the field size is that q ≥ N for the existence of the Reed–Solomon code of length N.
In the following, we present two constructions based on this idea.



Let N = P + 2X and q ≥ N.
Then there exists an X-secure SDMM scheme over _q using N workers.



By properties of Reed–Solomon codes,

    _P + 2X - 1(α)^⊥   = {ω}
    _P + 2X(α)^⊥   = {0},

for some ω∈ (_q^*)^N.
Therefore, we need to choose λ∈{ω}∖{0}.


We may also add redundancy to the construction such that some of the workers may be ignored.
Let S denote the number of straggling workers we wish to add resiliency to.



Let N = 2P + 2X + S - 1 and q ≥ N.
Then there exists an X-secure SDMM scheme over _q using N workers such that the product can be decoded from any 2P + 2X - 1 workers or from some specified P + 2X workers.



By properties of Reed–Solomon codes,

    _P + 2X - 1(α)^⊥   = _P + S(α, ω) 
    _P + 2X(α)^⊥   = _P + S - 1(α, ω),

for some ω∈ (_q^*)^N.
The minimum distance of the first code is P + 2X, while the minimum distance of the second code is P + 2X + 1.
Let λ be a nonzero codeword of minimum weight in _P + 2X - 1(α)^⊥.
Then it is clear that λ∉_P + 2X(α)^⊥.
As (λ) = P + 2X, it is enough to receive some specific P + 2X responses, since

    aMb^T = ∑_i=1^P λ_i h(α_i) =   ∑_i ∈(λ)  λ_i h(α_i).


As the responses are contained in the code 𝒞_A ⋆𝒞_B = _2P + 2X - 1(α), it is enough to receive any 2P + 2X - 1 = N - S responses to decode all h(α_i) and then compute

    aMb^T = ∑_i=1^Nλ_i h(α_i).



As the dual of a Reed–Solomon code can be explicitly computed, it is easy to find explicit constructions for the above theorems.
The encoding process and the decoding process are simply linear combinations of the matrix blocks.



 §.§ Construction Over the Binary Field



As the MDS conjecture does not state anything about MDS codes of dimension one, such as the repetition code, we may construct the following SDMM scheme over a small field.
Let P be even, X = 1, N = P + 2, and work over _2.
Consider the following shares:

    Ã_j    = R + A_j,    B̃_j    = S + B_j,    j ∈ [P] 
    Ã_P + 1   = R + ∑_j=1^P A_j,    B̃_P + 1   = S, 
    Ã_P + 2   = R,    B̃_P + 2   = S + ∑_j=1^P B_j.

Then, the sum of the responses Ã_i B̃_i, i ∈ [N], is

    ∑_j=1^P (R + A_j)(S + B_j) + (  R + ∑_j=1^P A_j ) S + R (  S + ∑_j=1^P B_j ) 
       = ∑_j=1^P A_jB_j + ( ∑_j=1^P A_j ) S + R ( ∑_j=1^P B_j ) + P · RS 
       + RS + ( ∑_j=1^P A_j ) S + RS + R ( ∑_j=1^P B_j ) = AB.

It is also clear that this is secure with X = 1, since all Ã_i and B̃_i are protected with uniform noise.



§ COMPARISON





In this section we will compare the constructions given in <ref> to those in <cit.>.
In particular, we will compare the number of workers required N, the recovery threshold R, the minimal number of workers needed for decoding, and the field size requirements.
These are listed in <ref>.

The authors of <cit.> do not show the existence of their construction for general parameters P and X.
As commented earlier, under the MDS security condition (<ref>) and the MDS conjecture, it is not possible to reduce the field size to below N - 2 even by using algebraic geometry codes, when X > 1.
On the other hand, the secure MatDot scheme in <cit.> requires the existence of a certain subgroup to make their construction work, which requires some divisibility constraints on the field size q and the other parameters.
Finally, the DFT scheme assumes N | (q - 1), which restricts the possible field.

The constructions given in <ref> provide the most flexibility in the field size and almost reach the bound q ≥ N - 1 (or q ≥ N - 2) given by the MDS conjecture.
Furthermore, <ref> achieves a balance between having redundancy against any S straggling workers, as well as having a set of few workers whose responses are sufficient for recovering the product.

This paper has focused on the number of workers, the recovery threshold, and the minimal recovery size, but for some applications the total download cost is more important.
The authors of <cit.> devise an SDMM scheme using the inner product partitioning that is able to reach lower download cost by downloading symbols in a subfield from a larger number of total workers.
This construction requires extremely large field extensions as seen in <cit.>.



§ CONCLUSIONS


In this paper, we construct SDMM schemes with minimal field size restrictions compared to the previous literature.
This construction can be seen as a generalization of the DFT scheme presented in <cit.> as we are able to efficiently cancel all interference terms in a single linear combination.
We discuss the implications of the MDS conjecture on the field size requirements of X-secure SDMM schemes and find that achieving significantly smaller field sizes is not possible.

So-called extended Reed–Solomon codes achieve the bound n = q + 1 given by the MDS conjecture.
It would be interesting to extend the construction given in this paper to work with extended Reed–Solomon codes and achieve the lowest possible field sizes for X-secure SDMM schemes.



§ ACKNOWLEDGMENT

tocsectionAcknowledgments

This work has been supported by the Research Council of Finland under Grant No. 336005 (PI C. Hollanti) and by the Vilho, Yrjö and Kalle Väisälä Foundation of the Finnish Academy of Science and Letters.

IEEEtran


