Justin Goshi
Richard E. Ladner
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.
- 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. Google Scholar
- Bayer, R. and McCreight, E. 1972. Organization and maintenance of large ordered indexes. Acta Inf. 1, 3, 173--189.Google Scholar
- Briscoe, B. 1999. MARKS: Zero side-effect multicast key management using arbitrarily revealed key sequences. In Proceedings of the First International Workshop on Networked Group Communication, Pisa, Italy. Lecture Notes in Computer Science, vol. 1736. Springer, New York. 301--320. Google Scholar
- 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. Google Scholar
- 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. Google Scholar
- Deering, S. E. and Cheriton, D. R. 1990. Multicast routing in datagram internetworks and extended LANs. ACM Trans. Comput. Syst. 8, 2 (May), 85--110. Google Scholar
- Fiat, A. and Naor, M. 1993. Broadcast encryption. In Advances in Cryptology---CRYPTO '93, Proceedings of the 13th Annual International Cryptology Conference, Santa Barbara, California. Lecture Notes in Computer Science, vol. 773. Springer, New York. 480--491. Google Scholar
- Freier, A. O., Karlton, P., and Kocher, P. 1996. The ssl protocol version 3.0. IETF Internet-draft.Google Scholar
- Goshi, J. 2004. Efficient and secure media delivery. Ph.D. thesis, University of Washington. Google Scholar
- 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).Google Scholar
- Li, X., Yang, Y., Gouda, M. G., and Lam, S. S. 2001. Batch rekeying for secure group communications. In Proceedings of the tenth international World Wide Web Conference, Hong Kong, China. 525--534. Google Scholar
- 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.Google Scholar
- Mittra, S. 1997. Iolus: A framework for scalable secure multicasting. In Proceedings of the ACM SIGCOMM '97 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, September 14--18, 1997, Cannes, France. 277--288. Google Scholar
- 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.Google Scholar
- 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. Google Scholar
- 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. Google Scholar
- 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.Google Scholar
- Setia, S., Koussih, S., Jajodia, S., and Harder, E. 2000. Kronos: A scalable group rekeying approach for secure multicast. In Proceedings of the IEEE Symposium on Security and Privacy, Berkeley, California. 215--228. Google Scholar
- Shields, C. and Garcia-Luna-Aceves, J. J. 1999. KHIP---a scalable protocol for secure multicast routing. In Proceedings of the ACM SIGCOMM '99 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, Cambridge, MA. 53--64. Google Scholar
- 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.Google Scholar
- Steiner, M., Tsudik, G., and Waidner, M. 1998. Cliques: a new approach to group key agreement. In Proceedings of the 18th International Conference on Distributed Computing Systems, Amsterdam, The Netherlands. 380--387. Google Scholar
- Wallner, D. M., Harder, E. J., and Agee, R. C. 1998. Key management for multicast: issues and architectures. IETF Informational RFC. Google Scholar
- Wong, C. K. and Lam, S. S. 2000. Keystone: a group key management service. In Proceedings of the International Conference on Telecommunications, Acapulco, Mexico.Google Scholar
- Wong, C. K., Gouda, M. G., and Lam, S. S. 1998. Secure group communications using key graphs. In Proceedings of the ACM SIGCOMM '98 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, Vancouver, B.C., Canada. 68--79. Google Scholar
- Zhu, S., Setia, S., and Jajodia, S. 2003. Performance optimizations for group key management schemes. In Proceedings of the 23rd International Conference on Distributed Computing Systems, Providence, Rhode Island. IEEE Computer Society, Washington, DC. 163--173. Google Scholar
Index Terms
- Algorithms for dynamic multicast key distribution
Recommendations
Optimal communication complexity of generic multicast key distribution
We prove a tight lower bound on the communication complexity of secure multicast key distribution protocols in which rekey messages are built using symmetric-key encryption, pseudo-random generators, and secret sharing schemes. Our lower bound shows ...
Algorithms for dynamic multicast key distribution trees
PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computingMany 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 ...
Decentralized group key management for secure multicast communications
Multicast protocols provide mechanisms for a sender to send a message to multiple receivers simultaneously. When the multicast message is of a sensitive nature, it should be encrypted. This would require that all the members of the multicast group share ...
Reviews
Kevin W. Wall
What algorithm do you choose if you need to securely distribute an encryption key for a pay-per-view movie to hundreds of thousands of set-top boxes, among several million possible receivers, and you wish to periodically change the key, to prevent illegal copying of the movie__?__ That's the type of problem that Goshi and Ladner's algorithms address. What makes the authors' algorithms different from simple distribution algorithms is that theirs must "provide complete security against colluding members," and maintain "backward and forward security on every group membership change." (Backward security means that a new group member is unable to decrypt any previous group communications, and forward security means that a departing group member cannot decrypt any future group communications.) After describing terminology, these security requirements, and previous work in this area, the authors explain their approach to modeling the problem as various categories of balanced trees. For each of these balanced tree types, they depict the algorithms, and offer proof that the trees remain balanced through some number of additions to, or removals from, the group. They end by analyzing the worst-case behavior of each algorithm, and then examine empirical results based on numerous simulations. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments