Abstract
We provide algorithms to solve the free riders problem in broadcast encryption. In this problem, the broadcast server is allowed to choose some small subset F of the revoked set R of users to allow to decrypt the broadcast, despite having been revoked. This may allow the server to significantly reduce network traffic while only allowing a small set of non-privileged users to decrypt the broadcast.
Although there are worst-case instances of broadcast encryption schemes where the free riders problem is difficult to solve (or even approximate), we show that for many specific broadcast encryption schemes, there are efficient algorithms. In particular, for the complete subtree method [25] and some other schemes in the subset-cover framework, we show how to find the optimal assignment of free riders in O(|R||F|) time, which is independent of the total number of users. We also define an approximate version of this problem, and study specific distributions of R for which this relaxation yields even faster algorithms.
Along the way we develop the first approximation algorithms for the following problem: given two integer sequences a 1 ≥a 2 ≥⋯≥a n and b 1 ≥b 2 ≥⋯≥b n , output for all i, an integer j′ for which a j′ + b \(_{i--{\it j}\prime}\) ≤(1+ε) min j (a j + b \(_{i--{\it j}}\)). We show that if the differences a i – a i + 1, b i –b i + 1 are bounded, then there is an O(n 4/3/ε 2/3)-time algorithm for this problem, improving upon the O(n 2) time of the naive algorithm.
Chapter PDF
Similar content being viewed by others
References
Abdalla, M., Shavitt, Y., Wool, A.: Key Management for Restricted Multicast Using Broadcast Encryption. ACM Trans. on Networking 8(4) (2000)
Aiello, W., Lodha, S.P., Ostrovsky, R.: Fast digital identity revocation. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, p. 137. Springer, Heidelberg (1998)
Anzai, J., Matsuzaki, N., Matsumoto, T.: A Quick Group Key Distribution Scheme with “Entity Revocation”. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 333–347. Springer, Heidelberg (1999)
Asano, T.: A Revocation Scheme with Minimal Storage at Receivers. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 433–450. Springer, Heidelberg (2002)
Azuma, K.: Weighted Sums of Certain Dependent Random Variables. Tôhoku Math. Journ. 19, 357–367 (1967)
Berkovits, S.: How to Broadcast a Secret. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 535–541. Springer, Heidelberg (1991)
Canetti, R., Malkin, T.G., Nissim, K.: Efficient Communication-Storage Tradeoffs for Multicast Encryption. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 459. Springer, Heidelberg (1999)
Chan, T.M.: All-pairs shortest paths with real weights in O(n 3/logn) time. In: Dehne, F., López-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol. 3608, pp. 318–324. Springer, Heidelberg (2005)
Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. The MIT Press/McGraw-Hill (1990)
Content Protection for Pre-recorded Media Specification and Content Protection for Recordable Media Specification, available from: http://www.4centity.com/tech/cprm
van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Inform. Process. Lett. 6(3), 80–82 (1977)
van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Math Systems Theory 10(2) (1976/1977) (Also FOCS 1975)
Erickson, J.: Blog Post at (2005), http://3dpancakes.typepad.com/ernie//08/chans_technique.html
Fiat, A., Naor, M.: Broadcast encryption. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 480–491. Springer, Heidelberg (1994)
Gentry, C., Ramzan, Z.: RSA Accumulator Based Broadcast Encryption. In: Proc. Information Security Conference (2004)
Han, Y.: Deterministic sorting in O(n loglogn) time and linear space. Journal of Algorithms, 96–105 (2004)
Halevy, D., Shamir, A.: The LSD Broadcast Encryption Scheme. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 47–60. Springer, Heidelberg (2002)
Han, Y., Thorup, M.: Sorting in \(O(n \sqrt{\log \log n})\) expected time and linear space. In: FOCS, pp. 135–144 (2002)
Kim, Y., Perrig, A., Tsudik, G.: Simple and Fault-Tolerant Key Agreement for Dynamic Collaborative Groups. In: Proc. Of ACM CCS (2000)
Kumar, R., Rajagopalan, S., Sahai, A.: Coding Constructions for Blacklisting Problems without Computational Assumptions. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 609–623. Springer, Heidelberg (1999)
Luby, M., Staddon, J.: Combinatorial Bounds for Broadcast Encryption. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 512–526. Springer, Heidelberg (1998)
Matsuzaki, N., Anzai, J., Matsumoto, T.: Light Weight Broadcast Exclusion Using Secret Sharing. In: Clark, A., Boyd, C., Dawson, E.P. (eds.) ACISP 2000. LNCS, vol. 1841. Springer, Heidelberg (2000)
Mitra Iolus, S.: A Framework for Scalable Secure Multicasting. In: Proc. of ACM SIGCOMM (September 1997)
McGrew, D.A., Sherman, A.T.: Key Establishment in Large Dynamic Groups Using One-Way Function Trees. Manuscript available at: http://www.csee.umbc.edu/~Sherman/Papers/itse.ps
Naor, D., Naor, M., Lotspiech, J.: Revocation and Tracing Schemes for Stateless Receivers. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 41. Springer, Heidelberg (2001) (Full version: ECCC Report No. 43, 2002)
Panconesi, A., Srinivasan, A.: Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds. In: SICOMP (1997)
Poovendran, R., Baras, J.S.: An Information Theoretic Analysis of Rooted-Tree Based Secure Multicast Key Distribution Scheme. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, p. 624. Springer, Heidelberg (1999)
Ramzan, Z., Woodruff, D.P.: Fast Algorithms for the Free Riders Problem in Broadcast Encryption. IACR ePrint Archive (2006), http://eprint.iacr.org
Wallner, D.M., Harder, E.J., Agee, R.C.: Key Management for Multicast: Issues and Architectures. Internet Draft (September 1998)
Wong, C.K., Gouda, M., Lam, S.S.: Secure Group Communications Using Key Graphs. In: Proc. of SIGCOMM (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ramzan, Z., Woodruff, D.P. (2006). Fast Algorithms for the Free Riders Problem in Broadcast Encryption. In: Dwork, C. (eds) Advances in Cryptology - CRYPTO 2006. CRYPTO 2006. Lecture Notes in Computer Science, vol 4117. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11818175_18
Download citation
DOI: https://doi.org/10.1007/11818175_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37432-9
Online ISBN: 978-3-540-37433-6
eBook Packages: Computer ScienceComputer Science (R0)