Abstract
A revocation or a broadcast encryption technology allows a sender to transmit information securely over a broadcast channel to a select group of receivers excluding some revoked receivers. In this paper we propose two efficient revocation methods which are suitable for stateless receivers. The proposed methods use an a-ary key tree structure and require at most r (log (N/r)/log a + 1 ) ciphertexts broadcast. Our Method 1 requires only one key to be stored and O (2alog5 N/log a) computational overhead at a receiver, whereas Method 2 requires log N/log a keys and O (2a) computational overhead, where N and r respectively denote the total number of receivers and the number of revoked receivers. Our methods are very efficient with respect to the number of keys each receiver stores, especially Method 1 minimizes it.
Most of this work was done while the author was visiting Stanford University.
Chapter PDF
Similar content being viewed by others
References
S. G. Akl and P. D. Taylor, “Cryptographic Solution to a Problem of Access Control in a Hierarchy,” ACM Transactions on Computer Systems, Vol. 1, No. 3, pp. 239–248, 1983.
J. Anzai, N. Matsuzaki and T. Matsumoto, “A Quick Group Key Distibution Scheme with Entity Revocation,” Advances in Cryptology-Asiacrypt ”99, Lecture Notes in Computer Science 1716, Springer, pp. 333–347, 1999.
S. Berkovits, “How to Broadcast a Secret,” Advances in Cryptology-Eurocrypt’ 91, Lecture Notes in Computer Science 547, Springer, pp. 535–541, 1991.
D. Boneh and M. Franklin, “An Efficient Public Key Traitor Tracing Scheme,” Advances in Cryptology-Crypto’ 99, Lecture Notes in Computer Science, Vol. 1666, Springer-Verlag, pp. 338–353, 1999.
R. Canetti, T. Malkin and K. Nissim, “Efficient Communication-Storage Tradeoffs for Multicast Encryption,” Advances in Cryptology-Eurocrypt’ 99, Lecture Notes in Computer Science 1592, Springer, pp. 459–474, 1999.
G. C. Chick and S. E. Tavares, “Flexible Access Control with Master Keys,” Advances in Cryptology-Crypto’ 89, Lecture Notes in Computer Science 435, Springer, pp. 316–322, 1990.
B. Chor, A. Fiat and M. Naor, “Tracing Traitors,” Advances in Cryptology-Crypto’ 94, Lecture Notes in Computer Science, Vol. 839, Springer-Verlag, pp. 257–270, 1994.
“Content Protection for Pre-recorded Media Specification” and “Content Protection for Recordable Media Specification,” available from http://www.4centity.com/tech/cprm/.
W. Diffie and M. Hellman, “New Directions in Cryptography,” IEEE Transactions on Information Theory, IT-22(6), 1976.
A. Fiat and M. Naor, “Broadcast Encryption,” Advances in Cryptology-Crypto’ 93, Lecture Notes in Computer Science 773, Springer, pp. 480–491, 1994.
Y. Kim, A. Perrig and G. Tsudik, “Simple and Foult-Tolerant Key Agreement for Dynamic Collaborative Groups,” Proceedings of ACM Conference on Computer and Communication Security, CCS 2000.
D. E. Knuth, “The Art of Computer Programming,” vol. 2, Addison-Wesley, 1981.
R. Kumar, S. Rajagopalan and A. Sahai, “Coding Constructions for Blacklisting Problems without Computational Assumptions,” Advances in Cryptology-Crypto’ 99, Lecture Notes in Computer Science 1666, Springer, pp. 609–623, 1999.
M. Luby and J. Staddon, “Combinatorial Bounds for Broadcast Encryptions,” Advances in Cryptology-Eurocrypt’ 98, Lecture Notes in Computer Science 1403, Springer, pp. 512–526, 1998.
N. Matsuzaki, J. Anzai and T. Matsumoto, “Light Weight Broadcast Exclusion Using Secret Sharing,” Information Security and Privacy-5th Australasian Conference, ACISP 2000, Lecture Notes in Computer Science 1841, Springer, pp. 313–327, 2000.
D. A. McGrew and A. T. Sherman, “Key Establishment in Large Dynamic Groups Using One-Way Function Trees,’ Manuscript, available from http://www.csee.umbc.edu/~sherman/Papers/itse.ps, 1998.
D. Naor, M. Naor and J. Lotspiech, “Revocation and Tracing Schemes for Stateless Receivers,” Advances in Cryptology-Crypto 2001, Lecture Notes in Computer Science 2139, Springer, pp. 41–62, 2001.
M. Naor and B. Pinkas, “Efficient Trace and Revoke Schemes,” Financial Cryptography’ 2000, Lecture Notes in Computer Science 1962, Springer, pp. 1–20, 2000.
M. Naor and O. Reingold, “Number-Theoretic Constructions of Efficient Pseudo-Random Functions,” Proceedings of 38th IEEE Symposium on Foundations of Computer Science, pp. 458–467, 1997.
R. Poovendran and J. S. Baras, “An Information Theoretic Analysis of Rooted-Tree Based Secure Multicast Key Distribution Schemes,” Advances in Cryptology-Crypto’ 99, Lecture Notes in Computer Science 1666, Springer, pp. 624–638, 1999.
R. L. Rivest, A. Shamir and L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM, 21, pp. 120–126, 1978.
A. Shamir, “How to Share a Secret,” Communications of the ACM, 22, pp. 612–613, 1979.
D. R. Stinson, “Cryptography: Theory and Practice,” CRC Press, 1995.
D. Wallner, E. Harder and R. Agee, “Key Management for Multicast: Issues and Architectures,” IETF Network Working Group, Request for Comments: 2627, available from ftp://ftp.ietf.org/rfc/rfc2627.txt, 1999.
C. K. Wong, M. Gouda and S. S. Lam, “Secure Group Communications Using Key Graphs,” Proceedings of ACM SIGCOMM’ 98, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Asano, T. (2002). A Revocation Scheme with Minimal Storage at Receivers. In: Zheng, Y. (eds) Advances in Cryptology — ASIACRYPT 2002. ASIACRYPT 2002. Lecture Notes in Computer Science, vol 2501. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36178-2_27
Download citation
DOI: https://doi.org/10.1007/3-540-36178-2_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00171-3
Online ISBN: 978-3-540-36178-7
eBook Packages: Springer Book Archive