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

Lecture notes in computer science

MPC with Delayed Parties over Star-Like Networks

Mariana Botelho da Gama, Emad Heydari Beni, Emmanuela Orsini, Nigel Paul Smart, Oliver Zajonc

Published Jan 1, 2023• 3 citations
Publisher
DOI
10.1007/978-981-99-8721-4_6

Related papers

MPC in de echte wereld: praktische aspecten van meerpartijrekenen

Botelho da Gama, Mariana

In 1982, Yao presented a protocol that allowed two parties to compute over their private inputs while revealing nothing but the final output. This first theoretical construction originated a fruitful line of research exploring the possibilities of the cryptographic technique known as multi-party computation, or MPC. Today, we have MPC schemes with practical efficiency that can be used for a wide range of applications and use cases, from securing cryptographic keys to training Machine Learning models on private data. Despite the advancements from the past few decades, we have only started to bridge the gap between theory and practice, and several obstacles stand in the way of the widespread adoption of MPC. First, the performance overhead depends heavily on the computation we want to perform. Not all computations are well-suited to be distributed with MPC, and algorithms must usually be refactored before they can be executed securely. Furthermore, the practical efficiency of most modern protocols quickly deteriorates as the number of parties increases and comes at the expense of the security guarantees provided. On the other hand, almost all academic works assume a static set of MPC parties, all pairwise connected by dedicated channels in a network without delays or failures. Yet, these assumptions are hardly achievable in current real-world networks. In this thesis, we study three practical aspects of multi-party computation: (i) we discuss how to improve performance by designing algorithms tailor-made for execution with MPC. To this end, we present and evaluate secure auction mechanisms for the financial setting and for the peer-to-peer electricity market. (ii) We analyse the information leakage from the MPC computation outputs. In particular, we focus on the case of individual and private correlated outputs, for which we propose a new privacy notion. Lastly, (iii) we consider the problem of building efficient large-scale MPC. We explore the possibilities and limitations associated with standard (fully connected) networks and present a new protocol with a star-like network topology and resilience against delayed parties.

•Feb 10, 2025•0 citations

MPC with Friends and Foes

Bar Alon, Eran Omri, Anat Paskin-Cherniavsky

Lecture notes in computer science•Jan 1, 2020•18 citations

Almost-Asynchronous MPC with Faulty Minority.

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

Abstract. Secure multiparty computation (MPC) allows a set of parties to securely evaluate any agreed function of their inputs, even when up to t of the n parties are faulty. Protocols for synchronous networks (where every sent message is assumed to arrive within a constant time) tolerate up to t < n/2 faulty parties, whereas in the more realistic asynchronous setting (with no a priory information on maximal message delay) only security against t < n/3 is possible. Note that even asynchronous Byzantine agreement requires t < n/3. In this paper, we are interested in the minimal synchronicity assumption for achieving security against t < n/2. It turns out that the bottleneck of asynchronous MPC is the distribution of the inputs: Once the inputs are correctly distributed, any deterministic function can be computed over a fully asynchronous network with t < n/2. Furthermore, we show that the inputs can be verifiably distributed with t < n/2, if a single round of synchronous broadcast is available. Composing the above, we obtain the first MPC protocol that achieves security against t < n/2 without assuming a fully synchronous network. Actually our protocol guarantees security against any faulty minority in an almost asynchronous network, i.e. in a network with one single round of synchronous broadcast (followed by a fully asynchronous communication). Furthermore our protocol takes inputs of all parties (in a fully asynchronous network only inputs of n−t parties can be guaranteed), and so achieves everything that is possible in synchronous networks (but impossible in fully asynchronous networks) at the price of just one synchronous broadcast round. As tools for our protocol we introduce the notions of almost non-interactive verifiable secret-sharing and almost non-interactive zero-knowledge proof of knowledge, which are of independent interest as they can serve as efficient replacements for fully non-interactive verifiable secret-sharing and fully non-interactive zero-knowledge proof of knowledge.

•Jan 1, 2008•6 citations

A Toy MPC Protocol

Ashish Choudhury, Arpita Patra

Synthesis lectures on distributed computing theory•Jan 1, 2022•0 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

Network Agnostic MPC with Statistical Security

Ananya Appan, Ashish Choudhury

arXiv:2306.01401•Lecture notes in computer science•Jan 1, 2023•8 citations
In 1982, Yao presented a protocol that allowed two parties to compute over their private inputs while revealing nothing but the final output. This first theoretical construction originated a fruitful line of research exploring the possibilities of the cryptographic technique known as multi-party computation, or MPC. Today, we have MPC schemes with practical efficiency that can be used for a wide range of applications and use cases, from securing cryptographic keys to training Machine Learning models on private data. Despite the advancements from the past few decades, we have only started to bridge the gap between theory and practice, and several obstacles stand in the way of the widespread adoption of MPC. First, the performance overhead depends heavily on the computation we want to perform. Not all computations are well-suited to be distributed with MPC, and algorithms must usually be refactored before they can be executed securely. Furthermore, the practical efficiency of most modern protocols quickly deteriorates as the number of parties increases and comes at the expense of the security guarantees provided. On the other hand, almost all academic works assume a static set of MPC parties, all pairwise connected by dedicated channels in a network without delays or failures. Yet, these assumptions are hardly achievable in current real-world networks. In this thesis, we study three practical aspects of multi-party computation: (i) we discuss how to improve performance by designing algorithms tailor-made for execution with MPC. To this end, we present and evaluate secure auction mechanisms for the financial setting and for the peer-to-peer electricity market. (ii) We analyse the information leakage from the MPC computation outputs. In particular, we focus on the case of individual and private correlated outputs, for which we propose a new privacy notion. Lastly, (iii) we consider the problem of building efficient large-scale MPC. We explore the possibilities and limitations associated with standard (fully connected) networks and present a new protocol with a star-like network topology and resilience against delayed parties.
Abstract. Secure multiparty computation (MPC) allows a set of parties to securely evaluate any agreed function of their inputs, even when up to t of the n parties are faulty. Protocols for synchronous networks (where every sent message is assumed to arrive within a constant time) tolerate up to t < n/2 faulty parties, whereas in the more realistic asynchronous setting (with no a priory information on maximal message delay) only security against t < n/3 is possible. Note that even asynchronous Byzantine agreement requires t < n/3. In this paper, we are interested in the minimal synchronicity assumption for achieving security against t < n/2. It turns out that the bottleneck of asynchronous MPC is the distribution of the inputs: Once the inputs are correctly distributed, any deterministic function can be computed over a fully asynchronous network with t < n/2. Furthermore, we show that the inputs can be verifiably distributed with t < n/2, if a single round of synchronous broadcast is available. Composing the above, we obtain the first MPC protocol that achieves security against t < n/2 without assuming a fully synchronous network. Actually our protocol guarantees security against any faulty minority in an almost asynchronous network, i.e. in a network with one single round of synchronous broadcast (followed by a fully asynchronous communication). Furthermore our protocol takes inputs of all parties (in a fully asynchronous network only inputs of n−t parties can be guaranteed), and so achieves everything that is possible in synchronous networks (but impossible in fully asynchronous networks) at the price of just one synchronous broadcast round. As tools for our protocol we introduce the notions of almost non-interactive verifiable secret-sharing and almost non-interactive zero-knowledge proof of knowledge, which are of independent interest as they can serve as efficient replacements for fully non-interactive verifiable secret-sharing and fully non-interactive zero-knowledge proof of knowledge.
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.