## Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Broadcast encryption; subset difference; trees; augmented structure; general arity; probabilistic analysis; expectation; header length; transmission overhead.