An Optimal Subset Cover for Broadcast Encryption

In broadcast networks, it is often required to encrypt data so that only a privileged set of users with access to the session key can access the data. The standard technique of transferring the session key to each user individually does not scale with the number of users typically found on a network such as cable. This method is not only time-wise inefficient, but also incurs high communication cost. To counter this, a number of approaches have been proposed in the literature that include methods based on secret sharing schemes, construction of subset covers using combinatorial designs,

etc.

In this paper, we propose and study two natural combinatorial optimization problems related to the subset cover framework for broadcast encryption. Here our objective is to minimize the communication cost given certain security and storage related constraints. We first derive lower bounds for the optimal communication cost for both problems. Then we propose the Partition-and-Power (PaP) subset cover scheme and show that it can provide a secure broadcast encryption with the communication costs matching those lower bounds. We illustrate the merits of the PaP scheme through a few examples and compare it with some of the prevailing subset cover schemes.