A fully collusion resistant broadcast, trace, and revoke system

ABSTRACT

We introduce a simple primitive called Augmented Broadcast Encryption (ABE) that is sufficient for constructing broadcast encryption, traitor-tracing, and trace-and-revoke systems. These ABE-based constructions are resistant to an arbitrary number of colluders and are secure against adaptive adversaries. Furthermore, traitor tracing requires no secrets and can be done by anyone. These broadcast systems are designed for broadcasting to arbitrary sets of users. We then construct a secure ABE system for which the resulting concrete trace-and-revoke system has ciphertexts and private keys of size √N where N is the total number of users in the system. In particular, this is the first example of a fully collusion resistant broadcast system with sub-linear size ciphertexts and private keys that is secure against adaptive adversaries. The system is publicly traceable.

REFERENCES

• 1: 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
• 2: Omer Berkman , Michal Parnas , Jiři Sgall, Efficient dynamic traitor tracing, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.586-595, January 09-11, 2000, San Francisco, California, United States
• 3: Dan Boneh , Matthew K. Franklin, An Efficient Public Key Traitor Tracing Scheme, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.338-353, August 15-19, 1999
• 4: Dan Boneh, Craig Gentry, and Brent Waters. Collusion resistant broadcast encryption with short ciphertexts and private keys. In CRYPTO '05, pages 258--275, 2005.
• 5: Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. Evaluating 2-dnf formulas on ciphertexts. In Joe Kilian, editor, Proceedings of Theory of Cryptography Conference 2005, volume 3378 of LNCS, pages 325--342. Springer, 2005.
• 6: Dan Boneh, Amit Sahai, and Brent Waters. Fully collusion resistant traitor tracing with short ciphertexts and private keys. In Eurocrypt '06, 2006.
• 7: Dan Boneh and Alice Silverberg. Applications of multilinear forms to cryptography. Contemporary Mathematics, 324:71--90, 2003.
• 8: Ran Canetti, Shai Halevi, and Jonathan Katz. Chosen-ciphertext security from identity-based encryption. In Proceedings of Eurocrypt 2004, LNCS, pages 207--222, 2004.
• 9: Hervé Chabanne, Duong Hieu Phan, and David Pointcheval. Public traceability in traitor tracing schemes. In EUROCRYPT '05, pages 542--558, 2005.
• 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: Benny Chor, Amos Fiat, Moni Naor, and Benny Pinkas. Tracing traitors. IEEE Transactions on Information Theory, 46(3): 893--910, 2000.
• 12: Yevgeniy Dodis and Nelly Fazio. Public key broadcast encryption for stateless receivers. In Proceedings of the Digital Rights Management Workshop 2002, volume 2696 of LNCS, pages 61--80. Springer, 2002.
• 13: 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
• 14: Yevgeniy Dodis , Nelly Fazio , Aggelos Kiayias , Moti Yung, Scalable public-key tracing and revoking, Distributed Computing, v.17 n.4, p.323-347, May 2005 [doi>10.1007/s00446-004-0120-5]
• 15: 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
• 16: Amos Fiat , Tamir Tassa, Dynamic Traitor Training, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.354-371, August 15-19, 1999
• 17: 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
• 18: Juan A. Garay , Jessica Staddon , Avishai Wool, Long-Lived Broadcast Encryption, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.333-352, August 20-24, 2000
• 19: M. T. Goodrich, J. Z. Sun, , and R. Tamassia. Efficient tree-based revocation in groups of low-state devices. In Proceedings of Crypto '04, volume 2204 of LNCS, 2004.
• 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: Aggelos Kiayias , Moti Yung, On Crafty Pirates and Foxy Tracers, Revised Papers from the ACM CCS-8 Workshop on Security and Privacy in Digital Rights Management, p.22-39, November 05, 2001
• 22: Aggelos Kiayias and Moti Yung. Breaking and repairing asymmetric public-key traitor tracing. In Joan Feigenbaum, editor, ACM Workshop in Digital Rights Management -- DRM 2002, volume 2696 of Lecture Notes in Computer Science, pages pp. 32--50. Springer, 2002.
• 23: K. Kurosawa and Y. Desmedt. Optimum traitor tracing and asymmetric schemes. In Proceedings of Eurocrypt '98, pages 145--157, 1998.
• 24: 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
• 25: 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
• 26: Moni Naor , Benny Pinkas, Threshold Traitor Tracing, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.502-517, August 23-27, 1998
• 27: Birgit Pfitzmann, Trials of Traced Traitors, Proceedings of the First International Workshop on Information Hiding, p.49-64, May 30-June 01, 1996
• 28: Birgit Pfitzmann , Michael Waidner, Asymmetric fingerprinting for larger collusions, Proceedings of the 4th ACM conference on Computer and communications security, p.151-160, April 01-04, 1997, Zurich, Switzerland [doi>10.1145/266420.266453]
• 29: Reihaneh Safavi-Naini , Yejing Wang, Sequential Traitor Tracing, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.316-332, August 20-24, 2000
• 30: Alice Silverberg , Jessica Staddon , Judy L. Walker, Efficient Traitor Tracing Algorithms Using List Decoding, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.175-192, December 09-13, 2001
• 31: Jessica N. Staddon, Douglas R. Stinson, and Ruizhong Wei. Combinatorial properties of frameproof and traceability codes. Cryptology ePrint 2000/004, 2000.
• 32: D. R. Stinson , R. Wei, Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes, SIAM Journal on Discrete Mathematics, v.11 n.1, p.41-53, Feb. 1998 [doi>10.1137/S0895480196304246]
• 33: Douglas R. Stinson , R. Wei, Key Preassigned Traceability Schemes for Broadcast Encryption, Proceedings of the Selected Areas in Cryptography, p.144-156, August 17-18, 1998
• 34: D. R. Stinson , R. Wei, Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes, SIAM Journal on Discrete Mathematics, v.11 n.1, p.41-53, Feb. 1998 [doi>10.1137/S0895480196304246]
• 35: 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]
• 36: Doug R. Stinson , Tran Van Trung, Some New Results on Key Distribution Patterns and BroadcastEncryption, Designs, Codes and Cryptography, v.14 n.3, p.261-279, Sept. 1998 [doi>10.1023/A:1008209004667]
• 37: Wen-Guey Tzeng , Zhi-Jia Tzeng, A Public-Key Traitor Tracing Scheme with Revocation Using Dynamic Shares, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.207-224, February 13-15, 2001
• 38: Yuji Watanabe , Goichiro Hanaoka , Hideki Imai, Efficient Asymmetric Public-Key Traitor Tracing without Trusted Agents, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.392-407, April 08-12, 2001

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security