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

IEEE Symposium on Security and Privacy (S&P)

Breaking the Barrier for Asynchronous MPC with a Friend

Banashri Karmakar, Aniket Kate, S. C. Patil, Arpita Patra, Sikhar Patranabis, Protik Paul, Divya Ravi

Published May 18, 2026• 0 citations
Publisher

Abstract

Multiparty computation (MPC) is a topic of growing interest for privacy-preserving computation tasks. A few MPC libraries have been developed, and newer protocols are regularly proposed to reduce the latency overhead, improve scalability, and achieve strong termination guarantees. However, most current MPC protocols are designed and implemented assuming network synchrony: in theory, they assume that all messages are delivered within a known time bound, while for experimental analysis, most assume all nodes to be honest, such that the time bounds are never deployed. While deploying MPC systems in the wild and trying to minimize the latency, network synchrony is indeed a strong assumption to make: natural adverse network conditions can break the safety and/or liveness of the protocol due to simply delayed messages. Asynchronous MPC (AMPC) protocols can overcome the challenge as they do not assume fixed time bounds for message delivery delays; however, AMPC faces a natural threshold barrier of$\mathbf{2} \boldsymbol{/} \mathbf{3 r d}$honest majority and introduces significant computation and/or communication overheads. This work aims to achieve the best-of-both network models by designing a practical AMPC protocol that has stronger resilience guarantees matching those for synchronous MPC. We achieve this by adopting the emerging helper-aided model, and designing protocols that achieve fairness not only in the simple honest majority setting but also in the dishonest majority setting. Our protocols follow the standard preprocessing-online paradigm, enabling a lightweight and fast input-dependent online phase. In the honest majority setting, our protocol relies solely on lightweight cryptographic operations. In the dishonest majority setting, the protocol requires oblivious transfer (OT) during preprocessing, which we prove is necessary in this setting. We implement our constructions and provide a thorough performance comparison with state-of-theart MPC protocols in the helper-aided model. Our experiments demonstrate that our protocols substantially outperform the state-of-the-art helper-aided MPC scheme, while being significantly more resilient to network delays.

DOI
10.1109/sp63933.2026.00077

Related papers

Asterisk: Super-fast MPC with a Friend

Banashri Karmakar, Nishat Koti, Arpita Patra +3 more

Secure multiparty computation (MPC) enables privacy-preserving collaborative computation over sensitive data held by multiple mutually distrusting parties. Unfortunately, in the most natural setting where a majority of the parties are maliciously corrupt (also called the dishonest majority setting), traditional MPC protocols incur high overheads and offer weaker security guarantees than are desirable for practical applications. In this paper, we explore the possibility of circumventing these drawbacks and achieving practically efficient dishonest majority MPC protocols with strong security guarantees by assuming an additional semi-honest, non-colluding helper party HP .1We believe that this is a more realistic alternative to assuming an honest majority, since many real-world applications of MPC involving potentially large numbers of parties (such as dark pools) are typically enabled by a central governing entity that can be modeled as the HP.In the above model, we are the first to design, implement and benchmark a practically-efficient and general multi-party framework, Asterisk. Our framework requires invoking HP only a constant number of times, achieves the strong security guarantee of fairness (either all parties learn the output or none do), scales to hundreds of parties, outperforms all existing dishonest majority MPC protocols, and is, in fact, competitive with state-of-the-art honest majority MPC protocols. Our experiments show that Asterisk achieves 228 – 288× speedup in preprocessing as compared to the best dishonest majority MPC protocol. With respect to online time, Asterisk supports 100-party evaluation of a circuit with 106multiplication gates in approximately 20 seconds. We also implement and benchmark practically efficient and highly scalable dark pool instances using Asterisk. The corresponding run times showcase the effectiveness of Asterisk in enabling efficient realizations of real-world privacy-preserving applications with strong security guarantees.

IEEE Symposium on Security and Privacy (S&P)•May 19, 2024•10 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. 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

Velox: Scalable Fair Asynchronous MPC from Lightweight Cryptography

Akhil Bandarupalli, Xiaoyu Ji, Aniket Kate +3 more

Multi-party computation (MPC) enables a set of mutually n distrusting parties to compute any function on their private inputs. Mainly, MPC facilitates agreement on the function's output while preserving the secrecy of honest inputs, even against a subset of t parties controlled by an adversary. With applications spanning from anonymous broadcast to private auctions, MPC is considered a cornerstone of distributed cryptography, and significant research efforts have been aimed at making MPC practical in the last decade. However, most libraries either make strong assumptions like the network being bounded synchronous, or incur high computation overhead from the extensive use of expensive public-key operations that prevent them from scaling beyond a few dozen parties. This work presents Velox, an asynchronous MPC protocol that offers fairness against an optimal adversary corrupting up to t < n/3 parties. Velox significantly enhances practicality by leveraging lightweight cryptographic primitives-such as symmetric-key encryption and hash functions-which are 2-3 orders of magnitude faster than public-key operations, resulting in substantial computational efficiency. Moreover, Velox is highly communication-efficient, with linear amortized communication relative to circuit size and only O(n3) field elements of additive overhead. Concretely, Velox requires just 9.33 field elements per party per multiplication gate, more than 10× reduction compared to the state of the art. Moreover, Velox also offers Post-Quantum Security as lightweight cryptographic primitives retain their security against a quantum adversary. We implement Velox comprehensively, covering both offline and online phases, and evaluate its performance on a geographically distributed testbed through a real-world application: anonymous broadcast. Our implementation securely shuffles a batch of k = 256 messages in 4 seconds with n = 16 parties and 18 seconds with n = 64 parties, a 36× and 28.6× reduction in latency compared to the prior best work. At scale with n = 112 parties, Velox is able to shuffle the same batch of messages in under 50 seconds from end to end, illustrating its effectiveness and scalability. Overall, our work removes significant barriers faced by prior asynchronous MPC solutions, making asynchronous MPC practical and efficient for large-scale deployments involving 100s of parties.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 19, 2025•5 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•2 citations

AD-MPC: Asynchronous Dynamic MPC with Guaranteed Output Delivery

Wenxuan Yu, Minghui Xu, Bing Wu +2 more

MPC-as-a-Service (MPCaaS) systems enable clients to outsource privacy-preserving computations to distributed servers, offering flexibility by adapting and configuring MPC protocols to meet diverse security requirements. However, traditional MPC protocols rely on a fixed set of servers for the entire computation process, limiting scalability. Dynamic MPC (DMPC) addresses this limitation by permitting participants to join or leave during the computation. Nevertheless, existing DMPC protocols assume synchronous networks, which can lead to failures under unbounded network delays. In this paper, we present AD-MPC, the first asynchronous dynamic MPC protocol. Our protocol ensures guaranteed output delivery under optimal resilience ((n = 3t + 1)). To achieve this, we introduce two critical components: an asynchronous dynamic preprocessing protocol that facilitates the on-demand generation of Beaver triples for secure multiplication, and an asynchronous transfer protocol that maintains consistency during party hand-offs. These components collectively ensure computation correctness and transfer consistency across participants. We implement AD-MPC and evaluate its performance across up to 20 geographically distributed nodes. Experimental results demonstrate that the protocol not only offers strong security guarantees in dynamic and asynchronous network environments but also achieves performance comparable to state-of-the-art DMPC protocols.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 19, 2025•0 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
Multiparty computation (MPC) is a topic of growing interest for privacy-preserving computation tasks. A few MPC libraries have been developed, and newer protocols are regularly proposed to reduce the latency overhead, improve scalability, and achieve strong termination guarantees. However, most current MPC protocols are designed and implemented assuming network synchrony: in theory, they assume that all messages are delivered within a known time bound, while for experimental analysis, most assume all nodes to be honest, such that the time bounds are never deployed. While deploying MPC systems in the wild and trying to minimize the latency, network synchrony is indeed a strong assumption to make: natural adverse network conditions can break the safety and/or liveness of the protocol due to simply delayed messages. Asynchronous MPC (AMPC) protocols can overcome the challenge as they do not assume fixed time bounds for message delivery delays; however, AMPC faces a natural threshold barrier of2/3rd\mathbf{2} \boldsymbol{/} \mathbf{3 r d}2/3rdhonest majority and introduces significant computation and/or communication overheads. This work aims to achieve the best-of-both network models by designing a practical AMPC protocol that has stronger resilience guarantees matching those for synchronous MPC. We achieve this by adopting the emerging helper-aided model, and designing protocols that achieve fairness not only in the simple honest majority setting but also in the dishonest majority setting. Our protocols follow the standard preprocessing-online paradigm, enabling a lightweight and fast input-dependent online phase. In the honest majority setting, our protocol relies solely on lightweight cryptographic operations. In the dishonest majority setting, the protocol requires oblivious transfer (OT) during preprocessing, which we prove is necessary in this setting. We implement our constructions and provide a thorough performance comparison with state-of-theart MPC protocols in the helper-aided model. Our experiments demonstrate that our protocols substantially outperform the state-of-the-art helper-aided MPC scheme, while being significantly more resilient to network delays.
Secure multiparty computation (MPC) enables privacy-preserving collaborative computation over sensitive data held by multiple mutually distrusting parties. Unfortunately, in the most natural setting where a majority of the parties are maliciously corrupt (also called the dishonest majority setting), traditional MPC protocols incur high overheads and offer weaker security guarantees than are desirable for practical applications. In this paper, we explore the possibility of circumventing these drawbacks and achieving practically efficient dishonest majority MPC protocols with strong security guarantees by assuming an additional semi-honest, non-colluding helper party HP .1We believe that this is a more realistic alternative to assuming an honest majority, since many real-world applications of MPC involving potentially large numbers of parties (such as dark pools) are typically enabled by a central governing entity that can be modeled as the HP.In the above model, we are the first to design, implement and benchmark a practically-efficient and general multi-party framework, Asterisk. Our framework requires invoking HP only a constant number of times, achieves the strong security guarantee of fairness (either all parties learn the output or none do), scales to hundreds of parties, outperforms all existing dishonest majority MPC protocols, and is, in fact, competitive with state-of-the-art honest majority MPC protocols. Our experiments show that Asterisk achieves 228 – 288× speedup in preprocessing as compared to the best dishonest majority MPC protocol. With respect to online time, Asterisk supports 100-party evaluation of a circuit with 106multiplication gates in approximately 20 seconds. We also implement and benchmark practically efficient and highly scalable dark pool instances using Asterisk. The corresponding run times showcase the effectiveness of Asterisk in enabling efficient realizations of real-world privacy-preserving applications with strong security guarantees.
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
Multi-party computation (MPC) enables a set of mutually n distrusting parties to compute any function on their private inputs. Mainly, MPC facilitates agreement on the function's output while preserving the secrecy of honest inputs, even against a subset of t parties controlled by an adversary. With applications spanning from anonymous broadcast to private auctions, MPC is considered a cornerstone of distributed cryptography, and significant research efforts have been aimed at making MPC practical in the last decade. However, most libraries either make strong assumptions like the network being bounded synchronous, or incur high computation overhead from the extensive use of expensive public-key operations that prevent them from scaling beyond a few dozen parties. This work presents Velox, an asynchronous MPC protocol that offers fairness against an optimal adversary corrupting up to t < n/3 parties. Velox significantly enhances practicality by leveraging lightweight cryptographic primitives-such as symmetric-key encryption and hash functions-which are 2-3 orders of magnitude faster than public-key operations, resulting in substantial computational efficiency. Moreover, Velox is highly communication-efficient, with linear amortized communication relative to circuit size and only O(n3) field elements of additive overhead. Concretely, Velox requires just 9.33 field elements per party per multiplication gate, more than 10× reduction compared to the state of the art. Moreover, Velox also offers Post-Quantum Security as lightweight cryptographic primitives retain their security against a quantum adversary. We implement Velox comprehensively, covering both offline and online phases, and evaluate its performance on a geographically distributed testbed through a real-world application: anonymous broadcast. Our implementation securely shuffles a batch of k = 256 messages in 4 seconds with n = 16 parties and 18 seconds with n = 64 parties, a 36× and 28.6× reduction in latency compared to the prior best work. At scale with n = 112 parties, Velox is able to shuffle the same batch of messages in under 50 seconds from end to end, illustrating its effectiveness and scalability. Overall, our work removes significant barriers faced by prior asynchronous MPC solutions, making asynchronous MPC practical and efficient for large-scale deployments involving 100s of parties.
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.
MPC-as-a-Service (MPCaaS) systems enable clients to outsource privacy-preserving computations to distributed servers, offering flexibility by adapting and configuring MPC protocols to meet diverse security requirements. However, traditional MPC protocols rely on a fixed set of servers for the entire computation process, limiting scalability. Dynamic MPC (DMPC) addresses this limitation by permitting participants to join or leave during the computation. Nevertheless, existing DMPC protocols assume synchronous networks, which can lead to failures under unbounded network delays. In this paper, we present AD-MPC, the first asynchronous dynamic MPC protocol. Our protocol ensures guaranteed output delivery under optimal resilience ((n = 3t + 1)). To achieve this, we introduce two critical components: an asynchronous dynamic preprocessing protocol that facilitates the on-demand generation of Beaver triples for secure multiplication, and an asynchronous transfer protocol that maintains consistency during party hand-offs. These components collectively ensure computation correctness and transfer consistency across participants. We implement AD-MPC and evaluate its performance across up to 20 geographically distributed nodes. Experimental results demonstrate that the protocol not only offers strong security guarantees in dynamic and asynchronous network environments but also achieves performance comparable to state-of-the-art DMPC protocols.