skip to main content
article

Optimal communication complexity of generic multicast key distribution

Published: 01 August 2008 Publication History

Abstract

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 that the amortized cost of updating the group key for each group membership change (as a function of the current group size) is at least log2(n) - o(1) basic rekey messages. This lower bound matches, up to a subconstant additive term, the upper bound due to Canetti et al. [Proc. INFOCOM 1999], who showed that log2(n) basic rekey messages (each time a user joins and/or leaves the group) are sufficient. Our lower bound is, thus, optimal up to a small subconstant additive term. The result of this paper considerably strengthens previous lower bounds by Canetti et al. [Proc. Eurocrypt 1999] and Snoeyink et al. [Computer Networks, 47(3):2005], which allowed for neither the use of pseudorandom generators and secret sharing schemes nor the iterated (nested) application of the encryption function. Our model (which allows for arbitrarily nested combinations of encryption, pseudorandom generators and secret sharing schemes) is much more general and, in particular, encompasses essentially all known multicast key distribution protocols of practical interest.

References

[1]
M. Blum and S. Micali, "How to generate cryptographically strong sequences of pseudo-random bits," SIAM J. Comput., vol. 13, no. 4, pp. 850-864, Nov. 1984.
[2]
C. Blundo, L. A. F. Mattos, and D. R. Stinson, "Trade-offs between communication and storage in unconditionally secure schemes for broadcast encryption and interactive key distribution," in Proc. Adv. Cryptol.--CRYPTO, N. Koblitz, Ed., Aug. 1996, vol. 1109, Lecture Notes in Comput. Sci., pp. 387-400.
[3]
D. Boneh, G. Durfee, and M. Franklin, "Lower bounds for multicast message authentication," in Proc. Adv. Cryptol.--Eurocrypt, B. Pfitzmann, Ed., May 2001, vol. 2045, Lecture Notes in Comput. Sci., pp. 437-452.
[4]
D. Boneh, C. Gentry, and B. Waters, "Collusion resistant broadcast encryption with short ciphertexts and private keys," in Proc. Adv. Cryptol.--CRYPTO, V. Shoup, Ed., Aug. 2005, vol. 3621, Lecture Notes Comput. Sci., pp. 258-275.
[5]
R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas, "Multicast security: A taxonomy and some efficient constructions," in Proc. lNFOCOM, New York, Mar. 1999, vol. 2, pp. 708-716, IEEE.
[6]
R. Canetti, T. Malkin, and K. Nissim, "Efficient communication-storage tradeoffs for multicast encryption," in Proc. Adv. Cryptol.--Eurocrypt, J. Stern, Ed., May 1999, vol. 1592, Lecture Notes Comput. Sci., pp. 495-474.
[7]
I. Chang, R. Engel, D. Kandlur, D. Pen-darakis, and D. Saha, "Key management for secure internet multicast using Boolean function minimization techniques," in Proc. INFOCOM, New York, Mar. 1999, vol. 2, pp. 689-698.
[8]
J. H. Cheon, N. S. Jho, M.-H. Kim, and E. S. Yoo, "Skipping, cascade, and combined chain schemes for broadcast encryption," Cryptology ePrint Archive, Rep. 2005/136, 2005.
[9]
Y. Dodis and N. Fazio, "Public-key broadcast encryption for statless receivers," in Proc. Digit. Rights Manag., Feb. 2002, vol. 2696, Lecture Notes Comput. Sci., pp. 61-80.
[10]
D. Dolev and A. C. Yao, "On the security of public-key protocols," IEEE Trans. Inf. Theory, vol. 29, no. 2, pp. 198-208, Mar. 1983.
[11]
L. R. Dondeti, S. Mukherjee, and A. Samal, "Scalable secure one-to-many group communication using dual encryption," Comput. Commun., vol. 23, no. 17, pp. 1681-1701, Nov. 1999.
[12]
J. Fan, P. Judge, and M. H. Ammar, "Hysor: Group key management with collusion-scalability tradeoffs using a hybrid structuring of receivers," in Proc. IEEE Int. Conf. Comput. Commun. Netw., 2002, pp. 196-201.
[13]
A. Fiat and M. Naor, "Broadcast encryption," in Proc. Adv. Cryptol. --CRYPTO, D. R. Stinson, Ed., Aug. 1993, vol. 773, Lecture Notes Comput. Sci., pp. 480-499.
[14]
E. Gafni, J. Staddon, and Y. L. Yin, "Efficient methods for integrating traceability and broadcast encryption," in Proc. Adv. Cryptol.--CRYPTO, M. Wiener, Ed., Aug. 1999, vol. 1666, Lecture Notes Comput. Sci., pp. 372-387.
[15]
J. Garay, J. Staddon, and A. Wool, "Long-lived broadcast encryption," in Proc. Adv. Cryptol.--CRYPTO, M. Bellare, Ed., Aug. 2000, vol. 1880, Lecture Notes Comput. Sci., pp. 333-352.
[16]
R. Gennaro, "A protocol to achieve independence in constant rounds," IEEE Trans, Parallel Distrib. Syst., vol. ll, no. 7, pp. 636-647, Jul. 2000.
[17]
M. Goodrich, J. Sun, and R. Tamassia, "Efficient tree-based revocation in groups of low-state devices," in Proc. Adv. Cryptol.--CRYPTO, M. Franklin, Ed., Aug. 2004, vol. 3152, Lecture Notes Comput. Sci., pp. 511-527.
[18]
D. Halevy and A. Shamir, "The LSD broadcast encryption scheme," in Proc. Adv. Cryptol.--CRYPTO, M. Yung, Ed., Aug. 2002, vol. 2442, Lecture Notes Comput. Sci., pp. 47-60.
[19]
H. Harney and C. Muckenhirn, "Group key management protocol GKMP architecture," Request for Comments 2094, Jul. 1997.
[20]
H. Harney and C. Muckenhirn, "Group key management protocol GKMP specification," Request for Comments 2093, Jul. 1997.
[21]
M. Luby and J. Staddon, "Combinatorial bounds for broadcast encryption," in Proc. Adv. Cryptol.--Eurocrypt, K. Nyberg, Ed., May 1998, vol. 1403, Lecture Notes Comput. Sci., pp. 512-526.
[22]
D. A. McGrew and A. T. Sherman, "Key establishment in large dynamic groups using one-way function trees," IEEE Trans. Software Eng., vol. 29, no. 5, pp. 444-458, May 2003.
[23]
D. Micciancio and S. Panjwani, "Optimal communication complexity of generic multicast key distribution," in Proc. Adv. Cryptol.--Eurocrypt , C. Cachin and J. Camenisch, Eds., May 2-6, 2004, vol. 3027, Lecture Notes Comput. Sci., pp. 153-170.
[24]
D. Micciancio and S. Panjwani, "Corrupting one versus corrupting many: The case of broadcast and multicast encryption," in Proc. 33rd Int. Colloq. Automata, Languages and Programming, Venice, Italy, Jul. 2006, vol. 2, pp. 70-82.
[25]
S. Mittra, "Iolus: A framework for scalable secure multicasting," in Proc. ACM SIGCOMM, New York, 1997, vol. 27, pp. 277-288.
[26]
D. Naor, M. Naor, and J. Lotspiech, "Revocation and tracing schemes for stateless receivers," in Proc. Adv. Cryptol.--CRYPTO, J. Kilian, Ed., Aug. 2001, vol. 2139, Lecture Notes Comput. Sci., pp. 41-62.
[27]
M. Naor and B. Pinkas, "Efficient trace and revoke schemes," in Proc. 4th Int. Conf. Financial Cryptogr., London, U.K., 2000, pp. 1-20.
[28]
A. Perrig, R. Canetti, D. Song, and D. Tygar, "Efficient and secure source authentication for multicast," in Proc. Netw. Distrib. Syst. Security Symp., Feb. 2001, pp. 35-36.
[29]
A. Perrig, D. Song, and D. Tygar, "Elk, a new protocol for efficient large-group key distribution," in Proc. IEEE Symp. Security and Privacy , Oakland, CA, May 2001, pp. 247-262.
[30]
R. Safavi-Naini and H. Wang, "New constructions for multicast re-keying schemes using perfect hash families," in Proc. 7th ACM Conf. Comput. Commun. Security, Athens, Greece, Nov. 2000, pp. 228-234.
[31]
A. Shamir, "How to share a secret," Commun. ACM, vol. 22, no. 11, pp. 612-613, Nov. 1979.
[32]
J. Snoeyink, S. Suri, and G. Varghese, "A lower bound for multicast key distribution," Comput. Netw., vol. 47, no. 3, pp. 429-441, 2005.
[33]
J. Staddon, S. Miner, M. Franklin, D. Balfanz, M. Malkin, and D. Dean, "Self-healing key distribution with revocation," in Proc. IEEE Symp. Security Privacy, Washington, DC, 2002, pp. 241-257.
[34]
R. Tamassia and N. Triandopoulos, "Computational bounds on hierarchical data processing with applications to information security," in Proc. 32nd Int. Colloq. Automata, Languages and Programming , Berlin, Germany, Jul. 2-6, 2005, vol. 3580, pp. 153-165, Springer-Verlag.
[35]
D. M. Wallner, E. G. Harder, and R. C. Agee, "Key management for multicast: Issues and architecture," Request for Comments 2627, Jun. 1999.
[36]
C. K. Wong, M. Gouda, and S. S. Lam, "Secure group communications using key graphs," IEEE/ACM Trans. Netw., vol. 8, no. 1, pp. 16-30, Feb. 2000.
[37]
R. Yang, X. Li, X. Zhang, and S. S. Lam, "Reliable group rekeying: A performance analysis," in Proc. ACM SIGCOMM, Aug. 2001, pp. 27-38.
[38]
Y. R. Yang and S. S. Lam, "A secure group key management protocol communication lower bound," Tech. Rep. TR-00-24, 2000.
[39]
A. C. Yao, "Theory and applications of trapdoor functions," in Proc. 23rd Annu. Symp. Foundations Comput. Sci., Chicago, IL, Nov. 3-5, 1982, pp. 80-91.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 4
August 2008
249 pages

Publisher

IEEE Press

Publication History

Published: 01 August 2008
Received: 13 September 2006
Published in TON Volume 16, Issue 4

Author Tags

  1. key distribution
  2. lower bounds
  3. multicast
  4. nested encryption
  5. secret sharing
  6. security

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)A location-updating based self-healing group key management scheme for VANETsInternational Journal of Information Security10.1007/s10207-024-00937-624:1Online publication date: 5-Nov-2024
  • (2019)Group key management with efficient rekey mechanismComputer Communications10.1016/j.comcom.2016.08.00198:C(31-42)Online publication date: 5-Jan-2019
  • (2019)Symbolic Encryption with Pseudorandom KeysAdvances in Cryptology – EUROCRYPT 201910.1007/978-3-030-17659-4_3(64-93)Online publication date: 19-May-2019
  • (2017)Group Rekeying in the Exclusive Subset-Cover FrameworkTheoretical Computer Science10.1016/j.tcs.2017.03.046678:C(63-77)Online publication date: 23-May-2017
  • (2013)A novel batch-based group key management protocol applied to the Internet of ThingsAd Hoc Networks10.1016/j.adhoc.2013.05.00911:8(2724-2737)Online publication date: 1-Nov-2013
  • (2010)Optimizing the batch mode of group rekeyingProceedings of the 29th conference on Information communications10.5555/1833515.1833767(1846-1854)Online publication date: 14-Mar-2010
  • (2010)Computational soundness, co-induction, and encryption cyclesProceedings of the 29th Annual international conference on Theory and Applications of Cryptographic Techniques10.1007/978-3-642-13190-5_19(362-380)Online publication date: 30-May-2010
  • (2006)Corrupting one vs. corrupting manyProceedings of the 33rd international conference on Automata, Languages and Programming - Volume Part II10.1007/11787006_7(70-82)Online publication date: 10-Jul-2006

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media