Rate-Efficiency and Straggler-Robustness through Partition in Distributed Two-Sided Secure Matrix Computation

By Jaber Kakar, Seyedhamed Ebadifar, Aydin Sezgin. 2018

32 citations recorded by the source corpus.

Computationally efficient matrix multiplication is a fundamental requirement in various fields, including and particularly in data analytics. To do so, the computation task of a large-scale matrix multiplication is typically outsourced to multiple servers. However, due to data misusage at the servers, security is typically of concern. In this paper, we study the two-sided secure matrix multiplication problem, where a user is interested in the matrix product $\boldsymbol{AB}$ of two finite field private matrices $\boldsymbol{A}$ and $\boldsymbol{B}$ from an information-theoretic perspective. In this problem, the user exploits the computational resources of $N$ servers to compute the matrix product, but simultaneously tries to conceal the private matrices from the servers. Our goal is twofold: (i) to maximize the communication rate, and, (ii) to minimize the effective number of server observations needed to determine $\boldsymbol{AB}$, while preserving security, where we allow for up to $\ell\leq N$ servers to collude. To this end, we propose a general aligned secret sharing scheme for which we optimize the matrix partition of matrices $\boldsymbol{A}$ and $\boldsymbol{B}$ in order to either optimize objective (i) or (ii) as a function of the system parameters (e.g., $N$ and $\ell$). A proposed inductive approach gives us analytical, close-to-optimal solutions for both (i) and (ii). With respect to (i), our scheme significantly outperforms the existing scheme of Chang and Tandon in terms of (a) communication rate, (b) maximum tolerable number of colluding servers and (c) computational complexity.

Subfields: Artificial Intelligence

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

Citations in the corpus

On the Upload versus Download Cost for Secure and Private Matrix Multiplication (2019, background): “Both works proposed schemes based on polynomial codes, where the authors of [7] studied the non-colluding version of the problem and the authors of [6] studied the colluding version (also see recent improvements and variants in [8]–[11]).”
Distributed and Private Coded Matrix Computation with Flexible Communication Load (2019, background): “In [14], [15], [17] a reduction of the communication load is addressed by extending polynomial codes.”