Paper 2022/1655
Just How Fair is an Unreactive World?
, Visa Research, Georgia Institute of TechnologyAbstract
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
-
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}
}
