A ciphertext-policy attribute-based searchable encryption scheme in non-interactive model

Journal of Computer Science and Cybernetics, V.35, N.3 (2019), 233–249

DOI 10.15625/1813-9663/35/3/13667

A CIPHERTEXT-POLICY ATTRIBUTE-BASED SEARCHABLE

ENCRYPTION SCHEME IN NON-INTERACTIVE MODEL

1

2,∗

VAN ANH TRINH , VIET CUONG TRINH

¹Thanh Hoa University of Culture, Sports and Tourism

²Hong Duc University, Thanh Hoa, Viet Nam

^∗Trinhvietcuong@hdu.edu.vn

ꢀ

Abstract. We address the problem of searching on encrypted data with expressive searching predi-

cate and multi-writer/multi-reader, a cryptographic primitive which has many concrete application

scenarios such as cloud computing, email gateway application and so on. In this paper, we propose

a public-key encryption with keyword search scheme relied on the ciphertext-policy attribute-based

encryption scheme. In our system, we consider the model where a user can generate trapdoors by

himself/herself, we thus can remove the Trusted Trapdoor Generator which can save the resource and

communication overhead. We also investigate the problem of combination of a public key encryption

used to encrypt data and a public-key encryption with keyword search used to encrypt keywords,

which can save the storage of the whole system.

Keywords. Attribute-based Encryption; Searchable Encryption; Searching on Encrypted Data.

1. INTRODUCTION

Searching on encrypted data is an important task, which can be applicable to many

practical contexts such as cloud computing or email gateway application. In the context of

cloud computing, the user’s data is ﬁrst encrypted and then outsourced to the cloud server.

When user would like to ﬁnd some speciﬁc data, he/she needs to ask help from the cloud

server, user however doesn’t want the cloud server to know about his/her original data.

In the email gateway application, when anyone would like to securely send email to Alice,

he/she encrypts the content of email under Alice’s public key before sending. On the other

hand, Alice would like to set priority order of receiving her emails. To this aim, Alice gives

the email gateway the ability to check the priority order of incoming emails and then send

to her emails in the order she wants. However, Alice also doesn’t want the email gateway to

know about the content of such emails.

Searchable Encryption (SE) was introduced in [2, 16] to deal with such aforementioned

problems. In a nutshell, in a system which supports SE, we append encrypted keywords

with corresponding encrypted data. User then relies on his/her secret key in SE scheme

and chosen keywords to generate a trapdoor for the cloud server (or the email gateway) to

perform the search. The trapdoor is generated in such a way that the cloud server (or the

email gateway) using this trapdoor can perform successfully the search, but doesn’t get any

information about the original data in the resulted ciphertexts. On the other hand, since

keywords are encrypted, unauthorized users (called outsiders) as well as cloud server (called

c

ꢀ 2019 Vietnam Academy of Science & Technology

234

VAN ANH TRINH, VIET CUONG TRINH

insider) ideally also don’t know any information about keywords in each ciphertext. We can

category SE in two types:

1. SE in the private-key setting [16], where there is only one writer (data owner who

encrypts the data as well as the corresponding keywords) and one/multi reader (user

who would like to search and then should be able to decrypt the resulted ciphertexts).

This type of SE has obviously limited applications in practice. For example, it cannot

apply to the context of sending email above since anyone should have the capacity of

encrypting the content of emails sent to Alice.

2. SE in the public-key setting [2], where there are multi-writer and one/multi reader. A

full searchable encryption system in practice includes two components: the ﬁrst is a

Public Key Encryption (PKE) scheme used to encrypt data; the second is a Public-

Key Encryption with keyword Search (PEKS) used to encrypt keywords. Such full

system is called a PKE-PEKS scheme. In a PKE-PEKS scheme, a full ciphertext,

including both the encrypted keywords and encrypted data, should be in the form

0

PKE_Alice(data)||PEKS_Alice(keywords).

pk

There are two cases: PKE and PEKS are independent, that means Alice’s public-

key/secret-key in PKE is diﬀerent to the ones in PEKS; and otherwise, where Alice’s

public-key/secret-key could be the same in both PKE and PEKS. Obviously, such full

system will become more eﬃcient in the latter case. However, in this case we have to

consider carefully the security of the full system [10] since the adversary is now more

powerful than the one in the former case. When PKE and PEKS are independent, we

often only care about PEKS scheme and omit the PKE scheme for simplicity. In some

schemes [6, 11, 14], Alice cannot generate the trapdoor by himself/herself, he/she needs

to contact with a Trusted Trapdoor Generator (TTG), that will obviously increase the

communication overhead of the user, and moreover the Trusted Trapdoor Generator

should be always online. We call such schemes interactive schemes.

In summary, there are several following important properties one should take into

account when estimating a system which supports searching on encrypted data:

• Eﬃciency: Performance of encryption/decryption/searching algorithm, key-size/

ciphertext-size, PKE and PEKS are independent or not, interactive or non-

interactive, etc;

• Expressive searching predicate: Whether or not the PEKS scheme supports con-

junctive keywords or even boolean formulas of keywords for searching. Obviously,

this property is more desirable than simple equality keyword search in practice;

• Trapdoor security: Cloud server with a trapdoor in hand knows nothing about

the keywords in the ciphertext and trapdoor, even when the trapdoor “matches”

the ciphertext. We note that this property is very hard to achieve in the public-

key setting, to the best of our knowledge there is only one scheme [6] that can

partially achieve this property.

• Keyword security: Ideally, unauthorized users and cloud server cannot derive any

information about keywords in the ciphertext.

A CIPHERTEXT-POLICY ATTRIBUTE-BASED SEARCHABLE ENCRYPTION SCHEME

235

1.1. Related work

Over past decade, substantial progress has been made on problem of searching on encrypted

data [1, 2, 3, 6, 8, 9, 11, 14, 16, 17, 18, 19], to name a few. These papers use diﬀerent techni-

ques and consider diﬀerent situations for searching on encrypted data. SE in private-key

setting and supports only single-writer/single-reader was ﬁrst introduced in [16]. Continue

this line of research, the authors in [3] investigated searchable encryption with conjunctive

keyword searches and boolean queries. The authors in [17, 18] went further to investigate

searchable encryption scheme in single-writer/multi-reader setting and partially trapdoor

security. Partially non-interactive which can reduce the communication overhead was also

investigated in [17].

SE in the public-key setting was ﬁrst introduced by Boneh et al. [2], but their sche-

mes only support multi-writer/single-reader and equality queries. In [1, 19], the authors

extended to support multi-writer/multi-reader but their schemes still only support equa-

lity queries. Expressive searching predicate and multi-writer/multi-reader were investigated

in [6, 8, 11, 12, 14], where authors manage to transform from a key policy/ciphertext policy

attribute-based encryption scheme to a PEKS scheme, these schemes are thus called key

policy/ciphertext policy attribute-based searchable encryption scheme. The authors in [6]

went further to consider partially trapdoor security in the sense that, they split a keyword

into two parts: The keyword name and the keyword value, where one keyword name can

have many keyword values. They then showed that in their scheme, the cloud server with

the trapdoor in hand can only know keyword names but nothing about keyword values in the

ciphertext. This interesting property is useful in some speciﬁc practical contexts. However,

the downside of this technique is that the searching time is only acceptable if the keyword

names are included in the ciphertext, this leads to the fact that anyone can also know the

keyword names in the ciphertext. On the other hand, the combination of PKE and PEKS

was investigated in [10] where [10] also investigated the non-interactive property, however

this scheme does not support expressive searching predicate.

1.2. Our contribution and organization of the paper

In this paper, we propose a PKE-PEKS scheme supporting both the expressive searching

predicate and multi-writer/multi-reader, our scheme is built from the CP-ABE scheme in [13],

we thus name our scheme CP-ABSE scheme for short. Our scheme has following properties:

• Our scheme is a combination of an existing PKE scheme (which is exactly the CP-ABE

in [13]) and a new proposed PEKS scheme. In our scheme, user has only one pair of

public key/secret key for both PKE and PEKS, and moreover user can use the CP-ABE

setting to encrypt/decrypt data;

• Our scheme is non-interactive: User can generate the trapdoor by himself/herself, we

thus can remove the Trusted Trapdoor Generator in our system. On the other hand,

since trapdoor is generated from user’s secret key, user is able to decrypt all resulted

ciphertexts which can save time and communication overhead of the system;

• Eﬃciency: Since our CP-ABSE scheme is built from the CP-ABE scheme in [13], our

scheme naturally inherits the eﬃciency and properties of this CP-ABE scheme such as

236

VAN ANH TRINH, VIET CUONG TRINH

constant-size of user’s secret key, optimized ciphertext size, multi-authority and fast

decryption. Note that the CP-ABE scheme in [13] is still one of the most eﬃcient

CP-ABE schemes to date.

• We also note that our scheme does not achieve trapdoor security. We emphasize that

this property is very hard to achieve in the public-key setting, to the best of our

knowledge there is only one scheme [6] that can partially achieve this property.

In the Section 5, we give the details comparison among our scheme and several schemes

which also support both the expressive searching predicate and multi-writer/multi-reader.

The paper includes 6 sections. The ﬁrst section presents the deﬁnition and security model

of a CP-ABSE scheme. In Section 3, we present the construction of our CP-ABSE scheme and

prove that it is secure in the following section. The comparison and discussions are given in

Section 5. Finally, the conclusion is in Section 6.

2. PRELIMINARIES

In this section, we ﬁrst give the system workﬂow and the threat model of our system,

then we present the deﬁnition and security model for our CP-ABSE scheme.

2.1. Ciphertext policy attribute based searchable encryption

2.1.1. System workﬂow and threat model

Our CP-ABSE scheme is a combination of a traditional CP-ABE scheme and a PEKS scheme

supporting expressive searching predicate. In our scheme, there are four entities: data owner;

user; cloud server and Private Key Generator (PKG). More precisely:

1. PKG: Play the role of PKG in traditional CP-ABE scheme, generates secret keys for

users.

2. Data owner: Encrypt data as well as corresponding keywords, upload them to a public

cloud.

3. User: Rely on his/her secret key to generate a trapdoor, send this trapdoor to the

cloud server and get back resulted ciphertexts. Finally, decrypt resulted ciphertexts to

recover data.

4. Cloud server: Receive a trapdoor from a user, perform the search based on the trapdoor

and send back resulted ciphertexts to the user.

Threat model. Similar to the threat model in recent schemes [6, 8, 9, 11, 12, 14], in our

system, there are two goals for which an adversary would like to achieve: getting information

about encrypted data and getting information about encrypted keywords.

A CIPHERTEXT-POLICY ATTRIBUTE-BASED SEARCHABLE ENCRYPTION SCHEME

237

2.1.2. System algorithms

Formally, our CP-ABSE scheme includes seven following probabilistic algorithms.

Setup(1^ν, B): The inputs of this algorithm are security parameter ν and the description

of attribute universe B, the outputs are master key MSK and the public parameters

param of the system.

Extract(u, B(u), MSK, param): The inputs of this algorithm are attribute set B(u) of user

u, param and MSK, the output is the user’s secret key d_u.

Encrypt(M, A, param): The inputs of this algorithm are param, a message M and an

access policy A over the universe of attributes, the output is ciphertext ct along with

a description of the access policy A.

Decrypt(ct, d_u, param): The inputs of this algorithm are param, the ciphertext ct and the

secret key d_uof user u, the output is the message M if and only if B(u) satisﬁes A.

Otherwise, the output is ⊥.

Trapdoor(d_u, W_i, param): The inputs of this algorithm are param, secret key d_uof user u

and a set of keywords user would like to search W_i, the output is the trapdoor tds.

EncryptKW(KF, A⁰, param): The inputs of this algorithm are param, an access policy A⁰

over the universe of attributes and an access policy KF over the universe of keywords,

the output is the ciphertext ct⁰along with a description of the access policy A⁰.

Search(tds, ct⁰, param): The inputs of this algorithm are param, a trapdoor tds and a

ciphertext ct⁰, the output is 1 if the keyword set W_iembedded in tds matches the

access structure KF in ct⁰and B(u) satisﬁes A⁰. Otherwise, the output is 0.

We note that the full ciphertext should be the couple (ct, ct⁰). In addition, in order for

user to be able to decrypt the resulted ciphertext, we choose A⁰in ct⁰such that if B(u)

satisﬁes A⁰then B(u) satisﬁes A in ct.

2.1.3. Security model

Selective semantic security. The selective semantic security game is similar to the one

in [13], except that the adversary can ask additional corruption trapdoor query. Due to the

space limitations we refer the reader to [13] for details.

Insider security. Assume that A is the attacker, C is the challenger. The insider security

game is deﬁned as follows.

Setup(1^ν, B). At the beginning of the game, the adversary A provides a target access

policy A^∗over universe of attributes, and two equal target access policy KF₀^∗, KF^∗₁

over universe of keywords for which she intends to attack, where “equal access policy”

means that if KF^∗₀and KF^∗₁are described in the DNF form, they have the same

number of clauses. C runs the Setup(1^ν, B) algorithm to obtain param and MSK. She

then gives param to A.

238

VAN ANH TRINH, VIET CUONG TRINH

Query phase 1. A chooses a set of attributes B(u) as well as a set of keywords W_iand

asks corruption trapdoor query corresponding to these sets. The challenger computes

and returns corresponding tds to the adversary.

$

Challenge. C chooses b ← {0, 1} and runs EncryptKW(A^∗, KF_b^∗, param) to generate ct^0∗.

Finally, C outputs ct^0∗.

Query phase 2. The same as phase 1.

Guess. A ﬁnally outputs b⁰∈ {0, 1} as its guess for b.

A wins the game if b⁰= b, and if A never asks on B(u), W_isuch that both B(u) satisﬁes A^∗

and W_isatisﬁes either KF^∗₀or KF₁^∗. The advantage of A to win the game is deﬁned

ꢀ

ꢁ

1

Adv^I_A^S= Pr b = b⁰− .

2

Deﬁnition 1. A ciphertext-policy attribute-based searchable encryption scheme achieves

insider security if all polynomial time adversaries have at most a negligible advantage in the

above game.

Outsider security. The outsider security game is similar to the insider game, the diﬀerence

is that the adversary can ask corrupted secret key queries, instead of corrupted trapdoor

queries.

Due to the space limitations, we refer the reader to [13] for the deﬁnitions of Access

Structures, LSSS Matrices, Bilinear Maps and (P, Q, f) − GDDHE Assumptions and so on.

3.

CIPHERTEXT POLICY ATTRIBUTE BASED SEARCHABLE

ENCRYPTION

In this paper, we rely on the CP-ABE scheme in [13] to build our CP-ABSE scheme.

Concretely, our CP-ABSE scheme is a combination of CP-ABE scheme in [13] and a new

PEKS scheme, where the later scheme is also built from the former scheme. User in our

scheme, therefore, can use the same public key and secret key for both CP-ABE scheme and

PEKS scheme.

In our scheme, user relies on his/her secret key and a set of chosen keywords W =

(w₁, . . . , w_t) to generate the trapdoor. More precisely, from a set of chosen keywords W,

user has to indicate exactly which combinations of keywords he/she would like to search.

Consider the example in [6], W = (w₁, w₂, w₃) where w₁= “Diabetes”, w₂= “Age : 30”

and w₃= “Weight : 150 − 200”, user has to indicate the set of combinations of keywords

he/she would like to search W_i= (w₁||w₂, w₁||w₃). The advantage of this point is that we

can save the searching time and the communication overhead, since cloud server only needs

to ﬁnd and then send back ciphertexts user really wants. In other schemes [5, 6, 11, 14],

user doesn’t indicate exactly which combinations of keywords he/she would like to search,

the cloud server thus searches on all possible combinations of keywords.

A CIPHERTEXT-POLICY ATTRIBUTE-BASED SEARCHABLE ENCRYPTION SCHEME

239

3.1. Detailed construction

Our scheme is described as follows.

Setup(ν, B): Denote N = |B| the maximal number of attributes in the system,

(p, G, G_T, e(·, ·)) a bilinear group system. The algorithm ﬁrst picks a random gene-

rator g ∈ G, random scalars a, α, λ ∈ Z_p, computes g^a, g^α, g^λ. The algorithm conti-

nues to generate 2N group elements in G associated with N attributes in_∗the system

˜

h₁, . . . , h_N, h₁, . . . , h_N. Let H, H be hash functions such that H : {0, 1} → G and

∗

˜

H : G_T× {0, 1} → Z_p.

Suppose that the keyword universe in the system is W = (w₁, w₂, w₃, . . . ), where each

w_i∈ {0, 1}^∗. In our system the set W is unbounded, we can add any new keyword into

the system at anytime. For simplicity, we omit W in the global parameters. Finally,

we set the master secret key and global parameters as MSK = (g^α, λ) and

a

λ

α

˜

param = (g, g , g , e(g, g) , h₁, . . . , h_N, h₁, . . . , h_N, H, H).

Extract(u, B(u), MSK, param): Assume B(u) is the attribute set of user u. The algorithm

$

chooses s_u← Z_p, then computes user u’s secret key as d_u= (d_u, d⁰, {d_u}_i∈B(u), λ),

0

u₀

i

where

s_u

i

0

s_u

d_u= g^α· g^a·s, d_u= g , {d_u= h }_i∈B(u)

.

u

0

i

0

User u then keeps d_uand λ secret and publishes the rest of his/her secret key to the

public domain. That means the secret key of user is of the constant-size.

0

Encrypt(M, A, param): The inputs are a message M, an access policy A, as well as param.

Assume that A is a boolean formula β and that the size of β is |β|. At ﬁrst, encryptor

describes β in the form of DNF access policy as β = (β₁∨ · · · ∨ β_m), where each β_iis

a set of attributes, i = 1, . . . , m.

$

The encryptor chooses a scalar s ← Z_p, then computes C, C₀as

C = M · e(g, g)^α·s, C₀= g^s.

Next, encryptor compares between m and |β|, if m ≤ |β| he/she computes

Y

C₁= (g^a

h_i)^s, . . . , C_m= (g^a

h_i)^s.

i∈β₁

i∈β_m

Else, the encryptor constructs an LSSS matrix M representing the original boolean

formula β, and a map function ρ such that (M, ρ) ∈ (Z^`_p^×n, F([`] → [N])). She then

→−

chooses a random vector v = (s, y₂, . . . , y_n) ∈ Zⁿ_p. For i = 1, . . . , ` she computes

→−

λ_i= v · M_i, where M_iis the vector corresponding to the i’th row of M. She computes

−s

C_i= g^a.λh_ρ(i), i = 1, . . . , `.

i

Eventually, the output is either ct = (C, C₀, . . . , C_m) along with a description of β or

ct = (C, C₀, . . . , C_`) along with a description of (M, ρ).

240

VAN ANH TRINH, VIET CUONG TRINH

Decrypt(ct, d_u, param): The decryptor u ﬁrst parses the ct and checks the number of

elements in ct. If it is equal to m + 1, decryptor parses the ct as (C₀, C₁, . . . C_m), then

ﬁnds j such that β_j⊂ B(u), and computes

Q

e(C₀, d_u

d_u)

e(g^s, g^α(g^a

e(g^s^u, (g^a

h_i)^s^u)

h_i)^s)

0

i

i∈β_j

= e(g, g)^α·s= K.

Q

=

e(d⁰, C_j)

u₀

Finally, computes M = C · K⁻¹

.

Else, she deﬁnes the set I ⊂ {1, 2, . . . , `} such that I = {i : ρ(i) ∈ B(u)}. Let {ω_i∈

Z_p}_i∈Ibe a set of constants such that if {λ_i} are valid shares of any secret s according

P

to M then _i∈Iω_iλ_i= s. Note that from the relation _i∈Iω_iM_i= (1, 0, . . . , 0) where

M_iis the i-th row of the matrix M, she can determine these constants. She parses the

ct as (C₀, C₁, . . . C_`) and computes

Y

e( C_i^−ω, d ) · e(C₀, d_u

d⁻_u^ω) = K.

0

i

ρ(i)

u₀

0

i∈I

Then computes M = C · K⁻¹

.

Trapdoor(d_u, W_i= (w˜_i, . . . , w˜_i), param): Suppose that each w˜_i∈ {0, 1}^∗, j ∈ [k], is a

1

j

k

concatenation of set of keywords, for example “Diabetes||Age : 30”.

The user randomly chooses scalars r₁, . . . , r_k∈ Z_p, computes the trapdoor

ꢃ

ꢂ

˜

tds = {tds_0,j, tds_1,j, {tds_2,j,`

}

r_j

_j∈[k], tds₀, {tds_i}_i∈B(u), W_i

`∈B_u

ꢄ

ꢃ

r_j

s_u

ar_j

a

λ

s_u

= {g^αg^as^ug (g H(w˜_i)) , g , {h }_`∈B

}

_j∈[k], g , {h_i}_i∈B(u), W_i

.

˜

j

u

`

˜

where W_iis a short description of W_i. User then sends ({tds_0,j

}

_j∈[k], W_i) to the cloud

server, he/she publishes the rest of tds to the public domain. That means the trapdoor-

size is linear in the number of combinations of keywords user would like to search.

EncryptKW(KF, A⁰, param, ): Assume that access policy A⁰= β = (β₁∨ · · · ∨ β_m) and

0

KF = (kf₁∨ · · · ∨ kf_m), where each β_iis a set of attributes and kf_iis a concatenation

0

of set of keywords. Note that β_i= β_j, kf_i= kf_j, ∀i, j ∈ [m], i , j ∈ [m ].

$

The encryptor picks a scalar s ← Z_p, then computes

Y

C₀= g^s, C₁= (g^a

h_i)^s, . . . , C_m= (g^a

h_i)^s,

i∈β₁

i∈β_m

Y

a

s

˜

C₁= (g

h_i) , . . . , C_m= (g^a

h_i) .

˜

i∈β₁

i∈β_m

Next, he/she computes

X_i= e(g, g)^α·s· e(g, g^aH(kf_i))^λ·s, i = 1, . . . , m⁰,

then computes

˜

0

K₁= H(X₁, kf₁), . . . , K_m= H(X_m, kf_m).

A CIPHERTEXT-POLICY ATTRIBUTE-BASED SEARCHABLE ENCRYPTION SCHEME

241

Eventually, encryptor outputs

0

˜

0

ct = (C₀, . . . , C_m, C₁, . . . , C_m, K₁, . . . , K_m

)

along with a description of β.

Search(tds, ct⁰, param): The cloud server ﬁrst ﬁnds ` ∈ [m] such that β_`⊂ B(u), then

computes (X_j, Y_j), j = 1, . . . , k

Q

r_j

s_u

˜

e(C₀, tds_0,j

tds_i· tds_2,j,i

)

e(g^s, g^αg^as^ug^ar^jg^aλH(w˜_i)^λ

h_ih_i)

j

i∈β_`

X_j

=

Q

e(tds₀, C_`) · e(tds_1,j, C_`)

e(g^s^u, (g^a

h_i)^s) · e(g^r^j, (g^a

h_i) )

s

˜

i∈β_`

= e(g, g)^α·s· e(g, g^aH(w˜_i))^λ·s

,

j

˜

Y_j= H(X_j, w˜_i).

j

If there exists a pair (i, j), i ∈ [m⁰], j ∈ [k] such that K_i= Y_jthen the cloud server

outputs “yes”. Otherwise, the cloud server outputs “no”. Note that, the cloud server

doesn’t need to compute all pairs (X_j, Y_j), j = 1, . . . , k, as long as he/she ﬁnds a pair

(i, j), i ∈ [m⁰], j ∈ [k] such that K_i= Y_j, he/she outputs “yes” and stops.

Correctness: It is easy to verify that if there exists at least one pair w˜_i∈ W_iand kf_t∈ KF

j

such that w˜_i= kf_t, then

j

X_t= e(g, g)^α·s· e(g, g^aH(kf_t))^λ·s= e(g, g)^α·s· e(g, g^aH(w˜_i))^λ·s= X_j,

j

that means

˜

K_t= H(X_t, kf_t) = H(X_j, w˜_i) = Y_j.

j

Remark 1. As in [13] all sets β_imust be disjoint subsets to resist the simple attack,

i = 1, . . . , m. This leads to the fact that attributes in the system cannot be reused in the

access formula. To deal with this problem, they allow each attribute to have k_maxcopies of

itself as in [4, 7]. Note that the user’s secret key is still of constant-size.

4. SECURITY

In this section, we show that our scheme is secure in the model deﬁned in Subsection 2.1.3.

We ﬁrst refer the reader to the modiﬁed BDHE assumption deﬁned in [13], and then we

deﬁne a new modiﬁed BDHE assumption. We ﬁnally prove our scheme achieves the selective

semantic security under the new modiﬁed BDHE assumption, and achieves the insider and

outsider security under the modiﬁed BDHE assumption.

Deﬁnition 2. (New Modiﬁed-BDHE problem) Let (p, G, G_T, e) be a bilinear group system,

$

pick a, t, s, q, θ, r₁, . . . , r_θ← Z_p, a generator g ∈ G. Given

ꢄ

2q

q

s

a

a^qa^q+2

~

Y = g, g , g , . . . , g , g

, . . . , g^a, g^s(at+a), g^at, . . . , g^{a t}

,

ꢃ

q+2

2q

q+1

a^q+1

r₁

r_θ

g^{a t}, . . . , g^{a t}, g^ag^ar, . . . , g

g^ar, g , . . . , g

1

θ

^q+1s

$

it is hard to distinguish between T = e(g, g)^a

∈ G_Tand T ← G_T.

242

VAN ANH TRINH, VIET CUONG TRINH

Assume that A is an adversary that outputs b ∈ {0, 1} with advantage ꢀ in solving new

Modiﬁed-BDHE problem in G if

ꢅ

h

i

h

i

a^q+1

s

~

Pr A(Y , T = e(g, g)

) = 0 − Pr A(Y , T = R) = 0 ≥ ꢀ.

ꢅ

Deﬁnition 3. The new Modiﬁed-BDHE assumption is secure if no polytime adversary has

a non-negligible advantage in solving the new Modiﬁed-BDHE problem.

q+1

^q+1s

^q+1t

Intuitively, to compute e(g, g)^a

one should know one of the values g^a

or g^a

or

e(g, g)^sar, i ∈ [θ], but these elements are not provided in Y .

i

~

4.1. Selective semantic security

Theorem 1. Let β^∗be the challenge access policy, from β^∗we construct the corresponding

challenge LSSS matrix L’ of size `⁰× n⁰and map function ρ⁰. We next describe β^∗

=

β₁^∗∨ · · · ∨ β_m^∗where β_i^∗, i = 1, . . . , m are disjoint sets and then construct the corresponding

challenge LSSS matrix L^∗of size `^∗×n^∗and map function ρ^∗. If those LSSS matrices satisfy

`⁰, n⁰, `^∗, n^∗≤ q, and if θ ≥ k^∗· q^∗where k^∗and q^∗are maximum number of combinations

of keywords in a trapdoor and maximum number of trapdoor queries corresponding to β^∗

adversary can make, respectively, our scheme is selectively semantic secure under the new

Modiﬁed-BDHE assumption.

Compare to the proof in [13], here the simulator needs to answer additional corruption

q+1

trapdoor query. To answer this kind of query, the simulator uses the elements g^ag^a.r, . . . ,

1

q+1

r₁

r_θ

g^ag^a.r, g , . . . , g . Note that these elements only appear in new Modiﬁed-BDHE as-

sumption, not in Modiﬁed-BDHE assumption. The rest of the proof of this theorem is similar

to the one in [13].

θ

4.2. Keyword security

4.2.1. Insider security

Theorem 2. Assume that β^∗= β₁^∗∨ · · · ∨ β_m^∗is the challenge access policy and from β^∗

construct a corresponding challenge LSSS matrix L^∗of size `^∗× n^∗and map function ρ^∗.

If this LSSS matrix satisﬁes `^∗, n^∗≤ q, our scheme achieves insider security under the

Modiﬁed-BDHE assumption in the random oracle model.

Proof

In this proof we show that the simulator S who attacks Modiﬁed - BDHE assumption

can simulate an adversary A who attacks our scheme in the insider security game as deﬁned

in the Subsection 2.1.3. As a result, if A wins with non-negligible advantage then S also can

win with non-negligible advantage. More precisely:

At the setup phase, S is given an instance of Modiﬁed-BDHE assumption, and then receives

the challenge access policy β^∗= β₁^∗∨ · · · ∨ β_m^∗as well as KF₀^∗= (kf₀^∗_,1, . . . , kf₀^∗_,m₀) and

KF^∗₁= (kf₁^∗_,1, . . . , kf₁^∗_,m₀) from A. Note that β_i^∗, i = 1, . . . , m are disjoint sets. From

challenge access policy β^∗= β₁^∗∨ · · · ∨ β_m^∗, simulator builds LSSS matrix (M_`^∗_∗_×n_∗, ρ^∗)

A CIPHERTEXT-POLICY ATTRIBUTE-BASED SEARCHABLE ENCRYPTION SCHEME

243

such that both `^∗, n^∗≤ q. To program the parameters for the system, simulator picks

q

0

$

α⁰← Z_pand implicitly sets α = α⁰+a^q+1, then computes e(g, g)^α= e(g^a, g^a)e(g, g)^α.

The simulator ﬁnds sets of rows of matrix M^∗: I₁, . . . , I_mwhere {ρ(i), i ∈ I_j} = β_j^∗

(note that I_j, j = 1, . . . , m are disjoint sets since β_j^∗are disjoint sets). Now, β^∗can be

rewritten as (∧ρ(i))_i∈I∨ (∧ρ(i))_i∈I∨ · · · ∨ (∧ρ(i))_i∈I

.

m

1

2

˜

To program h₁, . . . , h_N, h₁, . . . , h_N, the simulator implicitly deﬁnes the vector

∗

→−

y = (t, ta, ta², . . . , ta^{n −1})^⊥∈ Zⁿ_p.

→−

∗

Let Λ = (λ₁, . . . , λ_`) = M · y be the vector shares, for j = 1, . . . , `^∗,

∗

P

λ_j= _i∈[n_∗_]M_j^∗_,itaⁱ⁻¹

.

P

∗

He/she next ﬁnds {ω_i}_1≤i≤`where for all j = 1, . . . , m,

ω_i· λ_i= t. Note that

i∈I_j

∗

we can ﬁnd {ω_i}_1≤i≤`since from the property of LSSS matrix, there exists {ω_i}_1≤i≤`

P

such that for all j = 1, . . . , m,

ω_i· M_i^∗= (1, 0, . . . , 0).

i∈I_j

∗

˜

For each h_j, h_j, 1 ≤ j ≤ N, where there exists an index i ∈ [` ] such that j = ρ (i)

$

(note that the function ρ^∗is injective), the simulator chooses z_j, z˜ ← Z_pand compute:

j

k

Note that the simulator knows matrix M^∗and g^tawhere k ∈ [n^∗] from the instance

of Modiﬁed-BDHE assumption.

P

_]M_i^∗_,kta^k

∗

k∈[n

h_j= g^z· g^ω

= g^z· g^{aω λ}; h_j= g · g^ω

= g^z˜· g^{aω λ}

.

∗

z˜_j

i

j

i

j

i i

˜

k∈[n

$

z_j

z˜_j

˜

Otherwise, the simulator chooses z_j, z˜ ← Z_pand computes h_j= g , h_j= g . We

j

˜

note that {h_j, h_j}_j=1,...,Nare distributed randomly due to choosing randomly z_j, z˜ .

j

q

To program g^λ, the simulator implicitly sets λ = −a^qand computes g^λ= (g^a)⁻¹

.

˜

Simulator also chooses hash functions H, H and in this proof simulator models H, H

as random oracles. At the end of this phase, the simulator gives following param to A

a

λ

α

˜

(g, g , g , e(g, g) , h₁, . . . , h_N, h₁, . . . , h_N, H, H).

Query phase 1. In this phase, the simulator needs to answer ﬁve types of query:

1. The hash query.

2. The corrupted trapdoor query (B_u, W_i= (w˜_i, . . . , w˜_i)) where W_idoesn’t “sa-

1

k

tisfy” KF^∗₀or KF₁^∗, that means there doesn’t exist any triple (i_j, b, b⁰) such that

w˜_i= kf_b^∗_,b₀

.

j

3. The corrupted trapdoor query (B_u, W_i) where W_i“satisﬁes” KF^∗₀or KF₁^∗, but

B_udoesn’t “satisfy” β^∗.

4. The partially corrupted trapdoor query (B_u, W_i) where W_i“satisﬁes” KF^∗₀or

KF^∗₁and B_u“satisﬁes” β^∗. Note that user only keeps ({tds_0,j

}

_j∈[k], W_i) secret

˜

and publishes the rest of tds to the public domain. That means A can know

({tds_1,j, {tds_2,j,`

}

`∈B_u

}_j∈[k], tds₀, {tds_i}_i∈B) for any (B_u, W_i= (w˜_i, . . . , w˜_i)).

u

1

k

244

VAN ANH TRINH, VIET CUONG TRINH

5. The partially corrupted secret key query B_ufor any B_u. The reason is that user

only keeps d_usecret.

0

˜

• Regarding the hash query: Simulator creates two lists L, L, at the beginning

˜

L, L are empty. For each hash query corresponding to w˜_iwhich doesn’t satisfy

KF^∗₀or KF^∗₁, the simulator ﬁrst checks whether w˜_ihas been queried before. If

$

not, he/she chooses y_i← Z_pand adds triple (w˜_i, g^yⁱ, y_i) ∈ ({0, 1}^∗, G, Z_p) into

L and returns g^yto A. Otherwise, he/she simply ﬁnds the triple (w˜_i, g , y_i)

y_i

i

and returns g^yto A. In the case w˜_i“satisﬁes” KF₀^∗or KF^∗₁, the simulator ﬁrst

i

$

checks whether w˜_ihas been queried before. If not, he/she chooses y_i← Z_pand

y_i

−a

adds triple (w˜_i, g^−a· g , y_i) into L and returns g · g^yto A. Otherwise, he/she

i

y_i

−a

simply ﬁnds the triple (w˜_i, g^−a· g , y_i) and returns g · g^yto A. For each hash

i

query corresponding to (K_i, kf_j) where K_i∈ G_T, kf_j∈ {0, 1}^∗, simulator ﬁrst

$

checks whether (K_i, kf_j) has been queried before. If not, he/she chooses y_i← Z_p

j

˜

and adds triple (K_i, kf_j, y_i) into L. Otherwise, he/she simply ﬁnds the triple

j

(K_i, kf_j, y_i) and returns y_ito A.

j

• Regarding the second type of query: A ﬁrst sends W_i= (w˜_i, . . . , w˜_i) and B(u) to

1

k

simulator with the requirement that W_idoesn’t satisfy KF^∗₀or KF₁^∗. To program

each tds_0,j, j ∈ [k], the simulator ﬁrst checks whether w˜_i, j ∈ [k] has been queried

j

$

before. If not, he/she chooses y_i← Z_pand adds triple (w˜_i, g^y, y_i) into L. In

i

j

both ways, simulator knows y_ifrom L, and H(w˜_i) = g^ysince W_idoesn’t

i

j

$

satisfy KF^∗₀or KF₁^∗. Next, simulator ﬁrst chooses s_u, r_j← Z_pthen computes

0

tds_0,j= g^αg^as^ug^ar^j(g^λ)^y^ij= g^αg^as^ug^ar^j(g^aH(w˜_i))^λ.

j

0

q+1

q

Note that g^α= g^α· g^a

· g^−a

= g^α· g^aλ, since g^λ= g^−a. Since simulator

knows s_u, r_j, j ∈ [k], he/she can easily computes the rest of the trapdoor for any

set B(u). Finally, simulator returns tds to A.

• Regarding the third type of query: A ﬁrst sends W_i= (w˜_i, . . . , w˜_i) and B(u) to

1

k

simulator with the requirement that B(u) doesn’t satisfy β^∗and W_i“satisﬁes”

→−

∗

n∗

∗

KF₀or KF₁. The simulator ﬁrst ﬁnds a vector x = (x₁, . . . , x_n) ∈ Z_psuch

→−

that x₁= −1 and for all i where ρ^∗(i) ∈ B(u) the product h x · M_i^∗i = 0. The

$

simulator continues to pick ζ ← Z_pand implictly deﬁne the value s_uas

q−n^∗+1

s_u= ζ + x₁a^q+ x₂a^q−1+ · · · + x_na

.

∗

The simulator computes

Y

0

q+1−i

x_i

0

d_u= g^αg^aζ

(g^a

)

= g^α· g^a·s; d_u= g^ζ

(g^a

)

= g^s^u.

u

0

i=2,...,n^∗

i=1,...,n^∗

For j ∈ B(u) such that there is no i ∈ [`^∗] satisfying ρ^∗(i) = j. The simulator

knows values z_jand computes h^s_j= (g ) . For j ∈ B(u) such that there is an

indice i ∈ [`^∗] satisfying ρ^∗(i) = j. The simulator computes

s_uz_j

u

P

∗

q

∗ a^q−n⁺¹)ω_i

_]M_i^∗_,kta^k

∗

h^s_j= (g ) · g^{(ζ+x a +···+x}

.

s_uz_j

1

u

n

k∈[n

A CIPHERTEXT-POLICY ATTRIBUTE-BASED SEARCHABLE ENCRYPTION SCHEME

245

→−

Note that the product h x ·M_i^∗i = 0 thus the simulator doesn’t need to know the

^q+1t

unknown term of form g^a

to compute h^s_j^u, all other terms he/she knows from

s_u

j

the assumption. Simulator simply sets g^sand {h }_j∈Bas tds₀and {tds_i}_i∈B

,

u

respectively. To program {tds_0,j, tds_1,j, {tds_2,j,`

}

}_j∈[k], the simulator consi-

`∈B_u

ders two cases:

1. w˜_i“satisﬁes” KF^∗₀or KF₁^∗, that means there exists at least a triple (i_j, b, b⁰)

j

such that w˜_i= kf_b^∗_,b₀. Simulator checks whether w˜ has been queried

i_j

j

$

before. If not, he/she chooses y_i← Z_pand adds triple (w˜_i, g^−ag^y^ij, y_i)

j

into L. In both ways, simulator knows y_ifrom L, and H(w˜_i) = g^−ag^yⁱ

.

j

$

Next, simulator chooses r_j← Z_pthen computes

ar_j−a^q

y_ij

tds_0,j= g^αg^as^ug (g

)

= g^αg^as^ug^ar^j(g^aH(w˜_i))^λ.

j

Note that λ = −a^q. With known r_j, simulator can easily compute tds_1,j

,

{tds_2,j,`

}

`∈B_u

.

2. w˜_idoesn’t “satisfy” KF₀^∗or KF₁^∗. Simulator checks whether w˜_ihas been

j

$

queried before. If not, he/she chooses y_i← Z_pand adds triple (w˜_i, g^y, y_i)

i

j

into L. In both ways, simulator knows y_ifrom L, and H(w˜_i) = g^y. Next,

simulator picks ζ_j← Z_pand implicitly deﬁnes the value r_jas

i

j

$

q−n^∗+1

r_j= ζ_j+ x₁a^q+ x₂a^q−1+ · · · + x_na

,

∗

r_j

then similarly computes g^αg^ar, g , {h_`

}

as above (note that r_jnow

j

˜

`∈B_u

−r_j

plays the role as s_u). He/she then sets g^−r, {h_`

}

as tds_1,j, {tds_2,j,`}

j

˜

`∈B_u

respectively, and computes

α⁰−a^q

−ar_j

y_ij

tds_0,j= g^αg^as^ug^−αg^−arg (g

)

= g^αg^as^ug

(g^aH(w˜_i))^λ.

j

0

q+1

q

y_ij

Note that g^α= g^αg^a

and (g^aH(w˜_i))^λ= g^−a(g^−a

)

.

j

Finally, simulator returns tds to A.

• Regarding the fourth and ﬁfth types of query: It is straightforward since the

unknown value g^αonly appears in the tds_0,jand d_u, therefore simulator can

0

$

simply choose s_u, {r_j}_j∈[k]← Z_pand then computes tds, or choose s_u, ← Z_pand

then computes d_u.

Challenge:

The simulator picks a random bit b, computes C₀^∗

=

g^sand

∗

˜

(C₁, . . . , C_m) = I, (C₁, . . . , C_m) = J, where

ꢄ



ꢃ

P

sz_ρ

∗

sz_ρ

m

∗

(i)

I = g^s(a+at)

g

⁽ⁱ⁾, . . . , g^s(a+at)g

i∈I

1





Y

s

a



=

g , (g

h_i)^s, . . . , (g^a

h_i)^s

,

i∈β₁^∗

i∈β_m^∗

246

VAN ANH TRINH, VIET CUONG TRINH

ꢄ



ꢃ

P

sz˜_ρ∗

m

J = g^s(a+at)

g

⁽ⁱ⁾, . . . , g^s(a+at)g

i∈I

(i)

i∈I

1





Y

a

s

a

s

˜



=

(g

h_i) , . . . , (g

h_i)

.

i∈β₁^∗

i∈β_m^∗

To computes {K_i^∗}_i∈[m₀_], simulator ﬁrst checks whether kf_b^∗_,ihas been queried before.

$

If not, he/she chooses y_i← Z_pand adds triple (kf_b^∗_,i, g^−ag^yⁱ, y_i) into L. Otherwise,

he/she ﬁnds (kf_b^∗_,i, g^−ag^yⁱ, y_i) from L. In both ways, simulator knows y_ifrom L, and

H(kf_b^∗_,i) = g^−ag^yⁱ. He/she computes

α⁰

X_i^∗= T · e(g^s, g ) · e(g^s, (g^λ)^yⁱ) = T · e(g^s, g ) · e(g^λ, g^aH(kf_b^∗_,i))^s

∗

˜

then computes K_i= H(X_i, kf_b,i). Finally, he/she outputs

ct^0∗= (C₀^∗, {C_i^∗}_i∈[m], {C_i}_i∈[m], {K_i^∗}_i∈[m₀_]).

∗

˜

^q+1s

Note that if T = e(g, g)^a

then ct^0∗is in valid form.

Query phase 2. Similar to phase 1.

^q+1s

Guess: A gives his guess b⁰to S, S will output its guess 0 corresponding to T = e(g, g)^a

q+1

if b⁰= b; otherwise, S outputs its guess 1 corresponding to T is a random element.

When T = e(g, g)^{a s}, S gives a perfect simulation so

h

i

1

a^q+1

~

Pr S(Y , T = e(g, g)

^s) = 0 = + Adv^I_A^S

.

2

When T is a random element {K_i^∗}_i∈[m₀_]are completely hidden from the A, so

1

~

Pr[S(Y , T = R) = 0] = . As a result, S is able to play the Modiﬁed - BDHE game

2

with non-negligible advantage (equal to Adv^I_A^S) or S is able to break the security of

Modiﬁed-BDHE assumption.

ꢀ

Outsider Security. Outsider security is similar to the case of Insider Security, due to the

space limitations we omit it here.

5. COMPARISON

Regarding PEKS scheme supporting both expressive searching predicate and multi-writer

/multi-reader, to our knowledge [6, 8, 9, 11, 14] are the best schemes to date. In these

schemes, the authors in [9] proposed a PEKS schemes scheme with constant size of ciphertext,

however their scheme only supports limited AND-gates access policy. The authors in [6, 8,

11, 14] managed to transform from existing KP-ABE or CP-ABE schemes to PEKS schemes,

these schemes enjoy some interesting properties such as fast keyword search or outsourcing

decryption or partially trapdoor security. Other properties such as ﬁned-grain access policy,

public key-size, ciphertext-size are similar to ones in our scheme, but our scheme has constant

A CIPHERTEXT-POLICY ATTRIBUTE-BASED SEARCHABLE ENCRYPTION SCHEME

247

size of secret key while they haven’t, moreover our model is diﬀerent to their model. We give

in Fig 1 the comparison between our model and the model in [6, 8, 11, 14]. We can easily

see from Fig 1 that there is no TTG in our model, user relies solely on his/her secret key to

generate a trapdoor. In contrast, in their model, TTG takes charge of generating trapdoors

and therefore should be always online. Compare to their model, our model has two following

advantages:

• There is no TTG in our model, we therefore can save the system resource and the

communication overhead between user and TTG.

• In our model, user uses his/her secret key to generate trapdoors, cloud server relies on

such trapdoors to search corresponding ciphertexts, user therefore is able to decrypt all

the resulted ciphertexts. In contrast, in their model, TTG takes charge of generating

trapdoors and user’s secret key is not involved in this process, this leads to the fact that

the resulted ciphertexts may contain ciphertexts for which the user cannot decrypt. We

argue that our model is more useful in practice since it is waste time and communication

overhead if user receives the ciphertexts for which he/she cannot decrypt.

Encrypt documents

and corresponding

keywords

Data

owner

Encrypt documents

and corresponding

keywords

Cloud

server

Data

owner

Cloud

server

3.Trapdoor

1.Trapdoor

4.Resulted

ciphertexts

2.Resulted

ciphertexts

Trusted

Trapdoor

Generator

User

1.Trapdoor request

2.Trapdoor

Figure 1. Our model on the left and their model on the right

We also note that the scheme in [15] can deal with well the problem of trapdoor secu-

rity, and moreover this scheme is very eﬃcient in term of both communication and com-

putation. However, this scheme is in the diﬀerent type to our scheme since our scheme

supports expressive searching while the scheme in [15] supports equality queries. Consi-

der the example in [6], W = (w₁, w₂, w₃) where w₁= “Diabetes⁰⁰, w₂= “Age : 30⁰⁰and

w₃= “Weight : 150 − 200⁰⁰, user in our scheme can search for ciphertexts which has key-

word either “Diabetes⁰⁰or “Weight : 150 − 200⁰⁰. While the user in the scheme in [15] must

specify the keyword search is ”Diabetes” or “Weight : 150 − 200⁰⁰and then receives only

the ciphertext corresponding to the keyword search. For example, if the keyword search is

“Diabetes⁰⁰, user only receives the ciphertext corresponding to “Diabetes⁰⁰. This is similar

to the diﬀerence between traditional public key encryption and attribute-based encryption.

248

VAN ANH TRINH, VIET CUONG TRINH

6. CONCLUSION

In this paper, we propose a CP-ABSE scheme which supports both expressive searching

predicate and multi-writer/multi-readers. To our knowledge, our scheme has some interesting

properties such as constant-size of secret key and in the non-interactive model. Our scheme

will become very eﬃcient when the number of combinations of keywords to which a user

would like to search is small. Our scheme is therefore very suitable for a large class of

applications in practice for which the aforementioned case falls into.

ACKNOWLEDGMENTS

This research is funded by Vietnam National Foundation for Science and Technology

Development (NAFOSTED) under grant number 102.01-2018.301.

REFERENCES

[1] M. R. Asghar, G. Russello, B. Crispo, and M. Ion, “Supporting complex queries and access

policies for multi-user encrypted databases,” in Proceeding CCSW ’13 Proceedings of the

2013 ACM workshop on Cloud computing security workshop, Berlin, Germany, November

4, 2013, pp 77–88. Doi 10.1145/2517488.2517492

[2] D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano, “Public key encryption with keyword

search,” Advances in Cryptology - EUROCRYPT 2004 International Conference on the

Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6,

2004, pp 506–522.

[3] D. Cash, S. Jarecki, C. S. Jutla, H. Krawczyk, M.-C. Rosu, and M. Steiner, “Highly-scalable

searchable symmetric encryption with support for Boolean queries”, in Advances in Cryptology

CRYPTO 2013 33rd Annual Cryptology Conference, Proceedings, Part I, Santa Barbara,

CA, USA, August 18-22, 2013.

[4] S. Canard and V. C. Trinh, “Constant-size ciphertext attribute-based encryption from multi-

channel broadcast encryption,” Information Systems Security. 12th International Confe-

rence, ICISS 2016, Proceedings, Jaipur, India, December 16-20, 2016.

[5] H. Cui, R. Deng, J. Liu, and Y. Li, “Attribute-based encryption with expressive and authorized

keyword search,” Information Security and Privacy. 22nd Australasian Conference, ACISP

2017, Proceedings, Auckland, New Zealand, July 35, 2017, Part I, pp. 106–126.

[6] H. Cui, Z. Wan, R. Deng, G. Wang, and Y. Li, “Eﬃcient and expressive keyword search over

encrypted data in the cloud,” IEEE Transactions on Dependable and Secure Computing,

vol. 15, no. 3, pp. 409–422, 2018. Doi 10.1109/TDSC.2016.2599883

[7] S. Hohenberger and B. Waters, “Attribute-based encryption with fast decryption,” Public-

Key Cryptography PKC 2013. 16th International Conference on Practice and Theory

in Public-Key Cryptography, Proceedings, Nara, Japan, February 26 March 1, 2013, pp.

162–179.

[8] Jianting Ning, Zhenfu Cao, Xiaolei Dong, Kaitai Liang, Hui Ma, Lifei Wei, “Auditable σ-

Time Outsourced Attribute-Based Encryption for Access Control in Cloud Computing,” IEEE

Transactions on Information Forensics and Security, vol. 13, no. 1, pp. 94–105, 2018. Doi

10.1109/TIFS.2017.2738601

A CIPHERTEXT-POLICY ATTRIBUTE-BASED SEARCHABLE ENCRYPTION SCHEME

249

[9] Jinguang Han, Ye Yang, Joseph K. Liu, Jiguo Li,Kaitai Liang,Jian Shen, “Expressive attribute-

based keyword search with constant-size ciphertext,” In Soft Computing Journal, vol. 22, no.

15, pp 5163-5177, August 2018.

[10] A. Kiayias, O. Oksuz, A. Russell, Q. Tang, and B. Wang, “Eﬃcient encrypted keyword search for

multi-user data sharing,” Computer Security ESORICS 2016. 21st European Symposium

on Research in Computer Security, Proceedings, Heraklion, Greece, September 26-30, 2016,

Part I, pp 173–195.

[11] J. Lai, X. Zhou, R. H. Deng, Y. Li, and K. Chen, “Expressive search on encrypted data,” ASIA

CCS ’13 Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and

Communications Security, Hangzhou, China, May 8-10, 2013, pp 243–251.

[12] Z. Lv, C. Hong, M. Zhang, and D. Feng, “Expressive and secure searchable encryption in the

public key setting,” Information Security 17th International Conference, ISC 2014, Pro-

ceedings, Hong Kong, China, October 12-14, 2014, pp 364–376.

[13] Q. M. Malluhi, A. Shikfa, and V. C. Trinh, “A ciphertext-policy attribute-based encryption

scheme with optimized ciphertext size and fast decryption,” Proceeding ASIA CCS ’17 Procee-

dings of the 2017 ACM on Asia Conference on Computer and Communications Security,

Abu Dhabi, United Arab Emirates, April 02 - 06, 2017, pp. 230–240.

[14] R. Meng, Y. Zhou, J. Ning, K. Liang, J. Han, and W. Susilo, “An eﬃcient key-policy attribute-

based searchable encryption in prime-order groups,” Provable Security 11th International

Conference, ProvSec 2017, Proceedings, Xi’an, China, October 23-25, 2017, pp. 39–56.

[15] Qiong Huang and Hongbo Li, “An eﬃcient public-key searchable encryption scheme secure

against inside keyword guessing attacks,” Information Sciences Journal, vol. 403–404, pp.

1–14, September 2017. Doi.org/10.1016/j.ins.2017.03.038

[16] D. X. Song, D. Wagner, and A. Perrig, “Practical techniques for searches on encrypted data,”

Proceeding 2000 IEEE Symposium on Security and Privacy, Berkeley, CA, USA, May 14–17,

2000, pp. 44–55. Doi 10.1109/SECPRI.2000.848445

[17] S. Sun, J. K. Liu, A. Sakzad, R. Steinfeld, and T. H. Yuen, “An eﬃcient non-interactive multi-

client searchable encryption with support for boolean queries,” Computer Security ESORICS

2016. 21st European Symposium on Research in Computer Security, Proceedings, Part I,

Heraklion, Greece, September 26–30, 2016, pp. 154–172.

[18] Y. Wang, J. Wang, S. Sun, J. Liu, W. Susilo, and X. Chen, “Towards multi-user searchable en-

cryption supporting boolean query and fast decryption,” Provable Security 11th International

Conference, ProvSec 2017, Proceedings, Xi’an, China, October 23–25, 2017, pp. 24–38.

[19] Y. Yang, H. Lu, and J. Weng, “Multi-user private keyword search for cloud computing,”

2011 IEEE Third International Conference on Cloud Computing Technology and Science,

Athens, Greece, 29 Nov.- Dec. 01, 2011, pp. 264–271. Doi 10.1109/CloudCom.2011.43

Received on March 05, 2019

Revised on April 18, 2019