Unconditionally secure multiparty computation (MPC) allows a set of n mutually distrusting parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can actively corrupt any t out of the n parties. Designing an asynchronous MPC (AMPC) protocol with a communication complexity of O(n) field elements per multiplication gate is a long standing open problem. We solve the open problem by presenting two AMPC protocols with the corruption threshold t < n/4. Our first protocol is statistically secure (i.e. involves a negligible error in the protocol outcome) in a completely asynchronous setting and improves the communication complexity of the previous best AMPC protocol in the same setting by a factor of Θ(n). Our second protocol is perfectly secure (i.e. error free) in a hybrid setting, where one round of communication is assumed to be synchronous and improves the communication complexity of the previous best AMPC protocol in the hybrid setting by a factor of Θ(n 2). Starting with the seminal work of Beaver (CRYPTO 1991), it is by now a well-known technique to evaluate multiplication gates in an MPC protocol using shared random multiplication triples. The central contribution common to both the presented protocols is a new and simple framework for generating shared random multiplication triples. All the existing protocols approach the problem by first producing shared pairs of random values, followed by computing
Unconditionally secure multiparty computation (MPC) allows a set of n mutually distrusting parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can actively corrupt any t out of the n parties. Designing an asynchronous MPC (AMPC) protocol with a communication complexity of O(n) field elements per multiplication gate is a long standing open problem. We solve the open problem by presenting two AMPC protocols with the corruption threshold t < n/4. Our first protocol is statistically secure (i.e. involves a negligible error in the protocol outcome) in a completely asynchronous setting and improves the communication complexity of the previous best AMPC protocol in the same setting by a factor of Θ(n). Our second protocol is perfectly secure (i.e. error free) in a hybrid setting, where one round of communication is assumed to be synchronous and improves the communication complexity of the previous best AMPC protocol in the hybrid setting by a factor of Θ(n 2). Starting with the seminal work of Beaver (CRYPTO 1991), it is by now a well-known technique to evaluate multiplication gates in an MPC protocol using shared random multiplication triples. The central contribution common to both the presented protocols is a new and simple framework for generating shared random multiplication triples. All the existing protocols approach the problem by first producing shared pairs of random values, followed by computing
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(n2) and O(n3), respectively. Our framework when applied to the synchronous setting results in round-efficient MPC protocols.
In this work, we study unconditionally-secure multi-party computation (MPC) tolerating t<n/3 corruptions, where n is the total number of parties involved. In this setting, it is well known that if the underlying network is completely asynchronous, then one can achieve only statistical security; moreover it is impossible to ensure input provision and consider inputs of all the honest parties. The best known statistically-secure asynchronous MPC (AMPC) with t<n/3 requires a communication of Ω(n5) field elements per multiplication. We consider a partially synchronous setting, where the parties are assumed to be globally synchronized initially for few rounds and then the network becomes completely asynchronous. In such a setting, we present a MPC protocol, which requires O(n2) communication per multiplication while ensuring input provision. Our MPC protocol relies on a new four round, communication efficient statistical verifiable secret-sharing (VSS) protocol with broadcast communication complexity independent of the number of secret-shared values.
In this paper, we present an optimally-resilient, unconditionally-secure asynchronous multi-party computation (AMPC) protocol for n parties, tolerating a computationally unbounded adversary, capable of corrupting up to t < n/3 parties. Our protocol needs a communication of 𝒪(n⁴) field elements per multiplication gate. This is to be compared with previous best AMPC protocol (Patra et al, ICITS 2009) in the same setting, which needs a communication of 𝒪(n⁵) field elements per multiplication gate. To design our protocol, we present a simple and highly efficient asynchronous verifiable secret-sharing (AVSS) protocol, which is of independent interest.
The N sets of parties which are allowed by unconditionally the secure multiparty computation (MPC) for computing securely with a registered function f with the help of unbounded adversary computational at some specified field. Here one can corrupt t among n parties maliciously corrupt. The Protocols of MPC which are known and efficient are developed for online or offline framework. Coming to the offline process, the private & random multiplication-triples which is sharable can be generated by the parties in this framework. Later on, these are useful for online to evaluate the multiplication of gates securely in a circuit which describes as f. In this, Protocols of the MPC efficiency depends on the how the offline implementation efficiently. Here, we proposed a simple method, for shared & private multiplication-triples which are random in nature generation without any conditions securely & safely. The typical protocols face this issue, when the random values of shared pairs produced initially. And also, in computing the product values which is shared for every pair. After that, protocols of multiplication and values which are considered as communication intensive. In proposed scheme, the multiplication protocols are completely used in different manner. Later on, we observe that the share multiplication-triples verification by parties or they are extracted securely or not. With the use of setting of the hybrid network and asynchronous, linear communication MPC protocols used which are multiplication gate overhead & indicates as f. The above are the improvements on the typical MPC protocols with the help of hybrid networking setting, asynchronous and complexity of the communication, if we give to result of synchronous setting in our system. It results efficient MPC protocols which are rounded.
We present a secure asynchronous multiparty computation (AMPC) protocol with optimal resilience, involving n = 3t + 1 parties and tolerating a computationally bounded static adversary, capable of corrupting upto t parties. For a security parameter k and for circuits of sufficiently large size, our protocol has an amortized communication complexity of O(cMnk) bits, where cM denotes the number of multiplication gates in the arithmetic circuit, representing the function to be computed. Prior to our work, the most efficient optimally resilient, computationally secure AMPC protocol was due to Hirt et al. (ICALP 2008). The protocol offers an amortized communication complexity of O(cMn2k) bits.
Securemulti-party computation(MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set ofnmutually distrusting parties to carry out any joint computation of their private inputs, without disclosing any additional information about their inputs. MPC withinformation-theoreticsecurity (also calledunconditional security) provides the strongest security guarantees and remains secure even againstcomputationally unboundedadversaries.Perfectly-secureMPC protocols are a class of information-theoretically secure MPC protocols, which provide all the security guarantees in anerror-freefashion. The focus of this work is perfectly-secure MPC. Known protocols are designedassumingeither asynchronousorasynchronouscommunication network. It is well known that perfectly-securesynchronousMPC is possible as long as the adversary can corrupt anyts<n/3parties. On the other hand, perfectly-secureasynchronousMPC protocols can tolerate up tota<n/4corrupt parties. A natural question is does there exist asingleMPC protocol for the setting where the parties arenot awareof the exact network type and which can tolerate up tots<n/3corruptions in a synchronous network and up tota<n/4corruptions in anasynchronousnetwork. We design such abest-of-both-worldsperfectly-secure MPC protocol, provided3ts+ta<nholds. For designing our protocol, we design two important building blocks which are of independent interest. The first building block is a best-of-both-worldsByzantine agreement(BA) protocol toleratingt<n/3corruptions which remains securebothin a synchronous as well as asynchronous network. The second building block is a polynomial-based best-of-both-worldsverifiable secret-sharing(VSS) protocol, which can tolerate up totsandtacorruptions in asynchronousand in anasynchronousnetwork respectively.