Broadcast encryption with short keys and transmissions

ABSTRACT

Broadcast Encryption allows a broadcaster to broadcast an encrypted message so that only a dynamically changing designated group of users can decrypt it. The stateless setting considers the case where the private key at each user is never updated. A central open problem in this area is to design a stateless scheme where both the size of transmission header which encapsulates the session key and the size of private key at each user are small and independent of the number of users (all/privileged/revoked users). We propose schemes that meet this requirement by providing a tradeoff between security against collusion and non-secret storage size. The proposed schemes are based upon new notions of one-way accumulators which are of independent interest.

REFERENCES

• 1: Tomoyuki Asano, A Revocation Scheme with Minimal Storage at Receivers, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.433-450, December 01-05, 2002
• 2: N. Attrapadung, K. Kobara, H. Imai, "Sequential Key Derivation Patterns for Broadcast Encryption and Key Predistribution Schemes", ASIACRYPT 2003, To appear.
• 3: Jun Anzai , Natsume Matsuzaki , Tsutomu Matsumoto, A Quick Group Key Distribution Scheme with "Entity Revocation", Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.333-347, November 14-18, 1999
• 4: Selim G. Akl , Peter D. Taylor, Cryptographic solution to a problem of access control in a hierarchy, ACM Transactions on Computer Systems (TOCS), v.1 n.3, p.239-248, August 1983 [doi>10.1145/357369.357372]
• 5: C. Blundo and A. Cresti. "Space Requirements for Broadcast Encryption", EUROCRYPT 1994, LNCS 950, pp. 287--298.
• 6: Josh Benaloh , Michael de Mare, One-way accumulators: a decentralized alternative to digital signatures, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.274-285, January 1994, Lofthus, Norway
• 7: Carlo Blundo , Luiz A. Frota Mattos , Douglas R. Stinson, Trade-offs Between Communication and Storage in Unconditionally Secure Schemes for Broadcast Encryption and Interactive Key Distribution, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.387-400, August 18-22, 1996
• 8: N. Baric and B. Pfitzmann,"Collision-free accumulators and fail-stop signature schemes without trees", EUROCRYPT 1997, LNCS 1233, pp. 480--494.
• 9: D. Boneh and A. Silverberg, "Applications of Multilinear Forms to Cryptography", 2002. Available from http://eprint.iacr.org.
• 10: Benny Chor , Amos Fiat , Moni Naor, Tracing Traitors, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.257-270, August 21-25, 1994
• 11: Jan Camenisch , Anna Lysyanskaya, Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.61-76, August 18-22, 2002
• 12: Ronald Cramer , Victor Shoup, Signature schemes based on the strong RSA assumption, ACM Transactions on Information and System Security (TISSEC), v.3 n.3, p.161-185, Aug. 2000 [doi>10.1145/357830.357847]
• 13: Gerald C. Chick , Stafford E. Tavares, Flexible access control with master keys, Proceedings on Advances in cryptology, p.316-322, July 1989, Santa Barbara, California, United States
• 14: Y. Dodis and N.Fazio, "Public Key Broadcast Encryption for Stateless Receivers", ACM Workshop on Digital Rights Management, November 2002.
• 15: Yevgeniy Dodis , Nelly Fazio, Public Key Trace and Revoke Scheme Secure against Adaptive Chosen Ciphertext Attack, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.100-115, January 06-08, 2003
• 16: Yevgeniy Dodis , Nelly Fazio , Aggelos Kiayias , Moti Yung, Scalable public-key tracing and revoking, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.190-199, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872062]
• 17: Amos Fiat , Moni Naor, Broadcast encryption, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.480-491, January 1994, Santa Barbara, California, United States
• 18: Craig Gentry , Alice Silverberg, Hierarchical ID-Based Cryptography, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.548-566, December 01-05, 2002
• 19: Eli Gafni , Jessica Staddon , Yiqun Lisa Yin, Efficient Methods for Integrating Traceability and Broadcast Encryption, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.372-387, August 15-19, 1999
• 20: 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
• 21: 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
• 22: Kaoru Kurosawa , Takuya Yoshida , Yvo Desmedt , Mike Burmester, Some Bounds and a Construction for Secure Broadcast Encryption, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.420-433, October 18-22, 1998
• 23: M. Luby, J. Staddon, "Combinatorial Bounds for Broadcast Encryption", EUROCRYPT 1998, LNCS 1403, pp. 512--526.
• 24: C. J. Mitchell , F. C. Piper, Key storage in secure networks, Discrete Applied Mathematics, v.21 n.3, p.215-228, October 1988 [doi>10.1016/0166-218X(88)90068-6]
• 25: 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
• 26: 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
• 27: Doug R. Stinson, On Some Methods for Unconditionally Secure Key Distributionand Broadcast Encryption, Designs, Codes and Cryptography, v.12 n.3, p.215-243, Nov. 1997 [doi>10.1023/A:1008268610932]
• 28: Chung Kei Wong , Mohamed Gouda , Simon S. Lam, Secure group communications using key graphs, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.68-79, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 29: D. Wallner, E. Harder and R. Agee, "Key Management for Multicast: Issues and Architectures", IETF NetworkWorking Group, Request for Comments: 2627, available from ftp://ftp.ietf.org/rfc/rfc2627.txt, 1999.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Access controls; Cryptographic controls

General Terms:
Security, Theory

Keywords:
broadcast encryption, constant transmission rate, copyright protection, one-way accumulators, revocation scheme