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

  • 5
    total views
  • 28
    total downloads
  • 1
    views this month
  • 5
    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.
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.