Cryptology ePrint Archive: Report 2008/206

Partial Fairness in Secure Two-Party Computation

Dov Gordon and Jonathan Katz

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.

Category / Keywords: cryptographic protocols / Secure computation, fairness

Date: received 9 May 2008, last revised 15 May 2008

Contact author: jkatz at cs umd edu

Available formats: PDF | BibTeX Citation

Note: Added Section 4.1

Version: 20080515:194106 (All versions of this report)

Discussion forum: Show discussion | Start new discussion