Paper 2012/337

Analysis and Trade-Offs for the (Complete Tree) Layered Subset Difference Broadcast Encryption Scheme

Sanjay Bhattacherjee and Palash Sarkar

Abstract

Broadcast Encryption (BE) is an important technique for digital rights management (DRM). Two key parameters of a BE scheme are the average size of the transmission overhead and the size of the secret information to be stored by the users. The most important BE scheme till date is the subset difference (SD) scheme proposed by Naor, Naor and Lotspiech in 2001 which achieves a good balance of these two parameters. A year later, Halevy and Shamir proposed a variant of the SD scheme called the layered SD (LSD) scheme which allowed to reduce the size of user storage at the cost of increasing the transmission overhead. Since then, there has been no further study of other possible trade-offs between transmission overhead and user storage that can be obtained from the SD scheme. In this work, we introduce several simple ideas to obtain new layering strategies with different trade-offs between user storage and transmission overhead. At one end, we introduce the notion of storage minimal layering, show that the Halevy-Shamir layering does not achieve minimal storage and describe a dynamic programming algorithm to compute layering strategies for which user storage is guaranteed to be the minimum possible. This results in user storage being 18\% to 24\% lower than that required by Halevy-Shamir layering schemes. At the other end, we consider the constrained minimization problem and show how to obtain BE schemes whose transmission overhead is not much more than that of the SD scheme but, whose user storage is still significantly lower than that of the SD scheme. The original SD and the LSD algorithms are defined only when the number of users is a power of two. In an earlier work, we have shown how to handle arbitrary number of users in the SD scheme. Here this is extended to the LSD scheme. Finally, we obtain an $O(r\log^2 n)$ time algorithm to compute the average transmission overhead in any layering based SD scheme with $n$ users out of which $r$ are revoked.