Good Things Come to Those Who Wait - Dishonest-Majority Coin-Flipping Requires Delay Functions
Lists
Only you see this
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.
BibTeX
@inproceedings{bonneau2025good,
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}},
booktitle = {EUROCRYPT},
year = {2025},
doi = {10.1007/978-3-031-91098-2\_9},
}| Cornucopia: Distributed randomness beacons at scale | IACR ePrint · 2023 |
| An Optimally Fair Coin Toss | J. Cryptol · 2016 |
| Adaptively Secure Coin-Flipping, Revisited | arXiv · 2015 |
| Rubato: Provably Post-Quantum Secure and Batched Asynchronous Randomness Beacon | IACR ePrint · 2025 |
| Fair Coin Flipping: Tighter Analysis and the Many-Party Case | J. Cryptol · 2026 |
| How Much Public Randomness Do Modern Consensus Protocols Need? | IACR ePrint · 2024 |