You are looking at a specific version 20131010:144943 of this paper. See the latest version.

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 ComputationSecret SharingGeneral AdversariesQ2 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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.