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.Category / Keywords: cryptographic protocols / Broadcast encryption; subset difference; layering; transmission overhead; user storage Date: received 13 Jun 2012 Contact author: sanjay bhattacherjee at gmail com Available format(s): PDF | BibTeX Citation Version: 20120622:193855 (All versions of this report) Short URL: ia.cr/2012/337 Discussion forum: Show discussion | Start new discussion