Fair distributed computation of reactive functions

Juan Garay, Björn Tackmann*, Vassilis Zikas

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A fair distributed protocol ensures that dishonest parties have no advantage over honest parties in learning their protocol’s output. What makes fairness a particularly intriguing research topic is Cleve’s seminal result [STOC’86], which proved that fairness is impossible to achieve in the presence of dishonest majorities and ignited a quest for more relaxed, yet meaningful definitions of fairness. A common pattern in existing works, however, is that they only treat the case of nonreactive computation—i.e., distributed computation of “one-shot” (stateless) functions, in which parties give all inputs strictly before any output is computed. Yet, many natural cryptographic tasks are of a reactive (stateful) nature. 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 et al. [PODC’15], which, informally, measures the protocol’s fairness by means of the utility of an adversary who aims to break it As in the [PODC’15] work, our approach enjoys the advantage of offering a comparative notion, inducing a partial order on protocols with respect to fairness. We investigate protocols that restrict the adversary’s utility and provide, for each choice of parameters specifying this utility, a protocol for fair and reactive two-party computation, which is optimal for a (natural) range of parameters. Our study shows that achieving fairness in the reactive setting is more complex than in the much-studied case of one-shot functions, as increasing the number of rounds used for reconstructing the output can lead to improved fairness, and the minimal required number of rounds depends on the exact values of the adversary’s utility.

Original languageEnglish
Title of host publicationDistributed Computing
Subtitle of host publication29th International Symposium, DISC 2015, Proceedings
EditorsYoram Moses
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages497-512
Number of pages16
ISBN (Electronic)978-3-662-48653-5
ISBN (Print)978-3-662-48652-8
DOIs
Publication statusPublished - 5 Nov 2015
Event29th International Symposium on Distributed Computing - Tokyo, Japan
Duration: 7 Oct 20159 Oct 2015
http://www.disc-conference.org/wp/disc2015/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer, Berlin, Heidelberg
Volume9363
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference29th International Symposium on Distributed Computing
Abbreviated titleDISC 2015
CountryJapan
CityTokyo
Period7/10/159/10/15
Internet address

Keywords

  • Cryptographic protocols
  • Fairness
  • Game theory
  • Secure multi-party computation

Fingerprint

Dive into the research topics of 'Fair distributed computation of reactive functions'. Together they form a unique fingerprint.

Cite this