Key management for restricted multicast using broadcast encryption
Résumé
The problem we address is how to communicate se- curely with a set of users (the target set) over an insecure broadcast channel. This problem occurs in two application domains: satel- lite/cable pay TV and the Internet MBone. In these systems, the parameters of major concern are the number of key transmissions and the number of keys held by each receiver. In the Internet do- main, previous schemes suggest building a separate key tree for each multicast program, thus incurring a setup cost of at least ﰂﰃﰁ  per program for target sets of size  . In the pay-TV do- main, a single key structure is used for all programs, but known theoretical bounds show that either very long transmissions are required, or that each receiver needs to keep prohibitively many keys. Our approach is targeted at both domains. Our schemes main- tain a single key structure that requires each receiver to keep only a logarithmic number of establishment keys for its entire lifetime. At the same time our schemes admit low numbers of transmissions. In order to achieve these goals, and to break away from the theo- retical bounds, we allow a controlled number of users outside the target set to occasionally receive the multicast. This relaxation is appropriate for many scenarios in which the encryption is used to force consumers to pay for a service, rather than to withhold sen- sitive information. For this purpose, we introduce  -redundant es- tablishment key allocations, which guarantee that the total number of recipients is no more than  times the number of intended recip- ients. We measure the performance of such schemes by the number of key transmissions they require, by their redundancy  , and by the probability that a user outside the target set (a free-rider) will be able to decrypt the multicast. We prove a new lower bound, present several new establishment key allocations, and evaluate our schemes' performance by extensive simulation.