**Authors:** Alejandro Hevia, Daniele Micciancio.

Proceedings of the 24th Symposium on Principles of Distributed Computing - PODC 2005. Las Vegas, NV. July 2005. ACM, pp. 324 - 333.

[DOI:10.1145/1073814.1073878]**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.