On the composition of authenticated byzantine agreement

ABSTRACT

A fundamental problem of distributed computing is that of simulating a (secure) broadcast channel, within the setting of a point-to-point network. This problem is known as Byzantine Agreement and has been the focus of much research. Lamport et al. showed that in order to achieve Byzantine Agreement in the standard model, more than 2/3 of the participating parties must be honest. They further showed that by augmenting the network with a public-key infrastructure, it is possible to obtain secure protocols for any number of faulty parties. This augmented problem is called "authenticated Byzantine Agreement".In this paper we consider the question of concurrent, parallel and sequential composition of authenticated Byzantine Agreement protocols. We present surprising impossibility results showing that:<ol>

Authenticated Byzantine Agreement cannot be composed in parallel or concurrently (even twice), if 1/3 or more of the parties are faulty.

Deterministic authenticated Byzantine Agreement protocols that run for r rounds and tolerate 1/3 or more faulty parties, can only be composed sequentially less than 2r times.

</ol>In contrast, we present randomized protocols for authenticated Byzantine Agreement that compose sequentially for any polynomial number of times. We exhibit two such protocols: The first protocol tolerates corruptions of up to 1/2 of themparties, while In the first protocol, the number of faulty parties may be any number less than 1/2. On the other hand, the second protocol can tolerate any number of faulty parties, but is limited to the case that the overall number of parties is O(log k), where k is a security parameter. Finally, we show that when the model is further augmented so that unique and common session identifiers are assigned to each concurrent session, then any polynomial number of authenticated Byzantine agreement protocols can be concurrently executed, while tolerating any number of faulty parties.

REFERENCES

• 1: D. Beaver. Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority. Journal of Cryptology, 4:75--122, 1991.
• 2: R. Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143--202, 2000.
• 3: 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
• 4: Ran Canetti , Joe Kilian , Erez Petrank , Alon Rosen, Black-box concurrent zero-knowledge requires \tilde {Ω} (logn) rounds, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.570-579, July 2001, Hersonissos, Greece [doi>10.1145/380752.380852]
• 5: Yevgeniy Dodis , Silvio Micali, Parallel Reducibility for Information-Theoretically Secure Computation, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.74-92, August 20-24, 2000
• 6: 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]
• 7: Michael J. Fischer , Nancy A. Lynch , Michael Merritt, Easy impossibility proofs for distributed consensus problems, Distributed Computing, v.1 n.1, p.26-39, Jan. 1986 [doi>10.1007/BF01843568]
• 8: Mattias Fitzi , Ueli Maurer, From partial consistency to global broadcast, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.494-503, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335363]
• 9: Oded Goldreich, Concurrent zero-knowledge with timing, revisited, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509959]
• 10: 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]
• 11: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 12: L. Gong, P. Lincoln, and J. Rushby. Byzantine Agreement with Authentication: Observations and Applications in Tolerating Hybrid and Link Faults. In Dependable Computing for Critical Applications, 1995.
• 13: 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]
• 14: Silvio Micali , Phillip Rogaway, Secure Computation (Abstract), Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.392-404, August 11-15, 1991
• 15: 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]
• 16: B. Pfitzmann and M. Waidner. Information-Theoretic Pseudosignatures and Byzantine Agreement for t ρ= n/3$. Technical Report RZ 2882 (#90830), IBM Research, 1996.
• 17: R. Richardson and J. Kilian. On the concurrent composition of zero-knowledge proofs. In Eurocrypt '99, pages 311--326, 1999. LNCS No. 1592.
• 18: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Algorithms, Experimentation, Performance, Theory