Simultaneous broadcast revisited

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.

REFERENCES

• 1: Michael Ben-Or , Ran El-Yaniv, Resilient-optimal interactive consistency in constant time, Distributed Computing, v.16 n.4, p.249-262, December 2003 [doi>10.1007/s00446-002-0083-3]
• 2: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 3: Christian Cachin , Klaus Kursawe , Frank Petzold , Victor Shoup, Secure and Efficient Asynchronous Broadcast Protocols, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.524-541, August 19-23, 2001
• 4: R. Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143--202, 2000.
• 5: Ran Canetti , Tal Rabin, Fast asynchronous Byzantine agreement with optimal resilience, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.42-51, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167105]
• 6: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 7: B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Veriable secret sharing and achieving simultaneity in the presence of faults. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pages 383--395. IEEE Computer Society Press, 1985.
• 8: Benny Chor , Michael O. Rabin, Achieving independence in logarithmic number of rounds, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.260-268, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41862]
• 9: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 10: P. Feldman and S. Micali. Byzantine agreement in constant expected time (and trusting no one). In Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pages 267--276. IEEE Computer Society Press, 1985.
• 11: Rosario Gennaro, Achieving independence efficiently and securely, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.130-136, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224979]
• 12: Rosario Gennaro, A Protocol to Achieve Independence in Constant Rounds, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.636-647, July 2000 [doi>10.1109/71.877748]
• 13: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 14: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 15: A. Hevia and D. Micciancio. Simultaneous broadcast revisited. Full version of this work, 2005. Available from http://www.cse.ucsd.edu/~ahevia/publications/hm-podc05.html.
• 16: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 17: Moses Liskov , Anna Lysyanskaya , Silvio Micali , Leonid Reyzin , Adam Smith, Mutually Independent Commitments, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.385-401, December 09-13, 2001
• 18: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 19: A. C.-C. Yao. How to generate and exchange secrets. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pages 162--167. IEEE Computer Society Press, 1986.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Reliability, Security

Keywords:
independence, parallel broadcast, secure function evaluation