Abstract:

Broadcast Encryption schemes enable a center to broadcast encrypted 
programs so that only designated subsets of users can decrypt each program. 
The stateless variant of this problem provides each user with a fixed set 
of keys which is never updated, and thus we have to solve the combinatorial
optimization problem of choosing a small number of subsets whose small unions 
contain all the possible designated subsets.  The best scheme published so far 
for this problem is the subset difference technique of Naor Naor and Lotspiech,
which makes it possible to exclude any $r$ out of the $n$ users by giving
each user $O(\log^{2}(n))$ keys and broadcasting $O(r)$ short messages
before the encrypted program. 

In this talk we describe an improved broadcast encryption scheme which reduces 
the number of keys given to each user by almost a square root factor, and
makes it possible to address more complicated subsets defined by any
nested combination of inclusion and exclusion conditions with a number of
messages which is proportional to the complexity of the description rather
than to the size of the subset. The new scheme is truly practical, and
makes it possible to broadcast an unlimited number of programs to 256,000,000 
possible customers by giving each new customer a smart card with one kilobyte 
of tamper-resistant memory.  It is then possible to address any subset defined 
by $t$ nested inclusion and exclusion conditions on subtrees of users by
sending less than $4t$ short messages, and the scheme remains secure even if 
all the excluded users form an adversarial coalition.
   
Joint work with Dani Halevy