Skip to main content
Kent Academic Repository

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

Bhattacherjee, Sanjay, Sarkar, Palash (2011) An Analysis of the Naor-Naor-Lotspiech Subset Difference Algorithm (For Possibly Incomplete Binary Trees). In: The Seventh International Workshop on Coding and Cryptography 2011, April 11-15, 2011, Paris, France. (KAR id:93931)


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[X_{n,r}]$ for arbitrary values of $n$ and $r$. Using this, $E[X_{n,r}]$ can be evaluated in $O(r \log n)$ time using constant space. (3) While concluding, we suggest a similar method for finding $E[X_{n,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.

Item Type: Conference or workshop item (Paper)
Uncontrolled keywords: Broadcast encryption, subset difference, recurrence, expected header length, asymptotic analysis, layered subset difference
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:54 UTC
Last Modified: 07 Apr 2022 14:08 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.