Traceable CP-ABE with short ciphertexts: How to catch people selling decryption devices on ebay efficiently

Ciphertext-policy attribute-based encryption (CP-ABE) is a highly promising solution for cloud computing, which has been widely applied to provide fine-grained access control in cloud storage services recently. However, for CP-ABE based cloud storage systems, if a decryption device appears on eBay described and advertised to be able to decrypt any ciphertexts with policies satisfied by an attribute set or even with a specific access policy only, no one can trace the malicious user(s) who built such a decryption device using their private key(s). This has been known as a major obstacle to deploying CP-ABE systems in real-world commercial applications. Due to the one-to-many encryption mechanism of CP-ABE, the same decryption privilege is shared by multiple users who have the same attributes. It is difficult to identity the malicious user(s) who built such a decryption device. To track people selling decryption devices on eBay efficiently, in this paper, we develop a new methodology for constructing traitor tracing functionality, and present the first black-box traceable CP-ABE (BT-CP-ABE) with short ciphertexts which are independent of the number of users N. The black-box traceability is public, fully collusion-resistant, and adaptively traceable against both key-like decryption black-box and policy-specific decryption black-box. Our construction combines the conventional CP-ABE with Anonymous Hierarchical Identity-Based Encryption (A-HIBE) in a novel way, which is the first to construct the (underlying) traitor tracing system from A-HIBE. The resulting ciphertexts are independent of N while the private keys are linear in N, which partially answers an open problem posed by Boneh and Waters [CCS 2006]. We believe this work is a constructive step towards efficient traitor tracing system with short ciphertexts and private keys. In particular, we believe that following the route of this work, any progress in A-HIBE (i.e., with shorter ciphertexts and private keys) may result in some progress in BT-CP-ABE and finally give a satisfactory solution to this open problem.