[Resource Topic] 2011/396: Fair Computation with Rational Players

Welcome to the resource topic for 2011/396

Fair Computation with Rational Players

Authors: Amos Beimel, Adam Groce, Jonathan Katz, Ilan Orlov


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.

ePrint: https://eprint.iacr.org/2011/396

Talk: https://www.youtube.com/watch?v=aaVCCrXq9h8

Slides: https://iacr.org/cryptodb/archive/2012/EUROCRYPT/presentation/24266.ppt

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .