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.
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.
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 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 work, we study perfectly-secure multi-party computation (MPC) against general (non-threshold) adversaries. Known protocols in a synchronous network are secure against Q(3) adversary structures, while in an asynchronous network, known protocols are secure against Q(4) adversary structures. A natural question is whether there exists a single protocol which remains secure against Q(3) and Q(4) adversary structures in a synchronous and in an asynchronous network respectively, where the parties are not aware of the network type. We design the first such best-of-both-worlds protocol against general adversaries. Our result generalizes the result of Appan, Chandramouli and Choudhury (PODC 2022), which presents a best-of-both-worlds perfectly-secure protocol against threshold adversaries. To design our protocol, we present two important building blocks which are of independent interest. The first building block is a best-of-both-worlds perfectly-secure Byzantine agreement (BA) protocol for Q(3) adversary structures, which remains secure both in a synchronous, as well as an asynchronous network. The second building block is a best-of-both-worlds perfectly-secure verifiable secret-sharing (VSS) protocol, which remains secure against Q(3) and Q(4) adversary structures in a synchronous network and an asynchronous network respectively.
In this work, we initiate the study of network-agnostic perfectly-secure multi-party computation (MPC) against general (non-threshold) adversaries, where the corruption capacity of the adversary is specified through an adversary structure, which is a set of potentially corrupt subsets of parties. Known MPC protocols are designed either assuming a synchronous network where every sent message is guaranteed to be delivered within some known time or assuming an asynchronous network where no timing assumptions are made and every sent message is eventually delivered. Perfectly-secure MPC protocols in the synchronous network can be designed as long as the underlying adversary structure satisfies the$ {{\mathcal {Q}}}^{(3)}condition,meaningthattheunionofnothreesubsetsfromtheadversarystructurecoverstheentiresetofparties.Ontheotherhand,perfectly−secureMPCprotocolsintheasynchronousnetworkcanbedesignedonlyagainst {{\mathcal {Q}}}^{(4)}adversarystructures,meaningthattheunionofnofoursubsetsfromtheadversarystructurecoverstheentiresetofparties.AnaturalquestioniswhetherasingleMPCprotocolexists,whichremainssecureevenifthepartiesareunawareofthenetworkconditionsatexecutiontime.Thatis,ifthesynchronyissatisfiedthroughouttheprotocolexecutionthentheprotocolshouldbesecureagainstany {{\mathcal {Q}}}^{(3)}adversarystructure.However,evenifanysynchronyassumptionisviolatedduringtheexecution,theprotocolshouldstillbesecureagainstany {{\mathcal {Q}}}^{(4)}adversarystructure.Weanswertheabovequestionaffirmatively.Fixanyadversarystructure{\mathcal {Z}}_{s}and{\mathcal {Z}}_{a}satisfying {{\mathcal {Q}}}^{(3)}and {{\mathcal {Q}}}^{(4)}conditionsrespectively,suchthat{\mathcal {Z}}_{a} \subset {\mathcal {Z}} _{s}.Weshowtheexistenceofanetwork−agnosticperfectly−secureMPCprotocoltolerating{\mathcal {Z}}_{s}and{\mathcal {Z}}_{a}insynchronousandasynchronousnetworksrespectivelyaslongasthe {{\mathcal {Q}}}^{(3, 1)}conditionissatisfied,meaningthattheunionofnothreesubsetsfrom{\mathcal {Z}}_{s}andonesubsetfrom{\mathcal {Z}}_{a}$covers the entire set of parties. Our result generalizes the result of Appan, Chandramouli and Choudhury (IEEE Transactions on IT, 2023), which presents the only known perfectly-secure network-agnostic MPC protocol against threshold adversaries.
We describe scalable protocols for solving the secure multi-party computation (MPC) problem among a large number of parties. We consider both the synchronous and the asynchronous communication models. In the synchronous setting, our protocol is secure against a static malicious adversary corrupting less than a 1/3 fraction of the parties. In the asynchronous setting, we allow the adversary to corrupt less than a 1/8 fraction of parties. For any deterministic function that can be computed by an arithmetic circuit with m gates, both of our protocols require each party to send a number of field elements and perform an amount of computation that is O~(m/n+n). We also show that our protocols provide perfect and universally-composable security. To achieve our asynchronous MPC result, we define the \emph{threshold counting problem} and present a distributed protocol to solve it in the asynchronous setting. This protocol is load balanced, with computation, communication and latency complexity of O(logn), and can also be used for designing other load-balanced applications in the asynchronous communication model.