Efficient Expressive Attribute-Based Encryption with Keyword Search over Prime-Order Groups

1  Introduction

In recent years, the infrastructure of Internet has been upgraded greatly. Consequently, the cost of data transmission has been reduced. These favorable conditions make cloud storage appear. Compared with data sharing by other ways (e.g., email), cloud data sharing avoids the single point transmission of data and provides great convenience. Today, cloud storage has become an indispensable part of people’s life and work.

Although cloud storage has many advantages, it brings new challenges to data security. Data storage service is usually provided by some entities who are often thought to be honest-but-curious or even untrusted. Therefore, it is not advisable to upload data plaintexts directly to cloud because the outer adversary and the server in the cloud are able to easily achieve all information. How to protect data privacy has become the focus issue in cloud storage environment. Encryption is a necessary step to protect data privacy. But new problems arise after data encryption:

1.    How to retrieve the data. Encryption ensures the security of data, but it is difficult for the data receiver to search specific files from cloud. It is not advisable to distinguish files by plaintext labels, because the plaintext labels describe the content of files and inevitably reveal private information.

2.    How to access control. The receiver needs to access data files according to his/her authority, but simple encryption cannot achieve this requirement.

PEKS (public key encryption with keyword search), which was originally introduced by Boneh et al. in [1], can effectively handle the above first issue. To make the ciphertexts searchable, the data owner needs to attach a keyword ciphertext to a data ciphertext to create a searchable ciphertext. The data user needs to generate a searchable token of the search keyword for the storage server using his/her own private key, so that the server can execute a search algorithm to find all matching data ciphertexts. During ciphertext retrieval, no privacy information (either the data content or the search keyword) would be revealed to the server.

The PEKS scheme only allows single keyword search and may result in rough results that do not meet the users’ requirements because a data file is often related to several keywords. Therefore, the multi-keyword search function is extremely essential. In [2], Park et al. proposed the first PEKS scheme that can execute multi-keyword search, namely public key encryption with conjunctive keyword search (PECKS). But PECKS just implements simple conjunctive connection of multiple keywords. When a user wants to find the files attached with the keywords “important” or “urgent”, he/she has to search twice. To address this issue, some scholars [3,4] put forward more flexible multi-keyword search encryption method that supports expressive search predicates formed by the logical expression of “AND” and “OR”, namely expressive PEKS (EPEKS). As shown in Fig. 1 [5], an EPEKS system contains three parties: sender, receiver and storage server. The sender sends the server the ciphertexts attached with searchable encrypted labels, which are associated with a keyword set. The receiver generates the trapdoor based on the logical expression of keywords (shown as a logical tree in Fig. 1) and sends it to the storage server. Once receiving the trapdoor, the storage server executes a test algorithm to find the ciphertexts that match the trapdoor, and sends the receiver all matching ciphertexts finally.

Figure 1: System framework of EPEKS

Attribute-based encryption (ABE) is a novel paradigm of public key cryptography. In ABE, only if the attribute set satisfies the given access structure, a user can recover the plaintext from a ciphertext correctly. Therefore, ABE has strong access control ability [6], which can be used to solve the second issue mentioned above. So far, many different ABE schemes have been proposed. Among them, the scheme which inserts the access structures into the users’ private keys is key-policy ABE (KP-ABE), while the scheme that inserts the access structures into the ciphertexts is ciphertext-policy ABE (CP-ABE). Attribute-based encryption with keyword search (ABEKS) was originally presented by Lai et al. in [3], which combines the functions of both PEKS and ABE. It simultaneously realizes the ciphertext retrieval and the fine-grained access control. Because ABEKS well meets the practical application requirements, it has become a hotspot of current research. In [7], Han et al. introduced the idea of expressive keyword search into ABEKS and put forward the first expressive ABEKS (EABEKS) scheme. Fig. 2 shows the system framework of a key-policy EABEKS scheme. In key-policy EABEKS, a trusted center (TC) is responsible for distributing a private key to every user according to the attribute-based access structure. The sender generates the searchable ciphertexts according to an attribute set and a keyword set, then sends the cloud server the ciphertexts. To retrieve ciphertexts on the server, the receiver needs requesting the trapdoor of the keyword-based search predicate from the TC and then sends the cloud server the trapdoor. After the server finishes searching operation, the ciphertexts matching the trapdoor are returned to the receiver. In a ciphertext-policy EABEKS system, the ciphertexts are associated with the attribute-based access structures, while the users’ private keys are produced according to their attributes.

Figure 2: System framework of key-policy EABEKS

1.1 Related Works

Song et al. [8] first proposed the definition of searchable encryption under the symmetric cryptosystem. The searchable encryption scheme under the public key system was presented by Boneh et al. [1], which also gave a general transformation from identity-based encryption (IBE) to PEKS. Since then, many improved schemes [9–22] involving security, performance, function were presented. After Park et al. [2] put forward a PECKS scheme which supports joint keyword search, many works [23–27] have been committed to reducing the computation cost and the trapdoor length. Lai et al. [3] firstly camp up with an EPEKS scheme that was constructed from the fully secure KP-ABE scheme presented in [28]. Later, Lv et al. [4] presented an EPEKS scheme supporting boolean logic combination of “AND”, “OR” and “NOT”. However, the above two schemes are based on the composite-order groups, which leads to low efficiency because the composite-order groups have longer elements and higher computation costs than the prime-order groups. In [29], Cui et al. inserted the linear secret sharing scheme (LSSS) structure into PEKS and constructed an EPEKS scheme over the prime-order groups. However, its efficiency is far from practical use. Therefore, the design of efficient and practical EPEKS schemes over the prime-order groups is still a problem worth studying.

The history of ABE was originated from 1984. In that year, the definition of identity-based signature (IBS) was put forward by Shamir [30]. Until 2001, the practical IBE scheme was presented by Boneh et al. [31] for the first time. Later, Sahai et al. [32] put forward a fuzzy IBE (FIBE) scheme that was considered as the rudiment of ABE. The KP-ABE scheme was first presented by Goval et al. [33]. The KP-ABE solution for the large universe was proposed by Lewko et al. [34], and the construction based on the prime-order group was implemented by Lewko [35]. The subsequent improved KP-ABE schemes can be reviewed in [36–39]. Bethencourt et al. [40] proposed the CP-ABE scheme for the first time. Subsequently, several improved schemes [41–43] were presented.

In [3], Lai et al. put forward a key-policy ABEKS scheme by combining KP-ABE with PEKS. At the same year, Wang et al. [44] also put forward an ABEKS scheme based on ciphertext-policy. After that, ABEKS quickly became a research hotspot and many schemes were designed, e.g., [44–49]. However, most of the existing ABEKS schemes have limited search capabilities and only support single or simple conjunctive keyword search. In [7], Han et al. showed a general transformation from KP-ABE to ciphertext-policy ABEKS and gave the first EABEKS scheme. Han et al.’s EABEKS scheme is based on the composite-order groups and thus suffers from poor efficiency. In [50], Meng et al. put forward a key-policy EABEKS scheme over the prime-order groups. However, the performance of Meng et al.’s scheme will deteriorate rapidly with the growth in the number of system keywords. Therefore, it cannot be applied to the applications with unbounded keyword universe.

Tab. 1 summarizes the characteristics of different frameworks of searchable public key encryption schemes mentioned above.

1.2 Our Contributions

We present a novel EABEKS scheme over the prime-order groups that supports unbounded keyword universe. The proposed scheme can efficiently convert any monotonic boolean search predicate (expressed by the logical connectives “AND” and “OR”) into a LSSS matrix and hence supply the expressive keyword search function. Interestingly, its performance is independent on the sizes of both the system keyword universe and attribute universe. Therefore, the scheme is very suitable for the applications with large keyword or attribute universe. We believe that our EABEKS scheme is the first one that supports both unbounded keyword and attribute universes. The security proofs without the random model demonstrate that it is secure against chosen keyword attack and chosen plaintext attack. Compared with the existing EABEKS schemes, it has the merits of low storage, computation and communication costs.

2  Preliminaries

2.1 Bilinear Map and Complexity Assumptions

Let G and GT be two groups of prime order p. The bilinear pairing is a bilinear map e: G × G → GT that possess the following properties:

1) Bilinearity: m, n ∈ G and x, y ∈ Zp∗ , e(mx, ny) = e(m, n)xy.

2) Non-degeneracy: m, n ∈ G, e(m, n) ≠ 1.

For the sake of simplicity, we call (p, G, GT, g, e) the bilinear groups, where g is the generator of the group G. The security of the proposed EABEKS scheme is based on the decisional (q-1) assumption and the decisional (q-2) assumption [5].

Definition 1. Let q be an integer and (p, G, GT, g, e) be the bilinear groups. The decisional (q-1) assumption is: given following elements

g,gygxi,gbj,gybj,gxibj,gxi/bj2∀(i,j)∈[q,q]gxi/bj∀(i,j)∈[2q,q],i≠q+1gxibj/bj′2∀(i,j,j′)∈[2q,q,q],j≠j′gyxibj/bj′,gyxibj/bj′2∀(i,j,j′)∈[q,q,q],j≠j′ in G, it is hard to differentiate e(g,g)yxq+1 from a random element T in GT for any polynomial-time (PT) adversary, where t,x,y,b1,b2,...,bq are chosen randomly from Zp∗ .

The decisional (q-1) assumption declares that for any PT adversary A, its advantage AdvA in working out the decisional (q-1) problem is negligible. The advantage AdvA in solving the decisional (q-1) problem is defined as

|Pr[A(S,e(g,g)yxq+1)=1]−Pr[A(S,T)=1|T∈GT]| (1)

where S stands for the set of above-mentioned parameters.

Definition 2. Let q be an integer and (p, G, GT, g, e) be the bilinear groups. The decisional (q-2) assumption is: given following elements

g,gx,gy,gz,g(xz)2gbi,gxzbi,gxz/bi,gx2zbi,gy/bi2,gy2/bi2∀i∈[q]gxzbi/bj,gybi/bj2,gxyzbi/bj,g(xz)2bi/bj∀i,j∈[q],i≠j in G, it is hard to differentiate e(g, g)xyz from a random element T in GT for any polynomial-time (PT) adversary. Here x, y, z, b1, …, bq are chosen randomly from Zp∗ .

The decisional (q-2) assumption declares that for any PT adversary A, its advantage AdvA in working out the decisional (q-2) problem is negligible. The advantage AdvA in solving the decisional (q-2) problem is defined as

|Pr[A(S,e(g,g)xyz)=1]−Pr[A(S,T)=1|T∈GT]| (2)

where S stands for the set of above-mentioned parameters.

2.2 Access Structure and Linear Secret Sharing Scheme

Let the system attribute/keyword universe be U. The access structure F defined on U comes from a set of attributes/keywords which is not empty, i.e., F ⊆ 2U/{Ø}. Only the sets which belong to F can be defined as the authorized sets. Otherwise, they are unauthorized. An access structure F can be defined to be monotone when it meets if ∀B, C ∈ F and B ⊆ C, then C ∈ F .

Definition 3. Let p be a prime and U be an universe of parties. A secret-sharing scheme Π is linear over Zp∗ based on the universe U when it meets the following conditions:

1) Every share of the parties forms a vector based on Zp∗ .

2) MA is a l⊆n matrix which can generate each different shares. There exists mapping ρ:{1,…,l}→U so that ρ(i) ( i=1,…,l ) links i-row of MA with the party from U. Set vector v→=(μ,r2,…,rn) , in which μ∈Zp∗ is a sharing secret and r2,…rn∈Zp∗ are random integers. Then, MAv→ has l shares of secret and (MAv→)i belongs to ρ(i) .

A LSSS can be linearly reconstructed. Assuming that Π is a LSSS for the access policy P=(MA,ρ) , A∈P is an authorized set. Let I⊆{1,…,l} as I={i|ρ(i)∈A} .There exists constants {ωi∈Zp∗}i∈I that satisfies ∑i∈Iωivi=μ where {vi} are valid shares of secret .

2.3 Framework of EABEKS and Security Definitions

The framework of an EABEKS scheme includes the following six algorithms:

1) Setup(f). A trusted central authority (TCA) runs the algorithm. It inputs a security parameter f, and produces the public parameters PP and a master secret key MSK. MSK is kept secret while PP is made public.

2) KeyGen(PP, MSK, AST). TCA runs the algorithm. It inputs PP, MSK and an attribute set AST, and returns a private key SKAST corresponding to AST.

3) Encrypt(PP, M, FS , WS). Data sender runs the algorithm. It inputs PP, a message M, an attribute access structure FS and a keyword set WS, and returns a ciphertext CT.

4) Trapdoor(PP, MSK, P). TCA runs the algorithm. It inputs PP, MSK and a keyword search predicate P, and produces a search trapdoor TP of the predicate P.

5) Test(PP, TP, CT). This algorithm is executed by the server and takes PP, TP and CT as inputs. It outputs 1 if CT matches TP or 0 else.

6) Decrypt(PP, SKAST, CT). The receiver runs the algorithm which takes PP, SKAST and CT as inputs. If the attribute set AST encoded in SKAST meets the access structure FS embedded in CT, it returns the message M. Otherwise, the receiver fails to decrypt.

An EABEKS scheme should ensure that the keyword ciphertext and the message ciphertext are both indistinguishable. The security of an EABEKS scheme can be defined by the following two adversarial games which are executed between an adversary A and a challenger Ch .

The keyword ciphertext indistinguishability of the EABEKS scheme is defined by the following adversary game:

1) Init. A submits two different equal-size keyword sets WS0 and WS1.

2) Setup. Ch runs Setup algorithm to obtain PP and MSK. MSK is kept secret and PP is given to A.

3) Phase 1. A adaptively queries trapdoor TP of any search predicate P, but with the restriction that WS0 and WS1 do not satisfy P. Ch executes the algorithm Trapdoor(PP, MSK, P) and returns A the result.

4) Challenge. A submits an access structure F and the message M. Ch selects the bit b ∈ {0, 1} randomly. Then, it executes the algorithm Encrypt(PP, M, FS , WSb) to produce a challenge ciphertext CT* and sends it to A.

5) Phase 2. Consistent with Phase 1.

6) Guess. The adversary A outputs b′ ∈{0, 1} and succeeds if b = b′ . A's advantage is defined as:

AdvA=|Pr[b=b′]−1/122|. (3)

Definition 4. An EABEKS scheme is indistinguishable against chosen keyword attack (IND-CKA) if any PT adversary’s advantage in the above game is negligible.

The message ciphertext indistinguishability of an EABEKS scheme is defined by the next game:

1) Init. A submits an access structure FS as its challenge.

2) Setup. Ch runs Setup algorithm to obtain PP and MSK. MSK is kept secret and PP is given to A.

3) Phase 1. A adaptively queries the SKAST of any attribute set AST, but with the restriction that AST does not satisfy FS . Ch executes the algorithm KeyGen (PP, MSK, AST) and returns A the result.

4) Challenge. A submits a keyword set WS and two message M0, M1 of same length. Ch selects a bit b ∈ {0, 1} randomly. Then, it executes the algorithm Encrypt(PP, Mb, FS , WS) to produce a challenge ciphertext CT* and sends it to A.

5) Phase 2. Consistent with Phase 1.

6) Guess. The adversary A outputs b′ ∈{0, 1} and succeeds if b = b′ . A’s advantage can be calculated as:

AdvA=|Pr[b=b′]−1/122|. (4)

Definition 5. An EABEKS scheme is indistinguishable against chosen plaintext attack (IND-CPA) if any PT adversary’s advantage in the above game is negligible.

3  The Proposed EABEKS Scheme

The proposed EABEKS scheme is described as below:

1) Setup(f). The algorithm creates the bilinear groups (p, G, GT, g, e); picks four elements u, h, w, v ∈ G and two numbers α, β ∈ Zp∗ randomly; sets the public parameters PP = (p, G, GT, e, g, u, h, w, v, e(g, g)α, e(g, g)β) and the master key MSK = (α, β).

2) KeyGen(PP, MSK, AST). The algorithm chooses κ+1 numbers γ,γ1,γ2...,γκ∈Zp∗ randomly and calculates K0=gβwγ , K1=gγ , Kυ,2=gγυ , Kυ,3=(uAυh)γυv−γ where Aυ∈AST , υ ∈ [κ], [κ] = {i ∈ Zp∗ | i < κ}. Finally, it outputs SKAST=(AST,K0,K1,{Kυ,2,Kυ,3}υ∈[κ]) as the private key.

3) Encrypt(PP, M, FS , WS). The algorithm first picks a random vector ψ→=(ψ,ψ2,...,ψn)⊤ and computes μ→=(μ1,μ2,...,μι)⊤=MAψ→ , where ψ,ψ2,...,ψn∈Zp∗ and MA is the matrix corresponding to FS which is used to generate the shares. Then, it randomly chooses ι numbers ς1,ς2,...,ςι∈Zp∗ , calculates CM=M⋅e(g,g)βψ , C1=gψ , Cv,A1=wμvvζv,  Cv,A2=(μρ(v)h)−ζv, Cυ,A3=gςυ and sets CTM=(FS,CM,C1,{ Cv,A1,Cv,A2,Cv,A3 }v∈[ l ]) Cυ,A2,Cυ,A3}υ∈[ι]) , where ρ is a function used to link every row of MA to the attribute in the access structure. The algorithm also randomly selects k+1 numbers s,r1,r2...,rk∈Zp∗ , computes C=CM⋅e(g,g)αs , C0=gs , Cτ,K1=grτ , Cτ,K2=(uWτh)rτw−s where Wτ∈WS , τ∈[k] , [k]={1,2,⋯k} and sets CTK=(C,C0,{ Cτ,K1,Cτ,K2 }τ∈[ k ]). The final searchable ciphertext is CT=(CTM,CTK).

4) Trapdoor(PP, MSK, P). The algorithm creates an access structure FP according to the search predicate P and choose u~,h~,v~,β∈Zp to calculate λ→=(λ1,λ2,…,λl)⊥=MAy→ , where y2,...,yn∈Zp∗ and the matrix MA is linked with FP . It then selects l numbers t1,t2,...,tl∈Zp∗ to calculate Tτ,0=gλτwtτ , Tτ,1=(uρ(τ)h)−tτ and e(g,g)β for each τ ∈ [l]. The trapdoor is TP=(MA,{Tτ,0,Tτ,1,Tτ,2}τ∈[l]) .

5) Test(PP, TP, CT). Define I as the minimum subset satisfying FP and IFP is the set of all Is. The server extracts IFP according to MA and decides if exists an I∈IFP fulfilling

CM=C∏i∈I⁡(e(C0,Ti,0)e(Cτ,K1,Ti,1)e(Cτ,K2,Ti,2))ωi (5)

where {ωi∈Zp}i∈I . If the above equation fails, output 0; else return 1.

Obviously, if the keyword set WS is authorized, then ∑i∈Iωiλi=α holds. Therefore, we can deduce that ∏i∈I⁡(e(C0,Ti,0)e(Cτ,K1,Ti,1)e(Cτ,K2,Ti,2))ωi = ∏i∈I⁡e(g,g)sωiλi ∏i∈I⁡e(g,uρ(i)h)rτtiωie(g,w)−stiωi =e(g,g)αs .

Thus, the test algorithm is correct.

6) Decrypt(PP, SKAST, CT). This algorithm computes IFP according to the matrix MA based on the access structure FP and determines if there exists an I∈IFP fulfilling

B=e(C1,K0)∏ρ(i)∈ATS⁡(e(Ci,A1,K1)e(Ci,A1,Kυ,2)e(Ci,A3,Kυ,2))ωi (6)

in which {ωi∈Zp∗}i∈I . If so, it outputs M=CM/B .

If AST is an authorized set, then ∑ρ(i)∈ASTωiμi=ψ holds. Therefore, we can deduce that

B=e(g,g)βψe(g,w)γψ∏ρ(i)∈AST⁡e(g,w)γωiμie(g,v)γςiωie(g,uρ(i)h)−γυςiωie(g,v)−γςiωi==e(g,g)βψe(g,w)γψe(g,w)γ∑ρ(i)∈ASTωiμi=e(g,g)βψ (7)

Thence, the above Decrypt algorithm can correctly decrypt the ciphertext.

Next, we prove the security of the proposed scheme.

Theorem 1. If the (q-2) decisional assumption holds, then the proposed EABEKS scheme achieves the IND-CKA security in the standard model.

Proof. Assume that there exists a PT adversary A that has an advantage ε in breaking the IND-CKA security of our EABEKS scheme, then an algorithm B can be created to settle the decisional (q-2) problem with same advantage ε.

Suppose an instance of the decisional (q-1) problem is given to the algorithm B as follows.

{p,G,GT,e,g,gx,gy,gz,g(xz)2gbi,gxzbi,gxz/bi,gx2zbi,gy/bi2,gy2/bi2∀i∈[q]gxzbi/bj,gybi/bj2,gxyzbi/bj,gxyzbi/bj∀i,j∈[q],i≠jT} , in which g ∈ G, x,y,z,b1,...,bq∈Zp∗ and T ∈ GT. The goal of the algorithm B is to determine whether T = e(g, g)xyz. For this purpose, B plays the role of challenger and interacts with the adversary A in the following game.

1) Init. Algorithm B gets two keyword sets WS0 and WS1 given by A. Assume that both WS0 and WS1 contain k (k ≤ q) diverse keywords.

2) Setup. Algorithm B first selects β ∈ {0, 1} at random. Next, it randomly selects four integers u~,h~,v~,β∈Zp and calculates: e(g, g)α = e(gx, gy), w=gx , u=gu~⋅∏i∈[k]gy/bi2 , v=gv~ and h=gh~⋅∏i∈[k]gxy/bi⋅∏i∈[k](gy/bi2)−Ai∗ . Then, PP = (p, G, GT , e, g, u, h, w, v, e(g,g)α , e(g,g)β ) is sent to A. Note that α in MSK is implicitly set to be xy.

3) Phase 1. For every trapdoor query from adversary A, B first generates an access structure FP=(MA,ρ) and then replies with the corresponding trapdoor for each search predicate P queried by the adversary A. Notice that FP cannot satisfied by either WS0 or WS1. Since WSβ is not an authorized set, there is a vector ω→=(ω1,...,ωn)⊥∈Zpn such that ω1 = 1 and MAi⋅ω→ = 0 for all (i ∈ [l], ρ(i) ∈ ASTβ). The sharing vector is y→=xyω→+(0,y→2,y→3,...,y→n)⊥ , where y→2,y→3,...,y→n are randomly selected in Zp . For every row τ ∈ [l], the share is λτ = MAτ y→ = xy(MAτ ω→ ) + (MAτ (0,y→2,y→3,...,y→n)⊥ ) = xy(MAτ ω→ ) + λ→τ .

For every row of MA, when ρ(τ) ∈ WSβ, MAτ ω→ = 0. In this case λτ = λ→τ , B chooses an element tτ ∈ Zp at random and then runs the Trapdoor algorithm to output trapdoor.

Under other circumstances, if ρ(τ) ∉ WSβ , B arbitrarily picks l elements {t~τ|t~τ∈Zp,τ∈[l]} and lets tτ=−y(MAτ⋅ω→)+∑i∈[k]xzbi(MAi⋅ω→)ρ(τ)−Wi+t~τ . After that, by the following calculation, we can get a correct trapdoor: Tτ,0=gλτwtτ =gxy(MAτ⋅ω→)+λ→τ⋅g−xy(MAτ⋅ω→)+∑i∈[k]x2zbi(MAτ⋅ω→)ρ(τ)−Wi⋅wt~τ =gλ~τ⋅∏i∈[n](gx2zbi)(MAτ⋅ω→)/(ρ(τ)−Wi)⋅wt~τ , Tτ,1=(uρ(τ)h)−tτ = (gρ(τ)u~+h~⋅∏i∈[n]gxz/bi⋅ ∏i∈kgy(ρ(τ)−Wi)/bi2)y(MAτ⋅ω→)−∑i∈[k]xzbi(MAτ⋅ω→)ρ(τ)−Wi⋅(uρ(τ)h)−t~τ = gy(MAτ⋅ω→)(ρ(τ)u~+h~)⋅ ∏i∈[k]g−xzbi(ρ(τ)u~+h~)(MAτ⋅ω→)/(ρ(τ)−Wi)⋅ ∏i∈[k]gxyz(MAτ⋅ω→)/bi⋅∏(i,j)∈[k,k]g−(xz)2bj(MAτ⋅ω→)/bi(ρ(τ)−Wi)⋅ ∏i∈[k]gy2(MAτ⋅ω→)(ρ(τ)−Wi)/bi2⋅ ∏(i,j)∈[k,k]g−xyz(MAτ⋅ω→)bj(ρ(τ)−Wi)/bi2(ρ(τ)−Wi)⋅(uρ(τ)h)−t~τ = ∏i∈[k](gxzbi)−(ρ(τ)u~+h~)(MAτ⋅ω→)/(ρ(τ)−Wi)⋅ (gy)(MAτ⋅ω→)(ρ(τ)u~+h~)⋅ ∏(i,j)∈[k,k](g(xz)2bj/bi)−(MAτ⋅ω→)/(ρ(τ)−Wi)⋅ ∏i∈[k](gy2/bi2)(MAτ⋅ω→)(ρ(τ)−Wi)⋅ ∏(i,j)∈[k,k]i≠j(gxyzbj/bi2)−(MAτ⋅ω→)(ρ(τ)−Wi)/(ρ(τ)−Wi)⋅(uρ(τ)h)−t~τ , Tτ,2=gtτ=(gy)−(MAτ⋅ω→)⋅∏i∈[k](gxzbi)(MAτ⋅ω→)/(ρ(τ)−Wi)⋅gt~τ .

4) Challenge. A sends B a message M and an access structure. B runs the algorithm Encrypt to create CTM . Then B lets s = z and rτ = bτ for every τ ∈ [k], computes C=CM⋅T , C0=gs=gz , Cτ,K1=grτ=gbτ and Cτ,K2=(uWτh)rτ⋅ω−s =gbτ(uWτ+h~)⋅∏i∈[k]gxzbτ/bi∏i∈[k]gybτ(Wk−Wi)/bi2⋅g−xz = ∏i∈[k]i≠τ(gybτ/bi2)Wτ−Wi⋅ (gbτ)u~Wτ+h~⋅∏i∈[k]i≠τgxzbτ/bi , where CM is contained in CTM. Finally, the algorithm B sends CT=(CTM,CTK) to A as the challenge ciphertext.

5) Phase 2. Consistent with Phase 1.

6) Guess. Finally, the adversary A produces its guess β′ ∈{0, 1} for β. If β′=β , B returns 1. On the contrary, the returned result is 0.

It is clear that if T = e(g, g)xyz, then the challenge ciphertext is legal and valid to A. Therefore, Pr[ β′=β ] = 1/2 ± ε. On the contrary, the ciphertext is illegal and therefore Pr[ β′=β ] = 1/2. Therefore, B's advantage in handling the given decisional (q-2) problem is |1/2 ± ε - 1/2| = ε.

This proves Theorem 1.

Theorem 2. If the (q-1) decisional assumption holds, then the proposed EABEKS scheme achieves the IND-CPA security in the standard model.

Proof. Assume that there exists a PT adversary A which has an advantage ε in breaking the IND-CPA security of our EABEKS scheme, then an algorithm B can be created to settle the decisional (q-1) problem with same advantage ε.

Suppose an instance of the decisional (q-1) problem is given to the algorithm B as follows.

{g,gygxi,gbj,gybj,gxibj,gxi/bj2∀(i,j)∈[q,q]gxi/bj∀(i,j)∈[2q,q],i≠q+1gxibj/bj′2∀(i,j,j′)∈[2q,q,q],j≠j′gyxibj/bj′,gyxibj/bj′2∀(i,j,j′)∈[q,q,q],j≠j′T} , in which g ∈ G, x,y,b1,...,bq∈Zp∗ and T ∈ GT. The goal of the algorithm B is to determine whether T = e(g,g)yxq+1 . For this purpose, B plays the role of challenger and interacts with the adversary A in the following game.

1) Init. The algorithm B receives an access structure FS from the adversary A. We assume that MA in FS is a l⊆n share generating matrix.

2) Setup. B arbitrarily picks five numbers u~,h~,v~,α,β~∈Zp randomly and sets: g∈G,w=gx , u=gu~⋅∏(j,k)∈[l,n](gxk/bj2)MAj,k , h=gh~⋅∏(j,k)∈[l,n](gxk/bj2)−ρ(j)MAj,k , v=gv~⋅∏(j,k)∈[l,n](gak/bj)MAj,k , e(g,g)β=e(gx,gxq)⋅e(g,g)β~ . Then, PP = (p, G, GT , e, g, u, h, w, v, e(g,g)α , e(g,g)β ) is public so A can receive. xq+1+β~ implicitly represents β which means B cannot obtain the value of β.

3) Phase 1. For every query from adversary A, B replies with the corresponding private key. However, above queried attribute sets fail to match the access structure defined by AST. Since AST is not an authorized set, there is a vector ω→=(ω1,...,ωn)⊥∈Zpn such that ω1 = 1 and MAτ⋅ω→=0 for all {υ|υ∈[l],ρ(υ)∈AST} . Then it randomly selects a number γ~∈Zp∗ , and calculates γ=γ~+ω1xq+ω2xq−1+...+ωnxq+1−n=γ~+∑i∈[n]ωixq+1−i . So, γυ can be calculated implicitly =γ~υ+γ~⋅∑i′∈[l]ρ(i′)∉ASTbi′Aυ−ρ(i′)+∑(i,i′)∈[n,l]ρ(i′)∉ASTωibi′xq+1−iAυ−ρ(i′) . Therefore, the private key can be calculated as follows:

K0=gβwγ=gxq+1gβ~gxγ~∏i∈[n]gωixq+2−i=gβ~(gx)γ~∏i=2n(gxq+2−i)ωi (8)

K1=gγ=gγ~∏i∈[n](gxq+1−i)ωi (9)

Kυ,2=gγυ=gγ~υ⋅∏i′∈[l]ρ(i′)∉AST(gbi′)γ~/(Aυ−ρ(i′))⋅∏(i,i′)∈[n,l]ρ(i′)∉AST(gbi′xq+1−i)ωi/(Aυ−ρ(i′)) (10)

Kυ,3=(uAυh)γ~υ⋅(Kυ,2/gγ~υ)u~Aυ+h~⋅ ∏(i′,j,k)∈[l,l,n]ρ(i′)∉AST(gbi′xk/bj2)γ~(Aυ−ρ(j))MAj,k/(Aυ−ρ(i′))⋅∏(i,i′,j,k)∈[n,l,l,n]ρ(i′)∉AST,(j≠i′∨i≠k)(gbi′xq+1+k−i/bj2)(Aυ−ρ(j))ωiMAj,k/(Aυ−ρ(i′))

⋅vγ~∏i∈[n](gxq+1−i)−v~ωi⋅∏(i,j,k)∈[n,l,n]i≠k(gxq+1+k−i/bj)−ωiMAj,k. (11)

4) Challenge. A sends algorithm B two equal-length messages M0 , M1 . B chooses β ∈ {0, 1} at random, and implicitly constructs a vector ψ→=(ψ,ψx+ψ~2,ψx2+ψ~3,...,ψxn−1+ψ~n)⊥ , where ψ~2,ψ~3,...,ψ~n∈Zp . The vector μ→=MAψ→ can be computed as:

μ→=∑i∈[n]MAυ,iyxi−1+∑i=2nMAυ,iψ~i=∑i∈[n]MAυ,iyxi−1+μ~υ (12)

B implicitly sets ςυ=−ybυ and calculates

CM=Mb⋅T⋅e(g,gy)β~ (13)

C1=gy (14)

Cυ,A1=wμυvςυ=wμ~υ⋅∏i∈[n]gMAυ,iyxi⋅(gybυ)−v~⋅∏(j,k)∈[l,n]g−MAj,kxkybυ/bj=wμ~υ⋅(gybυ)−v~⋅∏(j,k)∈[l,n]j≠υ(gyxkbυ/bj)−MAj,k (15)