Cryptology ePrint Archive: Report 2015/1071
Revisiting Secure Two-Party Computation with Rational Players
Arpita Maitra, Goutam Paul and Asim K. Pal
Abstract: 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.
Category / Keywords: Cryptography, embedded XOR, fairness, millionaires' problem, secure computation
Date: received 4 Nov 2015, last revised 24 May 2016
Contact author: goutam k paul at gmail com
Available format(s): PDF | BibTeX Citation
Note: Abstract, Introduction and Related Works updated.
Version: 20160524:193203 (All versions of this report)
Short URL: ia.cr/2015/1071
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]