
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Practical Broadcast Encryption from GraphTheoretic Techniques and SubsetIncrementalChain Structure
Nuttapong ATTRAPADUNG Hideki IMAI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E90A
No.1
pp.187203 Publication Date: 2007/01/01 Online ISSN: 17451337
DOI: 10.1093/ietfec/e90a.1.187 Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Application Keyword: broadcast encryption, revocation scheme,
Full Text: PDF>>
Summary:
We present generic frameworks for constructing efficient broadcast encryption schemes in the subsetcover 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 subsetincrementalchain. Our first construction improves the currently best schemes, including the one proposed by Goodrich et al., without any further assumptions (only pseudorandom 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(n^{1/k}log^{2} 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 collusionsecure scheme in the literature that achieves both ciphertext size and key size independent of n simultaneously while keeping all other costs efficient, in particular, sublinear 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.

