Complete tree subset difference broadcast encryption scheme and its analysis

Article


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

The subset difference (SD) method proposed by Naor, Naor and Lotspiech is the most popular broadcast encryption (BE) scheme. It is suitable for real-time applications like Pay-TV and has been suggested for use by the AACS standard for digital rights management in Blu-Ray and HD-DVD discs. The SD method assumes the number of users to be a power of two. We propose the complete tree subset difference (CTSD) method that allows the system to support an arbitrary number of users. In particular, it subsumes the SD method and all results proved for the CTSD method also hold for the SD method. Recurrences are obtained for the CTSD scheme to count the number, N(n, r, h), of possible ways r users in the system of n users can be revoked to result in a transmission overhead or header length of h. The recurrences lead to a polynomial time dynamic programming algorithm for computing N(n, r, h). Further, they provide bounds on the maximum possible header length. A probabilistic analysis is performed to obtain an O(r log n) time algorithm to compute the expected header length in the CTSD scheme. Further, for the SD scheme we obtain an explicit limiting upper bound on the expected header length.

KeywordsBroadcast encryption; Subset difference; Combinatorial analysis; Recurrence; Probabilistic analysis; Expected header length; Transmission overhead; Asymptotic analysis
JournalDesigns, Codes and Cryptography
Journal citation66 (1-3), pp. 335-362
ISSN0925-1022
Year2012
PublisherSpringer US
Accepted author manuscript
License
File Access Level
Anyone
Digital Object Identifier (DOI)https://doi.org/10.1007/s10623-012-9702-6
Web address (URL)https://doi.org/10.1007/s10623-012-9702-6
Publication dates
Online08 Jun 2012
Publication process dates
Deposited14 Dec 2018
Accepted14 May 2012
Accepted14 May 2012
Copyright information© Springer Science+Business Media, LLC 2012. This is a post-peer-review, pre-copyedit version of an article published in Designs, Codes and Cryptography. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10623-012-9702-6.
Permalink -

https://repository.uel.ac.uk/item/85yyz

Download files


Accepted author manuscript
3.pdf
License: Springer Nature terms of use for archived author accepted manuscripts (AAMs) of subscription articles, books and chapters
File access level: Anyone

  • 72
    total views
  • 215
    total downloads
  • 3
    views this month
  • 1
    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
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
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.