Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / Multiparty Computation, Secret Sharing, General Adversaries, Q2 Adversary Structures

Date: received 5 Oct 2013, last revised 3 May 2014

Contact author: jlampkins at math ucla edu, rafail at cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20140503:184154 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]