Simultaneous broadcast revisited
Alejandro Hevia, Daniele Micciancio · 2005
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