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.
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)doi: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

  • 6
    total views
  • 28
    total downloads
  • 2
    views this month
  • 8
    downloads this month

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