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.
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.