TY - GEN
T1 - Good Things Come to Those Who Wait
T2 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025
AU - Bonneau, Joseph
AU - Bünz, Benedikt
AU - Christ, Miranda
AU - Efron, Yuval
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2025.
PY - 2025
Y1 - 2025
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=105004788952&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=105004788952&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-91098-2_9
DO - 10.1007/978-3-031-91098-2_9
M3 - Conference contribution
AN - SCOPUS:105004788952
SN - 9783031910975
T3 - Lecture Notes in Computer Science
SP - 225
EP - 253
BT - Advances in Cryptology – EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
A2 - Fehr, Serge
A2 - Fouque, Pierre-Alain
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 4 May 2025 through 8 May 2025
ER -