Cleve’s result ignited a quest for more relaxed, yet meaningful definitions of fairness, with numerous works suggesting such relaxations and protocols satisfying them. A common pattern in these works, however, is that they only treat the case of non-reactive computation--i.e., distributed computation of “one-shot” (stateless) functions, in which parties give inputs strictly before any output is computed. Yet, many natural cryptographic tasks are of a reactive (stateful) nature, where parties provide inputs and receive outputs several times during the course of the computation. This is the case, for example, when computing multi-stage auctions or emulating a virtual stock-exchange market, or even when computing basic cryptographic tasks such as commitments and secret sharing.
In this work we introduce the first notion of fairness tailored to reactive distributed computation, which can be realized in the presence of dishonest majorities. Our definition builds on the recently suggested utility-based fairness notion (for non-reactive functions) by Garay, Katz, Tackmann and Zikas [PODC’15], which, informally, defines the utility of an adversary who wants to break fairness and uses it as a measure of a protocol’s success in satisfying the property. Similarly to the non-reactive notion, our definition enjoys the advantage of offering a comparative notion of fairness for reactive functions, inducing a partial order on protocols with respect to fairness.
We then turn to the question of finding protocols that restrict the adversary’s utility. We provide, for each parameter choice of the adversary’s utility, a protocol for fair and reactive two-party computation, and prove the optimality of this protocol for one (natural) class of parameter values and (non-tight) lower bounds for all remaining values. Our study shows that achieving fairness in the reactive setting is more complex than in the much-studied case of one-shot functions. For example, in contrast to the non-reactive case, (a) increasing the number of rounds used for reconstructing the output can lead to improved fairness, and (b) the minimal number or rounds required in the reconstruction depends on the exact values of the adversary’s utility.Category / Keywords: cryptographic protocols / Cryptographic protocols, secure multi-party computation, fairness, game theory Original Publication (with major differences): DISC 2015 Date: received 12 Aug 2015 Contact author: btackmann at eng ucsd edu Available format(s): PDF | BibTeX Citation Version: 20150813:025003 (All versions of this report) Short URL: ia.cr/2015/807 Discussion forum: Show discussion | Start new discussion