# Verifiable Outsourced Decryption of Attribute-Based Encryption with Constant Ciphertext Length.

1. IntroductionAttribute-based encryption (ABE) derives from identity-based encryption (IBE) introduced in [1]. A user's identity in IBE system is indicated by a binary bit string and the corresponding representation in ABE system is extended to an attribute set. The identity represented by an attribute set is not unique so ABE can realize the one-to-many encryption. Traditional IBE schemes can only provide coarse-grained access control. In order to solve this problem, Goyal et al. [2] presented a new scheme in which the fine-grained access control is associated with the user's private keys and ciphertexts are associated with a descriptive attribute set. ABE can be divided into two categories, namely, key-policy attribute-based encryption (KP-ABE) [2-4] and ciphertext-policy attribute-based encryption (CP-ABE) [5-11]. One of the main defects of current ABE schemes is expensive decryption operation for mobile device with low computing power and limited battery. To improve efficiency, Green et al. [12] presented an efficient ABE scheme by outsourcing expensive decryption operation to the cloud service provider (CSP). In their scheme, a user uses proxy reencryption method [13,14] to generate a transformation key and sends the transformation key and ABE ciphertext to the CSP. Given the transformation key, the CSP transforms an ABE ciphertext into a simple ciphertext, from which the user recovers plaintext by using less computation overhead. In this process, the CSP does not get any information about original plaintext. Chase [15] extended single authority ABE to propose a multiauthority ABE scheme. However, he only proves that the scheme is secure against the selective ID model. Liu et al. [16] provided a fully secure multiauthority CP-ABE. In order to protect privacy of the user, Han et al. [17] presented a decentralized key-policy attribute-based encryption with preserving privacy. Qian et al. [18] provided a decentralized CP-ABE with fully hidden access structure. Furthermore, they [19] proposed a privacy-preserving personal health record using multiauthority ABE with revocation. Several traceable CP-ABE schemes [20-22] were constructed to trace the identity of a misbehaving user who leaks its decryption key to others and thus reduces the trust assumptions on both users and attribute authorities. Recently, Li et al. [23] presented flexible and fine-grained attribute-based data storage in cloud computing. To protect data privacy, the sensitive data should be encrypted by the data owner prior to outsourcing. As the amount of encrypted files stored in cloud is becoming very huge, searchable encryption scheme over encrypted cloud data is a very challenging issue. To deal with above problem, Li et al. [24, 25] proposed a new cryptographic primitive called attribute-based encryption scheme with keyword search function [26-28]. In the proposed scheme, cloud service provider (CSP) performs partial decryption task delegated by data user without knowing anything about the plaintext. Moreover, the CSP can perform encrypted keyword search without knowing anything about the keywords embedded in trapdoor. In order to protect the privacy for the encryptor and decryptor, Li et al. [29] propose a CP-ABE scheme with hidden access policy and testing.

Our Motivations and Contributions. With the cloud service being more and more popular in modern society, ABE technology has become a promising orientation. It allows users to use flexible access control to access files stored in the cloud server with encrypted form. Though its advantages make it a powerful tool for cloud, one of its main performance challenges is that the complexity of decryption computation is linearly correlated with the access structure. By using the proxy reencryption technology, outsourced decryption ABE system can largely reduce the computation cost for users who intend to access the encrypted files stored in cloud. Given a ciphertext and a transformation key, CSP transforms a ciphertext into a simple ciphertext. The user only needs to spend less computational overhead to recover the plaintext from simple ciphertext. However, the correctness of the transformation ciphertext which the CSP gives to the user cannot be guaranteed because the latter does not have the original ciphertext. It is a security threat that malicious cloud service provider (CSP) may replace the original ciphertext and give the user a transformed ciphertext from another ciphertext which CSP wants the user to decrypt. The user is not aware of the CSP's malicious behavior. Mutual verifiable provable data auditing [30] in public cloud storage is a potential method to solve remote data possession checking. The security property about ABE with outsourcing decryption ensures that the malicious cloud server cannot obtain anything with respect to the encrypted message; nonetheless, the scheme does not ensure the validity of the transformation done by the CSP. In order to solve this problem, Lai et al. [31] put forward an ABE scheme with verifiable outsourcing decryption which guarantees verifiability of the transformation. Recently, Li et al. [32] presented an outsourcing ABE scheme which can check validity of the outsourced computation results. There is no doubt that verifiability brings about great progress to outsourced decryption of ABE. However, the ciphertext length and the amount of expensive pairing computations grow with the number of the attributes, which greatly limits its application in power constrained and bandwidth limited devices. Schemes in [33, 34] put forward a good solution to this problem in which the ciphertext length is constant. In this article, we present a novel verifiable outsourced CPABE scheme with constant ciphertext length to save the communication cost. The security of our scheme reduces to that of scheme in [33]. Similar to the proof in [31], the verifiability of our scheme reduces to the discrete logarithm assumption.

Organization. We organized the rest of the paper as follows. In Section 2, we review some preliminary knowledge and introduce the CP-ABE model of outsourced decryption. We also give the security definitions used in our paper in this section. In Section 3, we provide a new verifiable outsourced CP-ABE scheme with constant ciphertext length. We prove security and verifiability of our scheme in Section 4. In Section 5, we give some performance comparison with the existing schemes. Finally, we conclude the paper in Section 6.

2. Preliminaries

We introduce some basic knowledge about bilinear groups, security assumption, access structure, and CP-ABE which our scheme relies on.

2.1. Bilinear Pairing

Definition 1 (bilinear map). [G.sub.1] and [G.sub.T] are multiplicative cyclic groups with prime order p. Suppose g is a generator in [G.sub.1]. e : [G.sub.1] x [G.sub.1] [right arrow] [G.sub.T] is bilinear map if it satisfies the following properties:

(1) Bilinearity: for all u, v [member of] [G.sub.1], e([u.sup.a], [v.sup.b]) = e[(u, v).sup.ab], where a, b [member of] [Z.sub.p] are selected randomly.

(2) Nondegeneracy: there exists u, v [member of] [G.sub.1] such that e(u, v) [not equal to] 1.

(3) Computability: for all u, v [member of] [G.sub.1], there is an efficient algorithm to compute e(u, v).

2.2. Security Assumption

Definition 2 (discrete logarithm (DL) assumption [31]). Let (p, G, [G.sub.T], e) be a prime-order bilinear group system. Given (p, G, [G.sub.T], e, g, [g.sup.x]), where g [member of] G is randomly selected, the DL problem for (p, G, [G.sub.T], e) is to calculate x. The DL assumption in (p, G, [G.sub.T], e) is that no probabilistic polynomialtime (PPT) algorithm A solves the DL problem at nonnegligible advantage. The advantage for A is defined as Pr[A(p, G, [G.sub.T], e, g, [g.sup.x]) = x].

2.3. Access Structure. Access structure is being referred to in [33]; we utilize AND gates with respect to multivalued attributes as follows.

Definition 3. Assume that U = {[att.sub.1], ..., [att.sub.n]} is an attribute universe. [mathematical expression not reproducible] are some feasible values, where [n.sub.i] is the amount of feasible values of [att.sub.i] [member of] U. Let S = [[S.sub.1], [S.sub.2], [S.sub.n]], let [S.sub.i] [member of] [V.sub.i] be an attribute set for a user, and A = [[A.sub.1], [A.sub.2], ..., [A.sub.n]]; let [A.sub.i] [member of] [V.sub.i] be an access structure. The notation S [??] A denotes that an attribute set S satisfies an access structure A; that is to say, [S.sub.i] = [A.sub.i] (i = 1, 2, ..., n).

2.4. Outline of CP-ABE with Outsourced Decryption. Briefly speaking, a user interacts with the CSP as illustrated in Figure 1. Data owner encrypts message M into ciphertext CT and uploads it to the storage in cloud. A user who is permitted to access the data downloads the ciphertext. Then the user sends the ciphertext and transformation key to the CSP for outsourcing decryption. CSP computes partially decrypted ciphertext CT7 and sends it to the user. The user computes the message from the partially decrypted ciphertext and verifies whether the message is the original one.

We review the notion of CP-ABE in [31] with outsourced decryption. It is described by the seven algorithms as follows.

Setup([lambda], U). This algorithm takes the security parameter A and attribute universe U as input. It outputs public parameter PK and master secret key MK.

KeyGen(PK,MK,S). This algorithm takes PK, MK, and attribute set S as input. It outputs private key S[K.sub.S] related to S.

Encrypt(PK,M, A). This algorithm takes PK, message M, and access structure A as input and outputs ciphertext CT.

Decrypt(PK, S[K.sub.S], CT). This algorithm takes PK, S[K.sub.S], and CT as input. It outputs M if S[K.sub.S] associated with S satisfies A.

GenT[K.sub.out](PK,S[K.sub.S]). This algorithm takes PK and S[K.sub.S] as input. It outputs transformation key T[K.sub.S] associated with S and a corresponding retrieving key R[K.sub.S].

[Transform.sub.out](PK,CT,T[K.sub.S]). This algorithm takes PK, CT, and T[K.sub.S] as input. It outputs a partially decrypted ciphertext CT'.

[Decrypt.sub.out](PK, CT, CT', R[K.sub.S]). This algorithm takes PK, CT, CT', and R[K.sub.S] for S as input. It outputs message M or [perpendicular].

2.5. Security Model for CP-ABE with Outsourcing Decryption. Lai et al. [31] described security properties and verifiability for CP-ABE which supports outsourcing decryption. The traditional concept of security for chosen-ciphertext attack (CCA) is not suitable for the above CP-ABE scheme because it does not permit modifying any bit for the ciphertext. Therefore, they use a relaxation named replayed CCA (RCCA) security [35], which permits alternation for the ciphertext, so that they can change the potential message in a significant way.

2.5.1. Security. The RCCA security of outsourced decryption CP-ABE is described as a game in both an adversary and a challenger. According to the game in [31], it is described as follows.

Setup. The challenger C performs setup algorithm to get the public parameter PK and master secret key MK. It sends PK to the adversary A and keeps MK secret.

Query Phase 1. The challenger maintains a table Tb and a set D which are initialized empty. The adversary A adaptively issues queries.

(1) Private Key Query for Attribute Set S. The challenger runs S[K.sub.S] [less than or equal to] KeyGen(PK, MK, S) and sets D = D [union] {S}. It then sends the private key S[K.sub.S] to the adversary.

(2) Transformation Key Query on Attribute Set S. C scans the tuple (S, S[K.sub.S], T[K.sub.S], R[K.sub.S]) in table Tb. If such a tuple exists, it returns T[K.sub.S] as the transformation key. Otherwise, it runs S[K.sub.S] [less than or equal to] KeyGen(PK, MK, S) and (T[K.sub.S], R[K.sub.S]) [less than or equal to] GenT[K.sub.out](PK, S[K.sub.S]) and stores the tuple in table Tb. It then returns the transformation key T[K.sub.S] to the adversary.

Without loss of generality, we suppose that an adversary does not launch transformation key query for attribute set S, if a private key query about the same attribute set S has been issued. Since anyone can generate a transformation key of the user utilizing the user's private key and GenT[K.sub.out] algorithm by himself, the assumption is rational.

(3) Decryption Query for Attribute Set S and Ciphertext CT. C runs S[K.sub.S] [less than or equal to] KeyGen(PK, MK,S) and M [less than or equal to] Decrypt(PK, S[K.sub.S], CT). It sends M to the adversary.

(4) [Decryption.sub.out] Query for Attribute Set S and Ciphertext (CT,CT'). C searches the tuple (S, S[K.sub.S], T[K.sub.S], R[K.sub.S]) in table Tb. If such a tuple exists, it runs algorithm M [less than or equal to] [Decrypt.sub.out](PK, CT, CT', R[K.sub.S]) and returns M to C; otherwise, it returns [perpendicular].

Challenge. A sends [M.sub.0] and [M.sub.1] with equal length and an access policy [A.sup.*] to C subject to the restriction that, for all S [member of] D, [A.sup.*] cannot be satisfied by S. The challenger chooses b [member of] {0,1} and computes C[T.sup.*] = Encrypt(PK, Mb, [A.sup.*]). Then the challenger sends the challenge ciphertext C[T.sup.*] to A.

Query Phase 2. A proceeds to adaptively launch transformation key, decryption, [Decryption.sub.out], and private key queries as in phase 1 with the following restrictions:

(1) A cannot make private key query which results in attribute set S that satisfies the target access policy [A.sup.*].

(2) A cannot issue any trivial decryption queries. Namely, [Decryption.sub.out] and decryption queries are replied to as phase 1; if the response is either [M.sub.0] or [M.sub.1], then C returns [perpendicular].

Guess. The adversary A gives a guess b' [member of] {0,1} for b and succeeds in the game if b' = b.

[absolute value of Pr(b' = b)-1/2] is defined as the advantage for the adversary A in the game.

Definition 4. An outsourcing decryption CP-ABE scheme is RCCA secure if all probabilistic polynomial-time (PPT) adversaries have at most a negligible advantage of winning in this game.

CPA Security. An outsourcing decryption CP-ABE scheme is secure under chosen-plaintext attack (CPA) if A cannot launch decryption queries in the above game.

Selective Security. An outsourcing decryption CP-ABE scheme is selective security if we add an initialization phase prior to setup algorithm in above game, where the adversary gives the challenger access structure [A.sup.*] .

2.5.2. Verifiability. The verifiability for CP-ABE with outsourced decryption is depicted via a game in both an adversary and a challenger. The game proceeds as follows.

Setup. C performs algorithm setup to generate the public parameters PK and master secret key MSK. It returns PK to A and keeps MSK secret.

Query Phase 1. C initializes an empty table T. A adaptively issues the following queries.

(1) Private Key Query for Attribute Set S. C runs S[K.sub.S] [less than or equal to] KeyGen(PK, MK, S) and returns the private key S[K.sub.S] to the adversary.

(2) Transformation Key Query for Attribute Set S. The challenger runs S[K.sub.S] [less than or equal to] KeyGen(PK, MK, S) and (T[K.sub.S], R[K.sub.S]) [less than or equal to] GenT[K.sub.out](PK, S[K.sub.S]) and stores the entry (S, S[K.sub.S], T[K.sub.S], R[K.sub.S]) in table T. It then returns the transformation key T[K.sub.S] to the adversary.

Without loss of generality, we suppose that the adversary does not launch transformation key query for attribute set S, if a private key query about the same attribute set S has been issued. Anyone can generate a transformation key of the user utilizing the user's private key and GenT[K.sub.out] algorithm by himself.

(3) Decryption Query for Attribute Set S and a Ciphertext CT. C runs S[K.sub.S] [less than or equal to] KeyGen(PK, MK, S) and M [less than or equal to] Decrypt(PK, S[K.sub.S], CT). It sends M to C.

(4) [Decryption.sub.out] Query for Attribute Set S and Ciphertexts (CT, CT'). C searches the tuple (S, S[K.sub.S], T[K.sub.S], R[K.sub.S]) in table T. If such a tuple exists, it runs M [left arrow] [Decrypt.sub.out](PK, CT, CT', R[K.sub.S]) and returns M to C; otherwise, it returns [perpendicular].

Challenge. A sends challenge message [M.sup.*] and challenge access policy [A.sup.*] to the challenger C. C computes C[T.sup.*] = Encrypt(PK, [M.sup.*], [A.sup.*]) and returns C[T.sup.*] to A as its challenge ciphertext.

Query Phase 2. A proceeds to adaptively launch transformation key, decryption, [Decryption.sub.out], and private key queries as in phase 1.

Output. A returns attribute set [S.sup.*] and transformed ciphertext C[T.sup.*]7. We suppose that tuple ([S.sup.*], S[K.sub.S]., T[K.sub.S]., R[K.sub.S].) is included in table T. Otherwise, the challenger generates the tuple as the reply for transformation key query. A succeeds in the game if [mathematical expression not reproducible].

Definition 5. An outsourcing decryption CP-ABE scheme is verifiable if PPT adversary has at most a negligible advantage in the above game.

3. Construction of Our New Scheme

Our new scheme consists of seven algorithms.

Setup([1.sup.k]). A trusted authority (TA) picks two bilinear groups [mathematical expression not reproducible] is a hash function. TA computes [mathematical expression not reproducible]. It generates [mathematical expression not reproducible] as public parameters and [mathematical expression not reproducible] as master secret key. Note that, [mathematical expression not reproducible] is assumed.

KeyGen(PK, MSK, S). TA selects [mathematical expression not reproducible], and sends S[K.sub.S] = ([K.sub.1], [K.sub.2]) to a user associated with attribute set S.

Encrypt(PK,M, A). An encryptor randomly selects [mathematical expression not reproducible].

Decrypt(PK, S[K.sub.S], CT). A decryptor calculates as follows:

[mathematical expression not reproducible]. (1)

If [mathematical expression not reproducible], it outputs the message M; otherwise, it outputs [perpendicular].

GenT[K.sub.out](PK,S[K.sub.S]). A user generates his transformation key pair as follows. He chooses z [[member of].sub.R] [Z.sub.p] and computes the transformation key as T[K.sub.S] = ([K'.sub.1], [K'.sub.2]), where [K'.sub.1] = [K.sup.1/z.sub.1] and [K'.sub.2] = [K.sup.1/z.sub.2]. The retrieving key is R[K.sub.S] = z. Note that, with overwhelming probability, z has multiplicative inverse.

[Transform.sub.out](PK, CT, T[K.sub.S]). Given ciphertext CT and transformation key T[K.sub.S], the CSP computes as follows:

[mathematical expression not reproducible], (2)

and it outputs the transformed ciphertext as [mathematical expression not reproducible].

[Decrypt.sub.out](PK,CT,CT',R[K.sub.S]). A user checks whether the transformed ciphertext [mathematical expression not reproducible]; if the equations do not hold, he outputs [+ or -]. Otherwise, he computes [mathematical expression not reproducible], he outputs the message M; otherwise, he outputs [perpendicular].

Note that [mathematical expression not reproducible] according to assumption. If there exist S and S' such that [mathematical expression not reproducible], the user with attribute set S' is able to decrypt ciphertext related to A, where [mathematical expression not reproducible]. We have that the assumption holds with overwhelming probability:

[mathematical expression not reproducible], (3)

where N = [[PI].sup.n.sub.i=1] [n.sub.i]. If we randomly choose [t.sub.i,j] [member of] [Z.sub.p] as secret key, then our assumption is reasonable.

4. Security Proof

Note that, in our scheme, a ciphertext consists of three parts: ([C.sub.1], [C.sub.2], [C.sub.3]), ([C'.sub.1], [C'.sub.2], [C'.sub.3]), and C. The first two elements are ciphertexts for message M and random message M, respectively, utilizing the encryption algorithm [33]. In essence, the second and the third elements are redundant information. The redundant information is mainly used to design a CPABE scheme with verifiable outsourcing decryption from [33], which has been proven to be selectively CPA-secure. We denote the first four algorithms as Basic CP-ABE. To guarantee the security for our scheme, we firstly prove that if the scheme in [33] is selectively CPA-secure, then Basic CPABE scheme is selectively CPA-secure.

Theorem 6. Assume that the scheme in [33] is selectively CPA-secure. Then the Basic CP-ABE scheme is also selectively CPA-secure.

Proof. We prove that our Basic CP-ABE scheme is selectively CPA-secure by the following two games.

[Game.sub.0]. [Game.sub.0] is the originally selective CPA security game.

[Game.sub.1]. In Game:, the challenger randomly selects [??] [member of] [G.sub.1] and generates the remaining parts of the challenge ciphertext CT = (A,[??],[C.sub.1],[C.sub.2],[C.sub.3],[C'.sub.1],[C'.sub.2],[C'.sub.3]) as in [Game.sub.0].

This theorem is proven via the following lemmas. Lemma 7 shows that [Game.sub.0] and [Game.sub.1] are indistinguishable. Lemma 8 shows that the advantage for an adversary in [Game.sub.1] is negligible. Thus, we come to a conclusion that the advantage for an adversary in [Game.sub.0] is negligible. Theorem 6 is correct from the two lemmas below.

Lemma 7. Assume that the scheme in [33] is selectively CPA-secure; [Game.sub.0] and [Game.sub.1] are computationally indistinguishable.

Proof. If the adversary A is able to distinguish [Game.sub.0] and [Game.sub.1] at nonnegligible advantage, then we find an algorithm B which attacks the scheme [33] under the selective CPA security model at nonnegligible advantage.

Let C be the challenger for the selective CPA security game in scheme [33]. B and the adversary A interact as follows.

Init. A gives [A.sup.*] to B as its challenge access policy. B sends [A.sup.*] to C as its challenge access policy. C sends the public parameters [mathematical expression not reproducible] of the scheme [33] to B.

Setup. B selects x, y, z [[epsilon].sub.R] [Z.sub.p] and computes u = [g.sup.x.sub.1], v = [g.sup.y.sub.1], and d = [g.sup.z.sub.1]. B also selects hash function [mathematical expression not reproducible] to the adversary A.

Query Phase 1. A adaptively launches private key query on attribute set [S.sub.i]; then B gets the private key [mathematical expression not reproducible] via calling key generation oracle of C with respect to [S.sub.i]. B returns the private key [mathematical expression not reproducible].

Challenge. A sends two equal size messages [M.sub.0], [M.sub.1] to B as the challenge plaintext. B selects a random bit [beta] and random messages [mathematical expression not reproducible]. C randomly selects [gamma] [member of] {0,1}; the message [[??].sub.[gamma]] is encrypted by PK and [A.sup.*] using the encryption algorithm in [32] and sends the resulting ciphertext C[T.sup.*] to B. B denotes C[T.sup.*] as [mathematical expression not reproducible] as its challenge ciphertext.

Query Phase 2. A adaptively launches private key query as in phase 1. B answers the queries as in phase 1.

Guess. A gives a guess [beta]' [member of] {0,1} of B. B outputs [beta]' as a guess of [gamma].

Note that if [beta] = [gamma], B appropriately simulates [Game.sub.0]; else, B appropriately simulates [Game.sub.1]. Therefore, if A is able to distinguish [Game.sub.0] and [Game.sub.1] at nonnegligible advantage, we are able to find an algorithm B that attacks the scheme [33] in selective CPA security model at nonnegligible advantage.

Lemma 8. Assume that the CP-ABE scheme in [33] is selectively CPA-secure; the advantage for the adversary A on [Game.sub.1] is negligible.

Proof. If the adversary A has a nonnegligible advantage in [Game.sub.1], then we can find an algorithm B which attacks the scheme [33] at a nonnegligible advantage.

Let C be the challenger with respect to B of the scheme [33]. B interacts with A as demonstrated in the following steps.

Init. A submits challenge access policy [A.sup.*] to B. B gives [A.sup.*] to C as its challenge access policy. C returns [mathematical expression not reproducible] of scheme [25] to B as public parameters.

Setup. B chooses x, y, z [[member of].sub.R] [Z.sub.p] and sets u = [g.sup.x.sub.1], v = [g.sup.y.sub.1], and d = [g.sup.z.sub.1]. H : [G.sub.T] [right arrow] [Z.sup.*.sub.p] is a secure hash function. B sends [mathematical expression not reproducible] to the adversary A.

Query Phase 1. A adaptively launches private key query of attribute set [S.sub.i]; B gets the private key [mathematical expression not reproducible] via calling key generation oracle of C with respect to [S.sub.i], B sends the private key [mathematical expression not reproducible].

Challenge. A submits messages [M.sub.0], [M.sub.1] with equal size. B sends [M.sub.0], [M.sub.1] and [A.sup.*] to C. C randomly chooses [gamma] [member of] {0,1}; the message [M.sub.[gamma]] is encrypted by PK' and [A.sup.*] using the encryption algorithm in [33] and sends the resulting ciphertext [mathematical expression not reproducible] to A as its challenge ciphertext.

Query Phase 2. A adaptively launches private key query as in phase 1. B answers the queries as in phase 1.

Guess. A gives a guess [beta]' [member of] {0,1} on B. B returns [beta]' as its guess for [gamma]. Obviously, B has appropriately simulated [Game.sub.1]. If A has a nonnegligible advantage in [Game.sub.1], then B attacks the scheme in [33] at a nonnegligible advantage.

Now we have proven that the Basic CP-ABE scheme is selectively CPA-secure. After that we prove that if Basic CPABE scheme is selectively CPA-secure, then our new scheme is selectively CPA-secure.

Theorem 9. Assume that Basic CP-ABE scheme is selectively CPA-secure. Then our new scheme is selectively CPA-secure.

Proof. If A breaks our new CP-ABE scheme at nonnegligible advantage, then we find an algorithm B which breaks Basic CP-ABE scheme at nonnegligible advantage. We assume that C is the challenger with respect to B for Basic CP-ABE. B interacts with A as demonstrated in the following steps.

Init. A sends B its challenge access policy [A.sup.*]. B gives challenge access policy [A.sup.*] to C and obtains the public parameters [mathematical expression not reproducible] for Basic CP-ABE.

Setup. B sends PK to A.

Query Phase 1. B maintains a table Tb and a set D which are initialized as empty. A adaptively launches queries.

(1) Private Key Query on Attribute Set S. B obtains the private key S[K.sub.S] by calling the key generation oracle of C with respect to S. Then, B lets D = D [union] {S} and sends the private key S[K.sub.S] to A.

(2) Transformation Key Query on Attribute Set S. B scans the tuple (S, S[K.sub.S], T[K.sub.S], R[K.sub.S]) in table Tb. If such a tuple exists, it sends the transformation key T[K.sub.S] to A. Otherwise, B selects random exponents z,r [member of] [Z.sub.p]. B computes [mathematical expression not reproducible]. B stores the tuple (S, *, T[K.sub.S] = (S, [K'.sub.1],[K'.sub.2]), z) in table Tb and returns T[K.sub.S] to A. Observe that B does not know the actual retrieving key R[K.sub.S] = y/z. Here, we compute as follows:

[mathematical expression not reproducible]. (4)

Challenge. A submits messages [M.sub.0], [M.sub.1] with same length and challenge access policy [A.sup.*]. B gives [M.sub.0], [M.sub.1] and [A.sup.*] to C to obtain the challenge ciphertext C[T.sup.*]. B returns C[T.sup.*] to A as its challenge ciphertext.

Query Phase 2. A adaptively launches private key query as in phase 1, and B answers the queries as in phase 1.

Guess. A obtains [mu]'. B also obtains [mu]'.

If the guess [mu]' for A of our scheme is correct, the guess of B for Basic CP-ABE scheme is correct too. So we can conclude that if A can attack our scheme at nonnegligible advantage, then we will find an algorithm B which attacks Basic CP-ABE scheme under the selective CPA security model at nonnegligible advantage.

Theorem 10. Our CP-ABE scheme is verifiable if the discrete logarithm assumption defined in Section 2.2 holds.

Proof. Suppose that there exists an adversary A that attacks verifiability of our new scheme at nonnegligible advantage. We find an algorithm B that can solve the DL problem at nonnegligible advantage.

Setup. B chooses [mathematical expression not reproducible] is the public parameter. The master secret key is [mathematical expression not reproducible]. B returns PK to A.

Query Phase 1. A adaptively launches transformation key, private key, decryption, and [Decryption.sub.out] queries. As B knows MK, it can answer the queries properly.

Challenge. A gives [M.sup.*] and challenge access policy [A.sup.*] to B. B computes the ciphertext C[T.sup.*] of [M.sup.*] using the encryption algorithm in [33] and returns [mathematical expression not reproducible] is chosen by B randomly.

Query Phase 2. A adaptively launches private key queries as in phase 1. B answers queries as in phase 1.

Output. A returns attribute set [S.sup.*] and transformed ciphertext [mathematical expression not reproducible].

B computes [mathematical expression not reproducible], is the retrieving key for attribute set [S.sup.*]. If A wins the above game, then B can obtain

[mathematical expression not reproducible], (5)

where [mathematical expression not reproducible] are obtained by B. Because H is a collision-resistant hash function, H([M.sup.*]) is not equal to H(M) with overwhelming probability. Thus, B gets [mathematical expression not reproducible], which breaks the DL assumption. It is paradoxical, so our CP-ABE scheme is verifiable

5. Performance Comparison

PK, MK, SK, CT, TK, RK, and CT' represent the length of public key, master key, private key, ciphertext, transform key, retrieving key, and transformed ciphertext without the access policy, respectively. Additionally, Encrypt, Decrypt, Transform, and [Decrypt.sub.out] represent the computational costs of the algorithms' encryption, decryption, transformation, and outsourcing decryption, respectively. [absolute value of [G.sub.1]], [absolute value of Gr], and [absolute value of [Z.sub.p]] denote the bit-length of the elements belonging to [G.sub.1], [G.sub.T], and [Z.sub.p]. k[C.sub.e], kH, and k[G.sub.1] denote the k-times computation in the pairing, hash function, and group [G.sub.1], respectively U = {[att.sub.1], ..., [att.sub.n]} denote the attribute universe. [N.sub.1] and [N.sub.2] are the amounts of the attributes related to ciphertext and private key, respectively. N = [[summation].sup.n.sub.i=1] [n.sub.i] denotes the total number of possible attribute values.

Tables 1-3 show that our scheme is efficient. Table 1 illustrates that the size of private key, ciphertext, and transform key in our scheme is constant. However, the size of private key, ciphertext, and transform key in [11, 12, 31] depends upon the number of attributes. Therefore, our scheme greatly reduces the communication overhead and is very suitable for bandwidth limited devices. As the operation cost over [Z.sub.p] is much smaller than group and pairing operation, we ignore the computation time over [Z.sub.p]. Compared with the scheme in [11,12,31], the computational overhead for the decryption and transformation operations in our scheme is much smaller. From Table 2, we observe that the computational overhead over group and pairing in [11, 12, 31] depends on the number of attributes, while it is constant in our scheme. The computational overhead for the outsourcing decryption is constant in above schemes. Table 3 illustrates that only our scheme satisfies all properties.

In order to evaluate the efficiency for our scheme, we implement our scheme with java pairing-based cryptography (JPBC) library [36], a port for the pairing-based cryptography (PBC) library in C [37]. The elliptic curve parameter we choose is type-A, and the order of group is 160 bits. We run our code on a PC with 64-bit 2.6-GHz Intel Core i5-3320M CPU, with 6 GB RAM, and mobile phone with 4-core 1.8 GHz Processor 2 G memory Android OS 4.4.2, respectively. We also implement the scheme [31] for comparison. Figure 2 compares the times of decryption algorithm spent in our scheme and Lai et al.'s scheme [31]. The result shows that our scheme is much more efficient than Lai et al.'s scheme [31] because the time spent in our scheme does not grow with the amount of attributes involved in the access policy. Figure 3 shows the time of the transformation algorithm in PC and mobile phone for two schemes. Similar to the decryption algorithm, the time required by transformation grows linearly with the number of attributes for Lai et al.'s scheme [31], while it is almost constant for our scheme. Figure 4 shows that the times of the outsourcing decryption algorithm in PC and mobile phone for two schemes are nearly same. Figure 5 shows the ciphertext length in our scheme and Lai et al.'s scheme [31]. We can find that the ciphertext length in our scheme is constant, while it will grow with the amount of attributes involved in access policy linearly. So we can conclude that our scheme greatly reduces the communication overhead and is very suitable for bandwidth limited devices. Figure 6 illustrates that the length of partially decrypted ciphertext in two schemes is almost same.

6. Conclusions

In this article, we propose a new verifiable outsourced CPABE scheme with constant ciphertext length and, moreover, we prove that our scheme is secure and verifiable in standard model. Security in our scheme is reduced to that of scheme in [33] and verifiability is reduced to DL assumption. The computational overhead for the decryption and transformation operations in our scheme is constant, which does not rely on the amount of attributes. In addition, we outsource the expensive operation to the cloud service provider and leave the slight operations to be done on user's device. Therefore, our scheme is very efficient. What is more, the ciphertext length in our scheme does not grow with the number of attributes, which reduces the communication cost greatly. The proposed scheme has the potential application in various lower power devices with limited computational power, such as mobile phone.

https://doi.org/10.1155/2017/3596205

Competing Interests

The authors declare that they have no competing interests.

Acknowledgments

This research is supported by the National Natural Science Foundation of China (61272542, 61472083, 61202450, 61402110, and 61672207), Jiangsu Provincial Natural Science Foundation of China (BK20161511), the Priority Academic Program Development of Jiangsu Higher Education Institutions, the Fundamental Research Funds for the Central Universities (2016B10114), Jiangsu Collaborative Innovation Center on Atmospheric Environment and Equipment Technology, and the Project of Scientific Research Innovation for College Graduate Student of Jiangsu Province (KYZZ15_0151).

References

[1] D. Boneh and M. Franklin, "Identity-based encryption from the weil pairing," in Proceedings of the 21st Annual International Cryptology Conference (CRYPTO '01), Santa Barbara, Calif, USA, August 2001, vol. 2139 of Lecture Notes in Computer Science, pp. 213-229, Springer, Berlin, Germany, 2001.

[2] V. Goyal, O. Pandey, A. Sahai, and B. Waters, "Attribute-based encryption for fine-grained access control of encrypted data," in Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS '06), pp. 89-98, ACM, November 2006.

[3] J. Li, C. Jia, J. Li, and X. Chen, "Outsourcing encryption of attribute-based encryption with MapReduce," in Information and Communications Security, T. W. Chim and T. H. Yuen, Eds., vol. 7618 of Lecture Notes in Computer Science, pp. 191-201, Springer, Berlin, Germany, 2012.

[4] A. Lewko and B. Waters, "Unbounded HIBE and attribute-based encryption," in Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT '11), Tallinn, Estonia, May 2011, vol. 6632 of Lecture Notes in Computer Science, pp. 547-567, Springer, Berlin, Germany, 2011.

[5] J. Bethencourt, A. Sahai, and B. Waters, "Ciphertext-policy attribute-based encryption," in Proceedings of the IEEE Symposium on Security and Privacy (SP '07), pp. 321-334, May 2007.

[6] B. D. Qin, R. H. Deng, S. L. Liu, and S. Q. Ma, "Attribute-based encryption with efficient verifiable outsourced decryption," IEEE Transactions on Information Forensics and Security, vol. 10, no. 7, pp. 1384-1393, 2015.

[7] H. Deng, Q. Wu, B. Qin et al., "Ciphertext-policy hierarchical attribute-based encryption with short ciphertexts," Information Sciences, vol. 275, pp. 370-384, 2014.

[8] R. Ostrovsky, A. Sahai, and B. Waters, "Attribute-based encryption with non-monotonic access structures," in Proceedings of the 14th ACM Conference on Computer and Communications Security (CCS '07), pp. 195-203, ACM, Alexandria, Va, USA, November 2007.

[9] T. Okamoto and K. Takashima, "Fully secure functional encryption with general relations from the decisional linear assumption," in Advances in Cryptology--CRYPTO 2010, T. Rabin, Ed., vol. 6223 of Lecture Notes in Computer Science, pp. 191-208, Springer, Berlin, Germany, 2010.

[10] L. Cheung and C. Newport, "Provably secure ciphertext policy ABE," in Proceedings of the 14th ACM Conference on Computer and Communications Security (CCS '07), pp. 456-465, November 2007.

[11] J. Li, X. Chen, J. Li, C. Jia, J. Ma, and W. Lou, "Fine-grained access control system based on outsourced attribute-based encryption," in Computer Security--ESORICS 2013, J. Crampton, S. Jajodia, and K. Mayes, Eds., vol. 8134 of Lecture Notes in Computer Science, pp. 592-609, Springer, Berlin, Germany, 2013.

[12] M. Green, S. Hohenberger, and B. Waters, "Outsourcing the decryption of ABE ciphertexts," in Proceedings of the 20th USENIX Conference on Security (SEC '11), p. 34, 2011.

[13] G. Ateniese, K. Fu, M. Green, and S. Hohenberger, "Improved proxy re-encryption schemes with applications to secure distributed storage," ACM Transactions on Information and System Security, vol. 9, no. 1, pp. 1-30, 2006.

[14] M. Blaze, G. Bleumer, and M. Strauss, "Divertible protocols and atomic proxy cryptography," in Advances in Cryptology--EUROCRYPT'98, K. Nyberg, Ed., vol. 1403 of Lecture Notes in Computer Science, pp. 127-144, Springer, Berlin, Germany, 1998.

[15] M. Chase, "Multi-authority attribute based encryption," in Proceedings of the 4th Theory of Cryptography Conference (TCC '07), Amsterdam, The Netherlands, February 2007, Lecture Notes in Computer Science, pp. 515-534, Springer, Berlin, Germany, 2007.

[16] Z. Liu, Z. Cao, Q. Huang, D. S. Wong, and T. H. Yuen, "Fully secure multi-authority ciphertext-policy attribute-based encryption without random oracles," in Computer Security--ESORICS 2011: 16th European Symposium on Research in Computer Security, Leuven, Belgium, September 12-14, 2011. Proceedings, vol. 6879 of Lecture Notes in Computer Science, pp. 278-297, Springer, Berlin, Germany, 2011.

[17] J. G. Han, W. Susilo, Y. Mu, and J. Yan, "Privacy-preserving decentralized key-policy attribute-based encryption," IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 11, pp. 2150-2162, 2012.

[18] H. L. Qian, J. G. Li, and Y. C. Zhang, "Privacy-preserving decentralized ciphertext-policy attribute-based encryption with fully hidden access structure," in Proceedings of the 15th International Conference on Information and Communications Security (ICICS '13), vol. 8233 of Lecture Notes in Computer Science LNCS, pp. 363-372, Springer, Berlin, Germany, 2013.

[19] H. L. Qian, J. G. Li, Y. C. Zhang, and J. G. Han, "Privacy-preserving personal health record using multi-authority attribute-based encryption with revocation," International Journal of Information Security, vol. 14, no. 6, pp. 487-497, 2015.

[20] Z. Liu, Z. F. Cao, and D. S. Wong, "Blackbox traceable CP-ABE: how to catch people leaking their keys by selling decryption devices on eBay," in Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS '13), pp. 475-486, Berlin, Germany, November 2013.

[21] Z. Liu, Z. F. Cao, and D. S. Wong, "White-box traceable ciphertext-policy attribute-based encryption supporting any monotone access structures," IEEE Transactions on Information Forensics and Security, vol. 8, no. 1, pp. 76-88, 2013.

[22] J. T. Ning, Z. F. Cao, X. L. Dong, L. F. Wei, and X. D. Lin, "Large universe ciphertext-policy attribute-based encryption with white-box traceability," in Computer Security--ESORICS 2014: 19th European Symposium on Research in Computer Security, Wroclaw, Poland, September 7-11, 2014. Proceedings, Part II, vol. 8713 of Lecture Notes in Computer Science, pp. 55-72, Springer, Berlin, Germany, 2014.

[23] J. G. Li, W. Yao, Y. C. Zhang, H. L. Qian, and J. G. Han, "Flexible and fine-grained attribute-based data storage in cloud computing," IEEE Transactions on Services Computing, 2016.

[24] J. G. Li, X. N. Lin, Y. C. Zhang, and J. G. Han, "KSF-OABE: outsourced attribute-based encryption with keyword search function for cloud storage," IEEE Transactions on Services Computing, 2016.

[25] J. G. Li, Y. R. Shi, and Y. C. Zhang, "Searchable ciphertext-policy attribute-based encryption with revocation in cloud storage," International Journal of Communication Systems, 2015.

[26] Z. J. Fu, X. M. Sun, Q. Liu, L. Zhou, and J. G. Shu, "Achieving efficient cloud search services: multi-keyword ranked search over encrypted cloud data supporting parallel computing," IEICE Transactions on Communications, vol. 98, no. 1, pp. 190-200, 2015.

[27] Z. H. Xia, X. H. Wang, X. M. Sun, and Q. Wang, "A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data," IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 2, pp. 340-352, 2015.

[28] Z. Fu, K. Ren, J. Shu, X. Sun, and F. Huang, "Enabling personalized search over encrypted outsourced data with efficiency improvement," IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 9, pp. 2546-2559, 2016.

[29] J. G. Li, H. P. Wang, Y. C. Zhang, and J. Shen, "Ciphertext-policy attribute-based encryption with hidden access policy and testing," KSII Transactions on Internet and Information Systems, vol. 10, no. 8, pp. 3339-3352, 2016.

[30] Y.-J. Ren, J. Shen, J. Wang, J. Han, and S.-Y. Lee, "Mutual verifiable provable data auditing in public cloud storage," Journal of Internet Technology, vol. 16, no. 2, pp. 317-323, 2015.

[31] J.-Z. Lai, R. H. Deng, C. Guan, and J. Weng, "Attribute-based encryption with verifiable outsourced decryption," IEEE Transactions on Information Forensics and Security, vol. 8, no. 8, pp. 1343-1354, 2013.

[32] J. Li, X. Y. Huang, J. W. Li, X. F. Chen, and Y. Xiang, "Securely outsourcing attribute-based encryption with checkability," IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 8, pp. 2201-2210, 2014.

[33] K. Emura, A. Miyaji, A. Nomura, K. Omote, and M. Soshi, "A Ciphertext-policy attribute-based encryption scheme with constant ciphertext length," in Information Security Practice and Experience: 5th International Conference, ISPEC 2009 Xi'an, China, April 13-15, 2009 Proceedings, vol. 5451 of Lecture Notes in Computer Science, pp. 13-23, Springer, Berlin, Germany, 2009.

[34] J. Herranz, F. Laguillaumie, and C. Rafols, "Constant size ciphertexts in threshold attribute-based encryption," in Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography (PKC '10), Paris, France, May 2010, vol. 6056 of Lecture Notes in Computer Science, pp. 19-34, Springer, Berlin, Germany, 2010.

[35] R. Canetti, H. Krawczyk, and J. B. Nielsen, "Relaxing chosen-ciphertext security," in Proceedings of the 23rd Annual International Cryptology Conference (CRYPTO '03), Santa Barbara, Calif, USA, August 2003, vol. 2729 of Lecture Notes in Computer Science, pp. 565-582, Springer, Berlin, Germany, 2003.

[36] A. D. Caro, "Java pairing-based cryptography library," 2012, http://libeccio.dia.unisa.it/projects/jpbc/.

[37] B. Lynn, PBC (Pairing-Based Cryptography) Library, 2012, http://crypto.stanford.edu/pbc/.

Jiguo Li, (1) Fengjie Sha, (1) Yichen Zhang, (1) Xinyi Huang, (2) and Jian Shen (3)

(1) College of Computer and Information, Hohai University, Nanjing 211000, China

(2) School of Mathematics and Computer Science, Fujian Normal University, Fuzhou 350117, China

(3) School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing 210044, China

Correspondence should be addressed to Jiguo Li; ljg1688@163.com

Received 28 June 2016; Accepted 1 September 2016; Published 10 January 2017

Academic Editor: Angel Martin Del Rey

Caption: Figure 1: System architecture of our scheme.

Caption: Figure 2: Decryption time.

Caption: Figure 3: Transformation time.

Caption: Figure 4: Outsourcing decryption time.

Caption: Figure 5: Ciphertext length.

Caption: Figure 6: Partial decryption ciphertext length.

Table 1: Size of each value. PK MK LCL13 [11] (n + 4) [absolute value [absolute value of of [G.sub.1]] [Z.sub.p]] LDG 13 [31] (5 + n) [absolute value [absolute value of of [G.sub.1]] + [absolute [Z.sub.p]] value of [G.sub.T]] GHW 11 [12] 2 [absolute value of [absolute value of [G.sub.1]] + [absolute [Z.sub.p]] value of [G.sub.T]] Our scheme (N+5) [absolute value of (N+1) [absolute value of [G.sub.1]] + [absolute [Z.sub.p]] value of [G.sub.T]] SK CT LCL13 [11] None ([N.sub.1] + 2) [absolute value of [G.sub.1]] + [absolute value of [G.sub.T]] LDG 13 [31] (2 + [N.sub.2]) [absolute (4[N.sub.1] + 3) value of [G.sub.1]] [absolute value of [G.sub.1]] + 2[absolute value of [G.sub.T]] GHW 11 [12] None (2[N.sub.1] + 1) [absolute value of [G.sub.1]] + [absolute value of [G.sub.T]] Our scheme 2 [absolute value of 5 [absolute value of [G.sub.1]] [G.sub.1]] + 2 [absolute value of [G.sub.T]] TK RK LCL13 [11] 2 [N.sub.2] [absolute 2 [absolute value of value of [G.sub.1]] [G.sub.1]] LDG 13 [31] (2 + [N.sub.2]) [absolute [absolute value of value of [G.sub.1]] [Z.sub.p]] GHW 11 [12] (2 + [N.sub.2]) [absolute [absolute value of value of [G.sub.1]] [Z.sub.p]] Our scheme 2 [absolute value of [absolute value of [G.sub.1]] [Z.sub.p]] CT' LCL13 [11] 2 [absolute value of [G.sub.1]] + 2 [absolute value of [G.sub.T]] LDG 13 [31] [absolute value of [G.sub.1]] + 4[absolute value of [G.sub.T]] GHW 11 [12] 2 [absolute value of [G.sub.T]] Our scheme [absolute value of [G.sub.1]] + 4[absolute value of [G.sub.T]] Table 2: Computational times. Encrypt Decrypt LCL 13 [11] [C.sub.e] + 2 [G.sub.T] + None (3 + 2 [N.sub.1])[G.sub.1] LDG 13 [31] 2H + (10 + 8[N.sub.1]) 4([N.sub.2] -1) [C.sub.e] [G.sub.1] + 4 [G.sub.T] + 4[N.sub.2] [G.sub.T] GHW 11 [12] (4[N.sub.1] + 1) None [G.sub.1] + 3[G.sub.T] + [N.sub.1]H Our scheme 2H + (2[N.sub.1] + 4[C.sub.e] + 4[G.sub.T] 6)[G.sub.1] + 4[G.sub.T] Transform Decryptout LCL 13 [11] 2([N.sub.2] -1)[C.sub.e] 2[C.sub.e] + 3[G.sub.T] + 2[N.sub.2][G.sub.T] LDG 13 [31] (4[N.sub.2] -2) [G.sub.T] 4[G.sub.T] + (4[N.sub.2] -2) [C.sub.e] GHW 11 [12] (3[N.sub.2] -1) [G.sub.1] 2[G.sub.T] + ([N.sub.2] + 1) [G.sub.T] + ([N.sub.2] + 2) [C.sub.e] Our scheme 4[C.sub.e] + 2 [G.sub.T] 4[G.sub.T] Table 3: Property of each scheme. Outsourcing Verifiability Constant ciphertext length LCL 13 [11] Yes No No LDG 13 [31] Yes Yes No GHW 11 [12] Yes No No Our scheme Yes Yes Yes

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Li, Jiguo; Sha, Fengjie; Zhang, Yichen; Huang, Xinyi; Shen, Jian |

Publication: | Security and Communication Networks |

Article Type: | Report |

Date: | Jan 1, 2017 |

Words: | 7981 |

Previous Article: | Utilizing the Double-Precision Floating-Point Computing Power of GPUs for RSA Acceleration. |

Next Article: | BROSMAP: A Novel Broadcast Based Secure Mobile Agent Protocol for Distributed Service Applications. |

Topics: |