Thomas Martin (2005) A set theoretic approach to broadcast encryption .
Full text access: Open
Broadcast Encryption allows a centre to send information over a broadcast channel to a dynamically changing group of users. The performance is rated by the bandwidth required for the broadcast and the amount of secret information needed to be stored at the user end. It can also be rated by the computational overhead. In the "Stateless Receiver" model, receivers are incapable of storing any new information, or updating themselves, between broadcasts. We look at two Stateless Receiver schemes by Naor et al., the Complete Subtree Revocation Scheme and the Subset Difference Revocation Scheme. We improve the bound on the bandwidth for the Complete Subtree Revocation Scheme given by Naor from t_{max}(n,r) \leq r(k - log_2(r)) to t_{max}(n,r) = r(k - j) - 2(r - 2^j), where j = \lfloor log_2(r)\rfloor. We prove a similar bound on the maximum bandwidth for the Subset Difference Revocation Scheme. We also derive formula for the average bandwidth for both schemes. The schemes of Naor et al. are each based on a single binary tree. We construct some variations of the Complete Subtree Revocation Scheme, the first has more than one tree, the other is based on an \alpha-ary tree. We calculate the improved performance in bandwidth (traded off against an increase in storage). We make meaningful comparisons between these schemes and existing ones. Finally, we show how to reduce the storage requirement of the Complete Subtree Revocation Scheme from O(log_2(n)) to a constant term.
This is a Published version This version's date is: 05/04/2005 This item is peer reviewed
https://repository.royalholloway.ac.uk/items/20fae6e4-7ec9-fac7-6bae-81f3f97d3988/1/
Deposited by () on 13-Jul-2010 in Royal Holloway Research Online.Last modified on 13-Dec-2010
[1] Tomoyuki Asano. A revocation scheme with minimal storage at receivers.Proceedings of the 8th International Conference on the Theory and Appli-cation of Cryptology and Information Security: Advances in Cryptology,3108:433{450, 2002.
[2] Tomoyuki Asano. Reducing storage at receivers in sd and lsd broadcastencryption schemes. Information Security Applications, 4th InternationalWorkshop, WISA, pages 317{332, 2004.
[3] Tomoyuki Asano. Secure and insecure modi¯cations of the subset dif-ference broadcast encryption scheme. Information Security and Privacy:9th Australasian Conference, ACISP 2004, pages 12{23, 2004.
[4] Nuttapong Attrapadung, Kazukuni Kobara, and Hideki Imai. Sequentialkey derviation patterns for broadcast encryption and key predistributionschemes. Advances in Cryptology - ASIACRYPT 2003: 9th InternationalConference on the Theory and Application of Cryptology and InformationSecurity, pages 374{391, 2003.
[5] S. Berkovits. How to broadcast a secret. Advances in Cryptology -CRYPTO '91, Lecture Notes in Computer Science, 547:536{541, 1991.
[6] G. R. Blakley. Safeguarding cryptographic keys. Proceedings of the AFIPS1979 National Computer Conference, 48:313{317, 1979.
[7] R. Blom. An optimal class of symmetric key generation systems. Proc.of the EUROCRYPT 84 workshop on Advances in cryptology: theory andapplication of cryptographic techniques, pages 335{338, 1985.
[8] Weifeng Chen and Lakshminath R. Dondeti. Performance comparison ofstateful and stateless group rekeing algorithms. Proc. of Fourth Interna-tional Workshop on Networked Group Communication, NGC, 2002.
[9] Benny Chor, Amos Fiat, and Moni Naor. Tracing traitors. Lecture Notesin Computer Science, 839:257{270, 1994.
[10] E. J. Harder D. M. Wallner and R. C. Agee. Key management for mul-ticast: Issues and architectures. IETF, RFC 2627, 1997.
[11] Paolo D'Arco and Douglas R. Stinson. Fault tolerant and distributedbroadcast encryption. CT-RSA 2003, Lecture Notes in Computer Science,2612:263{280, 2003.
[12] Yevgeniy Dodis and Nelly Fazio. Public key broadcast encryption forstateless receivers. ACM Workshop on Digital Rights Management, Lec-ture Notes in Computer Science, 2696:61{80, 2002.
[13] Amos Fiat and Moni Naor. Broadcast encryption. Advances in Cryptology- CRYPTO '93, Lecture Notes in Computer Science, 773:480{491, 1994.
[14] Amos Fiat and Tamir Tassa. Dynamic traitor tracing. Journal of Cryptol-ogy: the journal of the International Association for Cryptologic Research,14(3):211{223, 2001.
[15] Juan A. Garay, Jessica Staddon, and Avishai Wool. Long-lived broadcastencryption. Lecture Notes in Computer Science, 1880:333{352, 2000.
[16] Dani Halevy and Adi Shamir. The LSD broadcast encryption scheme. Ad-vances in Cryptology - CRYPTO '02, Lecture Notes in Computer Science,2442:47{60, 2002.
[17] Kurosawa, Yoshida, Desmedt, and Burmester. Some bounds and a con-struction for secure broadcast encryption. In ASIACRYPT: Advances inCryptology { ASIACRYPT: International Conference on the Theory andApplication of Cryptology. LNCS, Springer-Verlag, 1998.
[18] Xiaozhou Steve Li, Yang Richard Yang, Mohamed G. Gouda, and Si-mon S. Lam. Batch rekeying for secure group communications. In Pro-ceedings of the tenth international World Wide Web conference on WorldWide Web, pages 525{534, Orlando, FL USA, 2001.
[19] Michael Luby and Jessica Staddon. Combinatorial bounds for broadcastencryption. Advances in Cryptology - EUROCRYPT '98, Lecture Notesin Computer Science, 1403:512{526, 1998.
[20] T. Matsumoto and H. Imai. On the key predistribution system: A prac-tical solution to the key distribution problem. Advances in Cryptology -CRYPTO '87, Lecture Notes in Computer Science, 293:185{193, 1987.
[21] Miodrag J. Mihaljevic. Key management schemes for stateless receiversbased on time varying heterogeneous logical key hierarchy. Lecture Notesin Computer Science, 2894:127{154, 2003.
[22] Dalit Naor and Moni Naor. Protecting cryptographic keys: The trace-and-revoke approach. IEEE Computer, 36:47{53, 2003.
[23] Dalit Naor, Moni Naor, and Je® Lotspiech. Revocation and tracingschemes for stateless receivers. Advances in Cryptology - CRYPTO '01,Lecture Notes in Computer Science, 2139:41{62, 2001.
[24] Moni Naor and Benny Pinkas. E±cient trace and revoke schemes. Fi-nancial Cryptography: 4th International Conference, Lecture Notes inComputer Science, 1962:1+, 2001.
[25] Carles Padro, Ignacio Gracia, Sebastia Martin, and Paz Morillo. Linearkey predistribution schemes. Designs, Codes and Cryptography, 25:281{298, 2002.
[26] Carles Padro, Ignacio Gracia, Sebastia Martin, and Paz Morillo. Linearbroadcast encryption schemes. Discrete Applied Mathematics, 128:223{238, 2003.
[27] A. Shamir R.L. Rivest and L. Adleman. A method for obtaining digitalsignatures and public-key cryptosystems. Communications of the ACM,pages 120{126, 1978.
[28] A. Shamir. How to share a secret. Communications of the ACM, 22:612{613, 1979.
[29] J. Staddon, S. Miner, M. Franklin, D. Balfanz, M. Malkin, and D. Dean.Self-healing key distribution with revocation. In Proceedings of IEEESymposium on Security and Privacy:241{257, 2002.
[30] Chun Zhang Jim Kurose Weifeng Chen, Zihui Ge and Don Towsley. Ondynamic subset di®erence revocation scheme. Networking 2004, LectureNotes in Computer Science, 3042:743{758, 2004.
[31] Chung Kei Wong, Mohamed G. Gouda, and Simon S. Lam. Secure groupcommunications using key graphs. In Proceedings of the ACM SIGCOMM'98 conference on Applications, Technologies, Architectures, and Protocolsfor Computer Communication, pages 68{79, 1998.
[32] Sencun Zhu, Sanjeev Setia, and Sushil Jajodia. Adding reliable and self-healing key distribution to the subset di®erence group rekeying method.5th COST 264 International Workshop on Networked Group Communi-cations, Lecture Notes in Computer Science, 2816:107{118, 2003.