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

An Asynchronous Multi-Party Computation Protocol

Martin Hirt, Jesper Buus Nielsen, Bartosz Przydatek

Published Jan 1, 2004• 0 citations
OpenAlex

Abstract

We consider secure multi-party computation in the asynchronous model and present an e#cient protocol with optimal resilience. For n parties, up to t n/3 of them being corrupted, and security parameter #, a circuit with c gates can be securely computed with communication complexity #) bits. In contrast to all previous asynchronous protocols with optimal resilience, our protocol requires access to an expensive broadcast primitive only O(n) times --- independently of the size c of the circuit. This results in a practical protocol with a very low communication overhead.

Related papers

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

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

Revisiting the Efficiency of Asynchronous Multi Party Computation Against General Adversaries

Ananya Appan, Anirudh Chandramouli, Ashish Choudhury

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

arXiv:2205.13169•May 26, 2022•0 citations

Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation.

Martin Hirt, Jesper Buus Nielsen

Abstract. We give improved upper bounds on the communication complexity of optimally-resilient secure multiparty computation in the cryptographic model. We consider evaluating an n-party randomized function and show that if f can be computed by a circuit of size c, thenO(cn 2 κ) is an upper bound for active security with optimal resilience t<n/2and security parameter κ. This improves on the communication complexity of previous protocols by a factor of at least n. This improvement comes from the fact that in the new protocol, only O(n) messages (of size O(κ) each) are broadcast during the whole protocol execution, in contrast to previous protocols which require at least O(n) broadcasts per gate. Furthermore, we improve the upper bound on the communication complexity of passive secure multiparty computation with resilience t<n from O(cn 2 κ)toO(cnκ). This improvement is mainly due to a simple observation. 1

•Jan 1, 2004•0 citations

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

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
We consider secure multi-party computation in the asynchronous model and present an e#cient protocol with optimal resilience. For n parties, up to t n/3 of them being corrupted, and security parameter #, a circuit with c gates can be securely computed with communication complexity #) bits. In contrast to all previous asynchronous protocols with optimal resilience, our protocol requires access to an expensive broadcast primitive only O(n) times --- independently of the size c of the circuit. This results in a practical protocol with a very low communication overhead.
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.
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.
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).
Abstract. We give improved upper bounds on the communication complexity of optimally-resilient secure multiparty computation in the cryptographic model. We consider evaluating an n-party randomized function and show that if f can be computed by a circuit of size c, thenO(cn 2 κ) is an upper bound for active security with optimal resilience t<n/2and security parameter κ. This improves on the communication complexity of previous protocols by a factor of at least n. This improvement comes from the fact that in the new protocol, only O(n) messages (of size O(κ) each) are broadcast during the whole protocol execution, in contrast to previous protocols which require at least O(n) broadcasts per gate. Furthermore, we improve the upper bound on the communication complexity of passive secure multiparty computation with resilience t<n from O(cn 2 κ)toO(cnκ). This improvement is mainly due to a simple observation. 1
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.
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.