Paper 2022/1655

Just How Fair is an Unreactive World?

Srinivasan Raghuraman, Visa Research
Yibin Yang, Georgia Institute of Technology
Abstract

Fitzi, Garay, Maurer, and Ostrovsky (J. Cryptology 2005) showed that in the presence of a dishonest majority, no primitive of cardinality $n - 1$ is complete for realizing an arbitrary $n$-party functionality with guaranteed output delivery. In this work, we show that in the presence of $n - 1$ corrupt parties, no unreactive primitive of cardinality $n - 1$ is complete for realizing an arbitrary $n$-party functionality with fairness. We show more generally that for $t > \frac{n}{2}$, in the presence of $t$ malicious parties, no unreactive primitive of cardinality $t$ is complete for realizing an arbitrary $n$-party functionality with fairness. We complement this result by noting that $(t+1)$-wise fair exchange is complete for realizing an arbitrary $n$-party functionality with fairness. In order to prove our results, we utilize the primitive of fair coin tossing and introduce the notion of predictability in coin tossing protocols, which we believe is of independent interest.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
secure computation unreactive functionalities fair coin tossing
Contact author(s)
srraghur @ visa com
yyang811 @ gatech edu
History
2022-11-28: approved
2022-11-28: received
See all versions
Short URL
https://ia.cr/2022/1655
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2022/1655,
      author = {Srinivasan Raghuraman and Yibin Yang},
      title = {Just How Fair is an Unreactive World?},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1655},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1655}},
      url = {https://eprint.iacr.org/2022/1655}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.