Algorithms for dynamic multicast key distribution trees

ABSTRACT

Many secure group communication systems rely on a group key, which is a secret shared among the members of the group. Secure messages are sent to the group by encrypting them with the group key. Because group membership is dynamic, it becomes necessary to change the group key in an efficient and secure fashion when members join or leave the group. We present a series of algorithms for solving this problem based on 2--3 trees, where each internal node has degree 2 or 3. The algorithms attempt to minimize the worst case communication cost of updating the group key and the auxiliary keys needed by the algorithms. The algorithms are analyzed for the worst case performance and evaluated empirically via simulations. We focus on the trade-off between the communication cost due to the structure of the tree and that due to the restructuring of the tree to maintain its structure.

REFERENCES

• 1: S. Banerjee and B. Bhattacharjee. Scalable secure group communication over IP multicast. In JSAC Special Issue on Network Support for Group Communication, October 2002.
• 2: R. Bayer and E.M. McCreight. Organization and maintenance of large ordered indexes. In Acta Informatica 1(3):173--189, 1972.
• 3: R. Canetti, T. Malkin, and K. Nissim. Efficient communication-storage tradeoffs for multicast encryption. In Advances in Cryptology, EUROCRYPT 1999, May 1999.
• 4: 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]
• 5: 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
• 6: A. O. Freier, P. Karlton, and P. Kocher. The SSL protocol version 3.0. IETF Internet-draft, March 1996.
• 7: M. Luby and J. Staddon. Combinatorial bounds for broadcast encryption. In Advances in Cryptology -- EUROCRYPT '98, pages 512--526, 1998.
• 8: 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
• 9: M. Moyer, J. Rao, and P. Rohatgi. Maintaining balanced key trees for secure multicast. Internet draft, draft-irtf-smug-key-tree-balance-00.txt, June 1999.
• 10: M. Moyer, J. Rao, and P. Rohatgi. A survey of security issues in multicast communications. In IEEE Network Magazine, November/December 1999.
• 11: 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
• 12: J. Snoeyink, S. Suri, and G. Varghese. A lower bound for multicast key distribution. In Proceedings of IEEE INFOCOM, 2001.
• 13: M. Steiner, G. Tsudik, and M. Waidner. Cliques: A protocol suite for key agreement in dynamic groups. In Proceedings of ICDCS, 1998.
• 14: D. M. Wallner, E. J. Harder, and R. C. Agee. Key management for multicast: issues and architectures. In IETF Informational RFC, September 1998.
• 15: 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
• 16: C. K. Wong and S. S. Lam. Keystone: a group key management service. In Proceedings of the International Conference on Telecommunications, 2000.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Performance, Security