International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Partial Fairness in Secure Two-Party Computation

Dov Gordon
Jonathan Katz
Search ePrint
Search Google
Abstract: Complete fairness is impossible to achieve, in general, in secure two-party computation. In light of this, various techniques for obtaining \emph{partial} fairness in this setting have been suggested. We explore the possibility of achieving partial fairness with respect to a strong, simulation-based definition of security within the standard real/ideal world paradigm. We show feasibility with respect to this definition for randomized functionalities where each player may possibly receive a different output, as long as at least one of the domains or ranges of the functionality are polynomial in size. When one of the domains is polynomial size, our protocol is also secure-with-abort. In contrast to much of the earlier work on partial fairness, we rely on standard assumptions only (namely, enhanced trapdoor permutations). We also provide evidence that our results are, in general, optimal. Specifically, we show a boolean function defined on a domain of super-polynomial size for which it is impossible to achieve both partial fairness and security with abort, and provide evidence that partial fairness is impossible altogether for functions whose domains and ranges all have super-polynomial size.
  title={Partial Fairness in Secure Two-Party Computation},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / Secure computation, fairness},
  note={ 14014 received 9 May 2008, last revised 15 May 2008},
  author={Dov Gordon and Jonathan Katz},