Cryptology ePrint Archive: Report 2005/136

Skipping, Cascade, and Combined Chain Schemes for Broadcast Encryption

Jung Hee Cheon and Nam-su Jho and Myung-Hwan Kim and Eun Sun Yoo

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.

Category / Keywords: applications / Broadcast encryption, Revocation, One-way key chain, Skipping chain, Cascade chain, Combined chain

Publication Info: An old version of a part of this paper appeared in Eurocrypt'05.

Date: received 11 May 2005, last revised 13 May 2005

Contact author: eunsun at math snu ac kr

Available format(s): PDF | BibTeX Citation

Version: 20050513:062600 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]