New broadcast encryption scheme using tree-based circle

ABSTRACT

Since broadcast encryption was first introduced in 1993 by Fiat and Naor, many broadcast encryption schemes have been developed. Among these, schemes based on tree structure and linear structure are notable. The subset difference (SD) scheme and layered subset difference (LSD) scheme based on tree structure have small user-key size and small transmission overhead when the number r of revoked users is very small. The punctured interval (PI) scheme based on linear (or circular) structure has better transmission overhead when r is not too small.In this paper, we propose a new broadcast encryption scheme, called the tree-based circle (TC) scheme, combining tree structure and circular structure. In this scheme, the transmission overhead is proportional to r like in the SD scheme for small r and becomes asymptotically same as that of the PI scheme when r grows, keeping the computation cost and the storage size small. The TC scheme also inherits the flexibility of the PI scheme. We further improve the transmission overhead of the TC scheme, when r is very small, by adopting the notion of cascade arc.

REFERENCES

• 1: J. H. Cheon, N.-S. Jho, M.-H. Kim, and E. S. Yoo. Skipping, Cascade, and Combined Chain Schemes for Broadcast Encryption. In http://eprint.iacr.org/2005/136, 2005
• 2: Amos Fiat , Moni Naor, Broadcast Encryption, Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology, p.480-491, August 22-26, 1993
• 3: M. Goodrich, J. Sun, and R. Tamassia. Efficient tree-based revocation in groups of low-state devices. In Advances in Cryptology - Crypto'04, Lecture Notes in Computer Science 3152, pages 511--527, 2004.
• 4: Dani Halevy , Adi Shamir, The LSD Broadcast Encryption Scheme, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.47-60, August 18-22, 2002
• 5: N.-S. Jho, J. Y. Hwang, J. H. Cheon, M.-H. Kim, D. H. Lee, and E. S. Yoo. One-way chain based broadcast encryption schemes. In Advances in Cryptology - Eurocrypt'05, Lecture Notes in Computer Science 3494, pages 559--574, 2005.
• 6: Ravi Kumar , Sridhar Rajagopalan , Amit Sahai, Coding Constructions for Blacklisting Problems without Computational Assumptions, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.609-623, August 15-19, 1999
• 7: Dalit Naor , Moni Naor , Jeffrey B. Lotspiech, Revocation and Tracing Schemes for Stateless Receivers, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.41-62, August 19-23, 2001
• 8: Moni Naor , Benny Pinkas, Efficient Trace and Revoke Schemes, Proceedings of the 4th International Conference on Financial Cryptography, p.1-20, February 20-24, 2000

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Design, Security

Keywords:
broadcast encryption, cascade, punctured interval, tree structure