论文标题
紧密的下限在适应性安全的全信息硬币翻转上
A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip
论文作者
论文摘要
在分布式硬币的协议中，BLUM [计算机系统'83上的ACM事务]，双方试图输出一个常见（接近）均匀位的位，即使某些对抗方面选择的当事方试图偏向公共输出。在适应性安全的全信息硬币翻转，ben-or和linial [focs '85]中，各方通过广播渠道进行通信，而计算无限的对手可以选择哪些当事方沿协议执行损坏。 Ben-or和Linial证明了$ n $ - 政党多数协议对$ o（\ sqrt {n}）$ rorportions（忽略poly-logarithmic因素）具有弹性，并猜想这是任何$ n $ - 选项协议（任何回合复杂性）的紧密上限。 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]。然而，多头协议的问题完全开放。 在这项工作中，我们缩小了上述差距，证明没有$ n $ - 零件协议（任何圆形复杂性的）均具有弹性到$ω（\ sqrt {n}）$（自适应）损坏。
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.
