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

SIAM Journal on Computing

Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions

Gilad Asharov, Amos Beimel, Nikolaos Makriyannis, Eran Omri

Published Sep 23, 2024• 0 citations
Publisher

Abstract

Abstract. Fairness is a desirable property in secure computation; informally it means that if one party gets the output of the function, then all parties get the output. Alas, an implication of Cleve’s result [18th ACM Symposium on the Theory of Computing, 1986] is that when there is no honest majority, in particular in the important case of the two-party setting, there exist functions that cannot be computed with fairness. In a surprising result, Gordon et al. [18th ACM Symposium on the Theory of Computing, 2008; J. ACM, 58 (2011), 24] showed that some interesting functions can be computed with fairness in the two-party setting and reopened the question of understanding which Boolean functions can be computed with fairness, and which cannot. Our main result in this work is a complete characterization of the (symmetric) Boolean functions that can be computed with fairness in the two-party setting; this settles an open problem of Gordon et al. The statement of the characterization is quite simple: A function can be computed with fairness if and only if the all-one vector or the all-zero vector are in the affine span of either the rows or the columns of the matrix describing the function. This is true for both deterministic and randomized functions. To prove the possibility result, we modify the protocol of Gordon et al.; the resulting protocol computes with full security (and in particular with fairness) all functions that are computable with fairness. Complementing this result, we also show that any function that does not satisfy the aforementioned condition can be reduced to a fair sampling protocol, which, by Agrawal and Prabhakaran [ Advances in Cryptology – CRYPTO 2013, 2013], cannot be computed with fairness.

DOI
10.1137/18m1232656

Related papers

Towards Characterizing Complete Fairness in Secure Two-Party Computation.

Gilad Asharov

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. Since then, 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, nite-domain) boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation. In this work we show that not only that some or few functions can be computed fairly, but rather an enormous number of functions can be computed fairly. In fact, almost all boolean functions with distinct domain sizes can be computed with complete fairness (for instance, more than 99:999 % of the boolean functions with domain sizes 31 30). The class of functions that is shown to be possible includes also rather involved and highly non-trivial tasks, such as set-membership, evaluation of a private (boolean) function, private matchmaking and set-disjointness.

•Jan 1, 2014•0 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 [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.

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

Fairness in two-party computation: characterizing fair functions

Nikolaos Makriyannis

Secure two-party computation is a classic problem in cryptography. It involves two parties computing a function of their private inputs, and only revealing what the output suggests. Additional security requirements may include fairness, which states that either all parties receive output, or no one does. A seminal result from the 1980's demonstrates that fairness cannot be guaranteed for all functions, and only recently have certain functions been shown to be computable with fairness. The two results naturally give rise to a distinction between fair functions and unfair ones. In this work, we investigate the characterization of such functions in the two-party setting. In the end, we obtain a full characterization for Boolean functions, and we develop a number of useful techniques for characterizing arbitrary fair functions.

•Sep 20, 2016•1 citation

Secure Multiparty Computation with Partial Fairness

Amos Beimel, Eran Omri, Ilan Orlov

A protocol for computing a functionality is secure if an adversary in this protocol cannot cause more harm than in an ideal computation where parties give their inputs to a trusted party which returns the output of the functionality to all parties. In particular, in the ideal model such computation is fair -- all parties get the output. Cleve (STOC 1986) proved that, in general, fairness is not possible without an honest majority. To overcome this impossibility, Gordon and Katz (Eurocrypt 2010) suggested a relaxed definition -- 1/p-secure computation -- which guarantees partial fairness. For two parties, they construct 1/p-secure protocols for functionalities for which the size of either their domain or their range is polynomial (in the security parameter). Gordon and Katz ask whether their results can be extended to multiparty protocols. We study 1/p-secure protocols in the multiparty setting for general functionalities. Our main result is constructions of 1/p-secure protocols when the number of parties is constant provided that less than 2/3 of the parties are corrupt. Our protocols require that either (1) the functionality is deterministic and the size of the domain is polynomial (in the security parameter), or (2) the functionality can be randomized and the size of the range is polynomial. If the size of the domain is constant and the functionality is deterministic, then our protocol is efficient even when the number of parties is O(log log n) (where n is the security parameter). On the negative side, we show that when the number of parties is super-constant, 1/p-secure protocols are not possible when the size of the domain is polynomial.

arXiv:1011.5567•Nov 25, 2010•0 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•111 citations
Abstract. Fairness is a desirable property in secure computation; informally it means that if one party gets the output of the function, then all parties get the output. Alas, an implication of Cleve’s result [18th ACM Symposium on the Theory of Computing, 1986] is that when there is no honest majority, in particular in the important case of the two-party setting, there exist functions that cannot be computed with fairness. In a surprising result, Gordon et al. [18th ACM Symposium on the Theory of Computing, 2008; J. ACM, 58 (2011), 24] showed that some interesting functions can be computed with fairness in the two-party setting and reopened the question of understanding which Boolean functions can be computed with fairness, and which cannot. Our main result in this work is a complete characterization of the (symmetric) Boolean functions that can be computed with fairness in the two-party setting; this settles an open problem of Gordon et al. The statement of the characterization is quite simple: A function can be computed with fairness if and only if the all-one vector or the all-zero vector are in the affine span of either the rows or the columns of the matrix describing the function. This is true for both deterministic and randomized functions. To prove the possibility result, we modify the protocol of Gordon et al.; the resulting protocol computes with full security (and in particular with fairness) all functions that are computable with fairness. Complementing this result, we also show that any function that does not satisfy the aforementioned condition can be reduced to a fair sampling protocol, which, by Agrawal and Prabhakaran [ Advances in Cryptology – CRYPTO 2013, 2013], cannot be computed with fairness.
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. Since then, 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, nite-domain) boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation. In this work we show that not only that some or few functions can be computed fairly, but rather an enormous number of functions can be computed fairly. In fact, almost all boolean functions with distinct domain sizes can be computed with complete fairness (for instance, more than 99:999 % of the boolean functions with domain sizes 31 30). The class of functions that is shown to be possible includes also rather involved and highly non-trivial tasks, such as set-membership, evaluation of a private (boolean) function, private matchmaking and set-disjointness.
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, 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.
Secure two-party computation is a classic problem in cryptography. It involves two parties computing a function of their private inputs, and only revealing what the output suggests. Additional security requirements may include fairness, which states that either all parties receive output, or no one does. A seminal result from the 1980's demonstrates that fairness cannot be guaranteed for all functions, and only recently have certain functions been shown to be computable with fairness. The two results naturally give rise to a distinction between fair functions and unfair ones. In this work, we investigate the characterization of such functions in the two-party setting. In the end, we obtain a full characterization for Boolean functions, and we develop a number of useful techniques for characterizing arbitrary fair functions.
A protocol for computing a functionality is secure if an adversary in this protocol cannot cause more harm than in an ideal computation where parties give their inputs to a trusted party which returns the output of the functionality to all parties. In particular, in the ideal model such computation is fair -- all parties get the output. Cleve (STOC 1986) proved that, in general, fairness is not possible without an honest majority. To overcome this impossibility, Gordon and Katz (Eurocrypt 2010) suggested a relaxed definition -- 1/p-secure computation -- which guarantees partial fairness. For two parties, they construct 1/p-secure protocols for functionalities for which the size of either their domain or their range is polynomial (in the security parameter). Gordon and Katz ask whether their results can be extended to multiparty protocols. We study 1/p-secure protocols in the multiparty setting for general functionalities. Our main result is constructions of 1/p-secure protocols when the number of parties is constant provided that less than 2/3 of the parties are corrupt. Our protocols require that either (1) the functionality is deterministic and the size of the domain is polynomial (in the security parameter), or (2) the functionality can be randomized and the size of the range is polynomial. If the size of the domain is constant and the functionality is deterministic, then our protocol is efficient even when the number of parties is O(log log n) (where n is the security parameter). On the negative side, we show that when the number of parties is super-constant, 1/p-secure protocols are not possible when the size of the domain is polynomial.
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.