Secure Coded Multi-Party Computation for Massive Matrix Operations

DOI10.1109/TIT.2021.3050853zbMATH Open1473.94036arXiv1908.04255OpenAlexW3124082353MaRDI QIDQ5001636

Hanzaleh Akbari-Nodehi, Mohammad Ali Maddah-Ali

Publication date: 22 July 2021

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: In this paper, we consider a secure multi-party computation problem (MPC), where the goal is to offload the computation of an arbitrary polynomial function of some massive private matrices (inputs) to a cluster of workers. The workers are not reliable. Some of them may collude to gain information about the input data (semi-honest workers). The system is initialized by sharing a (randomized) function of each input matrix to each server. Since the input matrices are massive, each share's size is assumed to be at most

1 / k

fraction of the input matrix, for some

k i n m a t h b b N

. The objective is to minimize the number of workers needed to perform the computation task correctly, such that even if an arbitrary subset of

t - 1

workers, for some

t i n m a t h b b N

, collude, they cannot gain any information about the input matrices. We propose a sharing scheme, called emph{polynomial sharing}, and show that it admits basic operations such as adding and multiplication of matrices and transposing a matrix. By concatenating the procedures for basic operations, we show that any polynomial function of the input matrices can be calculated, subject to the problem constraints. We show that the proposed scheme can offer order-wise gain in terms of the number of workers needed, compared to the approaches formed by the concatenation of job splitting and conventional MPC approaches.

Full work available at URL: https://arxiv.org/abs/1908.04255

zbMATH Keywords

polynomial sharing secure multi-party computation problem (MPC)

Mathematics Subject Classification ID

Source coding (94A29) Networks and circuits as models of computation; circuit complexity (68Q06)