International Association
for Cryptologic Research

In a Ciphertext-Policy Attribute-Based Encryption (CP-ABE) system, decryption privileges are defined over attributes that could be shared by multiple users. If some of the users leak their decryption privileges to the public or to some third party, say for profit gain, a conventional CP-ABE has no tracing mechanism for finding these malicious users out. There are two levels of traceability for tackling this problem: (1) given a well-formed decryption key, a \\emph{White-Box} tracing algorithm can find out the original key owner; and (2) given a decryption-device while the underlying decryption algorithm or key may not be given, a \\emph{Black-Box} tracing algorithm, which treats the decryption-device as an oracle, can find out at least one of the malicious users whose keys have been used for constructing the decryption-device.

In this paper we propose the first \\emph{Expressive Black-box Traceable CP-ABE} system which has two main merits: (1) it supports fully collusion-resistant black-box traceability, that is, an adversary is allowed to access an arbitrary number of keys of its own choice when building the decryption-device, and (2) it is highly expressive, that is, the system supports policies expressed in any monotonic access structures. In addition, the traceability of this new system is public, that no secret input is required and no authority needs to be called in, instead, anyone can run the tracing algorithm. We show that the system is secure against adaptive adversaries in the standard model, and is efficient, that when compared with the expressive (non-traceable) CP-ABE due to Lewko et al. in Eurocrypt 2010, our new system \\emph{adds} fully collusion-resistant black-box traceability with the price of adding only $O(\\sqrt{\\cal K})$ elements into the ciphertext and public key, rather than increasing the sizes linearly with ${\\cal K}$, which is the number of users in the system.