Paper 2008/206

Partial Fairness in Secure Two-Party Computation

Dov Gordon and Jonathan Katz


A seminal result of Cleve (STOC '86) is that, in general, complete fairness is impossible to achieve in two-party computation. In light of this, various techniques for obtaining partial fairness have been suggested in the literature. We propose a definition of partial fairness within the standard real-/ideal-world paradigm that addresses deficiencies of prior definitions. We also show broad feasibility results with respect to our definition: partial fairness is possible for any (randomized) functionality $f:X \times Y \rightarrow Z^1 \times Z^2$ at least one of whose domains or ranges is polynomial in size. Our protocols are always private, and when one of the domains has polynomial size our protocols also simultaneously achieve the usual notion of security with abort. In contrast to some prior work, we rely on standard assumptions only. We also show that, as far as general feasibility is concerned, our results are optimal. Specifically, there exist functions with super-polynomial domains and ranges for which it is impossible to achieve our definition.

Note: Added Section 4.1

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Eurocrypt 2010
Secure computationfairness
Contact author(s)
jkatz @ cs umd edu
2010-08-05: last of 4 revisions
2008-05-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dov Gordon and Jonathan Katz},
      title = {Partial Fairness in Secure Two-Party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2008/206},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.