International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Skipping, Cascade, and Combined Chain Schemes for Broadcast Encryption

Jung Hee Cheon
Nam-su Jho
Myung-Hwan Kim
Eun Sun Yoo
Search ePrint
Search Google
Abstract: We develop a couple of new methods to reduce transmission overheads in broadcast encryption. The methods are based on the idea of assigning {\it one key per each partition using one-way key chains} after partitioning the users. One method adopts {\it skipping chains} on partitions containing up to $p$ revoked users and the other adopts {\it cascade chains} on partitions with layer structure. The scheme using the former reduces the transmission overhead down to $\frac r{p+1}$ asymptotically as $r$ grows, and the scheme using the latter keeps the transmission overhead very small when $r$ approaches 0, where $r$ is the number of revoked users. Combining the two schemes, we propose a new broadcast encryption scheme with least transmission overhead. Our schemes also possess a remarkable feature that any number of new users can join at any time without key update, which is not available for most of known practical schemes.
  title={Skipping, Cascade, and Combined Chain Schemes for Broadcast Encryption},
  booktitle={IACR Eprint archive},
  keywords={applications / Broadcast encryption, Revocation, One-way key chain, Skipping chain, Cascade chain, Combined chain},
  note={An old version of a part of this paper appeared in Eurocrypt'05. 12916 received 11 May 2005, last revised 13 May 2005},
  author={Jung Hee Cheon and Nam-su Jho and Myung-Hwan Kim and Eun Sun Yoo},