Reducing Communication Overhead of the Subset Difference Scheme

Sanjay Bhattacherjee; Palash Sarkar

Paper 2014/577

Reducing Communication Overhead of the Subset Difference Scheme

Sanjay Bhattacherjee and Palash Sarkar

Abstract

In Broadcast Encryption (BE) systems like Pay-TV, AACS, online content sharing and broadcasting, reducing the header length (communication overhead per session) is of practical interest. The Subset Difference (SD) scheme due to Naor-Naor-Lotspiech (NNL) is the most popularly used BE scheme. It assumes an underlying full binary tree to assign keys to subsets of users. In this work, we associate short tree structures of height $a$ to nodes in the binary tree to assign keys to more subsets. This ensures that for any set of revoked users, the header length is in general less and never more than the NNL-SD scheme. Experimental studies show that the average header length is always less than that of the NNL-SD scheme and decreases as $a$ increases. User storage in the new scheme is more than that of the NNL-SD scheme but is not prohibitively expensive. By choosing a suitable value of $a$, it is possible to obtain substantial reduction in the communication overhead at the cost of a tolerable increase in the user storage.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
Keywords: Broadcast encryption subset difference trees augmented structure general arity probabilistic analysis expectation header length transmission overhead.
Contact author(s): sanjay bhattacherjee @ gmail com
History: 2014-07-24: received
Short URL: https://ia.cr/2014/577
License: CC BY

BibTeX

@misc{cryptoeprint:2014/577,
      author = {Sanjay Bhattacherjee and Palash Sarkar},
      title = {Reducing Communication Overhead of the Subset Difference Scheme},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/577},
      year = {2014},
      url = {https://eprint.iacr.org/2014/577}
}