×

Lower bounds and new constructions on secure group communication schemes. (English) Zbl 1147.94011

Summary: This paper presents both the theoretical and practical aspects of secure group communication schemes. We pointed out that multiple revocation is a fundamentally time-consuming task in secure group communication, by establishing lower bounds for broadcast encryption and group key distribution schemes. We showed that they are \(O(n)\) for BE and \(O(n/m)\) for GKD respectively, where \(m\) is storage requirement and \(n\) is the number of users. Thus, they are clearly far more costly than the ideal log bound. In practice, we designed a new broadcast encryption scheme RBE that actually achieves these lower bounds. RBE is shown to outperform most efficient BE schemes in mass revocation. We discuss the influence of join as well as the feasibility of adding it in BE schemes by means of performing full updating or overprovisioning.

MSC:

94A60 Cryptography
68M10 Network design and communication in computer systems
68P25 Data encryption (aspects in computer science)

Software:

Iolus
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ateniese, G.; Steiner, M.; Tsudik, G., New multiparty authentication services and key agreement protocols, IEEE Journal on Selected Areas in Communications, 18, 4, 628-640 (2000)
[2] M. Bechler, H.-J. Hof, D. Kraft, F. Pählke, L. Wolf, A cluster-based security architecture for ad hoc networks, in: INFOCOM, 2004; M. Bechler, H.-J. Hof, D. Kraft, F. Pählke, L. Wolf, A cluster-based security architecture for ad hoc networks, in: INFOCOM, 2004
[3] K. Becker, U. Wille, Communication complexity of group key distribution, in: 5th ACM Conference on Computer and Communications Security, Nov. 1998; K. Becker, U. Wille, Communication complexity of group key distribution, in: 5th ACM Conference on Computer and Communications Security, Nov. 1998
[4] C. Blundo, P. D’Arco, M. Listo, A new self-healing key distribution scheme, in: IEEE International Symposium on Computers and Communication, 2003; C. Blundo, P. D’Arco, M. Listo, A new self-healing key distribution scheme, in: IEEE International Symposium on Computers and Communication, 2003
[5] Burmester, M.; Desmedt, Y., A secure and efficient conference key distribution system, (Santis, A., Advances in Cryptology - EUROCRYPT 94. Advances in Cryptology - EUROCRYPT 94, Lecture Notes in Computer Science, vol. 950 (1995), Springer-Verlag: Springer-Verlag Berlin Germany), 275-286 · Zbl 0879.94021
[6] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, B. Pinkas, Multicast security: A taxonomy and efficient constructions, in: INFOCOM’99, vol. 2, New York, USA, Mar. 1999, pp. 708-716; R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, B. Pinkas, Multicast security: A taxonomy and efficient constructions, in: INFOCOM’99, vol. 2, New York, USA, Mar. 1999, pp. 708-716
[7] A.C.-F. Chan, Distributed symmetric key management for mobile ad hoc networks, in: INFOCOM, 2004; A.C.-F. Chan, Distributed symmetric key management for mobile ad hoc networks, in: INFOCOM, 2004
[8] H. Chan, A. Perrig, D. Song, Random key predistribution schemes for sensor networks, in: IEEE Symposium on Security and Privacy, May 2003; H. Chan, A. Perrig, D. Song, Random key predistribution schemes for sensor networks, in: IEEE Symposium on Security and Privacy, May 2003
[9] Diffie, W.; Hellman, M. E., New directions in cryptography, IEEE Transactions on Information Theory, 22, 644-654 (1976) · Zbl 0435.94018
[10] L.R. Dondeti, S. Mukherjee, A. Samal, DISEC: A distributed framework for scalable secure many-to-many communication, in: IEEE Symposium on Computers and Communications, 2000, pp. 693-698; L.R. Dondeti, S. Mukherjee, A. Samal, DISEC: A distributed framework for scalable secure many-to-many communication, in: IEEE Symposium on Computers and Communications, 2000, pp. 693-698
[11] L. Eschenauer, V.D. Gligor, A key-management scheme for distributed sensor networks, in: 9th ACM Conference on Computer and Communication Security, Nov. 2002, pp. 41-47; L. Eschenauer, V.D. Gligor, A key-management scheme for distributed sensor networks, in: 9th ACM Conference on Computer and Communication Security, Nov. 2002, pp. 41-47
[12] A. Fiat, M. Naor, Broadcast encryption, in: Advances in Cryptology — CRYPTO’93, 1993; A. Fiat, M. Naor, Broadcast encryption, in: Advances in Cryptology — CRYPTO’93, 1993
[13] D. Halevy, A. Shamir, The LSD broadcast encryption scheme, in: Advances in Cryptology CRYPTO’02, 2002, pp. 47-60; D. Halevy, A. Shamir, The LSD broadcast encryption scheme, in: Advances in Cryptology CRYPTO’02, 2002, pp. 47-60 · Zbl 1026.94528
[14] Q. Huang, J. Cukier, H. Kobayashi, B. Liu, J. Zhang, Fast authenticated key establishment protocols for self-organizing sensor networks, in: ACM WSNA, 2003; Q. Huang, J. Cukier, H. Kobayashi, B. Liu, J. Zhang, Fast authenticated key establishment protocols for self-organizing sensor networks, in: ACM WSNA, 2003
[15] Ingemarsson, I.; Tang, D.; Wang, C., A conference key distribution system, IEEE Transactions on Information Theory, 28, 714-720 (1982) · Zbl 0488.94021
[16] D. Liu, P. Ning, Establishing pairwise keys in distributed sensor networks, in: ACM CCS’03, 2003; D. Liu, P. Ning, Establishing pairwise keys in distributed sensor networks, in: ACM CCS’03, 2003
[17] D. Liu, P. Ning, K. Sun, Efficient self-healing group key distribution with revocation capability, in: ACM CCS, 2003; D. Liu, P. Ning, K. Sun, Efficient self-healing group key distribution with revocation capability, in: ACM CCS, 2003
[18] W. Lou, W. Liu, Y. Fang, SPREAD: Enhancing data confidentiality in mobile ad hoc networks, in: INFOCOM, 2004; W. Lou, W. Liu, Y. Fang, SPREAD: Enhancing data confidentiality in mobile ad hoc networks, in: INFOCOM, 2004
[19] S. Mittra, Iolus: A framework for scalable secure multicasting, in: ACM SIGCOMM’97, Cannes, France, 1997; S. Mittra, Iolus: A framework for scalable secure multicasting, in: ACM SIGCOMM’97, Cannes, France, 1997
[20] D. Naor, M. Naor, J. Lotspiech, Revocation and tracing schemes for stateless receivers, in: Advances in Cryptology- CRYPTO’01, 2001, pp. 41-62; D. Naor, M. Naor, J. Lotspiech, Revocation and tracing schemes for stateless receivers, in: Advances in Cryptology- CRYPTO’01, 2001, pp. 41-62 · Zbl 1002.94522
[21] A. Perrig, D. Song, D. Tygar, Elk, a new protocol for efficient large-group key distribution, in: IEEE Symposium on Security and Privacy, May 2001; A. Perrig, D. Song, D. Tygar, Elk, a new protocol for efficient large-group key distribution, in: IEEE Symposium on Security and Privacy, May 2001
[22] Rivest, R. L.; Adleman, L.; Dertouzos, M. L., On data banks and privacy homomorphisms, (Foundations of Secure Computation (1978)), 169-179
[23] Safavi-Naini, R.; Wang, H., New Constructions for Multicast Re-keying Schemes Using Perfect Hash Families (2000), ACM Press: ACM Press New York, NY, USA
[24] Sherman, A. T.; McGrew, D. A., Key establishment in large dynamic groups using one-way function trees, IEEE Transactions on Software Engineering, 29, 05, 444-458 (2003)
[25] J. Staddon, S. Miner, M. Franklin, Self-healing key distribution with revocation, in: IEEE Symposium on Security and Privacy, 2002; J. Staddon, S. Miner, M. Franklin, Self-healing key distribution with revocation, in: IEEE Symposium on Security and Privacy, 2002
[26] M. Steiner, G. Tsudik, M. Waidner, Diffie-Hellman key distribution extended to group communication, in: ACM SIGSAC: 3rd ACM Conference on Computer and Communications Security, New Dehli, India, Mar. 1996, pp. 31-37; M. Steiner, G. Tsudik, M. Waidner, Diffie-Hellman key distribution extended to group communication, in: ACM SIGSAC: 3rd ACM Conference on Computer and Communications Security, New Dehli, India, Mar. 1996, pp. 31-37
[27] Steiner, M.; Tsudik, G.; Waidner, M., Cliques: A new approach to group key agreement, IEEE Transactions on Parallel and Distributed Systems, August (2000)
[28] Steiner, M.; Tsudik, G.; Waidner, M., Key agreement in dynamic peer groups, IEEE Transactions on Parallel and Distributed Systems, 11, 8, 769-780 (2000)
[29] Y. Sun, K.J.R. Liu, Scalable hierarchical access control in secure group communications, in: INFOCOM, 2004; Y. Sun, K.J.R. Liu, Scalable hierarchical access control in secure group communications, in: INFOCOM, 2004
[30] Y. Sun, K.J.R. Liu, Securing dynamic membership information in multicast communications, in: INFOCOM, 2004; Y. Sun, K.J.R. Liu, Securing dynamic membership information in multicast communications, in: INFOCOM, 2004
[31] Trappe, W.; Wang, Y.; Liu, K. J.R., Establishment of conference keys in heterogeneous networks, (IEEE International Conference on Communications, vol. 4 (2002)), 2202-2205
[32] G. Tsudik, Y. Kim, A. Perrig, Simple and fault-tolerent key agreement for dynamic collaborative groups, in: ACM CCS, 2000; G. Tsudik, Y. Kim, A. Perrig, Simple and fault-tolerent key agreement for dynamic collaborative groups, in: ACM CCS, 2000
[33] Waldvogel, M.; Caronni, G.; Sun, D.; Weiler, N.; Plattner, B., The VersaKey framework: Versatile group key management, Middleware. Middleware, IEEE Journal on Selected Areas in Communications, 17, 9, 1614-1631 (1999), (special issue)
[34] Wallner, D. M.; Harder, E. J.; Agee, R. C., Key Management for Multicast: Issues and Architectures (1999)
[35] Wong, C. K.; Gouda, M. G.; Lam, S. S., Secure group communications using key graphs, IEEE/ACM Transactions on Networking, 8, 1, 16-30 (2000)
[36] S. Zhu, S. Setia, S. Jajodia, LEAP: Efficient security mechanisms for large-scale distributed sensor networks, in: ACM CCS’03, 2003; S. Zhu, S. Setia, S. Jajodia, LEAP: Efficient security mechanisms for large-scale distributed sensor networks, in: ACM CCS’03, 2003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.