An Efficient Framework for Unconditionally Secure Multiparty Computation
Authors:
- 4 October 2016
- journal article
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 63 (1) , 428-468
Abstract
parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can maliciously corrupt any t out of the n parties. Most of the known efficient MPC protocols are designed in the offline- online framework introduced in a seminal work by Beaver in CRYPTO 1991. In this framework, the parties generate shared random and private multiplication-triples during the offline phase, which are used later in the online phase for securely evaluating the multiplication gates in the circuit representing f . The efficiency of the MPC protocols in this framework then relies on efficient ways of implementing the offline phase. In this paper, we propose a new and simple framework for generating shared and private random multiplication triples with unconditional security. The existing protocols approach this problem by first producing shared pairs of private and random values, followed by securely computing the shared product of each pair of values. The latter task involves a multiplication protocol for shared values that are typically communication intensive. Our framework takes a completely different approach and shuns the use of multiplication protocol. Namely, we ask the parties to verifiably share random multiplication triples and then securely extract shared random multiplication triples unknown to the adversary, from the shared triples. Realizing our framework in the asynchronous and hybrid network setting,1 we present the first ever MPC protocols with a linear (in the number of parties) communication overhead per multiplication gate in the circuit representing f . These are significant improvements over the best known existing MPC protocols in the asynchronous and hybrid network setting with communication complexity O(n 2 ) and O(n 3 ), respectively. Our framework when applied to the synchronous setting results in round-efficient MPC protocols.Keywords
Funding Information
- Infosys Foundation
- INSPIRE Faculty Fellowship from Department of Science and Technology, India (DST/INSPIRE/04/2014/015727)
This publication has 39 references indexed in Scilit:
- Efficient Asynchronous Verifiable Secret Sharing and Multiparty ComputationJournal of Cryptology, 2013
- On the Complexity of Broadcast SetupLecture Notes in Computer Science, 2013
- Asynchronous Multiparty Computation with Linear Communication Complexity2013
- Information-Theoretically Secure Protocols and Security under CompositionSIAM Journal on Computing, 2010
- Improving the round complexity of VSS in point-to-point networksInformation and Computation, 2009
- Robust sharing of secrets when the dealer is honest or cheatingJournal of the ACM, 1994
- Perfectly secure message transmissionJournal of the ACM, 1993
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- On sharing secrets and Reed-Solomon codesCommunications of the ACM, 1981
- How to share a secretCommunications of the ACM, 1979