An Analysis of the Naor-Naor-Lotspiech Subset Difference Algorithm (For Possibly Incomplete Binary Trees)

Conference paper


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.
AuthorsBhattacherjee, S. and Sarkar, P.
TypeConference paper
Abstract

The Subset Difference (SD) method is the most popular of Broadcast Encryption schemes due to its use in AACS standard for video discs. The scheme assumes the number of users n to be a power of two. In this paper, we relax this and consider arbitrary values of n. In some applications, this leads to substantial savings in the transmission overhead. Our analysis consists of the following aspects: (1) A recurrence to count N(n, r, h) - the number of revocation patterns for arbitrary values of n and r (number of revoked users) resulting in a header length of h. The recurrence allows us to generate data and hence to completely analyze it for larger n than the brute force method. (2) We do a probabilistic analysis of the subset cover finding algorithm of the SD method and find an expression to evaluate the expected header length E[Xn,r] for arbitrary values of n and r. Using this, E[Xn,r] can be evaluated in O(r log n) time using constant space. (3) While concluding, we suggest a similar method for finding E[Xn,r] for the Layered Subset Difference (LSD) scheme of Halevy and Shamir. (4) In the SD method, for n being a power two, we find asymptotic values of the expected header length.

Year2011
ConferenceThe Seventh International Workshop on Coding and Cryptography 2011
PublisherWCC
Accepted author manuscript
License
File Access Level
Repository staff only
Publication dates
PrintApr 2011
Publication process dates
AcceptedMar 2011
Deposited07 Dec 2021
Journal citationpp. 483-492
Book title7th International Workshop on Coding and Cryptography
Web address (URL) of conference proceedingshttp://wcc2011.inria.fr/index.php?page=home
Permalink -

https://repository.uel.ac.uk/item/86y87

  • 6
    total views
  • 3
    total downloads
  • 1
    views this month
  • 0
    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
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. https://doi.org/10.1007/s10623-012-9702-6