Towards Making Broadcast Encryption Practical

Michel Abdalla, Yuval Shavitt, and Avishai Wool

The problem we address is how to communicate
securely with a set of users (the target set) over an insecure
broadcast channel. In order to solve this problem, several broadcast
encryption schemes have been proposed. In these systems, the
parameters of major concern are the length of transmission and
number of keys held by each user's set top terminal (STT). 
Due to the need to withstand hardware tampering, the amount of
secure memory available in the STTs is quite small, severely
limiting the number of keys each user holds.  In such cases, known
theoretical bounds seem to indicate that non-trivial broadcast encryption
schemes are only feasible when the number of users is small.
 
In order to break away from these theoretical bounds, our approach
is to allow a controlled number of users outside the target set to
occasionally receive the multicast. This relaxation is appropriate
for low-cost transmissions such as multicasting electronic coupons.
For this purpose, we introduce {\em $f$-redundant} establishment key 
allocations, which
guarantee that the total number of recipients is no more than $f$ times
the number of intended recipients. We measure the performance of
such schemes by the number of transmissions they require, by their
redundancy, and 
by their opportunity, which is the probability of a user outside the
target set to be part of the multicast. We first prove a new
lower bound and discuss the basic trade-offs associated with this
new setting.  Then we present several new $f$-redundant establishment key 
allocations.  We evaluate the schemes' performance under all the
relevant measures by extensive simulation.  Our results indicate
that, unlike previous solutions, it seems possible to design
practical schemes in this new setting.