Algorithms for dynamic multicast key distribution

ABSTRACT

We study the problem of multicast key distribution for group security. Secure group communication systems typically rely on a group key, which is a secret shared among the members of the group. This key is used to provide privacy by encrypting all group communications. Because groups can be large and highly dynamic, it becomes necessary to change the group key in a scalable and secure fashion when members join and leave the group. We present a series of algorithms for solving this problem based on key trees. The algorithms attempt to minimize the worst-case communication cost of updates by maintaining balanced key tree structures. We focus on the trade-off between the communication cost because of the structure of the tree and that due to the overhead of restructuring the tree to maintain its balanced structure. The algorithms are analyzed for worst-case tree structure bounds and evaluated empirically via simulations.

REFERENCES

• 1: Banerjee, S. and Bhattacharjee, B. 2002. Scalable secure group communication over ip multicast. JSAC Special Issue on Network Support for Group Communication 20, 8 (Oct.), 1511--1527.
• 2: Bayer, R. and McCreight, E. 1972. Organization and maintenance of large ordered indexes. Acta Inf. 1, 3, 173--189.
• 3: Bob Briscoe, MARKS: Zero Side Effect Multicast Key Management Using Arbitrarily Revealed Key Sequences, Proceedings of the First International COST264 Workshop on Networked Group Communication, p.301-320, November 17-20, 1999
• 4: Canetti, R., Malkin, T., and Nissim, K. 1999. Efficient communication-storage tradeoffs for multicast encryption. In Advances in Cryptology---EUROCRYPT '99, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic. Lecture Notes in Computer Science, vol. 1592. Springer, New York. 459--474.
• 5: Chong, C. N., Ren, B., Doumen, J., Etalle, S., Hartel, P. H., and Corin, R. 2004. License protection with a tamper-resistant token. In 5th Workshop on Information Security Applications (WISA 2004). Lecture Notes in Computer Science, vol. 3325. Springer, New York. 224--238.
• 6: Stephen E. Deering , David R. Cheriton, Multicast routing in datagram internetworks and extended LANs, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.85-110, May 1990 [doi>10.1145/78952.78953]
• 7: Amos Fiat , Moni Naor, Broadcast encryption, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.480-491, January 1994, Santa Barbara, California, United States
• 8: Freier, A. O., Karlton, P., and Kocher, P. 1996. The ssl protocol version 3.0. IETF Internet-draft.
• 9: Justin Goshi , Richard E. Ladner, Efficient and secure media delivery, 2004
• 10: Lazos, L. and Poovendran, R. 2004. Cross-layer design for energy-efficient secure multicast communications in ad hoc networks. In IEEE International Conference on Communications (ICC).
• 11: Xiaozhou Steve Li , Yang Richard Yang , Mohamed G. Gouda , Simon S. Lam, Batch rekeying for secure group communications, Proceedings of the 10th international conference on World Wide Web, p.525-534, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372153]
• 12: Luby, M. and Staddon, J. 1998. Combinatorial bounds for broadcast encryption. In Advances in Cryptology---EUROCRYPT '98, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland. Lecture Notes in Computer Science, vol. 1403. Springer, New York. 512--526.
• 13: Suvo Mittra, Iolus: a framework for scalable secure multicasting, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.277-288, September 14-18, 1997, Cannes, France
• 14: Moyer, M., Rao, J., and Rohatgi, P. 1999a. Maintaining balanced key trees for secure multicast. Internet draft, draft-irtf-smug-key-tree-balance-00.txt.
• 15: Moyer, M., Rao, J., and Rohatgi, P. 1999b. A survey of security issues in multicast communications. IEEE Network Magazine 13, 6 (Nov./Dec.), 12--23.
• 16: Poovendran, R. and Baras, J. S. 2001. An information-theoretic approach for design and analysis of rooted-tree-based multicast key management schemes. IEEE Transactions on Information Theory 47, 7, 2824--2834.
• 17: Rodeh, O., Birman, K. P., and Dolev, D. 2001. Using AVL trees for fault tolerant group key management. International Journal on Information Security 1, 2 (Feb.), 84--99.
• 18: Sanjeev Setia , Samir Koussih , Sushil Jajodia , Eric Harder, Kronos: A Scalable Group Re-Keying Approach for Secure Multicast, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.215, May 14-17, 2000
• 19: Clay Shields , J. J. Garcia-Luna-Aceves, KHIP—a scalable protocol for secure multicast routing, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.53-64, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 20: Snoeyink, J., Suri, S., and Varghese, G. 2001. A lower bound for multicast key distribution. In Proceedings of the IEEE INFOCOM 2001 Conference on Computer Communications, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, Alaska. Vol. 1. 422--431.
• 21: Michael Steiner , Michael Waidner , Gene Tsudik, CLIQUES: A New Approach to Group Key Agreement, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.380, May 26-29, 1998
• 22: D. Wallner , E. Harder , R. Agee, Key Management for Multicast: Issues and Architectures, RFC Editor, 1999
• 23: Wong, C. K. and Lam, S. S. 2000. Keystone: a group key management service. In Proceedings of the International Conference on Telecommunications, Acapulco, Mexico.
• 24: Chung Kei Wong , Mohamed Gouda , Simon S. Lam, Secure group communications using key graphs, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.68-79, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 25: Sencun Zhu , Sanjeev Setia , Sushil Jajodia, Performance Optimizations for Group Key Management Schemes, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.163, May 19-22, 2003

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Keywords:
Dynamic key distribution, experimental algorithms, multicast