Optimal Communication Complexity of Generic Multicast Key Distribution
Authors:
- 31 March 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 16 (4) , 803-813
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, pseudorandom 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.Keywords
This publication has 21 references indexed in Scilit:
- A lower bound for multicast key distributionComputer Networks, 2005
- Optimal Communication Complexity of Generic Multicast Key DistributionLecture Notes in Computer Science, 2004
- Key establishment in large dynamic groups using one-way function treesIEEE Transactions on Software Engineering, 2003
- Scalable secure one-to-many group communication using dual encryptionComputer Communications, 2000
- A protocol to achieve independence in constant roundsIEEE Transactions on Parallel and Distributed Systems, 2000
- Secure group communications using key graphsIEEE/ACM Transactions on Networking, 2000
- IolusACM SIGCOMM Computer Communication Review, 1997
- How to Generate Cryptographically Strong Sequences of Pseudorandom BitsSIAM Journal on Computing, 1984
- On the security of public key protocolsIEEE Transactions on Information Theory, 1983
- How to share a secretCommunications of the ACM, 1979