A set theoretic approach to broadcast encryption

by Thomas Martin

Abstract:

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.