A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip
Journal of the ACM · 30.06.2026 · 73 (3) · 1-32
DOI: 10.1145/3814954 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 16.06.2026. Verfasst von Iftach Haitner und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 26 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: ERC, Israel Science Foundation.
Abstract (Originalsprache)
In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems ’83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS ’85], the parties communicate over a broadcast channel, and a computationally unbounded adversary can choose which parties to corrupt along the protocol execution. Ben-Or and Linial proved that the n -party majority protocol is resilient to \(O(\sqrt {n})\) corruptions, and conjectured this is a tight upper bound for any n -party protocol (of any round complexity). Their conjecture was proved to be correct, up to polylogarithmic factors, for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein et al. [Combinatorica ’89], symmetric protocols Goldwasser et al. [ICALP ’15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai et al. [DISC ’18]. Yet, the question of many-turn protocols was left entirely open. In this work, we close the above gap, proving that no n -party protocol (of any round complexity) is resilient to \(\Omega (\sqrt {n} \cdot \log ^3 n)\) adaptive corruptions. Namely, majority is the optimal coin-flipping protocol against adaptive adversaries (up to polylogarithmic factors).
Förderung
- ERC
- Israel Science Foundation
Zitieren
APA
Haitner, I., & Karidi-Heller, Y. (2026). A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip. Journal of the ACM, 73(3), 1-32. https://doi.org/10.1145/3814954
Vancouver
Haitner I, Karidi-Heller Y. A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip. Journal of the ACM. 2026;73(3):1-32. doi:10.1145/3814954
BibTeX
@article{Haitner2026,
author = {Haitner, Iftach and Karidi-Heller, Yonatan},
title = {A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip},
journal = {Journal of the ACM},
year = {2026},
volume = {73},
number = {3},
pages = {1--32},
doi = {10.1145/3814954}
}
EUVIMED