Practical Broadcast Encryption from Graph-Theoretic Techniques and Subset-Incremental-Chain Structure(Application,<Special Section>Cryptography and Information Security)

スポンサーリンク

概要

• 論文の詳細を見る

• 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(n^<1/k>log^2n) 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.

• 社団法人電子情報通信学会の論文
• 2007-01-01

著者

• Imai Hideki

  Aist Tokyo Jpn

• ATTRAPADUNG Nuttapong

  University of Tokyo

• Imai Hideki

  Aist

関連論文

• Smallest Size of Circulant Matrix for Regular (3, L) and (4, L) Quasi-Cyclic LDPC Codes with Girth 6
• Flaws in Robust Optimistic Mix-Nets and Stronger Security Notions(Protocol, Cryptography and Information Security)
• A Strongly Unforgeable Signature under the CDH Assumption without Collision Resistant Hash Functions
• Efficient Identity-Based Encryption with Tight Security Reduction(Information Theory and Its Applications)
• Practical Broadcast Encryption from Graph-Theoretic Techniques and Subset-Incremental-Chain Structure(Application,Cryptography and Information Security)
• New Short Signature Scheme without Random Oracles
• AT-2-2 A Survey on Recent Advances in Broadcast Encryption
• How to Break COT-Based Fingerprinting Schemes and Design New One(Cryptography and Information Security, Information Theory and Its Applications)

スポンサーリンク