Skip to main content
Kent Academic Repository

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)


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)

University of Kent Author Information

Bhattacherjee, Sanjay.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.