Michael K. Reiter
ABSTRACT
Reliable and atomic group multicast have been proposed as fundamental communication paradigms to support secure distributed computing in systems in which processes may behave maliciously. These protocols enable messages to be multicast to a group of processes, while ensuring that all honest group members deliver the same messages and, in the case of atomic multicast, deliver these messages in the same order. We present new reliable and atomic group multicast protocols for asynchronous distributed systems. We also describe their implementation as part of Rampart, a toolkit for building high-integrity distributed services, i.e., services that remain correct and available despite the corruption of some component servers by an attacker. To our knowledge, Rampart is the first system to demonstrate reliable and atomic group multicast in asynchronous systems subject to process corruptions.
- 1.Y. Amir, D. Dolev, S. Kramer, and D. Malki. Transis: A communication sub-system for high availability. In Proceedings of the SP, nd International Symposium on Fault-Tolerant Computing, pages 76-84, July 1992.]]Google Scholar
- 2.D. Beaver. Multiparty protocols tolerating half faulty processors. In G. Brassard, editor, Advances in Gryptology-- CRYPTO '89 Proceedings (Lecture Notes in Computer Science 435), pages 560-57'2. Springer-Verlag, 1990.]] Google ScholarDigital Library
- 3.K. P. Birman, A. SchJper, and P. Stephenson. Lightweight causal and atomic group multicast. A CM Transactions on Computer Systems, 9(3):272-314, August 1991.]] Google ScholarDigital Library
- 4.D. F. C. Brewer and M. J. Nash. The Chinese wall security policy. In Proceedings of the 1989 IEEE Symposium on Security and Pri~acy, pages 206-214, April 1989.]]Google ScholarCross Ref
- 5.J. Chang and N. F. Maxemchuck. Reliable broadcast protocols. A CM Transactions on Computer Systems, 2(3):251- 27'3, August 1984.]] Google ScholarDigital Library
- 6.D. Chaum, C. Crdpeau, and I. Damg&rd. Multiparty unconditionally secure protocols. In Proceedings of the ~Oth ACM Symposium on Theory of Computing, pages 11-19, May 1988.]] Google ScholarDigital Library
- 7.F. Cristian, H. Aghili, R. Strong, and D. Dolev. Atomic broadcast: From simple message diffusion to Byzantine agreement. In Proceedings of the 15th International Symposium on Fault-Tolerant Computing, pages 200-206, June 1985. A revised version appears as IBM Research Laboratory Technical Report RJ5244 (April 1989).]]Google Scholar
- 8.M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process..Journal of the A CM, 32(2):37'4-382, April 1985.]] Google ScholarDigital Library
- 9.M. K. Franklin and M. Yung. The varieties of secure distributed computation. In Proceedings of Sequences II, Methods in Communications, Security and Computer Science, pages 392-417, June 1991.]]Google Scholar
- 10.H. Garcia-Molina and A. Spauster. Ordered and reliable multicast communication. ACId Transactions on Computer Systems, 9(3):242-27'1, August 1991.]] Google ScholarDigital Library
- 11.O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In Proceedings of the 19th A CM Symposium on Theory of Computing, pages 218-229, May 1987'.]] Google ScholarDigital Library
- 12.K. R. Iversen. A cryptographic scheme for computerized general elections. In J. Feigenbaum, editor, Advances in Cryptology--CRYPTO '91 Proceedings (Lecture Notes in Computer Science 576), pages 405-419. Springer-Verlag, 1992.]] Google ScholarDigital Library
- 13.M. F. Kaashoek and A. S. Tanenbaum. Group communica. tion in the Amoeba distributed operating system. In Proceedings of the 11th International Conference on Distributed Computing Systems, pages 222-230, May 1991.]]Google ScholarCross Ref
- 14.J. B. Lacy, D. P. Mitchell, and W. M. SCheU. CryptoLib: Cryptographyin software. In Proceedings of the ~th USENIX Security Workshop, pages 1-17, October 1993.]]Google Scholar
- 15.L. Laraport, R. Shostak, and M. Pease. The Byzantine generals problem. A CM Transactions on Programming Languages and Systems, 4(3):382-401, July 1982.]] Google ScholarDigital Library
- 16.S. W. Luan and V. D. Gligor. A fault-tolerant protocol for atomic broadcast. IEEE Transactions on Parallel and Distributed Systems, 1(3):27'1-285, July 1990.]] Google ScholarDigital Library
- 17.P. M. Melliar-Smith, L. E. Moser, and V. Agrawala. Broadcast protocols for distributed systems. IEEE Transactions on Parallel and Distributed Systems, 1(1):17-25, January 1990.]] Google ScholarDigital Library
- 18.J.H. Moore. Protocol failures in cryptosystems. Proceedings oy the IEEE, 76(5), May 1988.]]Google ScholarCross Ref
- 19.F. M. Pittelli and H. GarciwMolina. Reliable scheduling in a TMR database system. ACM Tran$actions on Computer Systems, 7'(1):25-60, February 1989.]] Google ScholarDigital Library
- 20.T. l%abin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. In Proceeding8 of |he ~lJf A CM Sympoeiurn on Theory of Computing, pages 73-85, May 1989.]] Google Scholar
- 21.M. K. Reiter. A secure group membership protocol. In Proceeding8 of the 1994 IEEE Symposium on Research in Secttrity and Pr~uac~, pages 176-189, May 1994.]] Google Scholar
- 22.M.K. Reiter and K. P. Birman. How to securely replicate services. A CM Transactions on Programming Languages and Systems, 16(3):986-1009, May 1994.]] Google ScholarDigital Library
- 23.M. K. Reiter, K. P. Birman, and R. van Renesse. A security architecture for fault-tolerant systems. To appear in A CM T~unaaction8 on Computer Sljatems, 1994.]] Google ScholarDigital Library
- 24.It, L. Rivest. The MD4 message digest algorithm. In A. J. Menezes and S. A. Vanstone, editors, Advances in Cryptoiogy--CRYPTO '90 Proceedings (Lecture Notes in Computer Science 537), pages 303-311. Springer-Verlag, 1991.]] Google ScholarDigital Library
- 25.B.. L. Rivest. RFC 19~I: The MD5 Meuage Digest Algorithm. Internet Activities Board, April 1992.]] Google ScholarDigital Library
- 26.R. L. Rivest, A. Shamir, and L. Adlemem. A method for obtaining digital signatures and public-key cryptosystems. Communications of the A CM, 21(2):120-126, February 1978.]] Google ScholarDigital Library
- 27.A. Schiper and A. Sandoz. Uniform reliable multicast in a virtually synchronous environment. In Proceeding8 of the 19th International Conference on Distributed Computing Systems, pages 561-568, May 1993.]]Google Scholar
- 28.F. B. Sc/meider. Implementing fettdt-tolerant services using the state machine approach: A tutorial. A CM CompuZing Sur~eya, 22(4):299-319, December 1990.]] Google ScholarDigital Library
- 29.S. K. Shrivastava, P. D. Ezhi}chelvan, N. A. Speirs, S. TaD, and A. Tully. Principal features of the VOLTAN family of reliable node architectures for distributed systems. IEEE Transactions on Computers, 41(5):542-549, May 1992.]] Google ScholarDigital Library
- 30.S. Toueg. Randomized Byzantine agreements. In Proceed. ing8 of the 3rd A CM Symposium on Principles of Distributed Computing, pages 163-178, August 1984.]] Google Scholar
- 31.R. van Renesse, K. Birman, R. Cooper, B. Glade, and P. Stephenson. R.eliable multicast between microkernels. In Proceeding8 of the USENIX Microkernels and Other Kernel Architecture8 Workshop, April 1992.]] Google ScholarDigital Library
- 32.V. L. Voydock and S. T. Kent. Security mechanisms in high-level network protocols. A GM Computing Surueys, 15(2):135-171, June 1983.]] Google ScholarDigital Library
Index Terms
- Secure agreement protocols: reliable and atomic group multicast in rampart
Recommendations
Collusive attacks to "circle-type" multi-party quantum key agreement protocols
We find that existing multi-party quantum key agreement (MQKA) protocols designed for fairness of the key are, in fact, unfair. Our analysis shows that these protocols are sensitive to collusive attacks; that is, dishonest participants can collaborate ...
Secure Multi-Party Computation without Agreement
It has recently been shown that authenticated Byzantine agreement, in which more than a third of the parties are corrupted, cannot be securely realized under concurrent or parallel (stateless) composition. This result puts into question any usage of ...
Secure Computation without Agreement
DISC '02: Proceedings of the 16th International Conference on Distributed ComputingIt has recently been shown that executions of authenticated Byzantine Agreement protocols in which more than a third of the parties are corrupted, cannot be composed concurrently, in parallel, or even sequentially (where the latter is true for ...
Comments