Unbounded Key-Policy Attribute-based Encryption with Black-Box Traceability

Attribute-based encryption received widespread attention as soon as it was proposed. However, due to its specific characteristics, some restrictions on attribute set are not flexible enough in actual operation. In addition, since access authorities are determined according to users' attributes, users sharing the same attributes are difficult to be distinguished. Once a malicious user makes illicit gains by their decryption authorities, it is difficult to track down specific user. This paper follows practical demands to propose a more flexible key-policy attribute-based encryption scheme with black-box traceability. The scheme has a constant size of public parameters which can be utilized to construct attribute-related parameters flexibly, and the method of traitor tracing in broadcast encryption is introduced to achieve effective malicious user tracing. In addition, the security and feasibility can be proved by the security proofs and performance evaluation in this paper.


I. INTRODUCTION
The rapid development of the network and communication industry has made communication system architectures more and more diverse. Complex business requirements require a more flexible access control of data. Therefore, the model of the authority management system is no longer confined to the traditional identity-based user management. At the same time, security issues are still one of the most important issues on any updated node. We have always used encryption to ensure data security, and then control user access authorities through key management. Nowadays, traditional encryption systems can hardly meet the current demand for flexible management of authorities. Therefore, attribute-based encryption (ABE) [1] came into being.
ABE makes the user's access authority or the access threshold of cipher-texts no longer bound to the individual user, but is bounded by a set of attributes. Therefore, ABE technology can better implement fine-grained access control. Normally, ABE systems are mainly grouped into two forms by different settings of access structures. Systems with key-policy construct access structures corresponding to the attributes owned by users and embeds them into users private keys, whereas the systems with cipher-policy bind such access structures to ciphers. Moreover, researches based on different needs have been proposed solutions one by one in both types.
However, ABE has brought new problems while meeting new demands. First of all, ABE are designed to better adapt to some changes, but there are some inherent limitations in the current structure. At present, the time consumption of most ABE systems in the stage of generating common parameters is linearly related to the maximum size of the global attribute set. For this problem, a concept called unbounded ABE is proposed which means that the public parameter size is not bound to the global attribute base size. Otherwise, since the relevant authorities are described by sets of attributes, once a traitor appears to sell his authority illegally, it will be hard to catch the traitor effectively. For protecting data privacy and interests of users, the traitor tracing mechanism has become indispensable.

A. Related Work
In order to achieve fine-grained access control, Sahai and Waters proposed the first encryption scheme that satisfies the characteristics of ABE in their paper [3]. Since then, Goyal et al. [3] proposed the first KP-ABE, as well as Bethencourt et al. proposed the first CP-ABE in [4], and both of them support any monotonic access tree. At present, there is a series of work on both KP-ABE and CP-ABE [5]- [10] according to different need to obtain better performance and achieve a higher security level.
For some inherent limitations of ABE system design, Lewko and Waters first proposed the concept of Unbounded ABE in [11] and gave their solutions. Since then, Tatsuaki and Katsuyuki have proposed the first unbounded inner-product encryption (IPE) scheme in [12]. In their scheme, the generation of public parameters is no longer limited to attribute sets. Also, there are many pieces of research [13]- [15] that have been explored in depth. The most recent work from this perspective comes from [5]. This scheme is not only unbounded but also implements selective security, relying on simple difficulties.
While ABE blurs the correspondence between the user's decryption authority and the user, it also brings some tricky security issues. Because of users' authorities in the ABE system are determined by the attributes they owned, it will be hard to trace malicious users. To solve this problem, Liu et al. first proposed their scheme in [8] of implementing white-box tracing to implement malicious user tracing in ABE systems, and introduced the concepts of black-box tracing and white-box tracing. After that, Liu et al. continue to put forward a black-box tracing scheme in [9] to solve the same S |: size of the attribute universe; ι: size of an policy; n: number of users in system; x: size of attribute set of a ciphertext. problem, which more in line with the actual scene. In addition, Ning et al. have further proposed more competitive whitebox tracing schemes in [16]- [19]. There are also a number of researches proposed like [10], [20]- [23] aiming at various needs. [24], [25] are recent results of further research on blackbox tracing functionality.

B. Motivation and Contribution
There have been many studies that have proposed some solutions to implement the tracing function in the attributebased encryption system. As we can see, most of the existing schemes with traceability implement related functions in the form of white-box tracing. However, it is clear that the whitebox tracing scenario is not very consistent with the actual malicious user tracing requirements. Moreover, according to the existing black-box tracing schemes, there are limitations to a certain extent. According to the actual need, we put forward the scheme with black-box traceability. Our main contributions are as follows: • Dynamic attribute addition (Unbounded). Our scheme is an unbounded system that can associate attributes with a constant number of public parameters. • Efficient black-box traceability. Our scheme can effectively trace the source of the decryption black-box without obtaining any details related to the private key in sublinear time. Furthermore, we have given the security proof on the hardness assumptions in V. And, from the comparison of efficiency, our solution is also quite competitive in terms of the actual time cost. The following table shows the comparison between our solution and several related works in terms of functionality and efficiency. In Table I, we show the results of comparing five related schemes from a functional standpoint of view. Furthermore, for the three schemes with black box traceability and similar structure, we show their efficiency comparison in Table II.

A. Unbounded Key-Policy Attribute-Based Encryption (KP-ABE)
A standard KP-ABE scheme concludes four algorithms (Setup, KeyGen, Encrypt, Decrypt): Setup(λ, S) → (pp, MSK) : This algorithm includes two input parameters, namely λ, the system security parameter, and S, the global attribute set. After running the system establishment algorithm, the public parameter and the system master key will be output, denoted as pp and MSK respectively.
KeyGen(pp, MSK, A) → SK A : This function is used to generate private keys for users. It has three input parameters, namely the global public parameter, the system master key and an access policy, expressed as pp, MSK, and A respectively.
Encrypt(pp, x, M) → CT x : Through the encryption algorithm, users can get the ciphertext corresponding to the plaintext. It also has three input parameters the system public parameter, an attribute set and the plaintext message, denoted as pp, x and M . And then, it outputs the ciphertext CT x . Note that, in KP-ABE, the attribute set x is publicly given in ciphertext CT x .
Decrypt(pp, CT x , SK A ) → M |⊥: The decryption algorithm can get a result through three parameters. Besides a ciphertext CT x and a private key SK A , it also need the system public parameters pp. Once the attribute set in the ciphertext satisfies the access policy in the private key, it can guarantee the correct plaintext output, otherwise, ⊥.
Correctness. when the x in CT x satisfies the access structure A in SK A . Unbounded If the time consumption of an ABE scheme in the Setup phase is only related to the input security parameters, then we call this scheme unbounded.

B. Bilinear Group of Composite Order
Bilinear group of composite order is firstly proposed in [26] and widely used in a variety of cryptographic systems. The specific definition is as follows.
There should have a group generation algorithm, denoted as G, which need a input parameter λ, usually referred to as safety parameters. And a tuple of (p, p 1 , p 2 , p 3 , G, H, G T , e) is the output. In that, p, p 1 , p 2 , p 3 are four different prime numbers determined by security parameter, G, H, G T are three cyclic groups of order N = pp 1 p 2 p 3 and e : G × H → G T is a mapping that satisfies the following conditions: h) is an N-order element of group G T . All group operations in G, H and G T and bilinear mapping e can be calculated in deterministic polynomial time relative to λ.
Computational Assumptions. The security of the scheme we propose in this paper needs to be proven based on the four assumptions in the compound sequence group, which used e.g. in [5], [27].
Subgroup Decision Assumption. With a generator G, we construct following distribution: The advantage of an algorithm A in breaking (p 1 → p 1 p 2 )− subgroup decision assumption is defined as: By exchanging the roles of G and H and/or permuting the indices for subgroups, one can define Subgroup Decision Diffie-Hellman Assumption. With a generator G, we construct following distribution: The advantage of an algorithm A in breaking p 1 −subgroup Dif f ie − Hellman assumption is defined as: By exchanging the roles of G and H and/or permuting the indices for subgroups, one can define p 2 −subgroup Dif f ie− Hellman assumption and p 3 − subgroup Dif f ie − Hellman assumption.
Decisional Linear Assumption. This is a simple extension of the Decisional Diffie-Hellman (DDH) Assumption. For a generator G, we define the following distribution: Then we define the advantage of an algorithm A in breaking decisional linear assumption to be: External Diffie-Hellman Assumption. For an asymmetrical bilinear mapping e : G × H → G T , the External Diffie-Hellman (XDH) assumption states that the Decisional Diffie-Hellman (DDH) assumption is hard in the group H (Not necessarily hard in G) which has been proved in [28].

C. Access Control
We can find the definition of access structure in [29], and in ABE, attributes correspond to the characteristics of participants, and access structure A can describe a set of them. With a collection of all attributes in the system denoted by {P 1 ,...,P n }, we define A including all the access structures for the attribute set, which has ..,Pn} \{∅}, we describe the sets in it as authorized set, and the unauthorized set identifies those not in L. We use a specific example to describe our system architecture. As showing in Fig.1, We abstract three types of entities from the system:

A. System Model
• Cloud server: In our system, the cloud server, as an entity that provides data storage and sharing, will not destroy the integrity of the data. It can also be said that the cloud server is always honest. But at the same time, it is curious about the data and the attributes of the users. In other words, the cloud server is a semi-trusted entity in our system. • Administrator: Generating system parameters, distributing user private keys, and tracing malicious users are all functions that the administrator is responsible for. In our system, the administrator is considered a trusted party. • User: In our system, users of the system use their private keys to obtain and decrypt data from the cloud server. There may be malicious users who gain benefits by selling their decryption rights which violates regulations.
The users encrypt their data through the public parameters generated by the system administrator to ensure data confidentiality, and then upload the corresponding ciphertexts. Without the system private key, any attacker (including the cloud server serving this system) cannot get any valid data. The uploaded encrypted data does not contain any information related to the users who send them to the cloud, so they are completely anonymous. In addition, when a malicious key leak occurs, we will obtain the source of the compromised key through a tracing algorithm.

B. Malicious User Tracing with Black-Box
In I, we have mentioned that ABE, due to its inherent characteristics, has some unavoidable disadvantages while implementing fine-grained access function. Unlike identitybased encryption, in an ABE system, users' authorities are made up of the attributes they own. Once the key is leaked, it is difficult to accurately trace the traitor. To solve this problem, an entity named black-box was proposed in [9] to simulate the corresponding scene.
In this article, we use a similar concept to describe the corresponding security requirements scenario: We assume that the compromised key is manufactured into a "Black-Box" with decryption authority by the malicious user in exchange for benefits. In return, a malicious user would sell a "black-box" indicating its value (that is, its maximum decryption rights) without providing any specific information about the key it contained. For a malicious user tracer (or surveillance agency), by interacting with this publicly sold decryption box, in the event that he cannot obtain any details of the decryption key it owns, he can trace back to the source of the "black-box" keys.

C. Security Model
We define the security of the scheme proposed in IV in the following games.
The first game is called a message-hiding game. We can find that this game is exactly the same as the standard key policy attribute-based encryption except that the indexes of private keys is specified during the key query phase. This is a standard semantic security game that includes a challenger and an adversary. At the beginning of the game, both the challenger and the adversary A get K and λ as inputs: Setup. The challenger runs Setup(λ) and gives the public parameter pp to A. Phase 1. For k = 1 to q, A adaptively submits A k = (ρ, A), and then, A will get the responses with SK k,A k from challenger.
Challenge. In this phase, A will choose two equal-length messages M 0 , M 1 and an attribute set x * to submit to challenger. The latter will get a random bit b ∈ {0, 1}. A will get CT x * ← Encrypt(pp, M b , x * , 1) which is contains the bit from challenger.
Phase 2. For k = q + 1 to K (K ≤ K), A adaptively submits A k = (ρ, A), and then, A will get the responses with SK k,A k from challenger. We describe tracing capability through the next security game called Game IH . It is worth noting that the ciphertext used to implement the tracing mechanism is different from ordinary ciphertexts. In order to achieve effective malicious user tracing, then it must be guaranteed: 1. When the adversary knows all the private keys except the private key whose matrix position is (i, j), it still cannot distinguish Encrypt (pp, M, x, k) and Encrypt (pp, M, x, k + 1). 2. Even if the adversary holds the key SK k,A , when x does not satisfy the access structure A, it should not be able to determine whether the index k or k +1 for encryption. The game takes the index k as input which is provided as input to both the challenger and the adversary.
Setup. Challenger runs the setup algorithm and gives the public parameter pp to adversary A. Phase 1. For k = 1 to q, A adaptively submits an access policy A k = (ρ, A) to challenger to get SK k,A k .
Challenge. A submits a message M and a non-empty attribute set x * . Challenger runs a random algorithm to get a bit b ∈ {0, 1} and sends Encrypt (pp, M, x * ,k + b) to A.
Phase 2. For k = q + 1 to K (K ≤ K), A adaptively submits an access policy A i = (A, ρ) to challenger to get SK k,A .
Guess. A outputs a guess b ∈ {0,1} as his guess. Game IH : A wins the game if b = b under the restriction that none of the pairs (k, If there were no polynomial-time adversary A with non-negligible advantage, the scheme should be index-hiding.

Theorem
2. If the XDH assumption and the decisional linear assumption hold, then no polynomial-time adversary can win the game Game IH with a non-negligible advantage.
Theorem 3. If our system is a message-hiding and index-hiding scheme, then it is secure and traceable.
IV. THE PROPOSED SCHEME Technical Overview. Our scheme is built in asymmetric composite-order bilinear groups (G, H, G T ). The order N is the product of four prime numbers p, p 1 , p 2 , p 3 . And the first challenge is associating attributes that can be added dynamically with a constant number of public parameters. We will implement the fine-grained access control part through a Monotone Span Programs from [30]. In our scheme, the index associated with the attribute is replaced with s k (ω 0 + kω 1 ), where s k(k∈[ι]) is a parameter generated randomly during encryption. We bind all s k (ω 0 + kω 1 ) through a universal random number s. In ciphertext, they would be used as sω + s k (ω 0 + kω 1 ).
Besides, in order to implement an effective tracing algorithm, we assume that the number of users is a square m 2 , otherwise, fill with some virtual users until the nearest square is satisfied. Thus, we can associate each user in the system with a location in the m × m matrix M . In addition, our ciphertext is composed of row components and column components. Through such a structure to ensure that the ciphertext with (i, j) as the encryption parameter, only the users whose index k ≤ (i − 1) × m + y can decrypt the message. In this way, we can locate the users involved in the construction of the decryption device only by constructing some tracing ciphertext without any details of the private keys.
Nations. We use K to represent the total number of users in the system. Each user corresponds to the position in the matrix M m×m . The user assigned an index k = (i−1)×m+j corresponding to the matrix position (i, j). Let n be a positive integer, then [n] represents the set of integers {1, 2, · · · , n}. And, for g v v v = (g v1 , g v2 , · · · , g vn ) and Similarly, e is a bilinear mapping, and e n n n (g v v v , g v v v ) = Π i∈[n] e(g vi , g v i ).

A. Initialization
The initialization phase is performed by a trusted third party. The main work at this stage is parameter initialization, which corresponds to the Setup algorithm of the standard KP-ABE scheme: Setup(λ, m) → (pp, MSK). The system setup algorithm takes the system security parameter λ and the matrix size m as input. Firstly run the group generation algorithm to get G(λ)→(N =pp 1 p 2 p 3 ,G,H,G T ,e). Then, the algorithm randomly choose exponents α, ω,ω 0 , [m] , and randomly choose generators h, h 1 , h p , g 1 of cyclic groups H p1p2p3 , H p1 , H p , G p1 . It sets public parameters as: The master secret key is set as h 1 , α, α 1 , ..., α m , r 1 , ..., r m , c 1 , ..., c m , ω, ω 0 , ω 1 )

B. User Registration
During the user registration phase, users perform a round of interaction with the system administrator to obtain their private keys. A user applies for registration by sending an access structure expressed in a monotone span program to the system administrator. Once the system administrator receives the user's application information, he adds the user to the user matrix. And embed the user's matrix location into the private key which is generated by the access structure provided by the user. The algorithm for generating the user's private key is as follows: KeyGen(pp, MSK, A = (A, ρ)) → SK (i,j),A . A is a monotonous span program used to describe users' access structure. Where A ∈ Z ι×n N is a matrix and ρ is a mapping. Through the mapping of ρ, we can associate each row of A with a certain attribute. Then, the algorithm randomly chooses exponents η i,j ,ξ 1 ,...,ξ ι ∈ Z N ,ū ū u ∈ Z n−1 N and computes: and sends to the user.
After successfully obtaining the private key, the users have completed their registration.

C. File Generation
Since our cloud server is only a semi-trusted server, in order to ensure data security, users can only store the cipher text on the cloud server. In our system, when a user encrypts data, he can specify the attribute set that needs to be met to access the file and to a certain extent control the range of users who can access the file. Specifically, he uses the public parameter pp of the system and the attribute set he selected to complete the encryption according to the encryption rules in the system. The user's operation can be described as the encryption algorithm below.

For each row i ∈ [m]:
• i <ī: It randomly chooses γ i ∈ Z p , v v v i ∈ Z 2 N and sets: And it computes: Finally, the user uploads the ciphertext CT x obtained by the encryption algorithm to the cloud server. It is worth noting that when generating non-tracing functional ciphertext, there is always (ī,j) = (1, 1) by default.

D. File Access
The condition for the user to successfully decrypt is that the attribute set specified by the file he accesses must satisfy his access structure. This stage is corresponding to the decryption algorithm in the standard KP-ABE system.
Decrypt(pp, CT x , SK (i,j),A ) → M |⊥ . When the selected attribute set in the ciphertext meets the access structure embedded in the user's private key, the algorithm could compute constants {μ k } k∈ [ι] such that And then, it could compute Finally, it could get M by It can be easily verified that M = M will hold only when the index contained in the user's key is not less than the number corresponding to the matrix coordinates defined in the ciphertext.

E. Malicious User Tracing
Before giving the specific definition of the tracing algorithm, let's sort out some necessary expressions.We will use A = (A, ρ) to represent the access structure that determines the user's decryption authority. And, through the form of A = {A 1 , · · · A n }, the set of all the smallest structures that A can be divided into is depicted. When the attribute set x is embedded in the ciphertext to be decrypted, only the corresponding part of A i (i ∈ {1, · · · , n}) is involved in the access. In this way, we can more clearly describe the user's access capabilities.
In a real scenario, a malicious user would typically trade in a decryption device that functions similarly to a decryption key. Such a decryption device takes the ciphertext as the only input, and then outputs the decryption result. During the tracing process, we consider the decryption device provided by the malicious user as a circuit O with probability ≥ 0. And according to the decryption mechanism of the KP-ABE system, we describe its decryption authority as an access structure A O . From this, our tracing algorithm is as follows: The sketch of our security proof is shown in Fig.2. This system IV should be a secure and traceable system, therefore, our need for security is divided into two aspects: • Message security; • The effectiveness of the tracing algorithm. We will reduce these security requirements to different complexity assumptions in later chapters.
A. Security Proof 1) Proof of Theorem 1: P roof. The proof of theorem 1 is similar to the scheme in [5], because they have a similar structure in the implementation of attribute set-based access control. Thus, we prove the theorem by reducing the messagehiding property of our scheme in Game MH to the security of the scheme in [5]. We have omitted the proof details which can be found in [31].
2) Proof of Theorem 2: P roof. Theorem 2 follows from following Lemma 1 and Lemma 2. Lemma 1. Given the XDH assumption and the decisional linear assumption hold, in polynomial time, there is no adversary can distinguish between the cipher-texts encrypted by (ī,j) and (ī,j + 1). P roof. If there is polynomial-time adversary A who can win the game Game IH , then we can construct an algorithm B to solve the XDH problem with the same advantage. As space is limited, we have omitted the format proof which can be found in [31].
Lemma 2. Given a adversary A, who can win the game Game IH in polynomial time, an algorithm B which can solve the XDH assumption is existing. It even has the same advantage as the adversary. P roof. To prove this lemma, we define three hybrid games: • G1: We would encrypt with index (ī,j = m), • G2: We would encrypt with index (ī,j = m + 1), • G3: We would encrypt with index (ī + 1, 1). From the following Claim 1 and Claim 2, we can see that Lemma 4 holds. Claim 1. Given the XDH assumption and the decisional linear assumption hold, in polynomial time, there is no adversary can distinguish G1 and G2 in game Game IH . P roof : Same as Lemma 1.
Claim 2. Given the XDH assumption and the decisional linear assumption hold, in polynomial time, there is no adversary can distinguish G2 and G3 in game Game IH . P roof : The indistinguishability of G2 and G3 can be proved by methods similar to Claim 5.5, 5.6 and 5.7 in [27]. Thus, we prove the theorem by reducing the message-hiding property of our scheme in Game IH to the security of the scheme in [27].
For the sake of simplicity, here we use IBE to represent the scheme of [27], and still use T R to describe our scheme. Therefore, Given a polynomial time adversary A, who can break T R with a non-negligible advantage in Game IH , a algorithm B which can break IBE in polynomial time is existing. And it has the same advantage.
3) Proof of Theorem 3: P roof. Theorem 3 follows from following Lemma 3 and Lemma 4. Lemma 3. If the scheme proposed in IV is messagehiding, then it is secure. P roof. We can see that in our scheme, the default index is set to 1 when users encrypt data. In this way, the non-tracing ciphertext is only a special case in Game MH , so the advantage of adversaries breaking through ordinary ciphertext is the same as winning the game Game MH . That is, if our scheme is message-hiding, then it is secure.
Lemma 4. If the scheme proposed in IV is index-hiding and message-hiding, then it is traceable. P roof. The proof is similar to that in [9], [27], [32]. As in the tracing algorithm, A O is expressed as its smallest form set A O = {x 1 , · · · , x nO }. We definê When O is a valid decryption device and S O satisfies A O , p i,1 ≥ . Because the ciphertext encrypted with the serial number K + 1 (that is, (m + 1, 1)) does not contain any information related to the message provided by the adversary, p i,K+1 is negligible. Therefore, there must be k ∈ [K] making the inequalityp i,k −p i,k+1 ≥ /2K founded. By the Chernoff bound, p i,k − p i,k+1 ≥ /4K holds with an overwhelming probability. As a result, holds with an overwhelming probability by the Chernoff bound. Hence, k ∈ K O and x i satisfying A k are both hold. In that way, K i ⊆ K O and {x i satisfying A k } k∈Ki are established at the same time.

VI. PERFORMANCE EVALUATION
In this section, we simulate our scheme by C++ programming language with the GMP Library(gmp-6.1.2) and PBC Library (pbc-0.5.14). All experiments are implemented on the same computer with the following features: 1) CPU: Intel Core i7-4720; 2) RAM: 8GB; 3) OS: Ubuntu 16.04 over VMware workstation player 15. In order to analyze the feasibility of our scheme more intuitively, we also performed simulation experiments on the [5] and [9] schemes in the same way. We evaluated multiple options in the trial. The experiment was set up in the initialization phase and file generation phase of the system. We conducted two sets of experiments in these two stages by controlling variables. In the initialization phase, simulation experiments were carried out on the three schemes. In the two sets of experiments at this stage, the variables are a pair (the size of the group/the size of the index) and the length of the attribute vector used for the access control part. The specific experimental results are shown in (a) and (b) in the figure 3.
In (a) of Fig.3, we can see that as the size of the groups and the size of the indices gradually increase the time cost in the setup phases of these three schemes has a similar upward trend. However, because the designs of the solutions are different, the actual values of the time cost are distinctly different. Overall, the time cost of our scheme at this stage is higher than the unbounded KP-ABE scheme without the tracing function from [5], and lower than the CP-ABE scheme with the same type of tracing function from [9]. The result of experiments described in (b) of Fig.3 uses attribute vectors as variables to perform simulations in different situations. We can see that for the two schemes with the Unbounded property, the time cost during the setup phase will not be affected by the length of the attribute vector at all. However, for the scheme without that, as the length of the attribute vector increases, the time cost increases significantly.
Besides, in order to realize the function of black-box tracing, our scheme and the scheme in [9] both add extra parts to the ciphertext. In the encrypt phase, the extra parts are the main reason that the schemes with black-box traceability have more time cost than the traditional ABE encryption schemes. Therefore, we performed a simulation experiment on the generation of the ciphertext added to the two schemes respectively during the encryption phase. The experimental results are displayed in (c) and (d) of Fig.3. Fig.3 shows the change of the time cost required to generate additional ciphertext parts as the sizes of the group and the index increase while the size of the matrix is unchanged in (c), as well as (d) shows the results in the opposite case. We can find that no matter the increase of the matrix or the increase of the group and index, the time cost of the two schemes increases significantly. However, under the same circumstances, the time cost and growth rate of the scheme proposed in this paper should be smaller, and the larger the variable, the more obvious the gap.