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

On the Computational Overhead of MPC with Dishonest Majority

Jesper Buus Nielsen, Samuel Ranellucci

Published Jan 1, 2017• 7 citations
Publisher

Abstract

We consider the situation where a large number n of players want to securely compute a large function f with security against an adaptive, malicious adversary which might corrupt $$t < c n$$ of the parties for some given $$c \in [0,1)$$ . In other words, only some arbitrarily small constant fraction of the parties are assumed to be honest. For any fixed c, we consider the asymptotic complexity as n and the size of f grows. We are in particular interested in the computational overhead, defined as the total computational complexity of all parties divided by the size of f. We show that it is possible to achieve poly-logarithmic computational overhead for all $$c < 1$$ . Prior to our result it was only known how to get poly-logarithmic overhead for $$c < \frac{1}{2}$$ . We therefore significantly extend the area where we can do secure multiparty computation with poly-logarithmic overhead. Since we allow that more than half the parties are corrupted, we can only get security with abort, i.e., the adversary might make the protocol abort before all parties learn their outputs. We can, however, for all c make a protocol for which there exists $$d > 0$$ such that if at most dn parties are actually corrupted in a given execution, then the protocol will not abort. Our result is solely of theoretical interest. In its current form, it has not practical implications whatsoever.

DOI
10.1007/978-3-662-54388-7_13

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•11 citations

Information-Theoretic Secure Multiparty Computation

Ueli M. Maurer, Vassilis Zikas

Most of this book has considered two-party and multiparty computation with security with (unfair) abort. This security notion allows the adversary to force the honest parties to abort even depending on the outputs of corrupted parties. (Note, however, that the adversary is not allowed to bias the output of honest parties in any other manner.) This relaxation of security is necessary if one wishes to tolerate arbitrarily many corruptions. A further relaxation considers computational security, where the adversary is assumed to be computationally bounded, e.g., probabilistic polynomial time. In this setting, any circuit can be securely realized even when arbitrarily many parties are corrupted, as long as one is willing to sacrifice fairness and robustness.

IOS Press eBooks•Jan 1, 2013•0 citations

Efficient MPC with a Mixed Adversary

Martin Hirt, Marta Mularczyk

Over the past 20 years, the efficiency of secure multi-party protocols has been greatly improved. While the seminal protocols from the late 80’s require a communication of Ω(n⁶) field elements per multiplication among n parties, recent protocols offer linear communication complexity. This means that each party needs to communicate a constant number of field elements per multiplication, independent of n. However, these efficient protocols only offer active security, which implies that at most t<n/3 (perfect security), respectively t<n/2 (statistical or computational security) parties may be corrupted. Higher corruption thresholds (i.e., t≥ n/2) can only be achieved with degraded security (unfair abort), where one single corrupted party can prevent honest parties from learning their outputs. The aforementioned upper bounds (t<n/3 and t<n/2) have been circumvented by considering mixed adversaries (Fitzi et al., Crypto' 98), i.e., adversaries that corrupt, at the same time, some parties actively, some parties passively, and some parties in the fail-stop manner. It is possible, for example, to achieve perfect security even if 2/3 of the parties are faulty (three quarters of which may abort in the middle of the protocol, and a quarter may even arbitrarily misbehave). This setting is much better suited to many applications, where the crash of a party is more likely than a coordinated active attack. Surprisingly, since the presentation of the feasibility result for the mixed setting, no progress has been made in terms of efficiency: the state-of-the-art protocol still requires a communication of Ω(n⁶) field elements per multiplication. In this paper, we present a perfectly-secure MPC protocol for the mixed setting with essentially the same efficiency as the best MPC protocols for the active-only setting. For the first time, this allows to tolerate faulty majorities, while still providing optimal efficiency. As a special case, this also results in the first fully-secure MPC protocol secure against any number of crashing parties, with optimal (i.e., linear in n) communication. We provide simulation-based proofs of our construction.

Leibniz international proceedings in informatics•Jan 1, 2020•1 citation

Two-Thirds Honest-Majority MPC for Malicious Adversaries at Almost the Cost of Semi-Honest

Jun Furukawa, Yehuda Lindell

Secure multiparty computation (MPC) enables a set of parties to securely carry out a joint computation of their private inputs without revealing anything but the output. Protocols for semi-honest adversaries guarantee security as long as the corrupted parties run the specified protocol and ensure that nothing is leaked in the transcript. In contrast, protocols for malicious adversaries guarantee security in the presence of arbitrary adversaries who can run any attack strategy. Security for malicious adversaries is typically what is needed in practice (and is always preferred), but comes at a significant cost. In this paper, we present the first protocol for a two-thirds honest majority that achieves security in the presence of malicious adversariesat essentially the exact same cost as the best known protocols for semi-honest adversaries. Our construction is not a general transformation and thus it is possible that better semi-honest protocols will be constructed which do not support our transformation. Nevertheless, for the current state-of-the-art for many parties (based on Shamir sharing), our protocol invokes the best semi-honest multiplication protocol exactly once per multiplication gate (plus some additional local computation that is negligible to the overall cost). Concretely, the best version of our protocol requires each party to send on average of just 2 2/3 elements per multiplication gate (when the number of multiplication gates is at least the number of parties). This is four times faster than the previous-best protocol of Barak et al. (ACM CCS 2018) for small fields, and twice as fast as the previous-best protocol of Chida et al. (CRYPTO 2018) for large fields.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 6, 2019•33 citations

Secure Multiparty Computation with Identifiable Abort and Fairness

Long Nie, Shaowen Yao, Jing Liu

Dishonest majority considered in the SPDZ(the nickname of the protocol of Damgard et al. from Crypto 2012) protocols implies the impossibility of fairness(which means that corrupted parties can prevent the honest parties from learning output). The corrupted parties can learn the outputs of the honest parties and abort the protocol. Settling for the second best, there are many works focusing on the detection of the cheaters. We construct a SPDZ-like protocol which achieves fairness when at most$n/2$parties behave maliciously and supports identifiable abort for dishonest majority. We suggest a sharing stage after the parties finish their computation. The parties share the returns of the computation in this stage. The correctness of the sharing is guaranteed by verifiable secret sharing and homomorphic signature. The honest parties can reconstruct the outputs of the cheaters in the setting of an honest majority. We can't prevent the corrupted parties from learning the outputs and aborting the protocol for dishonest majority. Therefore, the sharing stage does not harm to the honest parties. Instead, we provide the honest parties with the identities of all cheaters in this case.

International Conference on Cryptography, Security and Privacy (CSP)•Apr 1, 2023•2 citations

Multiparty computation secure against continual memory leakage

Elette Boyle, Shafi Goldwasser, Abhishek Jain +1 more

We construct a multiparty computation (MPC) protocol that is secure even if a malicious adversary, in addition to corrupting 1-ε fraction of all parties for an arbitrarily small constant ε >0, can leak information about the secret state of each honest party. This leakage can be continuous for an unbounded number of executions of the MPC protocol, computing different functions on the same or different set of inputs. We assume a (necessary) "leak-free" preprocessing stage. We emphasize that we achieve leakage resilience without weakening the security guarantee of classical MPC. Namely, an adversary who is given leakage on honest parties' states, is guaranteed to learn nothing beyond the input and output values of corrupted parties. This is in contrast with previous works on leakage in the multi-party protocol setting, which weaken the security notion, and only guarantee that a protocol which leaks l bits about the parties' secret states, yields at most l bits of leakage on the parties' private inputs. For some functions, such as voting, such leakage can be detrimental.

ACM Symposium on Theory of Computing (STOC)•May 19, 2012•55 citations
We consider the situation where a large number n of players want to securely compute a large function f with security against an adaptive, malicious adversary which might corrupt t<cnt < c nt<cn of the parties for some given c∈[0,1)c \in [0,1)c∈[0,1) . In other words, only some arbitrarily small constant fraction of the parties are assumed to be honest. For any fixed c, we consider the asymptotic complexity as n and the size of f grows. We are in particular interested in the computational overhead, defined as the total computational complexity of all parties divided by the size of f. We show that it is possible to achieve poly-logarithmic computational overhead for all c<1c < 1c<1 . Prior to our result it was only known how to get poly-logarithmic overhead for c<12c < \frac{1}{2}c<21​ . We therefore significantly extend the area where we can do secure multiparty computation with poly-logarithmic overhead. Since we allow that more than half the parties are corrupted, we can only get security with abort, i.e., the adversary might make the protocol abort before all parties learn their outputs. We can, however, for all c make a protocol for which there exists d>0d > 0d>0 such that if at most dn parties are actually corrupted in a given execution, then the protocol will not abort. Our result is solely of theoretical interest. In its current form, it has not practical implications whatsoever.
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.
Most of this book has considered two-party and multiparty computation with security with (unfair) abort. This security notion allows the adversary to force the honest parties to abort even depending on the outputs of corrupted parties. (Note, however, that the adversary is not allowed to bias the output of honest parties in any other manner.) This relaxation of security is necessary if one wishes to tolerate arbitrarily many corruptions. A further relaxation considers computational security, where the adversary is assumed to be computationally bounded, e.g., probabilistic polynomial time. In this setting, any circuit can be securely realized even when arbitrarily many parties are corrupted, as long as one is willing to sacrifice fairness and robustness.
Over the past 20 years, the efficiency of secure multi-party protocols has been greatly improved. While the seminal protocols from the late 80’s require a communication of Ω(n⁶) field elements per multiplication among n parties, recent protocols offer linear communication complexity. This means that each party needs to communicate a constant number of field elements per multiplication, independent of n. However, these efficient protocols only offer active security, which implies that at most t<n/3 (perfect security), respectively t<n/2 (statistical or computational security) parties may be corrupted. Higher corruption thresholds (i.e., t≥ n/2) can only be achieved with degraded security (unfair abort), where one single corrupted party can prevent honest parties from learning their outputs. The aforementioned upper bounds (t<n/3 and t<n/2) have been circumvented by considering mixed adversaries (Fitzi et al., Crypto' 98), i.e., adversaries that corrupt, at the same time, some parties actively, some parties passively, and some parties in the fail-stop manner. It is possible, for example, to achieve perfect security even if 2/3 of the parties are faulty (three quarters of which may abort in the middle of the protocol, and a quarter may even arbitrarily misbehave). This setting is much better suited to many applications, where the crash of a party is more likely than a coordinated active attack. Surprisingly, since the presentation of the feasibility result for the mixed setting, no progress has been made in terms of efficiency: the state-of-the-art protocol still requires a communication of Ω(n⁶) field elements per multiplication. In this paper, we present a perfectly-secure MPC protocol for the mixed setting with essentially the same efficiency as the best MPC protocols for the active-only setting. For the first time, this allows to tolerate faulty majorities, while still providing optimal efficiency. As a special case, this also results in the first fully-secure MPC protocol secure against any number of crashing parties, with optimal (i.e., linear in n) communication. We provide simulation-based proofs of our construction.
Secure multiparty computation (MPC) enables a set of parties to securely carry out a joint computation of their private inputs without revealing anything but the output. Protocols for semi-honest adversaries guarantee security as long as the corrupted parties run the specified protocol and ensure that nothing is leaked in the transcript. In contrast, protocols for malicious adversaries guarantee security in the presence of arbitrary adversaries who can run any attack strategy. Security for malicious adversaries is typically what is needed in practice (and is always preferred), but comes at a significant cost. In this paper, we present the first protocol for a two-thirds honest majority that achieves security in the presence of malicious adversariesat essentially the exact same cost as the best known protocols for semi-honest adversaries. Our construction is not a general transformation and thus it is possible that better semi-honest protocols will be constructed which do not support our transformation. Nevertheless, for the current state-of-the-art for many parties (based on Shamir sharing), our protocol invokes the best semi-honest multiplication protocol exactly once per multiplication gate (plus some additional local computation that is negligible to the overall cost). Concretely, the best version of our protocol requires each party to send on average of just 2 2/3 elements per multiplication gate (when the number of multiplication gates is at least the number of parties). This is four times faster than the previous-best protocol of Barak et al. (ACM CCS 2018) for small fields, and twice as fast as the previous-best protocol of Chida et al. (CRYPTO 2018) for large fields.
Dishonest majority considered in the SPDZ(the nickname of the protocol of Damgard et al. from Crypto 2012) protocols implies the impossibility of fairness(which means that corrupted parties can prevent the honest parties from learning output). The corrupted parties can learn the outputs of the honest parties and abort the protocol. Settling for the second best, there are many works focusing on the detection of the cheaters. We construct a SPDZ-like protocol which achieves fairness when at mostn/2n/2n/2parties behave maliciously and supports identifiable abort for dishonest majority. We suggest a sharing stage after the parties finish their computation. The parties share the returns of the computation in this stage. The correctness of the sharing is guaranteed by verifiable secret sharing and homomorphic signature. The honest parties can reconstruct the outputs of the cheaters in the setting of an honest majority. We can't prevent the corrupted parties from learning the outputs and aborting the protocol for dishonest majority. Therefore, the sharing stage does not harm to the honest parties. Instead, we provide the honest parties with the identities of all cheaters in this case.
We construct a multiparty computation (MPC) protocol that is secure even if a malicious adversary, in addition to corrupting 1-ε fraction of all parties for an arbitrarily small constant ε >0, can leak information about the secret state of each honest party. This leakage can be continuous for an unbounded number of executions of the MPC protocol, computing different functions on the same or different set of inputs. We assume a (necessary) "leak-free" preprocessing stage. We emphasize that we achieve leakage resilience without weakening the security guarantee of classical MPC. Namely, an adversary who is given leakage on honest parties' states, is guaranteed to learn nothing beyond the input and output values of corrupted parties. This is in contrast with previous works on leakage in the multi-party protocol setting, which weaken the security notion, and only guarantee that a protocol which leaks l bits about the parties' secret states, yields at most l bits of leakage on the parties' private inputs. For some functions, such as voting, such leakage can be detrimental.