Adi Shamir Applied Math The Weizmann Institute

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