Practical Broadcast Encryption from Graph-Theoretic Techniques and Subset-Incremental-Chain Structure

Nuttapong ATTRAPADUNG  Hideki IMAI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.1   pp.187-203
Publication Date: 2007/01/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.1.187
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Application
broadcast encryption,  revocation scheme,  

Full Text: PDF>>
Buy this Article

We present generic frameworks for constructing efficient broadcast encryption schemes in the subset-cover paradigm, introduced by Naor et al., based on various key derivation techniques. Our frameworks characterize any instantiation completely to its underlying graph decompositions, which are purely combinatorial in nature. These abstract away the security of each instantiated scheme to be guaranteed by the generic one of the frameworks; thus, give flexibilities in designing schemes. Behind these, we present new techniques based on (trapdoor) RSA accumulators utilized to obtain practical performances. We then give some efficient instantiations from the frameworks, via a new structure called subset-incremental-chain. Our first construction improves the currently best schemes, including the one proposed by Goodrich et al., without any further assumptions (only pseudo-random generators are used) by some factors. The second instantiation, which is the most efficient, is instantiated based on RSA and directly improves the first scheme. Its ciphertext length is of order O(r), the key size is O(1), and its computational cost is O(n1/klog2 n) for any (arbitrary large) constant k; where r and n are the number of revoked users and all users respectively. To the best of our knowledge, this is the first explicit collusion-secure scheme in the literature that achieves both ciphertext size and key size independent of n simultaneously while keeping all other costs efficient, in particular, sub-linear in n. The third scheme improves Gentry and Ramzan's scheme, which itself is more efficient than the above schemes in the aspect of asymptotic computational cost.