Limited Sharing Multi-Party Computation for Massive matrix Operations
17 June 2018
In this paper, we introduce limited-sharing multi party computation; in which there is a network of workers (processors) and also a set of input nodes that have access to some massive matrices as private inputs. These input nodes aim to offload computation of a polynomial function of the matrices to the workers, while preserving the privacy of data. The load of link between each input node and the worker is assumed to be limited (as a proxy to the storage and computation load of the worker). The objective is to minimize the number of workers needed to perform the computation, such that even if an arbitrary subset of less than t workers, for some t 2 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 characterize the number of workers needed to compute any polynomial function using the proposed approach. In addition we show that for basic operation such as addition and multiplication, the proposed scheme offers orderwise gain, in terms of number of servers needed, compared to the approaches formed by concatenation of job splitting and conventional MPC approaches.
