Limited-Sharing Multi-Party Computation for Massive Matrix Operations

Hanzaleh Akbari Nodehi, Mohammad Ali Maddah-Ali

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

35 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication2018 IEEE International Symposium on Information Theory, ISIT 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1231-1235
Number of pages5
ISBN (Print)9781538647806
DOIs
StatePublished - Aug 15 2018
Externally publishedYes
Event2018 IEEE International Symposium on Information Theory, ISIT 2018 - Vail, United States
Duration: Jun 17 2018Jun 22 2018

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2018-June
ISSN (Print)2157-8095

Other

Other2018 IEEE International Symposium on Information Theory, ISIT 2018
Country/TerritoryUnited States
CityVail
Period6/17/186/22/18

Bibliographical note

Publisher Copyright:
© 2018 IEEE.

Keywords

  • Massive matrix computation
  • Multi-party computation
  • Polynomial sharing
  • Secure computation

Fingerprint

Dive into the research topics of 'Limited-Sharing Multi-Party Computation for Massive Matrix Operations'. Together they form a unique fingerprint.

Cite this