Paper 2015/1071

Revisiting Secure Two-Party Computation with Rational Players

Arpita Maitra, Goutam Paul, and Asim K. Pal


A seminal result of Cleve (STOC 1986) showed that fairness, in general, is impossible to achieve in case of two-party computation if one of them is malicious. Later, Gordon et al. (STOC 2008, JACM 2011) observed that there exist two distinct classes of functions for which fairness can be achieved. One is any function without an embedded XOR, and the other one is a particular function containing an embedded XOR. In this paper, we revisit both classes of functions in two-party computation under rational players for the first time. We identify that the protocols proposed by Gordon et al. achieve fairness in non-rational setting only. In this direction, we design two protocols, one for the millionares' problem or the greater-than function (any function without embedded XOR can be converted to this function) and the other for the particular embedded XOR function of Gordon et al., and show that with rational players, our protocols achieve fairness, correctness and strict Nash equilibrium under suitable choice of parameters in complete information game setting. The dealer is offline in both of our protocols and this is in contrast with the work of Groce et al. (Eurocrypt 2012) which shows fairness and Bayesian Nash equilibrium in two party computation with rational players for arbitrary function in an incomplete information game setting.

Note: Abstract, Introduction and Related Works updated.

Available format(s)
Publication info
Preprint. MINOR revision.
Cryptographyembedded XORfairnessmillionaires' problemsecure computation
Contact author(s)
goutam k paul @ gmail com
2016-05-24: last of 4 revisions
2015-11-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Arpita Maitra and Goutam Paul and Asim K.  Pal},
      title = {Revisiting Secure Two-Party Computation with Rational Players},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1071},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.