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

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.