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 \(\varOmega (n^5)\) 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 \(\mathcal {O}(n^2)\) 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 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 (\varOmega (n^5)) 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 (\mathcal {O}(n^2)) 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.
Perfectly-secure verifiable secret sharing (VSS) and multi-party computation (MPC) protocols in asynchronous network tolerate only at most one-fourth of corruption, while their counterparts in synchronous network sustain against at most one-third corruption. Moreover property-wise, synchronous protocols provide much stronger guarantees than the asynchronous counterparts. Taking note of the fact that asynchronous network is more realistic on one hand and on the other, synchrony of a network has positive impact on several aspects of distributed protocols including properties and fault-tolerance, we explore the power of hybrid networks that combines best of both the worlds by supporting a few synchronous rounds at the onset of a protocol execution, before turning to asynchronous mode. In hybrid networks, we investigate various feasibility questions pertaining to protocols giving guarantees attainable in synchronous and asynchronous networks. For the asynchronous protocols in hybrid networks, we hope to leverage the initial synchronous rounds to bridge the gap in the fault-tolerance with the synchronous protocols under minimal synchrony assumption. We ask the following fundamental question of both theoretical and practical importance: What is the minimum number of initial synchronous rounds necessary and sufficient in a hybrid network to construct asynchronous perfectly-secure VSS and MPC protocols with the fault-tolerance of synchronous protocols? On the positive note, we show that the answer is one for VSS which is clearly optimal. Notably no broadcast oracle is invoked in the synchronous round of our proposed VSS protocol. On the negative side, we prove that one synchronous round is not enough for MPC, putting MPC on a higher pedestal than VSS in terms of difficulty. For synchronous protocols in hybrid networks, we hope to save on the synchronous rounds leveraging conveniently the available asynchronous phase. We settle the question for VSS in the negative showing that three rounds that are known to be necessary (and sufficient) for VSS in synchronous networks, are also required in hybrid networks. VSS being a special case of MPC, the lower bound holds true for MPC. We match the lower bound with a three-round protocol. Notably, synchronous MPC with cryptographic security is known to be achievable in hybrid networks with one synchronous round.
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.
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.
Secure multi-party computation (MPC) is a fundamental problem in secure distributed computing. The optimal resilience for perfectly-secure MPC in synchronous and asynchronous networks is t < n/3 and t < n/4 respectively, where n is the number of parties and t is the number of corruptions. A natural question is whether there exists a protocol tolerating ts < n/3 corruptions in a synchronous network and ta < n/4 corruptions in an asynchronous network. We design such a protocol, if 3ts + ta < n. For our protocol, we present a perfectly-secure Byzantine agreement (BA) protocol, tolerating t < n/3 corruptions in any network and a perfectly-secure verifiable secret-sharing (VSS) protocol, tolerating ts and ta corruptions in a synchronous and an asynchronous network respectively.
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.
Multiparty computation (MPC) among n parties can tolerate up to t < n/2 active corruptions in a synchronous communication setting; however, in an asynchronous communication setting, the resiliency bound decreases to only t < n/3 active corruptions. We improve the resiliency bound for asynchronous MPC (AMPC) to match synchronous MPC using non-equivocation. Non-equivocation is a message authentication mechanism to restrict a corrupted sender from mak-ing conflicting statements to different (honest) parties. It can be implemented using an increment-only counter and a digital signature oracle, realizable with trusted hardware modules readily available in com-modity computers and smartphone devices. A non-equivocation mechanism can also be transferable and allow a receiver to verifiably transfer the authenticated statement to other parties. In this work, using transferable non-equivocation, we present an AMPC protocol tolerating t < n/2 faults. From a practical point of view, our AMPC protocol requires fewer setup assumptions than the previous AMPC protocol with t < n/2 by Beerliová-Trubı́niová, Hirt and Nielsen [PODC 2010]: unlike their AMPC protocol, it does not require any synchronous broadcast round at the beginning of the protocol and avoids the threshold homomorphic encryption setup assumption. Moreover, our AMPC protocol is also efficient and provides a gain of Θ(n) in the communication complexity per multiplication gate, over the AMPC protocol of Beerliová-Trubı́niova ́ et al. In the process, using non-equivocation, we also define the first asynchronous verifiable secret sharing (AVSS) scheme with t < n/2, which is of independent interest to threshold cryptography. 1