Simultaneous broadcast revisited
Simultaneous broadcast revisited
复制标题
DOI：
10.1145/1073814.1073878
复制
发表时间：
2005-07
期刊：
影响因子：
--
通讯作者：
A. Hevia;Daniele Micciancio
中科院分区：
文献类型：
--
作者：
A. Hevia;Daniele Micciancio
同时广播协议允许不同方并行广播值，同时保证广播值的相互独立性。在这项工作中，我们研究了Chor，Goldwasser，Micali和Awerbuch(FOCS 1985)，Chor和Rabin(PODC 1987)和Gennaro(IEEE译文)提出的关于独立性的各种定义。关于并行和分布式系统，2000)，并证明了它们之间的蕴涵和分离。总之，我们证明了每个定义(被推广以允许任意输入分布)都由一类“可实现”的输入分布来刻画，使得对于类中的所有分布都存在一个同时满足定义的协议，而对于类外的任何分布，没有协议可能达到该定义。在比较可实现的分布集合时，Gennaro的定义是最严格的(其次是Chor和Rabin One，而Chor、Goldwasser、Micali和Awerbuch是最宽松的)，因为它对于最小的分布类别是可以实现的。这表明Gennaro、Chor和Rabin的定义的适用性是有限的。然后，我们比较了限制在可实现分布时的定义。这一次，我们的比较结果以相反的顺序对定义进行了排名，其中Chor、Goldwasser、Micali和Awerbuch的定义是最强的(其次是Chor和Rabin，然后是Gennaro)，因为根据较强的定义的安全意味着根据较弱的定义的安全。我们还给出了例子，证明了这些蕴含是严格的，即存在输入分布，使得协议可以满足较弱的定义，但不能满足较强的定义。Gennaro和Chor和Rabin的定义之间的分离特别强，因为我们证明了在任何可实现的输入分布下根据Gennaro同时安全的单一协议，但不满足Chor和Rabin对于任何非平凡分布的定义。特别地，这种分离适用于作者在其论文中最初考虑的均匀输入分布的特殊情况。
Simultaneous Broadcast protocols allow different parties to broadcast values in parallel while guaranteeing mutual independence of the broadcast values. In this work, we study various definitions of independence proposed in the literature by Chor, Goldwasser, Micali and Awerbuch (FOCS 1985), Chor and Rabin (PODC 1987) and Gennaro (IEEE Trans. on Parallel and Distributed Systems, 2000), and prove implications and separations among them.In summary, we show that each definition (generalized to allow arbitrary input distributions) is characterized by a class of "achievable" input distributions such that there is a single protocol that simultaneously meets the definition for all distributions in the class, while for any distribution outside the class no protocol can possibly achieve the definition. When comparing sets of achievable distributions, the definition of Gennaro is the most stringent (followed by the Chor and Rabin one, and Chor, Goldwasser, Micali and Awerbuch as the most relaxed) in the sense that it is achievable for the smallest class of distributions. This demonstrates that the definitions of Gennaro, and Chor and Rabin are of limited applicability.Then, we compare the definitions when restricted to achievable distributions. This time the results of our comparison rank the definitions in the opposite order, with the definition of Chor, Goldwasser, Micali and Awerbuch as the strongest one (followed by Chor and Rabin, and then Gennaro) in the sense that security according to the stronger definitions implies security according to the weaker ones. We also give examples showing that the implications are strict, i.e., there are input distributions such that a protocol can meet the weaker definition, but fail to satisfy the stronger. The separation between the definitions of Gennaro and Chor and Rabin is particularly strong, as we show that there is a single protocol that is simultaneously secure according to Gennaro under any achievable input distribution, but does not satisfy the definition of Chor and Rabin for any non-trivial distribution. In particular, the separation holds for the special case of the uniform input distribution originally considered by the authors in their papers.