Abstract
Secure group communication relies on secure and robust distribution of group keys. A stateless group key distribution scheme is an ideal candidate when the communication channel is unreliable. Several stateless group key distribution schemes have been proposed. However, these schemes require all users store a certain number of auxiliary keys. The number of such keys increases as the group size grows. As a result, it is quite challenging to use these schemes when the users in a relatively large group have memory constraints. Thus, it is desirable to develop new schemes that can reduce the memory requirement. This paper introduces two novel stateless group key revocation schemes named key-chain tree (KCT) and layered key-chain tree (LKCT), which combine one-way key chains with a logical key tree. These schemes reduce the user storage requirements by trading off it with communication and computation costs. Specifically, these schemes can revoke any R users from a user group of size N by sending a key update message with at most 4R keys, while only requiring each user to store 2log N keys.
This work is partially supported by NCSU Center for Advanced Computing & Communcation (CACC)
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blundo, C., Cresti, A.: Space Requirements for Broadcast Encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 287–298. Springer, Heidelberg (1995)
Blundo, C., D’Arco, P., et al.: Design of Self-Healing Key Distribution Schemes. Design, Codes, and Cryptography 32 (2004)
Blundo, C., Frota Mattos, L.A., Stinson, D.R.: Trade-offs Between Communication and Storage in Unconditionally Secure Schemes for Broadcast Encryption and Interactive Key Distribution. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 387–400. Springer, Heidelberg (1996)
Canetti, R., Goldreich, O., Halevi, S.: The Random Oracle Methodology, Revisited. In: Proceedings of 30th Annual ACM Symposium on the Theory of Computing (1998)
Canetti, R., Micciancio, D., Reingold, O.: Perfectly One-Way Probabilistic Hash Functions. In: Proceedings of 30th Annual ACM Symposium on the Theory of Computing (1998)
Chan, K., Chan, S.: Key Management Approaches to Offer Data Confidentiality for Secure Multicast. IEEE Network 17, 30–39 (2003)
Chang, I., Engel, R., et al.: Key Management for Secure Internet Multicast Using Boolean Function Minimisation Technique. In: Proceedings of INFOCOM 1999, New York, NY (1999)
Coppersmith, D., Jakobsson, M.: Almost Optimal Hash Sequence Traversal. In: The Sixth International Conference on Financial Cryptography 2002 (2002)
Dondeti, L.R., Mukherjee, S., Samal, A.: Survey and Comparison of Secure Group Communication Protocols, University of Nebraska-Lincoln (June 1999)
Fiat, A., Naor, M.: Broadcast Encryption. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 480–491. Springer, Heidelberg (1994)
Halevy, D., Shamir, A.: The LSD Broadcast Encryption Scheme. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, p. 47. Springer, Heidelberg (2002)
Jakobsson, M.: Fractal Hash Sequence Representation and Traversal. In: The IEEE International Symposium on Information Theory 2002 (ISIT 2002) (July 2002)
Kumar, P.S.: A survey of Multicast Security Issues and Architectures. In: Proceedings of 21st National Information Systems Security Conferences, Arlington, VA (1999)
Kumar, R., Rajagopalan, R., Sahai, A.: Coding constructions for blacklisting problems without computational assumptions. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, p. 609. Springer, Heidelberg (1999)
Kurnio, H., McAven, L., Safavi-Naini, R., Wang, H.: A Dynamic Group Key Distribution Scheme with Flexible User Join. In: CRYPTO 1989. LNCS, vol. 435, pp. 478–496. Springer, Heidelberg (2003)
Lamport, L.: Password Authentication with Insecure Communication. Communications of the ACM 24(11), 770–772 (1981)
Liu, D., Ning, P.: Efficient Self-Healing Group Key Distribution with Revocation Capability. In: Proceedings of CCS 2003, Washington D.C. (October 2003)
Luby, M., Staddon, J.: Combinatorial Bounds for Broadcast Encryption. In: Advances in Cryptology-EUROCRYPTO 1998 (1998)
Naor, D., Naor, M., Lotspiech, J.: Revocation and Tracing Schemes for Stateless Receivers. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 41. Springer, Heidelberg (2001)
Safavi-Naini, R., Wang, H.: New Constructions of Secure Multicast Re-keying Schemes using Perfect Hash Families. In: Proceedings of CCS 2000, Athens, Greece (2000)
Staddon, J., Miner, S., et al.: Self-Healing Key Distribution with Revocation. In: Proceedings of 2002 IEEE Symposium on Security and Privacy, Berkeley, California, USA (2002)
Stinson, D.R., van Trung, T.: Some New Results on Key Distribution Patterns and Broadcast Encryption. Designs, Codes and Cryptography 14, 261–279 (1998)
Wong, C., Gouda, M., Lam, S.: Secure Group Communications Using Key Graphs. In: Proceedings of the ACM SIGCOMM 1998, Vancouver, B.C. (1998)
Wallner, D., Harder, E., Agee, R.: Key Management for Multicast: Issues and Architectures, IETF Request For Comments, RFC2627 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, P., Ning, P., Reeves, D.S. (2004). Storage-Efficient Stateless Group Key Revocation. In: Zhang, K., Zheng, Y. (eds) Information Security. ISC 2004. Lecture Notes in Computer Science, vol 3225. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30144-8_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-30144-8_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23208-7
Online ISBN: 978-3-540-30144-8
eBook Packages: Springer Book Archive