Paper 2011/396

Fair Computation with Rational Players

Amos Beimel, Adam Groce, Jonathan Katz, and Ilan Orlov

Abstract

We consider the problem of fair multiparty computation, where fairness means (informally) that all parties should learn the correct output. A seminal result of Cleve (STOC 1986) shows that fairness is, in general, impossible to achieve if a majority of the parties is malicious. Here, we treat all parties as rational and seek to understand what can be done. Asharov et al. (Eurocrypt 2011) showed impossibility of rational fair computation in the two-party setting, for a particular function and a particular choice of utilities. We observe, however, that in their setting the parties have no strict incentive to compute the function even in an ideal world where fairness is guaranteed. Revisiting the problem, we show that rational fair computation is possible, for arbitrary functions, as long as the parties have a strict incentive to compute the function in an ideal world where fairness is guaranteed. Our results extend to more general utility functions that do not directly correspond to fairness, as well as to the multi-party setting. Our work thus shows a new setting in which game-theoretic considerations can be used to circumvent a cryptographic impossibility result.

Note: This is the full version, and contains additional results not present in the conference version.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. Eurocrypt 2012
Keywords
game theorysecure computation
Contact author(s)
jkatz @ cs umd edu
History
2015-04-14: revised
2011-07-28: received
See all versions
Short URL
https://ia.cr/2011/396
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/396,
      author = {Amos Beimel and Adam Groce and Jonathan Katz and Ilan Orlov},
      title = {Fair Computation with Rational Players},
      howpublished = {Cryptology ePrint Archive, Paper 2011/396},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/396}},
      url = {https://eprint.iacr.org/2011/396}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.