Skip to main content
Kent Academic Repository

Complete Tree Subset Difference Broadcast Encryption Scheme and its Analysis

Bhattacherjee, Sanjay, Sarkar, Palash (2012) Complete Tree Subset Difference Broadcast Encryption Scheme and its Analysis. Designs, Codes and Cryptography, 66 (1). ISSN 0925-1022. E-ISSN 1573-7586. (doi:10.1007/s10623-012-9702-6) (KAR id:93930)

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.

Item Type: Article
DOI/Identification number: 10.1007/s10623-012-9702-6
Uncontrolled keywords: Broadcast encryption; subset difference; combinatorial analysis; recurrence; probabilistic analysis; expected header length; transmission overhead; asymptotic analysis
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
University-wide institutes > Institute of Cyber Security for Society
Depositing User: Sanjay Bhattacherjee
Date Deposited: 06 Apr 2022 09:46 UTC
Last Modified: 07 Apr 2022 14:11 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/93930 (The current URI for this page, for reference purposes)

University of Kent Author Information

Bhattacherjee, Sanjay.

Creator's ORCID: https://orcid.org/0000-0002-3367-6192
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.