Cryptology ePrint Archive: Report 2005/373

Efficient Broadcast Encryption Scheme with Log-Key Storage

Yong Ho Hwang and Pil Joong Lee

Abstract: In this paper, we present a broadcast encryption scheme with efficient transmission cost under the \emph{log-key} restriction. Given $n$ users and $r$ revoked users, our scheme has the transmission cost of $O(r)$ and requires the storage of $O(\log n)$ keys at each receiver. These are optimal complexities in broadcast encryptions using one-way hash functions (or pseudo-random generators.) To achieve these complexities, the stratified subset difference (SSD) scheme and the $\overline{B1}$ scheme were introduced by Goodrich et al. and Hwang et al. respectively. However, their schemes have the disadvantage that transmission cost increases linearly according to the number of stratifications. By assigning the related keys between stratifications, our scheme remedies the defect and achieves very efficient transmission cost even in an environment where the key storage is restricted. To the best of our knowledge, our scheme has the most efficient transmission cost in the existing schemes with log-key storage. In addition, our result is comparable to other schemes that allow a large key storage.

Category / Keywords: cryptographic protocols / broadcast encryption, revocation scheme

Date: received 16 Oct 2005, last revised 19 Oct 2005

Contact author: yhhwang at oberon postech ac kr

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20051023:204407 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]