JET: dynamic join-exit-tree amortization and scheduling for contributory key management

ABSTRACT

In secure group communications, the time cost associated with key updates in the events of member join and departure is an important aspect of quality of service, especially in large groups with highly dynamic membership. To achieve better time efficiency, we propose a join-exit-tree (JET) key management framework. First, a special key tree topology with join and exit subtrees is introduced to handle key updates for dynamic membership. Then, optimization techniques are employed to determine the capacities of join and exit subtrees for achieving the best time efficiency, and algorithms are designed to dynamically update the join and exit trees. We show that, on average, the asymptotic time cost for each member join/departure event is reduced to O(log (log n)) from the previous cost of O(log n), where n is the group size. Our experimental results based on simulated user activities as well as the real MBone data demonstrate that the proposed JET scheme can significantly improve the time efficiency, while maintaining low communication and computation cost, of tree-based contributory key management.

REFERENCES

• 1: [1] M. J. Moyer, J. R. Rao, and P. Rohatgi, "A survey of security issues in multicast communications," IEEE Network, vol. 13, no. 6, pp. 12-23, Nov./Dec. 1999.
• 2: Sanjoy Paul, Multicasting on the Internet and Its Applications, Kluwer Academic Publishers, Norwell, MA, 1998
• 3: Laurent Eschenauer , Virgil D. Gligor, A key-management scheme for distributed sensor networks, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586117]
• 4: [4] P. Judge and M. Ammar, "Gothic: A group access control architecture for secure multicast and anycast," in Proc. IEEE INFOCOM, 2002, pp. 1547-1556.
• 5: [5] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas, "Multicast security: A taxonomy and some efficient constructions," in Proc. IEEE INFOCOM, 1999, pp. 708-716.
• 6: 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 [doi>10.1109/90.836475]
• 7: Adrian Perrig , Dawn Song , J. D. Tygar, ELK, a New Protocol for Efficient Large-Group Key Distribution, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.247, May 14-16, 2001
• 8: H. Harney , C. Muckenhirn, Group Key Management Protocol (GKMP) Specification, RFC Editor, 1997
• 9: D. Wallner , E. Harder , R. Agee, Key Management for Multicast: Issues and Architectures, RFC Editor, 1999
• 10: [10] I. Chang, R. Engel, D. Kandlur, D. Pendarakis, and D. Saha, "Key management for secure Internet multicast using Boolean function minimization techniques," in Proc. IEEE INFOCOM, 1999, vol. 2, pp. 689-698.
• 11: 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
• 12: Yongdae Kim , Adrian Perrig , Gene Tsudik, Simple and fault-tolerant key agreement for dynamic collaborative groups, Proceedings of the 7th ACM conference on Computer and communications security, p.235-244, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352638]
• 13: Lakshminath Dondeti , Sarit Mukherjee , Ashok Samal, DISEC: A Distributed Framework for Scalable Secure Many-to-Many Communication, Proceedings of the Fifth IEEE Symposium on Computers and Communications (ISCC 2000), p.693, July 04-06, 2000
• 14: Stephen E. Eldridge , Colin D. Walter, Hardware Implementation of Montgomery's Modular Multiplication Algorithm, IEEE Transactions on Computers, v.42 n.6, p.693-699, June 1993 [doi>10.1109/12.277287]
• 15: H. Harney , C. Muckenhirn, Group Key Management Protocol (GKMP) Architecture, RFC Editor, 1997
• 16: Yan Sun , Wade Trappe , K. J. Ray Liu, A scalable multicast key management scheme for heterogeneous wireless networks, IEEE/ACM Transactions on Networking (TON), v.12 n.4, p.653-666, August 2004 [doi>10.1109/TNET.2004.833129]
• 17: Refik Molva , Alain Pannetrat, Scalable multicast security in dynamic groups, Proceedings of the 6th ACM conference on Computer and communications security, p.101-112, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319723]
• 18: 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
• 19: [19] S. Banerjee and B. Bhattacharjee, "Scalable secure group communication over IP multicast," IEEE J. Sel. Areas Commun., vol. 20, no. 10, pp. 1511-1527, Oct. 2002.
• 20: [20] M. Waldvogel, G. Caronni, D. Sun, N. Weiler, and B. Plattner, "The VersayKey framework: Versatile group key management," IEEE J. Sel. Areas Commun., vol. 17, no. 9, pp. 1614-1631, Sep. 1999.
• 21: Wade Trappe , Yuke Wang , K. J. Ray Liu, Resource-aware conference key establishment for heterogeneous networks, IEEE/ACM Transactions on Networking (TON), v.13 n.1, p.134-146, February 2005 [doi>10.1109/TNET.2004.842236]
• 22: [22] B. Sun, W. Trappe, Y. Sun, and K. J. R. Liu, "A time-efficient contributory key agreeement scheme for secure group communications," in Proc. IEEE Int. Conf. Communications, 2002, pp. 1159-1163.
• 23: 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
• 24: [24] Y. Mao, Y. Sun, M. Wu, and K. J. R. Liu, "Dynamic join-exit amortization and scheduling for time-efficient group key agreement," in Proc. IEEE INFOCOM, 2004, vol. 4, pp. 2617-2627.
• 25: [25] I. Ingemarsson, D. T. Tang, and C. K. Wong, "A conference key distribution system," IEEE Trans. Inf. Theory, vol. IT-28, no. 5, pp. 714-720, Sep. 1982.
• 26: Michael Steiner , Gene Tsudik , Michael Waidner, Diffie-Hellman key distribution extended to group communication, Proceedings of the 3rd ACM conference on Computer and communications security, p.31-37, March 14-15, 1996, New Delhi, India [doi>10.1145/238168.238182]
• 27: Klaus Becker , Uta Wille, Communication complexity of group key distribution, Proceedings of the 5th ACM conference on Computer and communications security, p.1-6, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288094]
• 28: [28] M. Burmester and Y. Desmedt, "A secure and efficient conference key distribution system," in Proc. EUROCRYPT, 1994, vol. 950, LCNS, pp. 275-286.
• 29: [29] W. Diffie and M. Hellman, "New directions in cryptography," IEEE Trans. Inf. Theory, vol. IT-22, no. 6, pp. 644-654, Nov. 1976.
• 30: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 31: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 32: [32] MBone User Activity Data Mar. 2003 [Online]. Available: ftp://ftp.cc. gatech.edu/people/kevin/release-data
• 33: [33] K. C. Almeroth and M. H. Ammar, "Multicast group behavior in the Internet's multicast backbone (MBone)," IEEE Commun. Mag., vol. 35, no. 6, pp. 124-129, Jun. 1997.
• 34: [34] K. C. Almeroth, "A long-term analysis of growth and usage patterns in the multicast backbone (MBone)," in Proc. IEEE INFOCOM, Mar. 2000, vol. 2, pp. 824-833.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

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

General Terms:
Algorithms, Management, Security

Keywords:
contributory key management, dynamic tree topology, secure group communications, time efficiency