An Analysis of the Naor-Naor-Lotspiech Subset Difference Algorithm (For Possibly Incomplete Binary Trees)
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.
|Authors||Bhattacherjee, S. and Sarkar, P.|
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.
|Conference||The Seventh International Workshop on Coding and Cryptography 2011|
|Accepted author manuscript|
File Access Level
Repository staff only
|Publication process dates|
|Deposited||07 Dec 2021|
|Journal citation||pp. 483-492|
|Book title||7th International Workshop on Coding and Cryptography|
|Web address (URL) of conference proceedings||http://wcc2011.inria.fr/index.php?page=home|
1views this month
0downloads this month