We consider the problem of fair two-party computation, where fairness (informally) means that both parties should learn the correct output. A seminal result of Cleve (STOC 1986) shows that fairness is, in general, impossible to achieve for malicious parties. Here, we treat the parties as rational and seek to understand what can be done. Asharov et al. (Eurocrypt 2011) recently considered this problem and showed impossibility of rational fair computation for a particular function and a particular set of utilities. We observe, however, that in their setting the parties have no 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 and utilities) as long as the parties have a strict incentive to compute the function in the ideal world. This gives a new example where game theory can be used to circumvent impossibility results in cryptography.
We consider the problem of fair two-party computation, where fairness (informally) means that both parties should learn the correct output. A seminal result of Cleve (STOC 1986) shows that fairness is, in general, impossible to achieve for malicious parties. Here, we treat the parties as rational and seek to understand what can be done. Asharov et al. (Eurocrypt 2011) recently considered this problem and showed impossibility of rational fair computation for a particular function and a particular set of utilities. We observe, however, that in their setting the parties have no 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 and utilities) as long as the parties have a strict incentive to compute the function in the ideal world. This gives a new example where game theory can be used to circumvent impossibility results in cryptography.
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.
Secure computation is a fundamental problem in modern cryptography in which multiple parties join to compute a function of their private inputs without revealing anything beyond the output of the function. A series of very strong results in the 1980’s demonstrated that any polynomial-time function can be computed while guaranteeing essentially every desired security property. The only exception is the fairness property, which states that no player should receive their output from the computation unless all players receive their output. While it was shown that fairness can be achieved whenever a majority of players are honest, it was also shown that fairness is impossible to achieve in general when half or more of the players are dishonest. Indeed, it was proven that even boolean XOR cannot be computed fairly by two parties.
The fairness property is both natural and important, and as such it was one of the first questions addressed in modern cryptography (in the context of signature exchange). One contribution of this thesis is to survey the many approaches that have been used to guarantee different notions of partial fairness. We then revisit the topic of fairness within a modern security framework for secure computation. We demonstrate that, despite the strong impossibility result mentioned above, certain interesting functions can be computed fairly, even when half (or more) of the parties are malicious. We also provide a new notion of partial fairness, demonstrate feasibility of achieving this notion for a large class of functions, and show impossibility for certain functions outside this class. We consider fairness in the presence of rational adversaries, and, finally, we study the difficulty of achieving fairness by exploring how much external help is necessary for providing fair secure computation.
In his seminal result, Cleve [STOC’86] established that secure distributed computation— guaranteeing fairness—is impossible in the presence of dishonest majorities. A generous number of proposals for relaxed notions of fairness ensued this seminal result, by weakening in various ways the desired security guarantees. While these works also suggest completeness results (i.e., the ability to design protocols which achieve their fairness notion), their assessment is typically of an all-or-nothing nature. That is, when presented with a protocol which is not designed to be fair according to their respective notion, they most likely would render it unfair and make no further statement about it. In this work we put forth a comparative approach to fairness. We present new intuitive notions that when presented with two arbitrary protocols, provide the means to answer the question “Which of the protocols is fairer? ” The basic idea is that we can use an appropriate utility function to express the preferences of an adversary who wants to break fairness. Thus, we can compare protocols with respect to how fair they are, placing them in a partial order according to this relative-fairness relation. After formulating such utility-based fairness notions, we turn to the question of finding optimal protocols—i.e., maximal elements in the above partial order. We investigate—and answer—this question for secure function evaluation, both in the two-party and multi-party settings. To our knowledge, the only other fairness notion providing some sort of comparative state-ment is that of 1/p-security (aka “partial fairness”) by Gordon and Katz [Eurocrypt’10]. We also show in this paper that for a special class of utilities our notion strictly implies 1/p-security. In addition, we fix a shortcoming of the definition which is exposed by our comparison, thus strengthening that result. Key words: Cryptographic protocols, secure multi-party computation, fairness, rational protocol design. 1
In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness, which guarantees that if either party receives its output, then the other party does too. Cleve (STOC 1986) showed that complete fairness cannot be achieved in general in the two-party setting; specifically, he showed (essentially) that it is impossible to compute Boolean XOR with complete fairness. Since his work, the accepted folklore has been that nothing non-trivial can be computed with complete fairness, and the question of complete fairness in secure two-party computation has been treated as closed since the late '80s.
The field of rational cryptography considers the design of cryptographic protocols in the presence of rational agents seeking to maximize local utility functions. This departs from the standard secure multiparty computation setting, where players are assumed to be either honest or malicious. We detail the construction of both a two-party and a multiparty game theoretic framework for constructing rational cryptographic protocols. Our framework specifies the utility function assumptions necessary to realize the privacy, correctness, and fairness guarantees for protocols. We demonstrate that our framework correctly models cryptographic protocols, such as rational secret sharing, where existing work considers equilibrium concepts that yield unreasonable equilibria. Similarly, we demonstrate that cryptography may be applied to the game theoretic domain, constructing an auction market not realizable in the original formulation. Additionally, we demonstrate that modeling players as rational agents allows us to design a protocol that destabilizes coalitions. Thus, we establish a mutual benefit from combining the two fields, while demonstrating the applicability of our framework to real-world market environments. We also give an application of game theory to adversarial interactions where cryptography is not necessary. Specifically, we consider adversarial machine learning, where the adversary is rational and reacts to the presence of a data miner. We give a general extension to classification algorithms that returns greater expected utility for the data miner than existing classification methods.
Complete fairness means that either all parties learn the output of the function or none of them does. It was deemed as an impossible task in general in secure two party computation by Cleve (STOC 1986). However, a seminal result of complete fairness between two parties was achieved by Gordorn et al. (STOC 2008). Recently Groce and Katz (Euro crypt 2012) corrected the insufficient assumptions and gave some positive results of fairness. Here we revisit this problem and introduce the Tit-for-Tat (TFT) strategy into rational two-party computation. To the best of our knowledge, it is the first secure two-party computation protocol with constant rounds that allows both parties to know the terminal round.