Paper 2006/293
Fast Algorithms for the Free Riders Problem in Broadcast Encryption
Zulfikar Ramzan and David P. Woodruff
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 nonprivileged users to decrypt the broadcast. Although there are worstcase 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 and some other schemes in the subsetcover framework, we show how to find the optimal assignment of free riders in O(RF) 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_{ij'} <= (1+\epsilon) min_j a_j + b_{ij}. We show that if the differences a_i  a_{i+1}, b_ib_{i+1} are bounded, then there is an O(n^{4/3}/\epsilon^{2/3})time algorithm for this problem, improving upon the O(n^2) time of the naive algorithm.
Metadata
 Available format(s)
 PDF PS
 Category
 Applications
 Publication info
 Published elsewhere. This is the full version of the corresponding paper in Crypto 2006.
 Keywords
 broadcastcertificate revocationcombinatorial cryptography
 Contact author(s)
 dpwood @ mit edu
 History
 20060829: revised
 20060826: received
 See all versions
 Short URL
 https://ia.cr/2006/293
 License

CC BY
BibTeX
@misc{cryptoeprint:2006/293, author = {Zulfikar Ramzan and David P. Woodruff}, title = {Fast Algorithms for the Free Riders Problem in Broadcast Encryption}, howpublished = {Cryptology ePrint Archive, Paper 2006/293}, year = {2006}, note = {\url{https://eprint.iacr.org/2006/293}}, url = {https://eprint.iacr.org/2006/293} }