Tree based symmetric key broadcast encryption

Article


Bhattacherjee, S. and Sarkar, Palash 2015. Tree based symmetric key broadcast encryption. Journal of Discrete Algorithms. 34, pp. 78-107.
AuthorsBhattacherjee, S. and Sarkar, Palash
Abstract

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,⌈n/k⌉). An expression for the expected header length is obtained and it is shown that the expression can be evaluated in O(rlogn) 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=⌈logkn⌉ and χk is the number of cyclotomic cosets modulo 2k−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.

KeywordsBroadcast encryption; Subset difference; Trees; General arity; Probabilistic analysis; Header length; Transmission overhead; Cyclotomic cosets; Layering
JournalJournal of Discrete Algorithms
Journal citation34, pp. 78-107
ISSN1570-8667
Year2015
PublisherElsevier
Accepted author manuscript
License
Digital Object Identifier (DOI)doi:10.1016/j.jda.2015.05.010
Web address (URL)https://doi.org/10.1016/j.jda.2015.05.010
Publication dates
Online01 Jun 2015
Publication process dates
Deposited14 Dec 2018
Accepted27 May 2015
Accepted27 May 2015
Copyright information© 2015 Elsevier
LicenseCC BY-NC-ND 4.0
Permalink -

https://repository.uel.ac.uk/item/855x4

  • 6
    total views
  • 22
    total downloads
  • 2
    views this month
  • 6
    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.
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.
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.