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 Cryptography, Security and Privacy (CSP)

Secure Multiparty Computation with Identifiable Abort and Fairness

Long Nie, Shaowen Yao, Jing Liu

Published Apr 1, 2023• 2 citations
Publisher

Abstract

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.

DOI
10.1109/csp58884.2023.00023

Related papers

Efficient Fair and Robust SPDZ-Like Multi-Party Computation

Chung-Li Wang

Effective multi-party computation protocols have been developed, but concerns regarding privacy and correctness persist. Classic results demonstrate that guaranteed output delivery can be achieved by assuming fairness and identifiable abort. However, if the majority is malicious, it is still challenging to design an efficient implementation that can deliver correct outputs while maintaining robustness and fairness. To address this issue, we have redesigned the secret-sharing mechanism and employed a semi-trusted third party (TTP) as the key manager to provide optimistic backup for output delivery. The verification and delivery procedures prevent the malicious parties from “stealing” the output, when there is at least one honest party. Furthermore, the TTP has no knowledge of output, so even if he is malicious and colluding, we only lose fairness. The decryption is needed only when misconduct is detected. Our scheme also enables identified abort for offline preprocessing, and the audit of the offline sub-protocols can be publicly performed, holding corrupted parties accountable before receiving private inputs. With fairness and identifiable abort, output delivery is guaranteed by excluding the cheaters.

•Jul 29, 2023•1 citation

Extending the Security of SPDZ with Fairness

Bart Veldhuizen, Gabriele Spini, Thijs Veugen +1 more

SPDZ refers to a family of protocols for Secure Multi-Party Computation (MPC) that lie at the foundation of very popular software frameworks for MPC, such as SCALE-MAMBA and MP-SPDZ. SPDZ provides good efficiency while guaranteeing security even when all but one of the participants are corrupted. This seemingly optimal property comes at a price: the protocol only offers security with abort, meaning that even a single cheating participant can force the protocol to abort, leaving honest participants with no clue on what the correct output is, or who cheated. This is especially problematic since cheating participants are able to obtain the correct output of the computation, effectively `stealing' it. We propose a *hybrid secure* adaptation to SPDZ, which retains the existing security guarantees, but in case the number of cheating players is less than half of the total, we achieve *fairness*, meaning that either all players obtain the correct output of the computation, or no player does. The `less than half' threshold of corrupted players has been proven to be a tight bound to achieve fairness. Aside from the description of the protocol and its security proof, we also present a proof-of-concept implementation, and evaluate its practical performance, thereby demonstrating that our solution has negligible overhead compared to standard SPDZ in most application scenarios.

Proceedings on Privacy Enhancing Technologies•Apr 1, 2024•2 citations

SPDZ-Based Optimistic Fair Multi-Party Computation Detection

Chung-Li Wang

The fairness of multi-party computation has been investigated for long time. Classic results demonstrate that fair exchange can be achieved by utilizing cryptographic tools, as most of them are based on garbled circuits. For the secret-sharing schemes, such as SPDZ, it may incur significant overhead to simply apply a fair escrow scheme, since it encrypts all the shares of delivered results. To address this issue, we design a twolevel secret-sharing mechanism. The escrow encryption is only for the first level of sharing and performed in preprocessing. The second level of sharing is used for computation and always handled by plaintexts, such that the online phase is still efficient. Our work also employs a semi-trusted third party (TTP) which provide optimistic escrow for output delivery. The verification and delivery procedures prevent the malicious parties from corrupting the outcome or aborting, when there is at least one honest party. Furthermore, the TTP has no knowledge of output, so even if he is malicious and colluding, we only lose fairness. The escrow decryption is needed only when misconduct is detected for opening the first-level shares.

International Journal of Network Security & Its Applications•Sep 28, 2023•0 citations

On the Computational Overhead of MPC with Dishonest Majority

Jesper Buus Nielsen, Samuel Ranellucci

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.

Lecture notes in computer science•Jan 1, 2017•8 citations

On Achieving the “Best of Both Worlds” in Secure Multiparty Computation

Yuval Ishai, Jonathan I. Katz, Eyal Kushilevitz +2 more

Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Existing protocols that assume an honest majority provide “full security” (and, in particular, guarantee output delivery and fairness) when this assumption holds, but are completely insecure if this assumption is violated. On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the “best of both worlds”: namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) and show some positive results regarding what can be achieved.

SIAM Journal on Computing•Jan 1, 2011•32 citations

Hidden Δ\DeltaΔ-fairness: A Novel Notion for Fair Secure Two-Party Computation

Saskia Bayreuther, Robin Berger, Felix Dörre +2 more

Secure two-party computation allows two mutually distrusting parties to compute a joint function over their inputs, guaranteeing properties such as \emph{input privacy} or \emph{correctness}. For many tasks, such as joint computation of statistics, it is important that when one party receives the result of the computation, the other party also receives the result. Unfortunately, this property, which is called \emph{fairness}, is unattainable in the two-party setting for arbitrary functions. So weaker variants have been proposed. One such notion, proposed by Pass \etal (EUROCRYPT 2017) is called \emph{$\Delta$-fairness}. Informally, it guarantees that if a corrupt party receives the output in round $r$ and stops participating in the protocol, then the honest party receives the output by round $\Delta(r)$. This notion is achieved by using so-called \emph{secure enclaves}. In many settings, $\Delta$-fairness is not sufficient, because a corrupt party is \emph{guaranteed} to receive its output before the honest party, giving the corrupt party an advantage in further interaction. Worse, as $\Delta$ is known to the corrupt party, it can abort the protocol when it is most advantageous. We extend the concept of $\Delta$-fairness by introducing a new fairness notion, which we call \emph{hidden $\Delta$-fairness}, which addresses these problems. First of all, under our new notion, a corrupt party may not benefit from aborting, because it may not, with probability $\nicefrac{1}{2}$, learn the result first. Moreover, $\Delta$ and other parameters are sampled according to a given distribution and remain unknown to the participants in the computation. We propose a 2PC protocol that achieves hidden $\Delta$-fairness, also using secure enclaves, and prove its security in the Generalized Universal Composability (GUC) framework.

•Jan 1, 2024•0 citations
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.
Effective multi-party computation protocols have been developed, but concerns regarding privacy and correctness persist. Classic results demonstrate that guaranteed output delivery can be achieved by assuming fairness and identifiable abort. However, if the majority is malicious, it is still challenging to design an efficient implementation that can deliver correct outputs while maintaining robustness and fairness. To address this issue, we have redesigned the secret-sharing mechanism and employed a semi-trusted third party (TTP) as the key manager to provide optimistic backup for output delivery. The verification and delivery procedures prevent the malicious parties from “stealing” the output, when there is at least one honest party. Furthermore, the TTP has no knowledge of output, so even if he is malicious and colluding, we only lose fairness. The decryption is needed only when misconduct is detected. Our scheme also enables identified abort for offline preprocessing, and the audit of the offline sub-protocols can be publicly performed, holding corrupted parties accountable before receiving private inputs. With fairness and identifiable abort, output delivery is guaranteed by excluding the cheaters.
SPDZ refers to a family of protocols for Secure Multi-Party Computation (MPC) that lie at the foundation of very popular software frameworks for MPC, such as SCALE-MAMBA and MP-SPDZ. SPDZ provides good efficiency while guaranteeing security even when all but one of the participants are corrupted. This seemingly optimal property comes at a price: the protocol only offers security with abort, meaning that even a single cheating participant can force the protocol to abort, leaving honest participants with no clue on what the correct output is, or who cheated. This is especially problematic since cheating participants are able to obtain the correct output of the computation, effectively `stealing' it. We propose a *hybrid secure* adaptation to SPDZ, which retains the existing security guarantees, but in case the number of cheating players is less than half of the total, we achieve *fairness*, meaning that either all players obtain the correct output of the computation, or no player does. The `less than half' threshold of corrupted players has been proven to be a tight bound to achieve fairness. Aside from the description of the protocol and its security proof, we also present a proof-of-concept implementation, and evaluate its practical performance, thereby demonstrating that our solution has negligible overhead compared to standard SPDZ in most application scenarios.
The fairness of multi-party computation has been investigated for long time. Classic results demonstrate that fair exchange can be achieved by utilizing cryptographic tools, as most of them are based on garbled circuits. For the secret-sharing schemes, such as SPDZ, it may incur significant overhead to simply apply a fair escrow scheme, since it encrypts all the shares of delivered results. To address this issue, we design a twolevel secret-sharing mechanism. The escrow encryption is only for the first level of sharing and performed in preprocessing. The second level of sharing is used for computation and always handled by plaintexts, such that the online phase is still efficient. Our work also employs a semi-trusted third party (TTP) which provide optimistic escrow for output delivery. The verification and delivery procedures prevent the malicious parties from corrupting the outcome or aborting, when there is at least one honest party. Furthermore, the TTP has no knowledge of output, so even if he is malicious and colluding, we only lose fairness. The escrow decryption is needed only when misconduct is detected for opening the first-level shares.
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.
Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Existing protocols that assume an honest majority provide “full security” (and, in particular, guarantee output delivery and fairness) when this assumption holds, but are completely insecure if this assumption is violated. On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the “best of both worlds”: namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) and show some positive results regarding what can be achieved.
Secure two-party computation allows two mutually distrusting parties to compute a joint function over their inputs, guaranteeing properties such as \emph{input privacy} or \emph{correctness}. For many tasks, such as joint computation of statistics, it is important that when one party receives the result of the computation, the other party also receives the result. Unfortunately, this property, which is called \emph{fairness}, is unattainable in the two-party setting for arbitrary functions. So weaker variants have been proposed. One such notion, proposed by Pass \etal (EUROCRYPT 2017) is called \emph{Δ\DeltaΔ-fairness}. Informally, it guarantees that if a corrupt party receives the output in round rrr and stops participating in the protocol, then the honest party receives the output by round Δ(r)\Delta(r)Δ(r). This notion is achieved by using so-called \emph{secure enclaves}. In many settings, Δ\DeltaΔ-fairness is not sufficient, because a corrupt party is \emph{guaranteed} to receive its output before the honest party, giving the corrupt party an advantage in further interaction. Worse, as Δ\DeltaΔ is known to the corrupt party, it can abort the protocol when it is most advantageous. We extend the concept of Δ\DeltaΔ-fairness by introducing a new fairness notion, which we call \emph{hidden Δ\DeltaΔ-fairness}, which addresses these problems. First of all, under our new notion, a corrupt party may not benefit from aborting, because it may not, with probability $\nicefrac{1}{2}$, learn the result first. Moreover, Δ\DeltaΔ and other parameters are sampled according to a given distribution and remain unknown to the participants in the computation. We propose a 2PC protocol that achieves hidden Δ\DeltaΔ-fairness, also using secure enclaves, and prove its security in the Generalized Universal Composability (GUC) framework.