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

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.
Type de document :
Communication dans un congrès
WCC 2011 - Workshop on coding and cryptography, Apr 2011, Paris, France. pp.483-492, 2011
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00614487
Contributeur : Marie Trape <>
Soumis le : jeudi 11 août 2011 - 17:19:53
Dernière modification le : mercredi 29 novembre 2017 - 10:26:43
Document(s) archivé(s) le : lundi 12 novembre 2012 - 15:20:16

Fichier

80.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00614487, version 1

Collections

Citation

Sanjay Bhattacherjee, Palash Sarkar. An Analysis of the Naor-Naor-Lotspiech Subset Difference Algorithm (For Possibly Incomplete Binary Trees). WCC 2011 - Workshop on coding and cryptography, Apr 2011, Paris, France. pp.483-492, 2011. 〈inria-00614487〉

Partager

Métriques

Consultations de la notice

182

Téléchargements de fichiers

289