Communication-Efficient MPC for General Adversary Structures

Joshua Lampkins; Rafail Ostrovsky

Paper 2013/640

Communication-Efficient MPC for General Adversary Structures

Joshua Lampkins and Rafail Ostrovsky

Abstract

A multiparty computation (MPC) protocol allows a set of players to compute a function of their inputs while keeping the inputs private and at the same time securing the correctness of the output. Most MPC protocols assume that the adversary can corrupt up to a fixed fraction of the number of players. Hirt and Maurer initiated the study of MPC under more general corruption patterns, in which the adversary is allowed to corrupt any set of players in some pre-defined collection of sets [6]. In this paper we consider this important direction of research and present significantly improved communication complexity of MPC protocols for general adversary structures. More specifically, ours is the first unconditionally secure protocol that achieves linear communication in the size of Monotone Span Program representing the adversary structure in the malicious setting against any Q2 adversary structure, whereas all previous protocols were at least cubic.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint. MINOR revision.
Keywords: Multiparty Computation Secret Sharing General Adversaries Q2 Adversary Structures
Contact author(s): jlampkins @ math ucla edu
rafail @ cs ucla edu
History: 2014-05-03: revised; 2013-10-10: received; See all versions
Short URL: https://ia.cr/2013/640
License: CC BY

BibTeX

@misc{cryptoeprint:2013/640,
      author = {Joshua Lampkins and Rafail Ostrovsky},
      title = {Communication-Efficient {MPC} for General Adversary Structures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/640},
      year = {2013},
      url = {https://eprint.iacr.org/2013/640}
}