Paper 2015/807

Fair Distributed Computation of Reactive Functions

Juan Garay, Björn Tackmann, and Vassilis Zikas

Abstract

A fair distributed protocol ensures that dishonest parties have no advantage over honest parties in learning their protocol’s output. This is a desirable property, as honest parties are more reluctant to participate in an (unfair) protocol in which cheaters learn their outputs while the honest parties waste their time and computation resources. But what makes fairness an even more intriguing topic is Cleve’s seminal result [STOC’86], which proves that it is impossible to achieve in the presence of dishonest majorities. 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. DISC 2015
Keywords
Cryptographic protocolssecure multi-party computationfairnessgame theory
Contact author(s)
btackmann @ eng ucsd edu
History
2015-08-13: received
Short URL
https://ia.cr/2015/807
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/807,
      author = {Juan Garay and Björn Tackmann and Vassilis Zikas},
      title = {Fair Distributed Computation of Reactive Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/807},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/807}},
      url = {https://eprint.iacr.org/2015/807}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.