2006 | OriginalPaper | Buchkapitel
Fast Algorithms for the Free Riders Problem in Broadcast Encryption
verfasst von : Zulfikar Ramzan, David P. Woodruff
Erschienen in: Advances in Cryptology - CRYPTO 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.