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

Article


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
AuthorsBhattacherjee, S. and Sarkar, Palash
Abstract

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 log2 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.

KeywordsBroadcast encryption; Subset difference; Layering; Transmission overhead; Dynamic programming; User storage
JournalIEEE Transactions on Computers
Journal citation63 (7), pp. 1709-1722
ISSN0018-9340
Year2013
PublisherIEEE
Accepted author manuscript
Digital Object Identifier (DOI)https://doi.org/10.1109/TC.2013.68
Web address (URL)https://doi.org/10.1109/TC.2013.68
Publication dates
Print21 Mar 2013
Publication process dates
Deposited11 Dec 2018
Accepted24 Nov 2012
Accepted24 Nov 2012
Copyright information©2013 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/85x9x

Download files


Accepted author manuscript
  • 123
    total views
  • 290
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as

Related outputs

Reducing Communication Overhead of the Subset Difference Scheme
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
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
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.