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

Secure Computation with Partial Message Loss

Chiu‐Yuen Koo

Published Feb 6, 2008• 0 citations
OpenAlex

Abstract

Abstract. Existing communication models for multiparty computation (MPC) either assume that all messages are delivered eventually or any message can be lost. Under the former assumption, MPC protocols guaranteeing output delivery are known. However, this assumption may not hold in some network settings like the Internet where messages can be lost due to denial of service attack or heavy network congestion. On the other hand, the latter assumption may be too conservative. Known MPC protocols developed under this assumption have an undesirable feature: output delivery is not guaranteed even only one party suffers message loss. In this work, we propose a communication model which makes an intermediate assumption on message delivery. In our model, there is a common global clock and three types of parties: (i) Corrupted parties (ii) Honest parties with connection problems (where message delivery is never guaranteed) (iii) Honest parties that can normally communicate but may lose a small fraction of messages at each round due to transient network problems. We define secure MPC under this model. Output delivery is guaranteed to type (ii) parties that do not abort and type (iii) parties. Let n be the total number of parties, ef and ec be upper bounds on the number of corrupted parties and type (ii) parties respectively. We construct a secure MPC protocol for n> 4ef + 3ec. Protocols for broadcast and verifiable secret sharing are constructed along the way. 1

Related papers

Secure Multiparty Computation with Dynamic Participants and Guaranteed Output

Giovanni Deligios

Secure Multiparty Computation (MPC) is an expression encompassing cryptographic techniques that allow mutually distrustful parties to jointly perform computations over private data, ensuring correctness and preserving privacy despite malicious behavior. Guaranteed output is the strongest security goal for MPC: protocols with this property always deliver results. This is in contrast with weaker notions that allow malicious aborts. The seminal works of Ben-Or, Goldwasser, and Wigderson (STOC’88) and Rabin and Ben-Or (STOC’89) showed interactive protocols to compute any function with guaranteed output and perfect security if fewer than one third of parties are corrupted, or with statistical security (with a small error probability) if fewer than half are corrupted. These results hold when the set of participants is fixed throughout the execution. Ostrovsky and Yung’s proactive model (PODC’91) relaxes this assumption by allowing the set of corrupted parties to evolve over time, better capturing the dynamics of long-lived computations, where machines may be periodically compromised and recovered. The recent YOSO (You Only Speak Once) and fluid MPC models (CRYPTO’21) push this ambitious modelling even further by allowing for fully dynamic participation, with parties joining and leaving the computation at will. In this setting, known protocols with guaranteed output fall short of optimal resilience or rely on non-standard communication and adversarial assumptions. Matching the classical BGW and Rabin–Ben-Or bounds in these settings remained an open problem. We resolve these questions within the Layered MPC abstraction of David et al. (CRYPTO’23), in which the interaction pattern of a protocol is restricted to be a layered graph, meaning parties are partitioned into a sequence of disjoint sets (layers) and can send private and broadcast messages to parties in immediately subsequent layers. We match the BGW and Rabin and Ben-Or bounds in this model, fully characterizing the feasibility landscape of Layered MPC with guaranteed output. As a stepping stone towards our statistically secure protocol, we construct a more efficient and conceptually simpler computationally secure protocol relying on linear non-interactive commitments. Our results yield optimally-resilient and maximally-proactive MPC protocols with guaranteed output for both perfect and statistical security.

•Jan 1, 2025•0 citations

Broadcast-Efficient Secure Multiparty Computation.

Juan A. Garay, Clint Givens, Rafail Ostrovsky

Secure multiparty computation (MPC) is perhaps the most popular paradigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case of unconditional (information-theoretic) security, protocols are known which tolerate a dishonest minority of players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general MPC protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource

•Jan 1, 2012•3 citations

Measures of efficiency for secure multiparty computation

Rafail Ostrovsky, Clint Givens

Multiparty computation (MPC) is a powerful and generic cryptographic framework capable of realizing essentially any cryptographic task (functionality) while preserving privacy and robustness. In the MPC model, a group of mutually distrustful parties seek to jointly compute a function f of their privately held inputs x1, ..., xn, while revealing no information about those inputs beyond what is entailed by the function output(s). Some portion of these players may be corrupted, controlled by a centralized adversary who directs their (mis)behavior and seeks to gain information on private inputs or to disrupt the protocol execution. In this work, we examine the resource requirements of information-theoretically secure multiparty computation. In particular, we look at trade-offs involving what we call assumptions, by which we mean two aspects of the model's setup: (1) the extent to which parties are connected by secure, pairwise communication channels; and (2) the usage (as a black box) of a channel—a primitive which enforces consistency among views by allowing a single party to send a message to all other parties which is guaranteed to be consistent, even if the broadcaster is corrupted. Part I of this work focuses on the first network-model assumption, that of the graph's connectivity by pairwise channels. We show upper and lower bounds on communication complexity in the Secure Message Transmission with Public Discussion (SMT-PD) model, as a function of the threshold of corrupted parties. The SMT-PD model, which abstracts the problem of secure communication over a partially connected network, includes two components: a public and a set of simple channels. We show significant improvements in both areas: on the channel, we reduce communication to logarithmic in terms of the message's bit-length m, where the previous best result was linear in m; on the simple channels, we reduce from O(mn) to O(mn/(n−t)), where n is the number of simple channels and t is a bound on the number of corrupted channels. Using tools from information theory, we show this amount of simple-wire communication is essentially optimal. Finally, we give an amortized solution which drastically improves communication over channel when the protocol is repeated many times sequentially. Part II shifts focus to the second network-model assumption, the use of an atomic broadcast primitive. Here we show that three broadcast rounds suffice for general secure computation, while two broadcast rounds are necessary. In particular we show that even for the natural and important functionality of Weak Secret Sharing—a type of distributed commitment—there is no protocol which uses only a single broadcast and achieves better than an explicit constant probability of success (so the protocol's success cannot be a function of a security parameter).

•Jan 1, 2013•0 citations

Fast Secure Computation for Small Population over the Internet

Megha Byali, Arun Antony Joseph, Arpita Patra +1 more

Secure Multi-Party Computation (MPC) with small number of parties is an interesting area of research, primarily due to its ability to model most real-life MPC applications and the simplicity and efficiency of the resulting protocols. In this work, we present efficient, constant-round 3-party (3PC) and 4-party (4PC) protocols in the honest-majority setting that achieve strong security notions of fairness (corrupted parties receive their output only if all honest parties receive output) and guaranteed output delivery (corrupted parties cannot prevent honest parties from receiving their output). Being constant-round, our constructions are suitable for Internet-like high-latency networks and are built from garbled circuits (GC). Assuming the minimal model of pairwise-private channels, we present two protocols that involve computation and communication of a single GC-- (a) a 4-round 3PC with fairness, (b) a 5-round 4PC with guaranteed output delivery. Empirically, our protocols are on par with the best known 3PC protocol of Mohassel et al. [CCS 2015] that only achieves security with selective abort, in terms of the computation time, LAN runtime, WAN runtime and communication cost. In fact, our 4PC outperforms the 3PC of Mohassel et al. significantly in terms of per-party computation and communication cost. With an extra GC, we improve the round complexity of our 4PC to four rounds. The only 4PC in our setting, given by Ishai et al. [CRYPTO 2015], involves 12 GCs. Assuming an additional broadcast channel, we present a 5-round 3PC with guaranteed output delivery that involves computation and communication of a single GC. A broadcast channel is inevitable in this setting for achieving guaranteed output delivery, owing to an impossibility result in the literature. The overall broadcast communication of our protocol is nominal and most importantly, is independent of the circuit size. This protocol too induces a nominal overhead compared to the protocol of Mohassel et al.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 15, 2018•23 citations

A Little Honesty Goes a Long Way: The Two-Tier Model for Secure Multiparty Computation.

Juan A. Garay, Ran Gelles, David Johnson +2 more

Abstract. Secure multiparty computation (MPC) as a service is becoming a tangible reality. In such a service, a population of clients wish to utilize a set of servers to delegate privately and reliably a given computation on their inputs. MPC protocols have a number of desired properties including tolerating active misbehavior by some of the servers and guaranteed output delivery. A fundamental result is that in order to achieve the above, an honest majority among servers is necessary. There are settings, however, where this condition might be overly restrictive, making it important to investigate models where this impossibility result can be circumvented, allowing secure computation to be performed even when the number of malicious participants outweighs the number of honest participants. To this end, we introduce the two-tier model for MPC, where a set of m parties that are guaranteed to be honest (the first tier) remains “hidden ” within a set of n − m servers which are of dubious trustworthiness (the second tier), and where the objective is to perform MPC withstanding a number of active misbehaviors that is larger than m/2. Indeed, assuming αn of the second-tier servers are dishonest (where α ∈ (0, 1)), we present an MPC protocol that can withstand up to (1 − )(1 − α)n/2 additional faults, for any > 0 and m = ω(logn). Somewhat surprisingly, this allows the total number of faulty parties to exceed n/2 across both tiers. We demonstrate that the two-tier model naturally arises in various settings, as in the case, for example, of a resource-constrained service provider wishing to utilize a pre-existing set of servers. 1

•Jan 1, 2014•1 citation

Fairness Versus Guaranteed Output Delivery in Secure Multiparty Computation.

Ran Cohen, Yehuda Lindell

In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their private inputs. The computation should preserve security properties such as privacy, correctness, independence of inputs, fairness and guaranteed output delivery. In the case of no honest majority, fairness and guaranteed output delivery cannot always be obtained. Thus, protocols for secure multiparty computation are typically of two disparate types: protocols that assume an honest majority (and achieve all properties including fairness and guaranteed output delivery), and protocols that do not assume an honest majority (and achieve all properties except for fairness and guaranteed output delivery). In addition, in the two-party case, fairness and guaranteed output delivery are equivalent. As a result, the properties of fairness (which means that if corrupted parties receive output then so do the honest parties) and guaranteed output delivery (which means that corrupted parties cannot prevent the honest parties from receiving output in any case) have typically been considered to be the same. In this paper, we initiate a study of the relation between fairness and guaranteed output delivery in secure multiparty computation. We show that in the multiparty setting these proper-ties are distinct and proceed to study under what conditions fairness implies guaranteed output delivery (the opposite direction always holds). We also show the existence of non-trivial func-tions for which complete fairness is achievable (without an honest majority) but guaranteed output delivery is not, and the existence of non-trivial functions for which complete fairness and guaranteed output delivery are achievable. Our study sheds light on the role of broadcast in fairness and guaranteed output delivery, and shows that these properties should sometimes be considered separately.

•Jan 1, 2014•0 citations
Abstract. Existing communication models for multiparty computation (MPC) either assume that all messages are delivered eventually or any message can be lost. Under the former assumption, MPC protocols guaranteeing output delivery are known. However, this assumption may not hold in some network settings like the Internet where messages can be lost due to denial of service attack or heavy network congestion. On the other hand, the latter assumption may be too conservative. Known MPC protocols developed under this assumption have an undesirable feature: output delivery is not guaranteed even only one party suffers message loss. In this work, we propose a communication model which makes an intermediate assumption on message delivery. In our model, there is a common global clock and three types of parties: (i) Corrupted parties (ii) Honest parties with connection problems (where message delivery is never guaranteed) (iii) Honest parties that can normally communicate but may lose a small fraction of messages at each round due to transient network problems. We define secure MPC under this model. Output delivery is guaranteed to type (ii) parties that do not abort and type (iii) parties. Let n be the total number of parties, ef and ec be upper bounds on the number of corrupted parties and type (ii) parties respectively. We construct a secure MPC protocol for n> 4ef + 3ec. Protocols for broadcast and verifiable secret sharing are constructed along the way. 1
Secure Multiparty Computation (MPC) is an expression encompassing cryptographic techniques that allow mutually distrustful parties to jointly perform computations over private data, ensuring correctness and preserving privacy despite malicious behavior. Guaranteed output is the strongest security goal for MPC: protocols with this property always deliver results. This is in contrast with weaker notions that allow malicious aborts. The seminal works of Ben-Or, Goldwasser, and Wigderson (STOC’88) and Rabin and Ben-Or (STOC’89) showed interactive protocols to compute any function with guaranteed output and perfect security if fewer than one third of parties are corrupted, or with statistical security (with a small error probability) if fewer than half are corrupted. These results hold when the set of participants is fixed throughout the execution. Ostrovsky and Yung’s proactive model (PODC’91) relaxes this assumption by allowing the set of corrupted parties to evolve over time, better capturing the dynamics of long-lived computations, where machines may be periodically compromised and recovered. The recent YOSO (You Only Speak Once) and fluid MPC models (CRYPTO’21) push this ambitious modelling even further by allowing for fully dynamic participation, with parties joining and leaving the computation at will. In this setting, known protocols with guaranteed output fall short of optimal resilience or rely on non-standard communication and adversarial assumptions. Matching the classical BGW and Rabin–Ben-Or bounds in these settings remained an open problem. We resolve these questions within the Layered MPC abstraction of David et al. (CRYPTO’23), in which the interaction pattern of a protocol is restricted to be a layered graph, meaning parties are partitioned into a sequence of disjoint sets (layers) and can send private and broadcast messages to parties in immediately subsequent layers. We match the BGW and Rabin and Ben-Or bounds in this model, fully characterizing the feasibility landscape of Layered MPC with guaranteed output. As a stepping stone towards our statistically secure protocol, we construct a more efficient and conceptually simpler computationally secure protocol relying on linear non-interactive commitments. Our results yield optimally-resilient and maximally-proactive MPC protocols with guaranteed output for both perfect and statistical security.
Secure multiparty computation (MPC) is perhaps the most popular paradigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case of unconditional (information-theoretic) security, protocols are known which tolerate a dishonest minority of players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general MPC protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource
Multiparty computation (MPC) is a powerful and generic cryptographic framework capable of realizing essentially any cryptographic task (functionality) while preserving privacy and robustness. In the MPC model, a group of mutually distrustful parties seek to jointly compute a function f of their privately held inputs x1, ..., xn, while revealing no information about those inputs beyond what is entailed by the function output(s). Some portion of these players may be corrupted, controlled by a centralized adversary who directs their (mis)behavior and seeks to gain information on private inputs or to disrupt the protocol execution. In this work, we examine the resource requirements of information-theoretically secure multiparty computation. In particular, we look at trade-offs involving what we call assumptions, by which we mean two aspects of the model's setup: (1) the extent to which parties are connected by secure, pairwise communication channels; and (2) the usage (as a black box) of a channel—a primitive which enforces consistency among views by allowing a single party to send a message to all other parties which is guaranteed to be consistent, even if the broadcaster is corrupted. Part I of this work focuses on the first network-model assumption, that of the graph's connectivity by pairwise channels. We show upper and lower bounds on communication complexity in the Secure Message Transmission with Public Discussion (SMT-PD) model, as a function of the threshold of corrupted parties. The SMT-PD model, which abstracts the problem of secure communication over a partially connected network, includes two components: a public and a set of simple channels. We show significant improvements in both areas: on the channel, we reduce communication to logarithmic in terms of the message's bit-length m, where the previous best result was linear in m; on the simple channels, we reduce from O(mn) to O(mn/(n−t)), where n is the number of simple channels and t is a bound on the number of corrupted channels. Using tools from information theory, we show this amount of simple-wire communication is essentially optimal. Finally, we give an amortized solution which drastically improves communication over channel when the protocol is repeated many times sequentially. Part II shifts focus to the second network-model assumption, the use of an atomic broadcast primitive. Here we show that three broadcast rounds suffice for general secure computation, while two broadcast rounds are necessary. In particular we show that even for the natural and important functionality of Weak Secret Sharing—a type of distributed commitment—there is no protocol which uses only a single broadcast and achieves better than an explicit constant probability of success (so the protocol's success cannot be a function of a security parameter).
Secure Multi-Party Computation (MPC) with small number of parties is an interesting area of research, primarily due to its ability to model most real-life MPC applications and the simplicity and efficiency of the resulting protocols. In this work, we present efficient, constant-round 3-party (3PC) and 4-party (4PC) protocols in the honest-majority setting that achieve strong security notions of fairness (corrupted parties receive their output only if all honest parties receive output) and guaranteed output delivery (corrupted parties cannot prevent honest parties from receiving their output). Being constant-round, our constructions are suitable for Internet-like high-latency networks and are built from garbled circuits (GC). Assuming the minimal model of pairwise-private channels, we present two protocols that involve computation and communication of a single GC-- (a) a 4-round 3PC with fairness, (b) a 5-round 4PC with guaranteed output delivery. Empirically, our protocols are on par with the best known 3PC protocol of Mohassel et al. [CCS 2015] that only achieves security with selective abort, in terms of the computation time, LAN runtime, WAN runtime and communication cost. In fact, our 4PC outperforms the 3PC of Mohassel et al. significantly in terms of per-party computation and communication cost. With an extra GC, we improve the round complexity of our 4PC to four rounds. The only 4PC in our setting, given by Ishai et al. [CRYPTO 2015], involves 12 GCs. Assuming an additional broadcast channel, we present a 5-round 3PC with guaranteed output delivery that involves computation and communication of a single GC. A broadcast channel is inevitable in this setting for achieving guaranteed output delivery, owing to an impossibility result in the literature. The overall broadcast communication of our protocol is nominal and most importantly, is independent of the circuit size. This protocol too induces a nominal overhead compared to the protocol of Mohassel et al.
Abstract. Secure multiparty computation (MPC) as a service is becoming a tangible reality. In such a service, a population of clients wish to utilize a set of servers to delegate privately and reliably a given computation on their inputs. MPC protocols have a number of desired properties including tolerating active misbehavior by some of the servers and guaranteed output delivery. A fundamental result is that in order to achieve the above, an honest majority among servers is necessary. There are settings, however, where this condition might be overly restrictive, making it important to investigate models where this impossibility result can be circumvented, allowing secure computation to be performed even when the number of malicious participants outweighs the number of honest participants. To this end, we introduce the two-tier model for MPC, where a set of m parties that are guaranteed to be honest (the first tier) remains “hidden ” within a set of n − m servers which are of dubious trustworthiness (the second tier), and where the objective is to perform MPC withstanding a number of active misbehaviors that is larger than m/2. Indeed, assuming αn of the second-tier servers are dishonest (where α ∈ (0, 1)), we present an MPC protocol that can withstand up to (1 − )(1 − α)n/2 additional faults, for any > 0 and m = ω(logn). Somewhat surprisingly, this allows the total number of faulty parties to exceed n/2 across both tiers. We demonstrate that the two-tier model naturally arises in various settings, as in the case, for example, of a resource-constrained service provider wishing to utilize a pre-existing set of servers. 1
In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their private inputs. The computation should preserve security properties such as privacy, correctness, independence of inputs, fairness and guaranteed output delivery. In the case of no honest majority, fairness and guaranteed output delivery cannot always be obtained. Thus, protocols for secure multiparty computation are typically of two disparate types: protocols that assume an honest majority (and achieve all properties including fairness and guaranteed output delivery), and protocols that do not assume an honest majority (and achieve all properties except for fairness and guaranteed output delivery). In addition, in the two-party case, fairness and guaranteed output delivery are equivalent. As a result, the properties of fairness (which means that if corrupted parties receive output then so do the honest parties) and guaranteed output delivery (which means that corrupted parties cannot prevent the honest parties from receiving output in any case) have typically been considered to be the same. In this paper, we initiate a study of the relation between fairness and guaranteed output delivery in secure multiparty computation. We show that in the multiparty setting these proper-ties are distinct and proceed to study under what conditions fairness implies guaranteed output delivery (the opposite direction always holds). We also show the existence of non-trivial func-tions for which complete fairness is achievable (without an honest majority) but guaranteed output delivery is not, and the existence of non-trivial functions for which complete fairness and guaranteed output delivery are achievable. Our study sheds light on the role of broadcast in fairness and guaranteed output delivery, and shows that these properties should sometimes be considered separately.