Secure agreement protocols

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Secure agreement protocols: reliable and atomic group multicast in rampart

Full text

Pdf (1.46 MB)

Source

Conference on Computer and Communications Security archive
Proceedings of the 2nd ACM Conference on Computer and communications security table of contents

Fairfax, Virginia, United States

Pages: 68 - 80

Year of Publication: 1994

ISBN:0-89791-732-4

Author

Michael K. Reiter

AT&T Bell Laboratories, Holmdel, New Jersey

Sponsor

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 24, Citation Count: 42

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/191177.191194 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	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.
	2	Donald Beaver, Multiparty protocols tolerating half faulty processors, Proceedings on Advances in cryptology, p.560-572, July 1989, Santa Barbara, California, United States
	3	André Schiper , Kenneth Birman , Pat Stephenson, Lightweight causal and atomic group multicast, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.272-314, Aug. 1991 [doi>10.1145/128738.128742]
	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.
	5	Jo-Mei Chang , N. F. Maxemchuk, Reliable broadcast protocols, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.251-273, Aug. 1984 [doi>10.1145/989.357400]
	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	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).
	8	Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
	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.
	10	Hector Garcia-Molina , AnneMarie Spauster, Ordered and reliable multicast communication, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.242-271, Aug. 1991 [doi>10.1145/128738.128741]
	11	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]
	12	Kenneth R. Iversen, A Cryptographic Scheme for Computerized Elections, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.405-419, August 11-15, 1991
	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.
	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.
	15	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]
	16	S. W. Luan , V. D. Gligor, A Fault-Tolerant Protocol for Atomic Broadcast, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.271-285, July 1990 [doi>10.1109/71.80156]
	17	P. M. Melliar-Smith , L. E. Moser , V. Agrawala, Broadcast Protocols for Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.17-25, January 1990 [doi>10.1109/71.80121]
	18	J.H. Moore. Protocol failures in cryptosystems. Proceedings oy the IEEE, 76(5), May 1988.
	19	Frank M. Pittelli , Hector Garcia-Molina, Reliable scheduling in a TMR database system, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.25-60, Feb. 1989 [doi>10.1145/58564.59294]
	20	T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
	21	Micheal K. Reiter, A Secure Group Membership Protocol, Proceedings of the 1994 IEEE Symposium on Security and Privacy, p.176, May 16-18, 1994
	22	Michael K. Reiter , Kenneth P. Birman, How to securely replicate services, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.986-1009, May 1994 [doi>10.1145/177492.177745]
	23	Michael K. Reiter , Kenneth P. Birman , Robbert van Renesse, A security architecture for fault-tolerant systems, ACM Transactions on Computer Systems (TOCS), v.12 n.4, p.340-371, Nov. 1994 [doi>10.1145/195792.195823]
	24	Ronald L. Rivest, The MD4 Message Digest Algorithm, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.303-311, August 11-15, 1990
	25	B.. L. Rivest. RFC 19~I: The MD5 Meuage Digest Algorithm. Internet Activities Board, April 1992.
	26	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]
	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.
	28	Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]
	29	Santosh K. Shrivastava , Paul D. Ezhilchelvan , Neil A. Speirs , Sha Tao , Alan Tully, Principal Features of the VOLTAN Family of Reliable Node Architectures for Distributed Systems, IEEE Transactions on Computers, v.41 n.5, p.542-549, May 1992 [doi>10.1109/12.142680]
	30	Sam Toueg, Randomized Byzantine Agreements, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.163-178, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806744]
	31	Robbert van Renesse , Kenneth P. Birman , Robert Cooper , Bradford B. Glade , Pat Stephenson, Reliable Multicast between Micro-Kernels, Proceedings of the Workshop on Micro-kernels and Other Kernel Architectures, p.269-284, April 27-28, 1992
	32	Victor L. Voydock , Stephen T. Kent, Security Mechanisms in High-Level Network Protocols, ACM Computing Surveys (CSUR), v.15 n.2, p.135-171, June 1983 [doi>10.1145/356909.356913]

CITED BY 42

	Kim Potter Kihlstrom , L. E. Moser , P. M. Melliar-Smith, The SecureRing group communication system, ACM Transactions on Information and System Security (TISSEC), v.4 n.4, p.371-406, November 2001
	Robbert van Renesse , Kenneth P. Birman , Silvano Maffeis, Horus: a flexible group communication system, Communications of the ACM, v.39 n.4, p.76-83, April 1996
	Li Gong , Nachum Shacham, Multicast security and its extension to a mobile environment, Wireless Networks, v.1 n.3, p.281-295, 1995
	David A. Cooper , Kenneth P. Birman, The design and implementation of a private message service for mobile computers, Wireless Networks, v.1 n.3, p.297-309, 1995
	Meng-Jang Lin , Aleta M. Ricciardi , Keith Marzullo, A new model for availability in the face of self-propagating attacks, Proceedings of the 1998 workshop on New security paradigms, p.134-137, September 22-26, 1998, Charlottesville, Virginia, United States
	Michael Reiter, Distributing trust with the Rampart toolkit, Communications of the ACM, v.39 n.4, p.71-74, April 1996
	Chung Kei Wong , Mohamed Gouda , Simon S. Lam, Secure group communications using key graphs, IEEE/ACM Transactions on Networking (TON), v.8 n.1, p.16-30, Feb. 2000
	The architecture and performance of security protocols in the ensemble group communication system: Using diamonds to guard the castle, ACM Transactions on Information and System Security (TISSEC), v.4 n.3, p.289-319, August 2001
	Boaz Barak , Amir Herzberg , Dalit Naor , Eldad Shai, The proactive security toolkit and applications, Proceedings of the 6th ACM conference on Computer and communications security, p.18-27, November 01-04, 1999, Kent Ridge Digital Labs, Singapore
	Petros Maniatis , David S. H. Rosenthal , Mema Roussopoulos , Mary Baker , TJ Giuli , Yanto Muliadi, Preserving peer replicas by rate-limited sampled voting, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
	Dahlia Malkhi , Michael Reiter, Byzantine quorum systems, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.569-578, May 04-06, 1997, El Paso, Texas, United States
	Michael K. Reiter , Matthew K. Franklin , John B. Lacy , Rebecca N. Wright, The Ω key management service, Proceedings of the 3rd ACM conference on Computer and communications security, p.38-47, March 14-15, 1996, New Delhi, India
	Christian Cachin, An asynchronous protocol for distributed computation of RSA inverses and its applications, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.153-162, July 13-16, 2003, Boston, Massachusetts
	Jay J. Wylie , Michael W. Bigrigg , John D. Strunk , Gregory R. Ganger , Han Kiliççöte , Pradeep K. Khosla, Survivable Information Storage Systems, Computer, v.33 n.8, p.61-68, August 2000
	Ugur Çetintemel , Peter J. Keleher , Bobby Bhattacharjee , Michael J. Franklin, Deno: A Decentralized, Peer-to-Peer Object-Replication System for Weakly Connected Environments, IEEE Transactions on Computers, v.52 n.7, p.943-959, July 2003
	Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
	Dahlia Malkhi , Yishay Mansour , Michael K. Reiter, Diffusion without false rumors: on propagating updates in a Byzantine environment, Theoretical Computer Science, v.299 n.1-3, p.289-306, 18 April 2003
	Miguel Castro , Barbara Liskov, Practical byzantine fault tolerance and proactive recovery, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.398-461, November 2002
	Dahlia Malkhi , Michael Merritt , Ohad Rodeh, Secure reliable multicast protocols in a WAN, Distributed Computing, v.13 n.1, p.19-28, January 2000
	Petros Maniatis , Mema Roussopoulos , T. J. Giuli , David S. H. Rosenthal , Mary Baker, The LOCKSS peer-to-peer digital preservation system, ACM Transactions on Computer Systems (TOCS), v.23 n.1, p.2-50, February 2005
	Yair Amir , Yongdae Kim , Cristina Nita-Rotaru , Gene Tsudik, On the performance of group key agreement protocols, ACM Transactions on Information and System Security (TISSEC), v.7 n.3, p.457-488, August 2004
	Sebastian Gutierrez-Nolasco , Nalini Venkatasubramanian , Mark-Oliver Stehr , Carolyn Talcott, Exploring adaptability of secure group communication using formal prototyping techniques, Proceedings of the 3rd workshop on Adaptive and reflective middleware, p.232-237, October 19-19, 2004, Toronto, Ontario, Canada
	Xavier Défago , André Schiper , Péter Urbán, Total order broadcast and multicast algorithms: Taxonomy and survey, ACM Computing Surveys (CSUR), v.36 n.4, p.372-421, December 2004
	Dahlia Malkhi , Michael K. Reiter, An Architecture for Survivable Coordination in Large Distributed Systems, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.187-202, March 2000
	Michael K. Reiter, A Secure Group Membership Protocol, IEEE Transactions on Software Engineering, v.22 n.1, p.31-42, January 1996
	Wiebe K. Wiechers , Semir Daskapan , Willem G. Vree, Simulating the establishment of trust infrastructures in multi-agent systems, Proceedings of the 6th international conference on Electronic commerce, October 25-27, 2004, Delft, The Netherlands
	Partha Pal , Franklin Webber , Richard Schantz, Survival by defense-enabling, Proceedings of the 2001 workshop on New security paradigms, September 10-13, 2001, Cloudcroft, New Mexico
	Yair Amir , Yongdae Kim , Cristina Nita-Rotaru , John L. Schultz , Jonathan Stanton , Gene Tsudik, Secure Group Communication Using Robust Contributory Key Agreement, IEEE Transactions on Parallel and Distributed Systems, v.15 n.5, p.468-480, May 2004
	Yair Amir , Cristina Nita-Rotaru , Jonathan Stanton , Gene Tsudik, Secure Spread: An Integrated Architecture for Secure Group Communication, IEEE Transactions on Dependable and Secure Computing, v.2 n.3, p.248-261, July 2005
	Matthew K. Franklin , Michael K. Reiter, The Design and Implementation of a Secure Auction Service, IEEE Transactions on Software Engineering, v.22 n.5, p.302-312, May 1996
	Secure virtual enclaves: Supporting coalition use of distributed application technologies, ACM Transactions on Information and System Security (TISSEC), v.4 n.2, p.103-133, May 2001
	Miguel Correia , Nuno Ferreira Neves , Lau Cheuk Lung , Paulo Veríssimo, Worm-IT - A wormhole-based intrusion-tolerant group communication system, Journal of Systems and Software, v.80 n.2, p.178-197, February, 2007
	Rachid Guerraoui , Marko Vukolić, How fast can a very robust read be?, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Giovanni Mella , Elena Ferrari , Elisa Bertino , Yunhua Koglin, Controlled and cooperative updates of XML documents in byzantine and failure-prone distributed systems, ACM Transactions on Information and System Security (TISSEC), v.9 n.4, p.421-460, November 2006
	Lukasz Opyrchal , Atul Prakash, Secure distribution of events in content-based publish subscribe systems, Proceedings of the 10th conference on USENIX Security Symposium, p.21-21, August 13-17, 2001, Washington, D.C.
	Patrick McDaniel , Atul Prakash , Peter Honeyman, Antigone: a flexible framework for secure group communication, Proceedings of the 8th conference on USENIX Security Symposium, p.9-9, August 23-26, 1999, Washington, D.C.
	Li Gong, Enclaves: enabling secure collaboration over the internet, Proceedings of the 6th conference on USENIX Security Symposium, Focusing on Applications of Cryptography, p.15-15, July 22-25, 1996, San Jose, California
	Lukasz Opyrchal , Atul Prakash, Secure distribution of events in content-based publish subscribe systems, Proceedings of the 10th conference on USENIX Security Symposium, p.21-21, August 13-17, 2001, Washington, D.C.
	Meng Yu , Peng Liu , Wanyu Zang, Specifying and using intrusion masking models to process distributed operations, Journal of Computer Security, v.13 n.4, p.623-658, July 2005
	Patrick McDaniel , Atul Prakash, Enforcing provisioning and authorization policy in the Antigone system, Journal of Computer Security, v.14 n.6, p.483-511, November 2006
	Ross Anderson , Francesco Bergadano , Bruno Crispo , Jong-Hyeon Lee , Charalampos Manifavas , Roger Needham, A new family of authentication protocols, ACM SIGOPS Operating Systems Review, v.32 n.4, p.9-20, Oct. 1998
	HariGovind V. Ramasamy , Adnan Agbaria , William H. Sanders, A Parsimonious Approach for Obtaining Resource-Efficient and Trustworthy Execution, IEEE Transactions on Dependable and Secure Computing, v.4 n.1, p.1-17, January 2007