Sequential composition of protocols without simultaneous termination

ABSTRACT

The question of the composition of protocols is an important and heavily researched one. In this paper we consider the problem of sequential composition of synchronous protocols that do not have simultaneous termination; i.e., the parties do not necessarily conclude a protocol execution in the same round. A problem arises becauses such protocols must begin in synchrony; therefore a second execution cannot follow from the first in a straightforward manner. An important example of a protocol with this property is that of randomized Byzantine Agreement with an expected constant number of rounds (such as the one due to Feldman and Micali). We note that expected constant-round Byzantine Agreement cannot have simultaneous termination and thus this (problematic) property is inherent.Given that the termination of the parties is not simultaneous, a natural question to consider is how to synchronize the parties so that such protocols can be sequentially composed. Furthermore, such a composition should preserve the original running-time of the protocol, i.e. running the protocol ℓ times sequentially should take in the order of ℓ times the running-time of the protocol. In this paper, we present a method for sequentially composing any protocol in which the players do not terminate in the same round, while preserving the original round complexity. An important application of this result is the sequential composition of parallel Byzantine Agreement. Such a composition can be used by parties connected in a point-to-point network to run protocols designed for the broadcast model, while maintaining the original round complexity.

REFERENCES

• 1: M. Ben-Or and R. El-Yaniv. Interactive Consistency in Constant Time. Submitted for publication, 1991.
• 2: Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
• 3: R. Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143-202, 2000.
• 4: R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.136, October 14-17, 2001
• 5: Christian Cachin , Klaus Kursawe , Victor Shoup, Random oracles in constantipole: practical asynchronous Byzantine agreement using cryptography (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.123-132, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343531]
• 6: 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]
• 7: C Dwork , Y Moses, Knowledge and common knowledge in a Byzantine environment I: crash failures, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.149-169, March 1986, Monterey, California, United States
• 8: Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.409-418, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276853]
• 9: M. Fischer and N. Lynch. A Lower Bound for the Time to Assure Interactive Consistency. Information Processing Letters, 14(4):183-186, 1982.
• 10: Pesech Feldman , Silvio Micali, An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement, SIAM Journal on Computing, v.26 n.4, p.873-933, Aug. 1997 [doi>10.1137/S0097539790187084]
• 11: Oded Goldreich , Hugo Krawczyk, On the Composition of Zero-Knowledge Proof Systems, SIAM Journal on Computing, v.25 n.1, p.169-192, Feb. 1996 [doi>10.1137/S0097539791220688]
• 12: Yehuda Lindell , Anna Lysyanskaya , Tal Rabin, On the composition of authenticated byzantine agreement, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509982]
• 13: Y. Moses and M. R. Tuttle. Programming Simultaneous Actions Using Common Knowledge. In Proc. 27th FOCS, pages 208-221. IEEE, 1986.
• 14: M. Rabin. Randomized Byzantine Generals. In Proceeding 24th Annual Symposium on the Foundations of Computer Science, pages 403-409. IEEE, 1983.
• 15: R. Richardson and J. Kilian. On the concurrent composition of zero-knowledge proofs. In Eurocrypt '99, pages 311-326, 1999. LNCS No. 1592.