Optimal communication complexity of generic multicast key distribution

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: Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
• 2: Carlo Blundo , Luiz A. Frota Mattos , Douglas R. Stinson, Trade-offs Between Communication and Storage in Unconditionally Secure Schemes for Broadcast Encryption and Interactive Key Distribution, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.387-400, August 18-22, 1996
• 3: Dan Boneh , Glenn Durfee , Matthew K. Franklin, Lower Bounds for Multicast Message Authentication, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.437-452, May 06-10, 2001
• 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: Amos Fiat , Moni Naor, Broadcast encryption, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.480-491, January 1994, Santa Barbara, California, United States
• 14: Eli Gafni , Jessica Staddon , Yiqun Lisa Yin, Efficient Methods for Integrating Traceability and Broadcast Encryption, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.372-387, August 15-19, 1999
• 15: Juan A. Garay , Jessica Staddon , Avishai Wool, Long-Lived Broadcast Encryption, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.333-352, August 20-24, 2000
• 16: Rosario Gennaro, A Protocol to Achieve Independence in Constant Rounds, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.636-647, July 2000 [doi>10.1109/71.877748]
• 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: Dani Halevy , Adi Shamir, The LSD Broadcast Encryption Scheme, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.47-60, August 18-22, 2002
• 19: H. Harney , C. Muckenhirn, Group Key Management Protocol (GKMP) Architecture, RFC Editor, 1997
• 20: H. Harney , C. Muckenhirn, Group Key Management Protocol (GKMP) Specification, RFC Editor, 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: Alan T. Sherman , David A. McGrew, Key Establishment in Large Dynamic Groups Using One-Way Function Trees, IEEE Transactions on Software Engineering, v.29 n.5, p.444-458, May 2003 [doi>10.1109/TSE.2003.1199073]
• 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: 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
• 26: Dalit Naor , Moni Naor , Jeffrey B. Lotspiech, Revocation and Tracing Schemes for Stateless Receivers, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.41-62, August 19-23, 2001
• 27: Moni Naor , Benny Pinkas, Efficient Trace and Revoke Schemes, Proceedings of the 4th International Conference on Financial Cryptography, p.1-20, February 20-24, 2000
• 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: 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
• 30: Rei Safavi-Naini , Huaxiong Wang, New constructions for multicast re-keying schemes using perfect hash families, Proceedings of the 7th ACM conference on Computer and communications security, p.228-234, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352637]
• 31: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 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: Jessica Staddon , Sara Miner , Matt Franklin , Dirk Balfanz , Michael Malkin , Drew Dean, Self-Healing Key Distribution with Revocation, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.241, May 12-15, 2002
• 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. Wallner , E. Harder , R. Agee, Key Management for Multicast: Issues and Architectures, RFC Editor, 1999
• 36: 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]
• 37: Yang Richard Yang , X. Steve Li , X. Brian Zhang , Simon S. Lam, Reliable group rekeying: a performance analysis, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.27-38, August 2001, San Diego, California, United States
• 38: Y. R Yang , Simon S. Lam, A Secure Group Key Management Communication Lower Bound, University of Texas at Austin, Austin, TX, 2000
• 39: Andrew C. Yao, Theory and application of trapdoor functions, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), p.80-91, November 03-05, 1982

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)
      C.2.2 Network Protocols
          Subjects: Routing protocols

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms, Design, Security

Keywords:
key distribution, lower bounds, multicast, nested encryption, secret sharing, security