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

Chicago Journal of Theoretical Computer Science

Legally Enforceable Fairness in Secure Two-Party Communication.

Yehuda Lindell

Published Jan 1, 2009• 2 citations
OpenAlex

Abstract

In the setting of secure multiparty computation, a set of mutually distrustful parties wish to securely compute some joint function of their private inputs. The computation should be carried out in a secure way, meaning that the properties privacy, correctness, independence of inputs, fairness and guaranteed output delivery should all be preserved. Unfortunately, in the case of no honest majority – and specifically in the important two-party case – it is impossible to achieve fairness and guaranteed output delivery. In this paper, we show how a legal infrastructure that respects digital signatures can be used to enforce fairness in two-party computation. Our protocol has the property that if one party obtains output while the other does not (meaning that fairness is breached), then the party not obtaining output has a digitally signed cheque from the other party. Thus, fairness can be “enforced ” in the sense that any breach results in a loss of money by the adversarial party. 1

Related papers

Complete Fairness in Secure Two-Party Computation

Steven Gordon, Carmit Hazay, Jonathan I. Katz +1 more

In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve [1986] showed that complete fairness cannot be achieved in general without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting. We demonstrate that this folklore belief is false by showing completely fair protocols for various nontrivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an “embedded XOR”; this class of functions includes boolean AND/OR as well as Yao’s “millionaires’ problem”. We also demonstrate feasibility for certain functions that do contain an embedded XOR, though we prove a lower bound showing that any completely fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely fair secure computation without an honest majority is far from closed.

Journal of the ACM•Dec 1, 2011•72 citations

Complete fairness in secure two-party computation

Dov Gordon, Carmit Hazay, Jonathan I. Katz +1 more

In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness, which guarantees that if either party receives its output, then the other party does too. Cleve (STOC 1986) showed that complete fairness cannot be achieved in general in the two-party setting; specifically, he showed (essentially) that it is impossible to compute Boolean XOR with complete fairness. Since his work, the accepted folklore has been that nothing non-trivial can be computed with complete fairness, and the question of complete fairness in secure two-party computation has been treated as closed since the late '80s.

ACM Symposium on Theory of Computing (STOC)•May 17, 2008•109 citations

Complete Fairness in Secure Two-Party Computation.

Steven Gordon, Carmit Hazay, Jonathan I. Katz +1 more

In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve (STOC 1986) showed that complete fairness cannot be achieved in general without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting, and the problem has been treated as closed since the late ’80s. In this paper, we demonstrate that this folklore belief is false by showing completely-fair protocols for various non-trivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an “embedded XOR”; this class of functions includes boolean AND/OR as well as Yao’s “millionaires ’ problem”. We also demonstrate feasibility for certain functions that do contain an embedded XOR, and prove a lower bound showing that any completely-fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely-fair secure computation without an honest majority is far from closed.

•Jan 1, 2008•24 citations

Secure multi-party computation with legally-enforceable fairness

Takeshi Nakai, Kazumasa Shinagawa

Abstract Fairness is a security notion of secure computation and cannot always be achieved if an adversary corrupts a majority of parties in standard settings. Lindell (CT-RSA 2008) showed that imposing a monetary penalty on an adversary can circumvent the impossibility. He formalized such a security notion as “legally enforceable fairness" for the two-party setting based on the ideal trusted bank functionality and showed a protocol achieving the requirements. Based on the same framework, we introduce secure multi-party computation with legally enforceable fairness that is applicable for an arbitrary number of parties. Further, we propose two protocols that realize our introduced functionality. The first one achieves O(n) rounds and $$O(n \alpha )$$ O ( n α ) fees, where n is the number of parties, and $$\alpha $$ α is a parameter for the penalty amount. The fee refers to the balance amount in the bank required at the beginning of the protocol, which evaluates the difficulty of participating in the protocol in a financial sense. The second one achieves O(1) rounds and $$O(n^2 \alpha )$$ O ( n 2 α ) fees.

International Journal of Information Security•Aug 29, 2024•6 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

Foundations of Secure Computation: Perfect Security and Fairness

Gilad Asharov

In the setting of secure multiparty computation, several distrustful parties wish to carry out a distributed computing task on their local private data while satisfying several security properties such as correctness, privacy, independence of inputs and fairness. The aim of secure multiparty computation (MPC) is to enable the parties to carry out the computation in a secure manner, eliminating any attempt of an adversarial entity to harm the execution. The concept of secure computation is very general and fundamental in cryptography, and models any distributed computing task, including simple computations as coin-tossing and broadcast, as well as more complex tasks such as electronic auctions and anonymous transactions. In this thesis, we study two foundational aspects of secure computation: perfect security and fairness. In the first part of this thesis, we study perfect security in secure computation. A protocol that is perfectly secure cannot be broken even when the adversary has unlimited computational power and its security holds unconditionally. One of the most fundamental results of secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. When the adversary is semi-honest this holds as long as t < n/2 parties are corrupted, and when the adversary is malicious this holds as long as t < n/3 parties are corrupted. Unfortunately, a full proof of these results was never published. In this thesis, we remedy this situation and provide a full proof of security of the BGW protocol. This also includes a full description of the protocol for the malicious setting. In addition to the above, we observe that by some simple and natural modifications, the BGW protocol can be significantly simplified and one of its expensive (and perhaps most complicated) subprotocols can be saved. We present a new multiplication protocol that is based on the original construction, but is simpler and achieves higher efficiency. In the second part of this thesis, we study fairness in secure two party computation. Informally, the fairness property guarantees that if one party receives its output, then the other party does too. The well-known impossibility result of Cleve (STOC 1986) implies that, in general, it is impossible to securely compute a function with complete fairness without an honest majority. Until recently, the accepted belief has been that nothing non-trivial can be computed with complete fairness in the two party setting. The surprising work of Gordon, Hazay, Katz and Lindell (STOC 2008) shows that this belief is false, and that there exist some non-trivial (deterministic, finite-domain) Boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation. We focus on this question and give both positive and negative results. We first characterize

•Jan 1, 2014•0 citations
In the setting of secure multiparty computation, a set of mutually distrustful parties wish to securely compute some joint function of their private inputs. The computation should be carried out in a secure way, meaning that the properties privacy, correctness, independence of inputs, fairness and guaranteed output delivery should all be preserved. Unfortunately, in the case of no honest majority – and specifically in the important two-party case – it is impossible to achieve fairness and guaranteed output delivery. In this paper, we show how a legal infrastructure that respects digital signatures can be used to enforce fairness in two-party computation. Our protocol has the property that if one party obtains output while the other does not (meaning that fairness is breached), then the party not obtaining output has a digitally signed cheque from the other party. Thus, fairness can be “enforced ” in the sense that any breach results in a loss of money by the adversarial party. 1
In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve [1986] showed that complete fairness cannot be achieved in general without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting. We demonstrate that this folklore belief is false by showing completely fair protocols for various nontrivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an “embedded XOR”; this class of functions includes boolean AND/OR as well as Yao’s “millionaires’ problem”. We also demonstrate feasibility for certain functions that do contain an embedded XOR, though we prove a lower bound showing that any completely fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely fair secure computation without an honest majority is far from closed.
In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness, which guarantees that if either party receives its output, then the other party does too. Cleve (STOC 1986) showed that complete fairness cannot be achieved in general in the two-party setting; specifically, he showed (essentially) that it is impossible to compute Boolean XOR with complete fairness. Since his work, the accepted folklore has been that nothing non-trivial can be computed with complete fairness, and the question of complete fairness in secure two-party computation has been treated as closed since the late '80s.
In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve (STOC 1986) showed that complete fairness cannot be achieved in general without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting, and the problem has been treated as closed since the late ’80s. In this paper, we demonstrate that this folklore belief is false by showing completely-fair protocols for various non-trivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an “embedded XOR”; this class of functions includes boolean AND/OR as well as Yao’s “millionaires ’ problem”. We also demonstrate feasibility for certain functions that do contain an embedded XOR, and prove a lower bound showing that any completely-fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely-fair secure computation without an honest majority is far from closed.
Abstract Fairness is a security notion of secure computation and cannot always be achieved if an adversary corrupts a majority of parties in standard settings. Lindell (CT-RSA 2008) showed that imposing a monetary penalty on an adversary can circumvent the impossibility. He formalized such a security notion as “legally enforceable fairness" for the two-party setting based on the ideal trusted bank functionality and showed a protocol achieving the requirements. Based on the same framework, we introduce secure multi-party computation with legally enforceable fairness that is applicable for an arbitrary number of parties. Further, we propose two protocols that realize our introduced functionality. The first one achieves O(n) rounds and O(nα)O(n \alpha )O(nα) O ( n α ) fees, where n is the number of parties, and α\alpha α α is a parameter for the penalty amount. The fee refers to the balance amount in the bank required at the beginning of the protocol, which evaluates the difficulty of participating in the protocol in a financial sense. The second one achieves O(1) rounds and O(n2α)O(n^2 \alpha )O(n2α) O ( n 2 α ) fees.
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.
In the setting of secure multiparty computation, several distrustful parties wish to carry out a distributed computing task on their local private data while satisfying several security properties such as correctness, privacy, independence of inputs and fairness. The aim of secure multiparty computation (MPC) is to enable the parties to carry out the computation in a secure manner, eliminating any attempt of an adversarial entity to harm the execution. The concept of secure computation is very general and fundamental in cryptography, and models any distributed computing task, including simple computations as coin-tossing and broadcast, as well as more complex tasks such as electronic auctions and anonymous transactions. In this thesis, we study two foundational aspects of secure computation: perfect security and fairness. In the first part of this thesis, we study perfect security in secure computation. A protocol that is perfectly secure cannot be broken even when the adversary has unlimited computational power and its security holds unconditionally. One of the most fundamental results of secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. When the adversary is semi-honest this holds as long as t < n/2 parties are corrupted, and when the adversary is malicious this holds as long as t < n/3 parties are corrupted. Unfortunately, a full proof of these results was never published. In this thesis, we remedy this situation and provide a full proof of security of the BGW protocol. This also includes a full description of the protocol for the malicious setting. In addition to the above, we observe that by some simple and natural modifications, the BGW protocol can be significantly simplified and one of its expensive (and perhaps most complicated) subprotocols can be saved. We present a new multiplication protocol that is based on the original construction, but is simpler and achieves higher efficiency. In the second part of this thesis, we study fairness in secure two party computation. Informally, the fairness property guarantees that if one party receives its output, then the other party does too. The well-known impossibility result of Cleve (STOC 1986) implies that, in general, it is impossible to securely compute a function with complete fairness without an honest majority. Until recently, the accepted belief has been that nothing non-trivial can be computed with complete fairness in the two party setting. The surprising work of Gordon, Hazay, Katz and Lindell (STOC 2008) shows that this belief is false, and that there exist some non-trivial (deterministic, finite-domain) Boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation. We focus on this question and give both positive and negative results. We first characterize