Abstract
Broadcast encryption schemes allow a message sender to broadcast an encrypted data so that only legitimate receivers decrypt it. Because of the intrinsic nature of one-to-many communication in broadcasting, transmission length may be of major concern. Several broadcast encryption schemes with good transmission overhead have been proposed. But, these broadcast encryption schemes are not practical since they are greatly sacrificing performance of other efficiency parameters to achieve good performance in transmission length.
In this paper we study a generic transformation method which transforms any broadcast encryption scheme to one suited to desired application environments while preserving security. Our transformation reduces computation overhead and/or user storage by slightly increasing transmission overhead of a given broadcast encryption scheme. We provide two transformed instances. The first instance is comparable to the results of the “stratified subset difference (SSD)” technique by Goodrich et al. and firstly achieves \(\mathcal{O}(log n)\) storage, \(\mathcal{O}(log n)\) computation, and \(\mathcal{O}(\frac{log n}{log log n}r)\) transmission, at the same time, where n is the number of users and r is the number of revoked users. The second instance outperforms the “one-way chain based broadcast encryption” of Jho et al., which is the best known scheme achieving less than r transmission length with reasonable communication and storage overhead.
This research was supported by the MIC(Ministry of Information and Communication), Korea, under the ITRC(Information Technology Research Center) support program supervised by the IITA(Institute of Information Technology Assessment).
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Asano, T.: A Revocation Scheme with Minimal Storage at Receivers. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 433–450. Springer, Heidelberg (2002)
Attrapadung, N., Kobara, K., Imai, H.: ACM Workshop on Digital Rights Management 2003. In: ACM Workshop on Digital Rights Management 2003, pp. 55–66 (2003)
Anzai, J., Matsuzaki, N., Matsumoto, T.: Quick Group Key Distribution Scheme with Entity Revocation. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 333–347. Springer, Heidelberg (1999)
Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A Concrete Security Treatment of Symmetric Encryption: Analysis of the DES Modes of Operation. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science - FOCS 1997, pp. 394–403 (1997)
Boneh, D., Gentry, C., Waters, B.: Collusion Resistant Broadcst Encryption With Short Ciphertexts and Private Keys. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 258–275. Springer, Heidelberg (2005)
Boneh, D., Silverberg, A.: Applications of Multilinear Forms to Cryptography (2002), Available from http://eprint.iacr.org
Dolev, D., Dwork, C., Naor, M.: Pinkas Nonmalleable Cryptography. SIAM Journal on Discrete Mathematics 30(2), 391–437 (2000)
Fiat, A., Naor, M.: Broadcast encryption. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 480–491. Springer, Heidelberg (1994)
Goodrich, M.T., Sun, J.Z., Tamassia, R.: Efficient Tree-Based Revocation in Groups of Low-State Devices. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 511–527. Springer, Heidelberg (2004)
Garay, J.A., Staddon, J., Wool, A.: Long-Lived Broadcast Encryption. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 333–352. Springer, Heidelberg (2000)
Gafni, E., Staddon, J., Yin, Y.L.: Efficient Methods for Integrating Traceability and Broadcast Encryption. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 372–387. Springer, Heidelberg (1999)
Horwitz, J.: A Survey of Broadcast Encryption (2003) (manuscript)
Halevy, D., Shamir, A.: The LSD Broadcast Encryption Scheme. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 41–60. Springer, Heidelberg (2002)
Jho, N.-S., Hwang, J.Y., Cheon, J.H., Kim, M., Lee, D.H., Yoo, E.S.: One-way chain Based Broadcast Encryption Scheme. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 559–574. Springer, Heidelberg (2005)
Naor, M., Pinkas, B.: Efficient Trace and Revoke Scheme. In: Frankel, Y. (ed.) FC 2000. LNCS, vol. 1962, pp. 1–20. Springer, Heidelberg (2001)
Naor, D., Naor, M., Lotspiech, J.: Revocation and Tracing Schemes for Stateless Receivers. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 41–62. Springer, Heidelberg (2001)
Stinson, D.R., Trung, T.V.: Some New Results on Key Distribution Patterns and Broadcast Encryption. Designs, Codes and Cryptography 14(3), 261–279 (1998)
Stinson, D.R., Wei, R.: Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes. SIAM Journal on Discrete Mathematics 11(1), 41–53 (1998)
Wallner, D.M., Harder, E.G., Agee, R.C.: Key Agreement for Multicast: Issues and Architecture (September 1998), In internet draft draft-waller-key-arch-01.txt
Wong, C.K., Lam, S.S.: Digital Signatures for Flows and Multicasts. IEEE/ACM Transactions on Networking 7(4), 502–513 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hwang, J.Y., Lee, D.H., Lim, J. (2005). Generic Transformation for Scalable Broadcast Encryption Schemes. In: Shoup, V. (eds) Advances in Cryptology – CRYPTO 2005. CRYPTO 2005. Lecture Notes in Computer Science, vol 3621. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11535218_17
Download citation
DOI: https://doi.org/10.1007/11535218_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28114-6
Online ISBN: 978-3-540-31870-5
eBook Packages: Computer ScienceComputer Science (R0)