Entangled polynomial coding in limited-sharing multi-party computation

Hanzaleh Akbari Nodehi, Seyed Reza Hoseini Najarkolaei, Mohammad Ali Maddah-Ali

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Scopus citations


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.

Original languageEnglish (US)
Title of host publication2018 IEEE Information Theory Workshop, ITW 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781538635995
StatePublished - Jul 2 2018
Externally publishedYes
Event2018 IEEE Information Theory Workshop, ITW 2018 - Guangzhou, China
Duration: Nov 25 2018Nov 29 2018

Publication series

Name2018 IEEE Information Theory Workshop, ITW 2018


Conference2018 IEEE Information Theory Workshop, ITW 2018

Bibliographical note

Publisher Copyright:
© 2018 IEEE Information Theory Workshop, ITW 2018. All rights reserved.


  • Entangled polynomial sharing
  • Massive matrix computation
  • Multi-party computation
  • Secure computation


Dive into the research topics of 'Entangled polynomial coding in limited-sharing multi-party computation'. Together they form a unique fingerprint.

Cite this