International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 05 November 2015

Arpita Maitra, Goutam Paul, Asim K. Pal
ePrint Report ePrint Report
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) observed that there exist some functions for which fairness can be achieved even though one of the two parties is malicious. One of the functions considered by Gordon et al. is exactly the millionaires\' problem (Yao, FOCS 1982) or, equivalently, the `greater-than\' function. Interestingly, Gordon et al. (JACM, 2011) showed that any function over polynomial-size domains which does not contain an ``embedded XOR\" can be converted into the greater than function. In the same paper, they also demonstrated feasibility for certain functions that do contain an embedded XOR. In this paper, we revisit both the classes of two-party computation under rational players for the first time. We show that Gordon\'s protocols no longer remain fair when the players are rational. Further, we design two protocols, one without embedded XOR (the greater-than function) and the other with embedded XOR, and show that with rational players, our protocols achieve fairness under suitable choice of parameters.

Expand

Additional news items may be found on the IACR news page.