ECCC-Report TR20-071https://eccc.weizmann.ac.il/report/2020/071Comments and Revisions published for TR20-071en-usWed, 02 Sep 2020 22:11:49 +0300
Revision 1
| A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip |
Iftach Haitner,
Yonatan Karidi-Heller
https://eccc.weizmann.ac.il/report/2020/071#revision1In 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 for many-turn protocols was left completely 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})$ (adaptive) corruptions.Wed, 02 Sep 2020 22:11:49 +0300https://eccc.weizmann.ac.il/report/2020/071#revision1
Paper TR20-071
| A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip |
Iftach Haitner,
Yonatan Karidi-Heller
https://eccc.weizmann.ac.il/report/2020/071In 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 during the protocol execution. Ben-Or and Linial proved that the $n$-party majority protocol is resilient to $o(\sqrt{n})$ corruptions (ignoring log 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, Kalai, and Park [ICALP '15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai, Komargodski, and Raz [DISC '18]. Yet, the question for many-turn (even single-bit) protocols was left completely open.
In this work we close the above gap, proving that no $n$-party protocol (of any round complexity) is resilient to $O(\sqrt{n})$ (adaptive) corruptions.Mon, 04 May 2020 17:14:22 +0300https://eccc.weizmann.ac.il/report/2020/071