Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Symposium on Principles of Distributed Computing (PODC)

Perfectly-secure Network-agnostic MPC with Optimal Resiliency

Shravani Mahesh Patil, Arpita Patra

Published Jun 13, 2025• 4 citations
Publisher

Abstract

We study network-agnostic secure multiparty computation with perfect security. Traditionally MPC is studied assuming the underlying network is either synchronous or asynchronous. In a network-agnostic setting, the parties are unaware of whether the underlying network is synchronous or asynchronous.
DOI
10.1145/3732772.3733500

Related papers

Network Agnostic Perfectly Secure Multiparty Computation Against General Adversaries

Ananya Appan, Anirudh Chandramouli, Ashish Choudhury

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, meaning that the union of no three subsets from the adversary structure covers the entire set of parties. On the other hand, perfectly-secure MPC protocols in the asynchronous network can be designed only against$ {{\mathcal {Q}}}^{(4)}$adversary structures, meaning that the union of no four subsets from the adversary structure covers the entire set of parties. A natural question is whether a single MPC protocol exists, which remains secure even if the parties are unaware of the network conditions at execution time. That is, if the synchrony is satisfied throughout the protocol execution then the protocol should be secure against any$ {{\mathcal {Q}}}^{(3)}$adversary structure. However, even if any synchrony assumption is violated during the execution, the protocol should still be secure against any$ {{\mathcal {Q}}}^{(4)}$adversary structure. We answer the above question affirmatively. Fix any adversary structure${\mathcal {Z}}_{s}$and${\mathcal {Z}}_{a}$satisfying$ {{\mathcal {Q}}}^{(3)}$and$ {{\mathcal {Q}}}^{(4)}$conditions respectively, such that${\mathcal {Z}}_{a} \subset {\mathcal {Z}} _{s}$. We show the existence of a network-agnostic perfectly-secure MPC protocol tolerating${\mathcal {Z}}_{s}$and${\mathcal {Z}}_{a}$in synchronous and asynchronous networks respectively as long as the$ {{\mathcal {Q}}}^{(3, 1)}$condition is satisfied, meaning that the union of no three subsets from${\mathcal {Z}}_{s}$and one subset from${\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.

IEEE Transactions on Information Theory•Sep 30, 2024•1 citation

Network Agnostic Perfectly Secure MPC Against General Adversaries

Ananya Appan, Anirudh Chandramouli, Ashish Choudhury

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.

arXiv:2208.06223•Leibniz international proceedings in informatics•Aug 12, 2022•1 citation

Perfectly-Secure Synchronous MPC With Asynchronous Fallback Guarantees

Ananya Appan, Anirudh Chandramouli, Ashish Choudhury

Securemulti-party computation(MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set of$n$mutually 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 any$t_{s} < n/3$parties. On the other hand, perfectly-secureasynchronousMPC protocols can tolerate up to$t_{a} < n/4$corrupt 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 to$t_{s} < n/3$corruptions in a synchronous network and up to$t_{a} < n/4$corruptions in anasynchronousnetwork. We design such abest-of-both-worldsperfectly-secure MPC protocol, provided$3t_{s} + t_{a} < n$holds. 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 tolerating$t < n/3$corruptions 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 to$t_{s}$and$t_{a}$corruptions in asynchronousand in anasynchronousnetwork respectively.

IEEE Transactions on Information Theory•Apr 5, 2023•2 citations

Perfectly-Secure Synchronous MPC with Asynchronous Fallback Guarantees

Ananya Appan, Anirudh Chandramouli, Ashish Choudhury

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.

arXiv:2201.12194•ACM Symposium on Principles of Distributed Computing (PODC)•Jul 20, 2022•20 citations

On the theoretical gap between synchronous and asynchronous MPC protocols

Zuzana Beerliová-Trubíniová, Martin Hirt, Jesper Buus Nielsen

Multiparty computation (MPC) protocols among n parties secure against t active faults are known to exist if and only if

ACM Symposium on Principles of Distributed Computing (PODC)•Jul 25, 2010•21 citations

Asynchronous MPC with a strict honest majority using non-equivocation

Michael Backes A, Fabian Bendun, Ashish Choudhury +1 more

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.

ACM Symposium on Principles of Distributed Computing (PODC)•Jul 15, 2014•19 citations
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−secureMPCprotocolsintheasynchronousnetworkcanbedesignedonlyagainstcondition, meaning that the union of no three subsets from the adversary structure covers the entire set of parties. On the other hand, perfectly-secure MPC protocols in the asynchronous network can be designed only againstcondition,meaningthattheunionofnothreesubsetsfromtheadversarystructurecoverstheentiresetofparties.Ontheotherhand,perfectly−secureMPCprotocolsintheasynchronousnetworkcanbedesignedonlyagainst {{\mathcal {Q}}}^{(4)}adversarystructures,meaningthattheunionofnofoursubsetsfromtheadversarystructurecoverstheentiresetofparties.AnaturalquestioniswhetherasingleMPCprotocolexists,whichremainssecureevenifthepartiesareunawareofthenetworkconditionsatexecutiontime.Thatis,ifthesynchronyissatisfiedthroughouttheprotocolexecutionthentheprotocolshouldbesecureagainstanyadversary structures, meaning that the union of no four subsets from the adversary structure covers the entire set of parties. A natural question is whether a single MPC protocol exists, which remains secure even if the parties are unaware of the network conditions at execution time. That is, if the synchrony is satisfied throughout the protocol execution then the protocol should be secure against anyadversarystructures,meaningthattheunionofnofoursubsetsfromtheadversarystructurecoverstheentiresetofparties.AnaturalquestioniswhetherasingleMPCprotocolexists,whichremainssecureevenifthepartiesareunawareofthenetworkconditionsatexecutiontime.Thatis,ifthesynchronyissatisfiedthroughouttheprotocolexecutionthentheprotocolshouldbesecureagainstany {{\mathcal {Q}}}^{(3)}adversarystructure.However,evenifanysynchronyassumptionisviolatedduringtheexecution,theprotocolshouldstillbesecureagainstanyadversary structure. However, even if any synchrony assumption is violated during the execution, the protocol should still be secure against anyadversarystructure.However,evenifanysynchronyassumptionisviolatedduringtheexecution,theprotocolshouldstillbesecureagainstany {{\mathcal {Q}}}^{(4)}adversarystructure.Weanswertheabovequestionaffirmatively.Fixanyadversarystructureadversary structure. We answer the above question affirmatively. Fix any adversary structureadversarystructure.Weanswertheabovequestionaffirmatively.Fixanyadversarystructure{\mathcal {Z}}_{s}andandand{\mathcal {Z}}_{a}satisfyingsatisfyingsatisfying {{\mathcal {Q}}}^{(3)}andandand {{\mathcal {Q}}}^{(4)}conditionsrespectively,suchthatconditions respectively, such thatconditionsrespectively,suchthat{\mathcal {Z}}_{a} \subset {\mathcal {Z}} _{s}.Weshowtheexistenceofanetwork−agnosticperfectly−secureMPCprotocoltolerating. We show the existence of a network-agnostic perfectly-secure MPC protocol tolerating.Weshowtheexistenceofanetwork−agnosticperfectly−secureMPCprotocoltolerating{\mathcal {Z}}_{s}andandand{\mathcal {Z}}_{a}insynchronousandasynchronousnetworksrespectivelyaslongasthein synchronous and asynchronous networks respectively as long as theinsynchronousandasynchronousnetworksrespectivelyaslongasthe {{\mathcal {Q}}}^{(3, 1)}conditionissatisfied,meaningthattheunionofnothreesubsetsfromcondition is satisfied, meaning that the union of no three subsets fromconditionissatisfied,meaningthattheunionofnothreesubsetsfrom{\mathcal {Z}}_{s}andonesubsetfromand one subset fromandonesubsetfrom{\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)Q^{(3)}Q(3) adversary structures, while in an asynchronous network, known protocols are secure against Q(4)Q^{(4)}Q(4) adversary structures. A natural question is whether there exists a single protocol which remains secure against Q(3)Q^{(3)}Q(3) and Q(4)Q^{(4)}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)Q^{(3)}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)Q^{(3)}Q(3) and Q(4)Q^{(4)}Q(4) adversary structures in a synchronous network and an asynchronous network respectively.
Securemulti-party computation(MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set ofnnnmutually 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/3t_{s} < n/3ts​<n/3parties. On the other hand, perfectly-secureasynchronousMPC protocols can tolerate up tota<n/4t_{a} < n/4ta​<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/3t_{s} < n/3ts​<n/3corruptions in a synchronous network and up tota<n/4t_{a} < n/4ta​<n/4corruptions in anasynchronousnetwork. We design such abest-of-both-worldsperfectly-secure MPC protocol, provided3ts+ta<n3t_{s} + t_{a} < n3ts​+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/3t < n/3t<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 totst_{s}ts​andtat_{a}ta​corruptions in asynchronousand in anasynchronousnetwork 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.