Limited-Sharing Multi-Party Computation for Massive Matrix Operations

By Hanzaleh Akbari Nodehi, Mohammad Ali Maddah-Ali. 2018

50 citations recorded by the source corpus.

In this paper, we introduce limited-sharing multiparty computation; in which there is a network of workers (processors) and a set of sources, each having access to a massive matrix as a private input. These sources aim to offload the task of computing a polynomial function of the matrices to the workers, while preserving the privacy of data. We also assume that the load of the link between each source and each worker is upper bounded by a fraction of each input matrix for some $c\in\{1, \frac{1}{2},\frac{1}{3}, \ldots\}$. The objective is to minimize the number of workers needed to perform the computation, such that even if an arbitrary subset of $t-1$ workers, for some $t\in \mathbb{N}$, collude, they cannot gain any information about the input matrices. This framework extends the conventional problem of multi-party computation, where the complexity of computation in each worker is not a constraint. We propose a novel sharing scheme, called polynomial sharing, and several procedures for basic operations such as adding and multiplication of two matrices, and transposing a matrix, and show that any polynomial function of the input matrices can be calculated using the proposed sharing algorithm and above procedures, subject to the problem constraints. We show that for basic operation such as addition and multiplication, the proposed scheme offers order wise gain, in terms of number of servers needed, compared to the approaches formed by concatenation of job splitting and conventional MPC approaches.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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 Computational Theory and Mathematics

Citations in the corpus

On the Upload versus Download Cost for Secure and Private Matrix Multiplication (2019, background): “In [4], the authors considered a variation of the problem where the matrices are kept secure against the servers as well as the user.”
On the Capacity of Secure Distributed Matrix Multiplication (2018, neutral): “Several other recent works that studied secure distributed computing problems that are similar to ours include [12]–[14].”
Rate-Efficiency and Straggler-Robustness through Partition in Distributed Two-Sided Secure Matrix Computation (2018, background): “In [8], Nodehi and Maddah-Ali apply information theory to the framework of limited-sharing multi-party computation.”
Distributed and Private Coded Matrix Computation with Flexible Communication Load (2019, background): “Furthermore, stochastic coding can help keeping both input and output data secure from the workers, assuming that the latter are honest by carrying out the prescribed protocol, but curious [12]–[17].”