Design & Analysis of Optimal Coin-tossing: New Techniques
Design & Analysis of Optimal Coin-tossing: New Techniques
复制标题
设计
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Mingyuan Wang
中科院分区：
文献类型：
--
作者：
H. A. Khorasgani;H. K. Maji;Mingyuan Wang
集体抛硬币允许n个具有私有随机性源的处理器就一个公共硬币达成一致。在不失一般性的情况下，可以假设输出在集合{ 0，1 }中，并且掷硬币协议的期望输出是X。掷硬币协议的目标是对对抗性干预具有鲁棒性。在本文中，我们研究拜占庭的对手谁可以任意设置损坏的处理器的消息。从历史上看，对抛硬币协议的研究，即使在其设置中引入最温和的变化，也往往会产生令人惊讶和令人兴奋的结果。我们知道几个最优或渐近最优的协议，如部落，接力棒传递和阈值协议。顺便说一句，掷硬币有几种变体，其中多数协议（或更一般地说，阈值协议）被证明是渐近最优的。在这项工作中，我们考虑在两个安全模型中的抛硬币协议，并研究在这些设置对抗性攻击的最佳抛硬币协议的敏感性。在第一个模型中，有n个处理器，处理器i均匀且独立地广播她的随机消息xi ∈ { 0，1 }。处理器将函数fn：{ 0，1 } n → { 0，1 }应用于广播消息，并就它们的公共输出fn（x 1，. . .，xn）。在所有处理器广播消息后，攻击者最多可以破坏t个处理器并任意改变它们的消息。最优协议最小化了这个对手引起的预期输出的变化。我们把这个问题归结为布尔超立方体上的等周不等式，并证明了阈值协议是最优协议。在第二个模型中，在时间i，处理器i广播她的消息xi，并且她的消息分发可能取决于先前广播的消息。我们考虑一个对手谁可以控制一个处理器，并改变她的消息任意。在这种情况下，我们证明了阈值协议是渐近最优的。
Collective coin-tossing allows n processors with private randomness sources to agree on a common public coin. Without loss of generality, one can assume that the output is in the set { 0 , 1 } , and the expected output of a coin-tossing protocol is X . The objective of a coin-tossing protocol is to be robust to adversarial interventions. In this paper, we study Byzantine adversaries who can arbitrarily set the messages of the corrupted processors. Historically, the study of coin-tossing protocols, with the introduction of even the mildest of variations in its setting, tends to yield surprising and exciting outcomes. We know several optimal or asymptotically optimal protocols like tribes, baton passing, and threshold protocols. Incidentally, there are several variants of coin-tossing where the majority protocol (or, more generally, the threshold protocols) turn out to be asymptotically optimal. In this work, we consider coin-tossing protocols in two security models and study the susceptibility of the optimal coin-tossing protocols in those settings to adversarial attacks. In the first model, there are n processors and processor i broadcasts her uniformly and independently random message x i ∈ { 0 , 1 } . The processors apply a function f n : { 0 , 1 } n → { 0 , 1 } to the broadcast messages and agree on their common output f n ( x 1 , . . . , x n ). After all the processors broadcast their messages, the adversary may corrupt at most t processors and change their messages arbitrarily. The optimal protocol minimizes the change in the expected output that this adversary causes. We reduce this problem to an isoperimetric inequality over the boolean hypercube and demonstrate that the threshold protocols are the optimal protocols. In the second model, at time i , processor i broadcasts her message x i , and her message distribution possibly depends on the previously broadcast messages. We consider an adversary who can take control of one processor and change her message arbitrarily. In this case, we prove that the threshold protocols are asymptotically optimal.
影响因子：
4.9
作者：
Chattopadhyay, Eshan;Zuckerman, David
通讯作者：
Zuckerman, David