Paper 2024/1711
Good things come to those who wait: Dishonest-Majority Coin-Flipping Requires Delay Functions
Abstract
We reconsider Cleve's famous 1986 impossibility result on coin-flipping without an honest majority. Recently proposed constructions have circumvented this limit by using cryptographic delay functions. We show that this is necessary: a (weak) notion of delay functions is in fact implied by the existence of a protocol circumventing Cleve's impossibility. However, such delay functions are weaker than those used in existing constructions. We complete our result by showing an equivalence, that these weaker delay functions are also sufficient to construct not just fair dishonest-majority coin-flipping protocols, but also the stronger notion of a distributed randomness beacon. We also show that this is possible in a weaker communication model than previously considered, without the assumption of reliable broadcast or a public bulletin board.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Randomness BeaconDelay Function
- Contact author(s)
-
jbonneau @ gmail com
bb @ nyu edu
mchrist @ cs columbia edu
ye2210 @ columbia edu - History
- 2024-10-21: approved
- 2024-10-19: received
- See all versions
- Short URL
- https://ia.cr/2024/1711
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1711,
author = {Joseph Bonneau and Benedikt Bünz and Miranda Christ and Yuval Efron},
title = {Good things come to those who wait: Dishonest-Majority Coin-Flipping Requires Delay Functions},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1711},
year = {2024},
url = {https://eprint.iacr.org/2024/1711}
}
