Next Article in Journal
Applying the Upper Integral to the Biometric Score Fusion Problem in the Identification Model
Previous Article in Journal
Optimization of China Crude Oil Transportation Network with Genetic Ant Colony Algorithm
Article

Black Box Traceable Ciphertext Policy Attribute-Based Encryption Scheme

by 1,*, 1 and 2
1
School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu, 610054, China
2
School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, 611731, China
*
Author to whom correspondence should be addressed.
Academic Editor: Willy Susilo
Received: 9 June 2015 / Revised: 5 August 2015 / Accepted: 5 August 2015 / Published: 14 August 2015

Abstract

In the existing attribute-based encryption (ABE) scheme, the authority (i.e., private key generator (PKG)) is able to calculate and issue any user’s private key, which makes it completely trusted, which severely influences the applications of the ABE scheme. To mitigate this problem, we propose the black box traceable ciphertext policy attribute-based encryption (T-CP-ABE) scheme in which if the PKG re-distributes the users’ private keys for malicious uses, it might be caught and sued. We provide a construction to realize the T-CP-ABE scheme in a black box model. Our scheme is based on the decisional bilinear Diffie-Hellman (DBDH) assumption in the standard model. In our scheme, we employ a pair (ID, S) to identify a user, where ID denotes the identity of a user and S denotes the attribute set associated with her.
Keywords: black box; CP-ABE; oblivious transfer; private key generator; tracing black box; CP-ABE; oblivious transfer; private key generator; tracing

1. Introduction

With the advent of cloud computing, more and more data and computations will be migrated to the cloud. Storing the data in the cloud has advantages as follows: individuals can reliably store the data and can easily and conveniently access the data; and organizations can save costs. However, when the data are stored remotely, acute concerns for security and privacy are raised. That is to say the sensitive data, such as financial and medical records, are out of the owners’ control and may be accessed by untrusted parties. A traditional public key cryptosystem cannot be employed to protect the data well, since they have drawbacks as follows: (1) they only provide coarse-grained access to encrypted data decrypted only by a single secret key; (2) access to the encrypted data is all or nothing; one can either decrypt to recover the entire ciphertext or learns nothing from the plaintext, except for its length. In the cloud computing system, the data owner may share the data with groups of data consumers based on their attributes or credentials, and only the data consumers whose attributes satisfy the access policy can decrypt. The traditional public key cryptosystem cannot address these problems [1,2].
To address these problems, Sahai et al. [3] first presented the attribute-based encryption (ABE) scheme enforcing fine-grained access control over the ciphertexts. In their scheme, a ciphertext and a private key are associated with descriptive attribute sets. Decryption will succeed if and only if there exist at least d attributes overlapping them. Their scheme is suitable for error-tolerant encryption. However, one drawback of their scheme is that this construction is only able to address formulae comprising one threshold gate. To enhance the expressiveness, Goyal et al. [4] presented the key policy attribute-based encryption (KP-ABE) scheme in which ciphertexts are associated with attribute sets and the private keys are associated with access structures. While they proposed the CP-ABE scheme, they did not implement it. Bethencourt et al. [5] first implemented the CP-ABE scheme. In their scheme, attribute sets are employed to identify the private keys, and ciphertexts are associated with access structures. The ciphertexts are decrypted by the private keys iff the access structures are satisfied by the attribute sets. However, they proved security in the generic group model. To achieve CP-ABE schemes in the standard model, work has been done as follows: Cheung et al. [6] presented a CP-ABE scheme constructed under a policy with an AND gate. However, their scheme requires that the number of system attributes be fixed at setup, and the access structure of their scheme only supports an AND gate. These two drawbacks make it less expressive. To enhance the expressiveness, Goyal et al. [7] proposed the bounded CP-ABE scheme. However, the encryption and decryption cost blows up greatly, which influences its application in practice. Lewko et al. [8] presented a CP-ABE scheme that is expressive and adaptively secure. However, their scheme is based on a composite order bilinear group, which incurs some efficiency loss, and the assumption is a non-standard strong assumption. Waters [9] proposed an expressive, efficient and provable secure CP-ABE scheme in the standard model and achieves the same performance and functionality as the scheme of [5]. Researchers applied CP-ABE schemes to a cloud storage system, social networks, etc.
In a CP-ABE scheme, a private key for a user’s attributes is not able to be generated by herself. Hence, there exists a trusted party, named the authority, i.e., the private key generator (PKG), which sets up the system. To get a private key from the PKG, a user with some attributes will go to a PKG to get the private key associated with her attributes. During this process, she needs to prove to the PKG that these attributes are entitled to her. Then, the private key is generated and passed on to her by the PKG. Since the authority possesses the master secret of the scheme, it is capable of calculating the private key associated with the users’ arbitrary attributes, and it is able to decrypt any ciphertexts encrypted to any users; it has to be absolutely trusted. If the authority engages in malicious activities, it will not be caught and sued. Thus, it is required that the trust in the authority should be reduced in a CP-ABE scheme. That is to say, there still exists the key escrow problems in the CP-ABE scheme. Due to the inherent key escrow problem, the CP-ABE scheme is restricted to be used in the small and closed groups, where there exists a central trusted authority. If this problem is not solved well, it will influence the adoption of the CP-ABE scheme.
Our contributions: We formalize the conception of the black box traceable ciphertext policy attribute-based encryption scheme and propose its construction. This construction builds on the ciphertext policy attribute-based encryption scheme presented by [9]. In this scheme, a secure private key generation protocol is constructed. A new security proof is presented to show that this scheme is a traceable (T)-CP-ABE scheme, which handles black box decoders. In this T-CP-ABE scheme, the authority will access decryption oracles, and a judge will decide whether the decoder box is created by the malicious authority or the malicious user.
Organization: The remainder of our paper is organized as follows. Preliminaries are presented in Section 2. The scheme definition and the definition of the security game are presented in Section 3. The scheme construction is presented in Section 4. Security is proven in Section 5. Related works are discussed in Section 6. We make a conclusion and specify future work in Section 7.

2. Preliminaries

2.1. Bilinear Map

Let 𝔾 and 𝔾 T be two cyclic groups whose orders are prime order p, respectively. g , u are a generator of 𝔾, respectively. e is a bilinear map e : 𝔾 × 𝔾 𝔾 T , which has properties as follows. Bilinearity: for any a , b p , e ( g a , u b ) = e ( g , u ) a b . Nondegenerate: e ( g , g ) 1 𝔾 T , e ( g , g ) is a generator of 𝔾 T . If the group operations on 𝔾 and on the bilinear map e : 𝔾 × 𝔾 𝔾 T are efficiently computable, then 𝔾 is a bilinear group. In our scheme, the symmetric bilinear map is employed, such that: e ( g a , u b ) = e ( g , u ) a b = e ( g b , u a ) .

2.2. Access Structure

Let 𝕊 be the universe of attributes. An access structure [10] on 𝕊 is a collection 𝔸 of non-empty subsets of attributes, i.e., 𝔸 2 𝕊 { } . We call the sets in 𝔸 the authorized attribute sets and the sets not in 𝔸 the unauthorized attribute sets. Specifically, an access structure is monotone if B , C : if B 𝔸 and B C , then C 𝔸 . In this scheme, only the monotone access structure is handled.

2.3. Linear Secret Sharing Scheme

A secret sharing scheme [10] Π over the attribute set is called linear over p if .1. The shares for each attribute of a secret form a vector over p .2. There is a matrix M with h rows and c columns for Π. For any i = 1 , , h , let the function φ defined the attribute that labels the i-th row as φ ( i ) . Given the column vector v = ( s , x 2 , , x n ) T , in which T is the transpose of the vector v , s is the secret that will be shared and x 2 , , x n p are uniformly picked at random, then M v is the vector of h shares of the secret s based on Π. The share ( M v ) i belongs to the attribute φ ( i ) .
Let attribute set S 𝔸 S 𝕊 be any authorized attribute set, and let I = { i | i { 1 , , h } φ ( i ) S } . Then, there exist constants { η i p } i I , such that, if { s i } i I are valid shares of a secret s according to Π, then Π i I η i s i = s .

2.4. Complexity Assumptions

Decisional bilinear Diffie-Hellman (DBDH): Let G ( 1 κ ) ( p , g , 𝔾 , 𝔾 T , e ) . Pick ξ , ϖ , ρ , d p uniformly at random. No probabilistic polynomial time (PPT) attackers 𝓐 are able to distinguish the tuple ( A = g ξ , B = g ϖ , C = g ρ , D = e ( g , g ) ξ ϖ ρ ) from the tuple ( A = g ξ , B = g ϖ , C = g ρ , D = e ( g , g ) d ) with non-negligible advantages.

2.5. Fully Simulatable k-out-of-N Oblivious Transfer

A k-out-of-N oblivious transfer protocol makes a recipient pick and receive exactly k of the N messages from the sender, such that the remaining messages are hidden from the recipient and the choices of the recipient are hidden from the sender. We employ fully-simulatable oblivious transfer [11].

2.6. Ciphertext Policy Attribute-Based Encryption

Waters [9] proposed the ciphertext policy attribute-based encryption (CP-ABE) scheme, which is expressive, efficient and provably secure. In this scheme, ciphertexts are associated with access structures, and private keys are associated with attribute sets. They proposed a CP-ABE scheme, which is proven secure in the DBDH assumption in the standard model. Our scheme in part builds on this scheme.

3. Syntax and Definition of Security

3.1. Our Scheme Definition

Definition 1. A traceable ciphertext policy attribute-based encryption (T-CP-ABE) scheme comprises five components.
Setup ( 1 k ) ( MSK , PP ) : The Setup algorithm takes in a security parameter κ, and it returns a master secret key MSK and the public parameters PP.
PriKeyGen ( PP , MSK , ID , S ) ( ) K I D , S : This is a private key generation algorithm, which takes in PP,MSK, S and ID employed to trace back to the corresponding owner and the Authority engages in an oblivious transfer protocol with a user U, where S is an attribute set belonging to the user U. At the end, U receives a private key for her ID and her attribute set S, K ( I D , S ) . The notation ( ) denotes the fact that the authority may not exactly know which key the user has received.
Encrypt ( PP , ID , 𝔸 , m ) CT ID , 𝔸 : The Encrypt algorithm takes in the public parameters PP, the identity ID, access structure 𝔸 and a message m and it returns a ciphertext CT ID , 𝔸 .
Decrypt ( PP , CT ID , 𝔸 , K I D , S ) m : The Decrypt algorithm takes in the public parameters PP, the ciphertext CT ID , 𝔸 and a private key K I D , S . It returns a plaintext message m if the identity of the private key matches that of the ciphertext and the attribute set S satisfies the access structure 𝔸, else it returns an error symbol ⊥.
Definition 2. Useful Decoder Box) A PPT algorithm 𝒟 is a ε Useful Decoder Box for the identity ID, where ε is non-negligible, if P r [ 𝒟 ( Encrypt ( PP , ID , 𝔸 , m ) ) = m ] > ε .
Trace 𝒟 ( PP , ID , K I D , S , ε ) { User , Authority } : The Trace algorithm takes in the identity ID, the public parameters PP, a well-formed private key K I D , S , a parameter ε and has black box access to a ε useful decoder box 𝒟. It outputs User or Authority.
The tracing algorithm allows an honest user to present her private key and a captured decoder box to a judge to incriminate the misfeasance of Authority; furthermore, the tracing algorithm hinders a dishonest user from falsely incriminating that the Authority has created the decoder box.

3.2. Definition of Security

A secure black box traceable ciphertext policy attribute-based encryption (T-CP-ABE) scheme holds if the following three requirements are met: (1) it satisfies IND-ID-CCA security; (2) if the Authority created a decoder box 𝒟, the tracing algorithm should incriminate the Authority; (3) if the colluding users created the decoder box 𝒟, it should incriminate these users. We capture the security conditions in the three games as follows:
Definition 3. (IND-ID-Chosen Plaintext Attacks (CPA) Security Game) A T-CP-ABE scheme is IND-ID-CPA secure if no PPT attacker 𝒜 has non-negligible advantages in this game:
Setup: The challenger runs the Setup algorithm generating MSK and PP given to the attacker 𝒜.
Query Phase 1: The attacker 𝒜 runs the interactive PriKeyGen protocol with the challenger for adaptively-picked identities ID i and attribute sets S i , where i { 1 , , q } , and receives the corresponding private keys K ID i , S i .
Challenge: The attacker 𝒜 submits two plaintext messages m 0 and m 1 , which are of equal length, challenge identity ID and a challenge access structure 𝔸 , except that ID should not be equal to any of the identities queried in Query Phase 1, and the access structure 𝔸 is satisfied by none of the attribute sets S i where i { 1 , , q } in Query Phase 1. The challenger flips a fair binary coin β { 0 , 1 } and encrypts m β with ID and 𝔸 . The resulting ciphertext CT = Encrypt ( P P , I D , 𝔸 , m β ) is passed on to the attacker 𝒜.
Query Phase 2: Phase 1 is repeated, except that ID should not be equal to any of the identities in ID i , and the access structure 𝔸 is satisfied by none of the attribute sets S i in which i { q + 1 , , Q } , where Q is the number of the queries made by the attacker.
Guess: The attacker returns a guess β { 0 , 1 } of β; if β = β , the attacker will win.
Definition 4. The proposed scheme is secure against chosen plaintext attacks (CPA) if no probabilistic polynomial time adversary has a non-negligible advantage in the aforementioned game, in which the advantage is defined as:
| P r [ β = β ] - 1 2 |
The above game can be extended to obtain security against chosen ciphertext attacks where decryption oracles are allowed for in Phase 1 and Phase 2. Such a game is called the IND-ID-CCA security game.
Definition 5. (Dishonest User Security Game) In this game, some dishonest users ID i where i { 1 , , Q } collude to try to create a decoder box framing the Authority. The challenger and the attacker have the following common inputs: the security parameter κ and another parameter ε = 1 / p o l y ( κ ) . A T-CP-ABE scheme is Dishonest User secure if no PPT attacker 𝒜 has a non-negligible advantage in the following game:
Init: The attacker 𝒜 commits to a challenge identity ID to the challenger.
Setup: The challenger runs the Setup algorithm, which generates MSK and PP that are given to the attacker 𝒜.
Private Key Generation Queries: The attacker 𝒜 runs the interactive PriKeyGen protocol with the challenger for adaptively-picked identities ID i and attribute sets S i , where i { 1 , , Q } , and receives the corresponding private keys K ID i , S i .
Create Decoder Box: The attacker 𝒜 submits a private key K ID * , S and a decoder box 𝒟 for the challenge identity ID declared in the Init phase.
Tracing Failure: The tracing algorithm falsely incriminates the Authority, i.e., Trace 𝒟 ( ID , K ID , S , ε ) = Authority . Furthermore, the decoder box 𝒟 is ε useful for ID, i.e., P r [ 𝒟 ( Encrypt ( PP , ID , 𝔸 , m ) ) = m ] > ε . If these two conditions hold, the attacker 𝒜 will win this game.
Definition 6. (Dishonest Authority Security Game) In this game, a malicious Authority tries to create a decoder box framing the user. Both the challenger and the attacker Authority have common inputs as follows: the security parameter κ and another parameter ε = 1 / p o l y ( κ ) . A traceable CP-ABE scheme is Dishonest Authority secure if no PPT attacker 𝒜 has non-negligible advantages in the following game:
Setup: The challenger is given an identity ID and PP, which are generated by the attacker 𝒜 (acting as a malicious Authority) and checks whether ID and PP are well formed, aborting if these checks fail.
PriKeyGen: The attacker 𝒜 and the challenger conduct the private key generation protocol to generate a private key for the identity ID and the attribute set S. If no party aborts, the private key K ID , S is received by the challenger as output.
Decryption Queries: The attacker 𝒜 adaptively makes queries for ciphertexts CT 1 , , CT Q of the challenger, and the challenger responds with the decryption values under K ID , S .
Create Decoder Box: The attacker 𝒜 returns a decoder box 𝒟.
Tracing Failure: The tracing algorithm falsely incriminates the User, i.e., Trace 𝒟 ( ID , K ID , S , ε ) = User . Furthermore, the decoder box 𝒟 is ε useful for ID, i.e., P r [ 𝒟 ( Encrypt ( PP , ID , 𝔸 , m ) ) = m ] > ε . If these two conditions hold, the attacker 𝒜 will win this game.
Definition 7 A black box T-CP-ABE scheme is secure if no PPT attacker 𝒜 has non-negligible advantage in κ in the IND-ID-CCA security game, Dishonest User Security Game and Dishonest Authority Security Game.

4. Scheme Construction

A ciphertext has a structure as follows: (ID, 𝔸 1 , , 𝔸 Z ), where ID is the identity of the user and 𝔸 1 , , 𝔸 Z are Z (where Z is a positive integer) parallel repetitions, each comprising monotone access structure 𝔸 z ( 1 z Z ) . A private key has a structure as follows: (ID, S 1 , , S Z ), where each S z ( 1 z Z ) comprises k out of N attributes. A ciphertext can be decrypted by a user U iff (the ID of the private key matches that of the ciphertext) AND ( S 1 satisfies monotone access structure 𝔸 1 ) AND⋯ AND ( S Z satisfies monotone access structure 𝔸 Z ). Let L be the length of bits of the identity string ID p , N the global security parameter, Z super-logarithmic in N, C m a x the maximum number of columns of the matrix M and ID j the j-th bit of the identity ID p . Let [ L ] , [ N ] , [ C m a x ] and [ Z ] be the sets { 1 , , L } , { 1 , , N } , { 1 , , C m a x } and { 1 , , Z } , respectively.
Setup : For each j [ L ] , pick two random elements ω j , 0 and ω j , 1 from p with the restriction that these 2 L values are all different. For each c [ C m a x ] , j [ N ] and z [ Z ] , pick a random t c , j , z uniformly from p . Pick two random elements μ , θ p uniformly. The public parameters are:
P P = ( { W j , z = g ω j , z : j [ L ] , z { 0 , 1 } } { T c , j , z = g t c , j , z : c [ C m a x ] , j [ N ] , z [ Z ] } , U = e ( g , g ) μ , g , g θ ) .
The master secret key M S K = ( { ω j , z : j [ L ] , z { 0 , 1 } } , { t c , j , z : c [ C m a x ] , j [ N ] , z [ Z ] } , μ ) .
PriKeyGen : This protocol enables a user U to obliviously pick which attributes she needs, employing a k-out-of-N oblivious transfer protocol upon each repetition. The corresponding same index in each repetition has distinct attributes. Distinct attributes correspond to distinct elements in p . The repetitions are conducted in parallel and are viewed as individual components of the private key.
The private key generation protocol between the Authority and a user U is performed as follows:
Step 1. The user will abort if W j , z and T c , j , z are not all different.
Step 2. The Authority picks Z + 1 elements μ 0 , , μ Z p uniformly at random with the restriction that μ 0 + + μ Z = μ , where μ 0 is associated with the identity and μ 1 , , μ Z are associated with the sets of attributes.
Step 3. The Authority picks L elements ν 1 , , ν L p uniformly at random with the restriction that ν 1 + + ν L = μ 0 .
Step 4. The Authority picks r c , z , μ z p : c [ C m a x ] , z [ Z ] uniformly at random with the restriction that μ 1 + + μ Z = μ - μ 0 .
Step 5. The Authority calculates the private key components K j = g ν j / ω j , I D j for any j [ L ] and passes them on to the user U. It picks elements r c , z p : c [ C m a x ] , z [ Z ] uniformly at random, calculates the private key components ({ K b , z = g μ z g θ r 1 , z , D c , z = g r c , z : c [ C m a x ] , z [ Z ] } , { j S z , K j , z = c [ C m a x ] T c , j , z r c , z : c [ C m a x ] , j [ N ] , z [ Z ] } ), sends { K b , z , D c , z } to the user U and stores K j , z .
Step 6. The Authority picks permutations 𝒫 = ( P 1 , , P Z ) S N Z at random.
Step 7. The Authority and the user U conduct Z executions of a k-out-of-N oblivious transfer protocol in which the Authority is a sender and the user U is a receiver. In the z-th execution, the private input of the Authority is the private key components { K P z ( j ) , z } j = 1 N , and the private input of the user U is a set S z of k attributes picked at random. The private output of the user is the private key component { P z ( j ) , K P z ( j ) , z } j S z
Step 8. The Authority passes the permutation list 𝒫 to the user U. The user U checks whether she obtains the correct private key components as a percent 𝒫. If not, it will abort.
Step 9. The user U sets K I D , S = ( { K j } j [ L ] , { K b , z = g μ z g θ r 1 , z , D c , z = g r c , z : c [ C m a x ] , z [ Z ] } , { ( S z ) , { K j , z } j S z } z [ Z ] ) and checks whether a private key validity check on K I D , S passes. If not, the user U will abort.
Key Validity Check: For a given private key K I D , S = ( { K j } j [ L ] , { K b , z = g μ z g θ r 1 , z , D c , z = g r c , z : c [ C m a x ] , z [ Z ] } , { ( S z ) , { K j , z } j S z } z [ Z ] ) for the ID and attribute set S, to check whether this private key is well formed, a deterministic algorithm Key Validity Check is defined as follows:
Step 1.
e ( K b , z , g ) · e ( g θ , D 1 , z ) - 1 = e ( g μ z g θ r 1 , z , g ) · e ( g θ , g r 1 , z ) - 1 = e ( g μ z , g ) = e ( g , g ) μ z
Step 2. Check whether e ( g , g ) μ = j [ L ] e ( W j , z , K j ) z [ Z ] e ( g , g ) μ z and j S z , e ( K j , z , g ) = e ( T c , j , z , c [ C m a x ] D c , z ) holds. If not, it fails. If so, the private key validity check passed, and the user U sets K I D , S = K I D , S .
Encrypt : The encryption algorithm takes in P P , a message m G T and an LSSS access structure 𝔸 z = ( M z , φ z ) : z [ Z ] , where φ z associates rows of M z to attributes and φ z is an injective function. Let M z denote an h × C m a x matrix. This algorithm picks a random vector v z = ( s , y 2 , z , , y C m a x , z ) employed to share the encryption exponent s p . The ciphertext CT ID , 𝔸 is constructed as follows:
CT ID , 𝔸 = ( { 𝔸 z } z [ Z ] , E = m · e ( g , g ) μ s , E b , z = g s , { ( E j = W j , I D j s } ) : j [ L ] } , { E i , c , z = g θ M i , c , z v c , z T c , j , z - s : i { 1 , , h } , c [ C m a x ] , j S z , z [ Z ] } )
Ciphertext Validity Check: To check whether this ciphertext CT ID , 𝔸 is well formed, a deterministic Ciphertext Validity Check algorithm is defined as follows: If the attribute sets S z of the private keys satisfy the access structures 𝔸 z of the ciphertexts, then there exist coefficients { η i , z | η i , z p : i = 1 , , h , z [ Z ] } , such that φ ( i ) S z η i , z · M i , z = ( 1 , 0 , , 0 ) , where M i , z is the i-th row vector of the access matrix M z . Check if e ( E j , W 1 , I D 1 ) = e ( W j , I D j , E 1 ) , j [ L ] and φ ( i ) S z e ( E i , c , z , g ) η i , z = e ( g θ , E b , z ) · φ ( i ) S z e ( T c , j , z - 1 , E b , z ) η i , z , j S z , z [ Z ] holds. If not, it fails and returns ⊥. If so, the ciphertext validity check passed, and the user U sets CT ID , 𝔸 = CT ID , 𝔸 .
Decrypt : The Decrypt algorithm takes in the public parameters PP, the well-formed CT ID , 𝔸 and K I D , S . If the identity of the private key matches that of the ciphertext and the attribute sets S z of the private keys satisfy the access structures 𝔸 z of the ciphertexts, then there exist coefficients η i , z p , such that φ ( i ) S z η i , z · M i , z = ( 1 , 0 , , 0 ) ; the ciphertext is decrypted to recover the message m as follows:
E / j [ L ] e ( E j , K j ) z [ Z ] { e ( E b , z , K b , z ) / c [ C m a x ] e ( D c , z , φ ( i ) S z E i , c , z ) η i , z φ ( i ) S z e ( K j , z , E b , z ) η i , z } = m · e ( g , g ) μ s / j [ L ] e ( W j , I D j s , g ν j / ω j , I D j ) · z [ Z ] { e ( E b , z , K b , z ) / c [ C m a x ] e ( g r c , z , φ ( i ) S z g θ M i , c , z v c , z T c , j , z - s ) η i , z φ ( i ) S z e ( c [ C m a x ] T c , j , z r c , z , g s ) η i , z } = m · e ( g , g ) μ s / e ( g , g ) μ 0 s z [ Z ] { e ( E b , z , K b , z ) / c [ C m a x ] e ( g r c , z , φ ( i ) S z g θ M i , c , z v c , z ) η i , z } = m · e ( g , g ) μ s / e ( g , g ) μ 0 s z [ Z ] { e ( E b , z , K b , z ) / e ( g r 1 , z , φ ( i ) S z g θ M i , 1 , z v 1 , z ) η i , z } = m · e ( g , g ) μ s / e ( g , g ) μ 0 s z [ Z ] { e ( g s , g μ z g θ r 1 , z ) / e ( g r 1 , z , g θ s ) } = m · e ( g , g ) μ s / e ( g , g ) μ 0 s e ( g , g ) ( μ 1 + + μ Z ) s = m · e ( g , g ) μ s / e ( g , g ) μ s = m
Trace : The tracing algorithm runs a Key Validity Check to check whether the private key is well formed. It repeats the experiments p o l y ( κ ) times as follows:
Pick a set of attributes S z with the restriction with S z not satisfying the access structure 𝔸 z .
Pick a message m at random and encrypt m using the access structure 𝔸 z .
The decoder box returns some message m = D ( C T I D , 𝔸 ) .
For any iteration, if m = m , incriminate the Authority, else incriminate the user U.

5. Security Proofs

The security of the aforementioned scheme is proven as follows:
Theorem 1. The advantage of an attacker in the IND-ID-CCA security game is negligible for the T-CP-ABE scheme under the DBDH assumption.
This theorem is trivially reduced to the IND-ID-CCA security of [9] and [12]. If an attacker breaks the IND-ID-CCA security of our scheme, it is trivial to construct an attacker breaking the IND-ID-CCA security of Naccache’s scheme [12] and Waters’s scheme [9]. For any message m, it is a secret shared with m 1 m 2 in which a random m 1 is picked uniformly and encrypted with the CP-ABE scheme [9] and m 2 with Naccache’s IBE scheme [12] to achieve the T-CP-ABE scheme under the DBDH assumption.
Theorem 2. Provided that the k-out-of-N oblivious transfer is secure based on the real/ideal world security definition, the advantage of an attacker in the Dishonest Authority Security Game is negligible for the T-CP-ABE scheme.
Proof. This scheme comprises Z attribute sets in parallel and employs fully-simulatable oblivious transfer in the private key generation phase. If Key Validity Check and Ciphertext Validity Check pass, this scheme will incriminate the Authority, which can access a decryption oracle 𝒟. Via Key Validity Check and Ciphertext Validity Check, all of the same ciphertexts can be decrypted by the users whose attributes satisfy the access structures associated with these ciphertexts to the same value, and the Authority can decrypt to this value.
Let 𝒟 be a ε useful decoder box, where ε is non-negligible. Perform the experiment as follows:
Pick a set of attributes S z , except that S z does not satisfy the access structure 𝔸 z .
Pick a message m at random; encrypt it employing the access structure 𝔸 z , and this returns the resulting ciphertext CT ID , 𝔸 .
The decoder box returns m = 𝒟 ( CT ID , 𝔸 ) .
Return the Authority if m = m . □
Theorem 3. The advantage of an attacker in the Dishonest User Security Game is negligible for the T-CP-ABE scheme under the DBDH assumption.
Proof. A user can adapt the security proof in [9] to show that the selective ID Dishonest User Security Game can be reduced to the decisional bilinear Diffie-Hellman (DBDH) assumption. □
Init: The attacker 𝒜 declares a challenge identity ID . The ideal functionality from the ideal world in the simulation based model of Oblivious Transfer picks W j , z and the challenge access structures { 𝔸 z } z [ Z ] , which are employed to obtain the resulting challenge ciphertexts sent to the challenger 𝒞 by .
Setup: The challenger 𝒞 sends public parameters P P to , which transfers P P to 𝒜.
Private Key Generation Query: If 𝒜 makes a request for a private key on I D I D , then sends the corresponding user attributes to that passes it to 𝒞, it outputs a well-formed private key that sends back to 𝒜. If I D = I D * , since obtains the private keys, it can pick permutations P 1 , , P Z , such that the private key received by 𝒜 cannot decrypt a ciphertext containing the previously-picked access structure. queries 𝒞 for this private key and sends it back to 𝒜.
Create Decoder Box: 𝒜 submits a private key K I D , S and a decoder box 𝒟. If 𝒜 wins the Dishonest User Security Game, then the Authority will be incriminated by the decoder box. picks two messages m 0 , m 1 at random sent to 𝒞 that sends a challenge ciphertext CT ID , 𝔸 under the previously-picked access structures. If K I D , S can decrypt this message, so can , and sends the right guess to 𝒞; else CT ID * , 𝔸 is a random ciphertext that I D cannot decrypt. Hence, if 𝒜 wins the Dishonest User Security Game, 𝒟 has a non-negligible advantage in decrypting this ciphertext. Therefore, has a non-negligible advantage in the attribute-based selective set game against 𝒞, which is in contradiction with the security of the CP-ABE scheme under the DBDH assumption.

6. Related Work

To mitigate the trust on the PKG, Boneh et al. [13] proposed an approach that has the multiple PKGs distributed based on threshold cryptography. However, their scheme brings about extra infrastructure and communication. Without employing multiple PKGs, the known mitigation approaches are as follows: Goyal [14] presented a traceable identity based encryption scheme. To obtain black box security, Libert et al. [15] presented an IBE scheme, which is weak black box traceable, while ciphertexts and private keys are short, and Goyal et al. [16] proposed the black box traceable IBE scheme. Both schemes are selectively secure. To enhance the security, Libert et al. [15] proposed the fully-secure traceable IBE scheme. Since ABE schemes are the generalizations of IBE schemes, they inherit the key escrow problem from IBE schemes. Some traceable CP-ABE schemes [17] have been presented to handle this problem. Unfortunately, the access structures of these schemes only support the AND gate, which makes them less expressive. To enhance the expressiveness, Liu et al. [18] presented a novel T-CP-ABE scheme, which supports access polices as monotone access structures. Their scheme achieves traceability and high expressiveness at the same time. However, their scheme only achieves white box traceability. Furthermore, since their scheme builds on Lewko et al.’s scheme [8], which is based on the composite order group, which incurs some efficiency loss, and Lewko et al.’s scheme is based on non-standard assumption, Liu et al’s scheme [18] inherits the same drawbacks as Lewko et al.’s scheme.

7. Conclusions and Future Work

We present a traceable ciphertext policy attribute-based encryption scheme that addresses black box decoders. Security is proven in the IND-ID-CCA security game, Dishonest User Security Game and Dishonest Authority Security Game. Here, we only investigate the accountability of the attribute-based encryption scheme, which is only payload hiding, but not attribute hiding. In future work, we will design a traceable predicate encryption scheme to catch the malicious authority. Furthermore, there exists the key escrow problem in the attribute-based encryption scheme from lattice resisting quantum cryptoanalysis. To the best of our knowledge, the problem is still an open problem. In future work, we will solve this problem.

Acknowledgments

This work is supported by the NSF of China (No. 61402376) and the science and technology foundation of Sichuan Province of China (No. 2014GZ0109). The authors thank Shengke Zeng for many helpful suggestions and gratefully acknowledge the anonymous reviewers for their valuable comments.

Author Contributions

Xingbing Fu designed research and wrote the paper, Xunyun Nie and Fagen Li proposed suggestions and revised this paper. All authors have read and approved the final manuscript.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Boneh, D.; Sahai, A.; Waters, B. Functional encryption: Definitions and challenges. In Theory of Cryptography, Proceedings of the 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, 28–30 March 2011; Springer: Berlin/Heidelberg, Germany, 2011. Lecture Notes in Computer Science. Volume 6597, pp. 253–273. [Google Scholar]
  2. Hoeteckee, W. Functional Encryption and Its Impact on Cryptography. In Security and Cryptography for Networks, Proceedings of the 9th International Conference, SCN 2014, Amalfi, Italy, 3–5 September 2014; Springer: Berlin/Heidelberg, Germany, 2014. Lecture Notes in Computer Science. Volume 8642, pp. 318–323. [Google Scholar]
  3. Sahai, A.; Waters, B. Fuzzy identity-based encryption. In Advances in Cryptology—EUROCRYPT 2005, Proceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, 22–26 May 2005; Springer: Berlin/Heidelberg, Germany, 2005. Lecture Notes in Computer Science. Volume 3494, pp. 457–473. [Google Scholar]
  4. Goyal, V.; Pandey, O.; Sahai, A.; Waters, B. Attribute-based Encryption for Fine-Grained access Control of Encrypted Data. In Proceedings of the 13th ACM Conference on Computer and Communications Security, Alexandria, VA, USA, 30 October–3 November 2006; pp. 89–98.
  5. Bethencourt, J.; Sahai, A.; Waters, B. Ciphertext-Policy Attribute-Based Encryption. In Proceedings of the IEEE Symposium on Security and Privacy, Berkeley, CA, USA, 20–23 May 2007; pp. 321–334.
  6. Cheung, L.; Newport, C. Provably Secure Ciphertext Policy ABE. In Proceedings of the 14th ACM Conference on Computer and Communications Security, Alexandria, VA, USA, 29 October–2 November 2007; pp. 456–465.
  7. Goyal, V.; Jain, A.; Pandey, O.; Sahai, A. Bounded Ciphertext Policy Attribute-Based Encryption. In Automata, Languages and Programming, Proceedings of the 35th International Colloquium, ICALP 2008, Part II, Reykjavik, Iceland, 7–11 July 2008; Springer: Berlin/Heidelberg, Germany, 2008. Lecture Notes in Computer Science. Volume 5126, pp. 579–591. [Google Scholar]
  8. Lewko, A.; Okamoto, T.; Sahai, A.; Takashima, K.; Waters, B. Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption. In Advances in Cryptology—EUROCRYPT 2010, Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Riviera, French, 30 May–3 June 2010; Springer: Berlin/Heidelberg, Germany, 2010. Lecture Notes in Computer Science. Volume 6110, pp. 62–91. [Google Scholar]
  9. Waters, B. Ciphertext-Policy Attribute-Based Encryption: An Expressive, Efficient, and Provably Secure Realization. In Public Key Cryptography—PKC 2011, Proceedings of the 14th International Conference on Practice and Theory in Public Key Cryptography, Taormina, Italy, 6–9 March 2011; Springer: Berlin/Heidelberg, Germany, 2011. Lecture Notes in Computer Science. Volume 6571, pp. 53–70. [Google Scholar]
  10. Beimel, A. Secure Schemes for Secret Sharing and Key Distribution. Ph.D. Thesis, Israel Institute of Technology, Technion, Israel, 1996. [Google Scholar]
  11. Camenisch, J.; Neven, G.; Shelat, A. Simulatable Adaptive Oblivious Transfer. In Advances in Cryptology—EUROCRYPT 2007, Proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, 20–24 May 2007; Springer: Berlin/Heidelberg, Germany, 2007. Lecture Notes in Computer Science. Volume 4515, pp. 573–590. [Google Scholar]
  12. Naccache, D. Secure and Practical Identity-Based Encryption. IET Inf. Secur. 2007, 1, 59–64. [Google Scholar] [CrossRef]
  13. Boneh, D.; Franklin, M. Identity-Based Encryption from the Weil Pairing. In Advances in Cryptology—CRYPTO 2001, Proceedings of the 21st Annual International Cryptology Conference, Santa Barbara, CA, USA, 19–23 August 2001; Springer: Berlin/Heidelberg, Germany, 2001. Lecture Notes in Computer Science. Volume 2139, pp. 213–229. [Google Scholar]
  14. Goyal, V. Reducing Trust in the PKG in Identity Based Cryptosystems. In Advances in Cryptology—CRYPTO 2007, Proceedings of the 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, 19–23 August 2007; Springer: Berlin/Heidelberg, Germany, 2007. Lecture Notes in Computer Science. Volume 4622, pp. 430–447. [Google Scholar]
  15. Libert, B.; Vergnaud, D. Towards Black-Box Accountable Authority IBE with Short Ciphertexts and Private Keys. In Public Key Cryptography—PKC, Proceedings of the 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, CA, USA, 18–20 March 2009; Springer: Berlin/Heidelberg, Germany, 2009. Lecture Notes in Computer Science. Volume 5443, pp. 235–255. [Google Scholar]
  16. Goyal, V.; Lu, S.; Sahai, A.; Waters, B. Black-Box Accountable Authority Identity-Based Encryption. In Proceedings of the 15th ACM Conference on Computer and Communications Security, Alexandria, VA, USA, 27–31 October 2008; pp. 427–436.
  17. Li, J.; Ren, K.; Kim, K. A2BE: Accountable Attribute-based Encryption for Abuse Free Access Control. IACR Cryptology ePrint Archive. 2009; 118. [Google Scholar]
  18. Liu, Z.; Cao, Z.; Wong, D. White-Box Traceable Ciphertext-Policy Attribute-Based Encryption Supporting Any Monotone Access Structures. IEEE Trans Inf. Forensics Secur. 2013, 8, 76–88. [Google Scholar]
Back to TopTop