Authors: A.H., and Daniele Micciancio
Abstract: 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.
Ref: In Proceedings of the 24th Symposium on Principles of Distributed Computing (PODC 2005) July 17-20, 2005, Las Vegas, Nevada, USA, ACM Press.
Full paper: Available as Compressed Postscript, Postscript, and PDF.