Skip to main content

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

Bhattacherjee, Sanjay, Sarkar, Palash (2014) Concrete Analysis and Trade-Offs for the (Complete Tree) Layered Subset Difference Broadcast Encryption Scheme. IEEE Transactions on Computers, 63 (7). pp. 1709-1722. ISSN 0018-9340. (doi:10.1109/TC.2013.68) (KAR id:83282)

PDF Author's Accepted Manuscript
Language: English
Download (554kB) Preview
[thumbnail of 7818.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL


Two key parameters of broadcast encryption (BE) schemes are the transmission size and the user storage. Naor-Naor-Lotspiech (2001) introduced the subset difference (SD) scheme achieving a good trade-off between these two parameters. Halevy-Shamir (2002) introduced the idea of layering to reduce user storage of the NNL scheme at the cost of increased transmission overhead. Here, we introduce several simple ideas to obtain new layering strategies with different trade-offs between user storage and transmission overhead. We define the notion of storage minimal layering and describe a dynamic programming algorithm to compute layering schemes for which the user storage is the minimum attainable using layerings. Further, the constrained minimization problem is considered. A method is described which yields BE schemes whose transmission overhead is not much more than the SD scheme but, whose user storage is still significantly lower. Finally, an O(r log 2 n) algorithm is obtained to compute the average transmission overhead for any layering-based scheme where r out of n users are revoked. This algorithm works for any layering strategy and also for arbitrary number of users. The algorithm has been used here to generate all data for the average transmission overhead.

Item Type: Article
DOI/Identification number: 10.1109/TC.2013.68
Uncontrolled keywords: Broadcast encryption; subset difference; layering; transmission overhead; user storage
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
University-wide institutes > Institute of Cyber Security for Society
Depositing User: Sanjay Bhattacherjee
Date Deposited: 06 Oct 2020 10:09 UTC
Last Modified: 06 Apr 2022 09:34 UTC
Resource URI: (The current URI for this page, for reference purposes)
Bhattacherjee, Sanjay:
  • Depositors only (login required):


Downloads per month over past year