Skip to main content

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)

PDF Author's Accepted Manuscript
Language: English

Download (2MB) Preview
[thumbnail of 7820.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL


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)
Bhattacherjee, Sanjay:
  • Depositors only (login required):


Downloads per month over past year