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

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

Saskia Bayreuther, Robin Berger, Felix Dörre, Jeremias Mechler, Jörn Müller-Quade

Published Jan 1, 2024• 0 citations
Publisher

Abstract

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.

DOI
10.5445/ir/1000170464

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

Secure and fair two-party computation

Mehmet Sabır Kiraz

Consider several parties that do not trust each other, yet they wish to correctly compute some common function of their local inputs while keeping these inputs private. This problem is known as "Secure Multi-Party Computation", and was introduced by Andrew Yao in 1982. Secure multi-party computations have some real world examples like electronic auctions, electronic voting or fingerprinting. In this thesis we consider the case where there are only two parties involved. This is known as "Secure Two-Party Computation". If there is a trusted third party called Carol, then the problem is pretty straightforward. The participating parties could hand their inputs in Carol who can compute the common function correctly and could return the outputs to the corresponding parties. The goal is to achieve (almost) the same result when there is no trusted third party. Cryptographic protocols are designed in order to solve these kinds of problems. These protocols are analyzed within an appropriate model in which the behavior of parties is structured. The basic level is called the Semi-Honest Model where parties are assumed to follow the protocol specification, but later can derive additional information based on the messages which have been received so far. A more realistic model is the so-called Malicious Model. The common approach is to first analyze a protocol in the semi-honest model and then later extend it into the malicious model. Any cryptographic protocol for secure two-party computation must satisfy the following security requirements: correctness, privacy and fairness. It must guarantee the correctness of the result while preserving the privacy of the parties’ inputs, even if one of the parties is malicious and behaves arbitrarily throughout the protocol. It must also guarantee fairness. This roughly means that whenever a party aborts the protocol prematurely, he or she should not have any advantage over the other party in discovering the output. The main question for researchers is to construct new protocols that achieve the above mentioned goals for secure multi-party computation. Of course, such protocols must be secure in a given model, as well as be as efficient as possible. In 1986, Yao presented the first general protocol for secure two-party computation which was applicable only to the semi-honest model. He uses a tool called "Garbled Circuit". Yao’s protocol uses the underlying primitives ("Pseudorandom Generator" and "Oblivious Transfer") as blackboxes which lead to efficient results. After Yao’s work many variants and improvements have been proposed for the malicious model. In this thesis, we design several new protocols for secure two-party computation based on Yao’s garbled circuit. Before we present the details of our new designs, we first show several weaknesses, security flaws or problems with the existing protocols in the literature. We first work in the semi-honest model and then extend it into the malicious model by presenting new protocols. Finally we add fairness to our protocol. Oblivious transfer (OT) is a fundamental primitive in modern cryptography which is useful for implementing protocols for secure multi-party computation. We study several variants of oblivious transfer in this thesis. We present a new protocol for the so-called "Committed OT". This protocol is very efficient in the sense that it is quite good in comparison to the most efficient committed OT protocols in the literature. The abovementioned flaw with the use of OT can be fixed with our committed oblivious transfer protocol. Furthermore, it is more general than all previous protocols, and, therefore, it is of independent interest. We also deal with fairness in this thesis. For protocols based on garbled circuit, so far only Benny Pinkas has presented a protocol in the literature for achieving fairness. We show a subtle problem with this protocol where the privacy of the inputs of one party can be compromised. We also describe this problem in detail which is in fact related to the fairness, and finally propose a more efficient scheme that does achieve fairness.

•Jan 1, 2007•19 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•26 citations

Legally Enforceable Fairness in Secure Two-Party Communication.

Yehuda Lindell

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

Chicago Journal of Theoretical Computer Science•Jan 1, 2009•2 citations

On fairness in secure computation

Jonathan I. Katz, Samuel Dov Gordon

Secure computation is a fundamental problem in modern cryptography in which multiple parties join to compute a function of their private inputs without revealing anything beyond the output of the function. A series of very strong results in the 1980’s demonstrated that any polynomial-time function can be computed while guaranteeing essentially every desired security property. The only exception is the fairness property, which states that no player should receive their output from the computation unless all players receive their output. While it was shown that fairness can be achieved whenever a majority of players are honest, it was also shown that fairness is impossible to achieve in general when half or more of the players are dishonest. Indeed, it was proven that even boolean XOR cannot be computed fairly by two parties. The fairness property is both natural and important, and as such it was one of the first questions addressed in modern cryptography (in the context of signature exchange). One contribution of this thesis is to survey the many approaches that have been used to guarantee different notions of partial fairness. We then revisit the topic of fairness within a modern security framework for secure computation. We demonstrate that, despite the strong impossibility result mentioned above, certain interesting functions can be computed fairly, even when half (or more) of the parties are malicious. We also provide a new notion of partial fairness, demonstrate feasibility of achieving this notion for a large class of functions, and show impossibility for certain functions outside this class. We consider fairness in the presence of rational adversaries, and, finally, we study the difficulty of achieving fairness by exploring how much external help is necessary for providing fair secure computation.

•Jan 1, 2010•10 citations

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
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 \nicefrac12\nicefrac{1}{2}\nicefrac12, 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 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.
Consider several parties that do not trust each other, yet they wish to correctly compute some common function of their local inputs while keeping these inputs private. This problem is known as "Secure Multi-Party Computation", and was introduced by Andrew Yao in 1982. Secure multi-party computations have some real world examples like electronic auctions, electronic voting or fingerprinting. In this thesis we consider the case where there are only two parties involved. This is known as "Secure Two-Party Computation". If there is a trusted third party called Carol, then the problem is pretty straightforward. The participating parties could hand their inputs in Carol who can compute the common function correctly and could return the outputs to the corresponding parties. The goal is to achieve (almost) the same result when there is no trusted third party. Cryptographic protocols are designed in order to solve these kinds of problems. These protocols are analyzed within an appropriate model in which the behavior of parties is structured. The basic level is called the Semi-Honest Model where parties are assumed to follow the protocol specification, but later can derive additional information based on the messages which have been received so far. A more realistic model is the so-called Malicious Model. The common approach is to first analyze a protocol in the semi-honest model and then later extend it into the malicious model. Any cryptographic protocol for secure two-party computation must satisfy the following security requirements: correctness, privacy and fairness. It must guarantee the correctness of the result while preserving the privacy of the parties’ inputs, even if one of the parties is malicious and behaves arbitrarily throughout the protocol. It must also guarantee fairness. This roughly means that whenever a party aborts the protocol prematurely, he or she should not have any advantage over the other party in discovering the output. The main question for researchers is to construct new protocols that achieve the above mentioned goals for secure multi-party computation. Of course, such protocols must be secure in a given model, as well as be as efficient as possible. In 1986, Yao presented the first general protocol for secure two-party computation which was applicable only to the semi-honest model. He uses a tool called "Garbled Circuit". Yao’s protocol uses the underlying primitives ("Pseudorandom Generator" and "Oblivious Transfer") as blackboxes which lead to efficient results. After Yao’s work many variants and improvements have been proposed for the malicious model. In this thesis, we design several new protocols for secure two-party computation based on Yao’s garbled circuit. Before we present the details of our new designs, we first show several weaknesses, security flaws or problems with the existing protocols in the literature. We first work in the semi-honest model and then extend it into the malicious model by presenting new protocols. Finally we add fairness to our protocol. Oblivious transfer (OT) is a fundamental primitive in modern cryptography which is useful for implementing protocols for secure multi-party computation. We study several variants of oblivious transfer in this thesis. We present a new protocol for the so-called "Committed OT". This protocol is very efficient in the sense that it is quite good in comparison to the most efficient committed OT protocols in the literature. The abovementioned flaw with the use of OT can be fixed with our committed oblivious transfer protocol. Furthermore, it is more general than all previous protocols, and, therefore, it is of independent interest. We also deal with fairness in this thesis. For protocols based on garbled circuit, so far only Benny Pinkas has presented a protocol in the literature for achieving fairness. We show a subtle problem with this protocol where the privacy of the inputs of one party can be compromised. We also describe this problem in detail which is in fact related to the fairness, and finally propose a more efficient scheme that does achieve fairness.
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.
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
Secure computation is a fundamental problem in modern cryptography in which multiple parties join to compute a function of their private inputs without revealing anything beyond the output of the function. A series of very strong results in the 1980’s demonstrated that any polynomial-time function can be computed while guaranteeing essentially every desired security property. The only exception is the fairness property, which states that no player should receive their output from the computation unless all players receive their output. While it was shown that fairness can be achieved whenever a majority of players are honest, it was also shown that fairness is impossible to achieve in general when half or more of the players are dishonest. Indeed, it was proven that even boolean XOR cannot be computed fairly by two parties. The fairness property is both natural and important, and as such it was one of the first questions addressed in modern cryptography (in the context of signature exchange). One contribution of this thesis is to survey the many approaches that have been used to guarantee different notions of partial fairness. We then revisit the topic of fairness within a modern security framework for secure computation. We demonstrate that, despite the strong impossibility result mentioned above, certain interesting functions can be computed fairly, even when half (or more) of the parties are malicious. We also provide a new notion of partial fairness, demonstrate feasibility of achieving this notion for a large class of functions, and show impossibility for certain functions outside this class. We consider fairness in the presence of rational adversaries, and, finally, we study the difficulty of achieving fairness by exploring how much external help is necessary for providing fair secure computation.
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.