On the Capacity of Secure Distributed Matrix Multiplication

By Wei-Ting Chang, Ravi Tandon. 2018

140 citations recorded by the source corpus.

Matrix multiplication is one of the key operations in various engineering applications. Outsourcing large-scale matrix multiplication tasks to multiple distributed servers or cloud is desirable to speed up computation. However, security becomes an issue when these servers are untrustworthy. In this paper, we study the problem of secure distributed matrix multiplication from distributed untrustworthy servers. This problem falls in the category of secure function computation and has received significant attention in the cryptography community. However, characterizing the fundamental limits of information-theoretically secure matrix multiplication remain an open problem. We focus on information-theoretically secure distributed matrix multiplication with the goal of characterizing the minimum communication overhead. The capacity of secure matrix multiplication is defined as the maximum possible ratio of the desired information and the total communication received from $N$ distributed servers. In particular, we study the following two models where we want to multiply two matrices $A\in \mathbb{F}^{m\times \mathrm{n}}$ and $B\in \mathbb{F}^{n\times p}$: (a) one-sided secure matrix multiplication with $\ell$ colluding servers, in which $B$ is a public matrix available at all servers and $A$ is a private matrix. (b) fully secure matrix multiplication with $\ell$ colluding servers, in which both $A$ and $B$ are private matrices. The goal is to securely multiply $A$ and $B$ when any $\ell$ servers can collude. For model (a), we characterize the capacity as $C_{\mathbf{one}-\mathbf{sided}}^{(\ell)}= (N-\ell)/N$ by providing a secure matrix multiplication scheme and a matching converse. For model (b), we propose a novel scheme that lower bounds the capacity, i.e., $C_{\mathrm{fuly}}\geq(\lceil\sqrt{N}-\ell\rceil)^{2}/(\lceil\sqrt{N}-\ell\rceil+\ell)^{2}$.

Subfields: Artificial Intelligence, Federated & Distributed Learning, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Federated & Distributed Learning

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, methodology): “ent’s sub-model choice private? One promising approach is to use PIR for private sub-model download, while aggregating model updates using a variant of secure aggregation optimized for sparse vectors [94, 216, 310]. Open problems in this area include characterizing the sparsity regimes associated wi”
On the Upload versus Download Cost for Secure and Private Matrix Multiplication (2019, methodology): “, no privacy constraint), the download cost of D = N/(N−1) is information-theoretically optimal as shown in our previous work [6].”
Federated Learning on Non-IID Data: A Survey (2021, background): “focus on the secure modeling under decentralized data shards and propose a federated transfer learning (FTL) framework, which leverages homomorphic encryption [36] and secret sharing [14] as protocols [89].”
Distributed and Private Coded Matrix Computation with Flexible Communication Load (2019, background): “The security constraint (1) can be proved in a manner similar to [14] by the following steps:”
Rate-Efficiency and Straggler-Robustness through Partition in Distributed Two-Sided Secure Matrix Computation (2018, background): “In [10], Chang and Tandon study the communication rate of a secure matrix multiplication problem consisting of a single user and N curious servers which are responsible for the computation of two matrices available at the user.”
ON THE CAPACITY OF SECURE DISTRIBUTED FAST FOURIER TRANSFORM (2018, methodology): “A few works that do take security into account include [14, 15] where both works used secret sharing scheme along with different encoding strategies to make sure that the computations are secure, and [16] proposed a novel coded computing strat-”
GASP Codes for Secure Distributed Matrix Multiplication (2018, methodology): “Before launching into the construction of GASP, let us offer some intuitive explanation as to the large improvement in rate offered by GASP over [1], [2].”