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

International Conference on Distributed Computing and Networking (ICDCN)

Optimally Resilient Asynchronous MPC with Linear Communication Complexity

Ashish Choudhury, Arpita Patra

Published Jan 4, 2015• 33 citations
Publisher

Abstract

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.

DOI
10.1145/2684464.2684470

Related papers

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

Secure 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•1 citation

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. Non-equivocation is a message authentication mechanism to restrict a corrupted sender from mak-ing conflicting statements to different (honest) parties. It can be implemented using an increment-only counter and a digital signature oracle, realizable with trusted hardware modules readily available in com-modity computers and smartphone devices. A non-equivocation mechanism can also be transferable and allow a receiver to verifiably transfer the authenticated statement to other parties. In this work, using transferable non-equivocation, we present an AMPC protocol tolerating t < n/2 faults. From a practical point of view, our AMPC protocol requires fewer setup assumptions than the previous AMPC protocol with t < n/2 by Beerliová-Trubı́niová, Hirt and Nielsen [PODC 2010]: unlike their AMPC protocol, it does not require any synchronous broadcast round at the beginning of the protocol and avoids the threshold homomorphic encryption setup assumption. Moreover, our AMPC protocol is also efficient and provides a gain of Θ(n) in the communication complexity per multiplication gate, over the AMPC protocol of Beerliová-Trubı́niova ́ et al. In the process, using non-equivocation, we also define the first asynchronous verifiable secret sharing (AVSS) scheme with t < n/2, which is of independent interest to threshold cryptography. 1

•Jan 1, 2014•6 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

Round and Communication Efficient Unconditionally-secure MPC with t < n/3 in Partially Synchronous Network.

Ashish Choudhury, Arpita Patra, Divya Ravi

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 \(\varOmega (n^5)\) 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 \(\mathcal {O}(n^2)\) 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.

•Jan 1, 2017•0 citations

An Efficient Framework for Unconditionally Secure Multiparty Computation

Ashish Choudhury, Arpita Patra

parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can maliciously corrupt any t out of the n parties. Most of the known efficient MPC protocols are designed in the offline- online framework introduced in a seminal work by Beaver in CRYPTO 1991. In this framework, the parties generate shared random and private multiplication-triples during the offline phase, which are used later in the online phase for securely evaluating the multiplication gates in the circuit representing f . The efficiency of the MPC protocols in this framework then relies on efficient ways of implementing the offline phase. In this paper, we propose a new and simple framework for generating shared and private random multiplication triples with unconditional security. The existing protocols approach this problem by first producing shared pairs of private and random values, followed by securely computing the shared product of each pair of values. The latter task involves a multiplication protocol for shared values that are typically communication intensive. Our framework takes a completely different approach and shuns the use of multiplication protocol. Namely, we ask the parties to verifiably share random multiplication triples and then securely extract shared random multiplication triples unknown to the adversary, from the shared triples. Realizing our framework in the asynchronous and hybrid network setting,1 we present the first ever MPC protocols with a linear (in the number of parties) communication overhead per multiplication gate in the circuit representing f . These are significant improvements over the best known existing MPC protocols in the asynchronous and hybrid network setting with communication complexity O(n2) and O(n3), respectively. Our framework when applied to the synchronous setting results in round-efficient MPC protocols.

IEEE Transactions on Information Theory•Oct 4, 2016•63 citations
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.
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.
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. Non-equivocation is a message authentication mechanism to restrict a corrupted sender from mak-ing conflicting statements to different (honest) parties. It can be implemented using an increment-only counter and a digital signature oracle, realizable with trusted hardware modules readily available in com-modity computers and smartphone devices. A non-equivocation mechanism can also be transferable and allow a receiver to verifiably transfer the authenticated statement to other parties. In this work, using transferable non-equivocation, we present an AMPC protocol tolerating t < n/2 faults. From a practical point of view, our AMPC protocol requires fewer setup assumptions than the previous AMPC protocol with t < n/2 by Beerliová-Trubı́niová, Hirt and Nielsen [PODC 2010]: unlike their AMPC protocol, it does not require any synchronous broadcast round at the beginning of the protocol and avoids the threshold homomorphic encryption setup assumption. Moreover, our AMPC protocol is also efficient and provides a gain of Θ(n) in the communication complexity per multiplication gate, over the AMPC protocol of Beerliová-Trubı́niova ́ et al. In the process, using non-equivocation, we also define the first asynchronous verifiable secret sharing (AVSS) scheme with t < n/2, which is of independent interest to threshold cryptography. 1
In this work, we study unconditionally-secure multi-party computation (MPC) tolerating t<n/3t < n/3t<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/3t<n/3t<n/3 requires a communication of Ω(n5)\varOmega (n^5)Ω(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)\mathcal {O}(n^2)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.
parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can maliciously corrupt any t out of the n parties. Most of the known efficient MPC protocols are designed in the offline- online framework introduced in a seminal work by Beaver in CRYPTO 1991. In this framework, the parties generate shared random and private multiplication-triples during the offline phase, which are used later in the online phase for securely evaluating the multiplication gates in the circuit representing f . The efficiency of the MPC protocols in this framework then relies on efficient ways of implementing the offline phase. In this paper, we propose a new and simple framework for generating shared and private random multiplication triples with unconditional security. The existing protocols approach this problem by first producing shared pairs of private and random values, followed by securely computing the shared product of each pair of values. The latter task involves a multiplication protocol for shared values that are typically communication intensive. Our framework takes a completely different approach and shuns the use of multiplication protocol. Namely, we ask the parties to verifiably share random multiplication triples and then securely extract shared random multiplication triples unknown to the adversary, from the shared triples. Realizing our framework in the asynchronous and hybrid network setting,1 we present the first ever MPC protocols with a linear (in the number of parties) communication overhead per multiplication gate in the circuit representing f . These are significant improvements over the best known existing MPC protocols in the asynchronous and hybrid network setting with communication complexity O(n2) and O(n3), respectively. Our framework when applied to the synchronous setting results in round-efficient MPC protocols.