A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917817703464960 |
|---|---|
| author | Haitner, Iftach Karidi-Heller, Yonatan |
| author_facet | Haitner, Iftach Karidi-Heller, Yonatan |
| contents | 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 (ignoring poly-logarithmic factors), and conjectured this is a tight upper bound for any $n$-party protocol (of any round complexity). Their conjecture was proved to be correct for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein, Linial and Saks [Combinatorica '89], symmetric protocols Goldwasser, Tauman Kalai and Park [ICALP '15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai, Komargodski and Raz [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 $ω(\sqrt{n})$ (adaptive) corruptions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2005_01565 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip Haitner, Iftach Karidi-Heller, Yonatan Cryptography and Security F.0; G.3 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 (ignoring poly-logarithmic factors), and conjectured this is a tight upper bound for any $n$-party protocol (of any round complexity). Their conjecture was proved to be correct for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein, Linial and Saks [Combinatorica '89], symmetric protocols Goldwasser, Tauman Kalai and Park [ICALP '15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai, Komargodski and Raz [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 $ω(\sqrt{n})$ (adaptive) corruptions. |
| title | A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip |
| topic | Cryptography and Security F.0; G.3 |
| url | https://arxiv.org/abs/2005.01565 |