Skip to main content
Kent Academic Repository

Reducing Communication Overhead of the Subset Difference Scheme

Bhattacherjee, Sanjay, Sarkar, Palash (2016) Reducing Communication Overhead of the Subset Difference Scheme. IEEE Transactions on Computers, 65 (8). pp. 2575-2587. ISSN 0018-9340. (doi:10.1109/TC.2015.2485231) (KAR id:83283)


In Broadcast Encryption (BE) systems like Pay-TV, AACS, online content sharing and broadcasting, reducing the header length (communication overhead per session) is of practical interest. The Subset Difference (SD) scheme due to Naor-Naor-Lotspiech (NNL) is the most popularly used BE scheme. We introduce the (a,b,γ) augmented binary tree subset difference ( (a,b,γ) -ABTSD) scheme which is a generalization of the NNL-SD scheme. By varying the parameters (a,b,γ) , it is possible to obtain O(nlogn) different schemes. The average header length achieved by the new schemes is smaller than all known schemes having the same decryption time as that of the NNL-SD scheme and achieving non-trivial trade-offs between the user storage and the header size. The amount of key material that a user is required to store increases. For the earlier mentioned applications, reducing header size and achieving fast decryption is perhaps more of a concern than the user storage.

Item Type: Article
DOI/Identification number: 10.1109/TC.2015.2485231
Uncontrolled keywords: Broadcast encryption, subset difference, binary trees, augmented trees, header length, transmission, overhead, user storage, decryption time
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:28 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.