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

arXiv:2205.13169

Revisiting the Efficiency of Asynchronous Multi Party Computation Against General Adversaries

Ananya Appan, Anirudh Chandramouli, Ashish Choudhury

Published May 26, 2022• 0 citations
arXivHTMLPDF

Abstract

In this paper, we design secure multi-party computation (MPC) protocols in the asynchronous communication setting with optimal resilience. Our protocols are secure against a computationally-unbounded malicious adversary, characterized by an adversary structure $\mathcal{Z}$, which enumerates all possible subsets of potentially corrupt parties. Our protocols incur a communication of $\mathcal{O}(|\mathcal{Z}|^2)$ and $\mathcal{O}(|\mathcal{Z}|)$ bits per multiplication for perfect and statistical security respectively. These are the first protocols with this communication complexity, as such protocols were known only in the synchronous communication setting (Hirt and Tschudi, ASIACRYPT 2013).

DOI
10.48550/arxiv.2205.13169

Related papers

Asynchronous Multi-Party Computation in Large Networks

Varsha Dani, Valerie King, Mahnush Movahedi +2 more

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 $\tilde{O}(m/n + \sqrt 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(\log{n})$, and can also be used for designing other load-balanced applications in the asynchronous communication model.

arXiv:1203.0289•Mar 1, 2012•0 citations

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

Efficient General-Adversary Multi-Party Computation

Martin Hirt, Daniel Tschudi

Abstract. Secure multi-party computation (MPC) allows a set P of n players to evaluate a function f in presence of an adversary who corrupts a subset of the players. In this paper we consider active, general adversaries, characterized by a so-called adversary structure Z which enumerates all possible subsets of corrupted players. In particular for small sets of players general adversaries better capture real-world requirements than classical threshold adversaries. Protocols for general adversaries are “efficient ” in the sense that they require |Z | O(1) bits of communication. However, as |Z | is usually very large (even exponential in n), the exact exponent is very relevant. In the setting with perfect security, the most efficient protocol known to date communicates O(|Z | 3) bits; we present a protocol for this setting which communicates O(|Z | 2) bits. In the setting with statistical security, O(|Z | 3) bits of communication is needed in general (whereas for a very restricted subclass of adversary structures, a protocol with communication O(|Z | 2) bits is known); we present a protocol for this setting (without limitations) which communicates O(|Z | 1) bits.

•Dec 3, 2013•0 citations

Optimally Resilient Asynchronous MPC with Linear Communication Complexity

Ashish Choudhury, Arpita Patra

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.

International Conference on Distributed Computing and Networking (ICDCN)•Jan 4, 2015•30 citations

Unconditionally Secure Asynchronous Multiparty Computation with Linear Communication Complexity

Ashish Choudhury, Martin Hirt, Arpita Patra

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

•Jan 17, 2013•2 citations

Brief Announcement: Optimally-Resilient Unconditionally-Secure Asynchronous Multi-Party Computation Revisited

Ashish Choudhury

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.

Leibniz international proceedings in informatics•Jan 1, 2020•0 citations
In this paper, we design secure multi-party computation (MPC) protocols in the asynchronous communication setting with optimal resilience. Our protocols are secure against a computationally-unbounded malicious adversary, characterized by an adversary structure Z\mathcal{Z}Z, which enumerates all possible subsets of potentially corrupt parties. Our protocols incur a communication of O(∣Z∣2)\mathcal{O}(|\mathcal{Z}|^2)O(∣Z∣2) and O(∣Z∣)\mathcal{O}(|\mathcal{Z}|)O(∣Z∣) bits per multiplication for perfect and statistical security respectively. These are the first protocols with this communication complexity, as such protocols were known only in the synchronous communication setting (Hirt and Tschudi, ASIACRYPT 2013).
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/31/31/3 fraction of the parties. In the asynchronous setting, we allow the adversary to corrupt less than a 1/81/81/8 fraction of parties. For any deterministic function that can be computed by an arithmetic circuit with mmm 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)\tilde{O}(m/n + \sqrt n)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(log⁡n)O(\log{n})O(logn), and can also be used for designing other load-balanced applications in the asynchronous communication model.
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.
Abstract. Secure multi-party computation (MPC) allows a set P of n players to evaluate a function f in presence of an adversary who corrupts a subset of the players. In this paper we consider active, general adversaries, characterized by a so-called adversary structure Z which enumerates all possible subsets of corrupted players. In particular for small sets of players general adversaries better capture real-world requirements than classical threshold adversaries. Protocols for general adversaries are “efficient ” in the sense that they require |Z | O(1) bits of communication. However, as |Z | is usually very large (even exponential in n), the exact exponent is very relevant. In the setting with perfect security, the most efficient protocol known to date communicates O(|Z | 3) bits; we present a protocol for this setting which communicates O(|Z | 2) bits. In the setting with statistical security, O(|Z | 3) bits of communication is needed in general (whereas for a very restricted subclass of adversary structures, a protocol with communication O(|Z | 2) bits is known); we present a protocol for this setting (without limitations) which communicates O(|Z | 1) bits.
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.
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
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.