Entangled polynomial coding in limited-sharing multi-party computation

In a secure multiparty computation (MPC) system, there are some sources, where each one has access to a private input. The sources want to offload the computation of a polynomial function of the inputs to some processing nodes or workers. The processors are unreliable, i.e., a limited number of them may collude to gain information about the inputs. The objective is to minimize the number of required workers to calculate the polynomial, while the colluding workers gain no information about inputs. In this paper, we assume that the inputs are massive matrices, while the workers have the limited computation and storage at each worker. As proxy for that, we assume the link between each source and each worker admits a limited communication load. We propose a scheme for private data sharing, called entangled polynomial sharing, and show that it admits basic operations such as addition, multiplication, and transposing, respecting the constraint of the problem. Thus, it allows computing arbitrary polynomial of the input matrices, while it reduces the number of servers needed significantly compared to the conventional scheme. It also generalizes the recently proposed scheme of polynomial sharing.