Skip to main content

Tree Based Symmetric Key Broadcast Encryption

Bhattacherjee, Sanjay, Sarkar, Palash (2015) Tree Based Symmetric Key Broadcast Encryption. Journal of Discrete Algorithms, 34 . pp. 78-107. ISSN 1570-8667. (doi:10.1016/j.jda.2015.05.010) (KAR id:83842)


The most influential broadcast encryption (BE) scheme till date was introduced in 2001 by Naor, Naor and Lotspiech (NNL) and is based on binary trees. This paper generalizes the ideas of NNL to obtain BE schemes based on k-ary trees for any k ≥ 2. The treatment is uniform across all k and essentially provides a single scheme which is parameterized by the arity of the underlying tree. We perform an extensive analysis of the header length and user storage of the scheme. It is shown that for a k-ary tree with n users out of which r are revoked, the maximum header length is min(2r − 1, n − r, dn/ke). An expression for the expected header length is obtained and it is shown that the expression can be evaluated in O(r log n) time. Experimental results indicate that for values of r one would expect in applications such as pay TV systems, the average header length decreases as k increases. The number of keys to be stored by any user is shown to be at most (χ k −2)` 0 (` 0 +1)/2, where ` 0 = dlog k ne and χ k is the number of cyclotomic cosets modulo 2 k −1. In particular, when the number of users is more than 1024, we prove that the user storage required for k = 3 is less than that of k = 2. For higher values of k, the user storage is greater than that for binary trees. The option of choosing the value of k provides a designer of a BE system with a wider range of trade-offs between average header length and user storage. The effect of layering on the k-ary tree SD scheme is also explored.

Item Type: Article
DOI/Identification number: 10.1016/j.jda.2015.05.010
Uncontrolled keywords: Broadcast encryption; subset difference; trees; general arity; probabilistic analysis; header length; transmission overhead; cyclotomic cosets; layering
Subjects: Q Science > QA Mathematics (inc Computing science)
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: 01 Nov 2020 20:44 UTC
Last Modified: 06 Apr 2022 09:34 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

Bhattacherjee, Sanjay.

Creator's ORCID:
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.