Reducing Communication Overhead of the Subset Difference Scheme

Article


Bhattacherjee, S. and Sarkar, Palash 2015. Reducing Communication Overhead of the Subset Difference Scheme. IEEE Transactions on Computers. 65 (8), pp. 2575-2587. https://doi.org/10.1109/TC.2015.2485231
AuthorsBhattacherjee, S. and Sarkar, Palash
Abstract

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(n log n) 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.

KeywordsBroadcast encryption; Subset difference; Binary trees; Augmented trees; Header length; Transmission overhead; User storage; Decryption time
JournalIEEE Transactions on Computers
Journal citation65 (8), pp. 2575-2587
ISSN0018-9340
Year2015
PublisherIEEE
Accepted author manuscript
Digital Object Identifier (DOI)https://doi.org/10.1109/TC.2015.2485231
Web address (URL)https://doi.org/10.1109/TC.2015.2485231
Publication dates
Online01 Oct 2015
Publication process dates
Deposited17 Dec 2018
Accepted23 Sep 2015
Accepted23 Sep 2015
Copyright information© 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Permalink -

https://repository.uel.ac.uk/item/8546y

Download files


Accepted author manuscript
  • 127
    total views
  • 256
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as

Related outputs

Tree based symmetric key broadcast encryption
Bhattacherjee, S. and Sarkar, Palash 2015. Tree based symmetric key broadcast encryption. Journal of Discrete Algorithms. 34, pp. 78-107. https://doi.org/10.1016/j.jda.2015.05.010
Concrete Analysis and Trade-Offs for the (Complete Tree) Layered Subset Difference Broadcast Encryption Scheme
Bhattacherjee, S. and Sarkar, Palash 2013. Concrete Analysis and Trade-Offs for the (Complete Tree) Layered Subset Difference Broadcast Encryption Scheme. IEEE Transactions on Computers. 63 (7), pp. 1709-1722. https://doi.org/10.1109/TC.2013.68
Complete tree subset difference broadcast encryption scheme and its analysis
Bhattacherjee, S. and Sarkar, Palash 2012. Complete tree subset difference broadcast encryption scheme and its analysis. Designs, Codes and Cryptography. 66 (1-3), pp. 335-362. https://doi.org/10.1007/s10623-012-9702-6
An Analysis of the Naor-Naor-Lotspiech Subset Difference Algorithm (For Possibly Incomplete Binary Trees)
Bhattacherjee, S. and Sarkar, P. 2011. An Analysis of the Naor-Naor-Lotspiech Subset Difference Algorithm (For Possibly Incomplete Binary Trees). The Seventh International Workshop on Coding and Cryptography 2011. Paris, France 11 - 15 Apr 2011 WCC.
Generation of Test Vectors for Sequential Cell Verification
Bhowmick, S., Bhattacherjee, S., Nandakumar, G. N. and Patel, N. 2008. Generation of Test Vectors for Sequential Cell Verification. ARM Regional Engineering Conference. Bengaluru 2008 ARM.