# Secure and Efficient Conjunctive Keyword Search Scheme without Secure Channel.

1. IntroductionCloud storage is a new concept that extends and develops in the concept of cloud computing [1], and it is a new network storage technology [2]. We know that the direct control power of outsourced data is deprived from the data owners (DO). So, the data should be encrypted before stored to the cloud storage. Whatever, it may severely hinder several functionalities that users are accustomed to receiving from the cloud storage. For instance, it is impossible to search the encrypted data. One solution for this problem is the use of searchable encryption schemes.

There are two categories of searchable encryption schemes: symmetric encryption with keyword search and public key encryption with keyword search (PEKS). Song et al. [3] proposed the first symmetric encryption scheme with keyword search. Boneh et al. [4] proposed the first PEKS. For a network with too many users, PEKS is better than symmetric encryption scheme with keyword search.

In order to reduce the search scope and improve the query performance, mulit-keywords search capability is very important. Therefore, Golle et al. [5] proposed a conjunctive field keyword search scheme, which assumed that n keyword fields are associated with each document. Zhang et al. [6] proposed a conjunctive-subset keyword search algorithm that enables users to list keywords in any order. Lai et al. [7] proposed a PEKS based on the key-policy attribute-based encryption scheme, which is very efficient and has a strong expression.

The above schemes require a secure channel to transfer the trapdoor between the data users (DU) and the cloud service provider (CSP). And heavy computational and communication loads, such as a Secure Sockets Layer (SSL) between the DU and the CSP, are typically required to establish a secure channel. Aiming at solving this problem, Baek et al. [8] considered removing the secure channel and proposed a secure channel-free PEKS (SCF-PEKS). In this scheme, the CSP maintains its public key and private key. The DO generates the keyword ciphertexts based on the public key of the CSP. The CSP having the corresponding private key can run the Test algorithm.

Byun et al. [9] indicated that the scheme proposed by Baek [8] may be attacked by off-line keyword guessing attacks. It is because that the keyword space is much smaller than the password space. Then, Rhee et al. [10] constructed a new secure SCF-PEKS scheme against keyword guessing attacks. But the security proof of the scheme is not in the standard model. Yang et al. [11] proposed a scheme that supports the conjunctive keyword search and resists off-line keyword guessing attacks. However, this scheme uses a significantly complex assumption. Liang et al. [12] proposed a searchable attribute-based proxy re-encryption system, which is able to achieve fine-grained access control. At the same time, the encrypted data is also searchable.

Contribution. Based on the above analyses, an efficient conjunctive keyword search scheme without a secure channel is proposed for the cloud storage environment, which is called searchable encryption with conjunctive keyword search (SE-CKS). We propose an efficient mechanism for removing the secure channel and resisting off-line keyword guessing attacks. The DU is connected to the CSP via an unsecure communication channel, such as a GPRS network. The basic concept is for the server to maintain its private and public key pairs. By referencing the access structure [13] of ciphertext policy attribute-based encryption (CP-ABE) [14], the DO constructs the search policies using the keywords of the data files, generates keyword ciphertexts through the public keys of the server and the receiver, and then uploads the keyword ciphertexts to the CSP. The keyword set L is used to search the data files, and the AA then generates a trapdoor for the DU. The DU can then send the trapdoor to retrieve data associated with the keyword list and send it via a public channel. After receiving the trapdoor, the CSP can test whether the provided ciphertexts match the trapdoor using its private key. Our scheme is proved adaptively secure based on the decisional bilinear Diffie-Hellman (DBDH) assumption in the standard model. The results of theoretical analysis and experimental simulation show that the proposed scheme has advantages in security, storage overhead and efficiency, and it is more suitable for practical applications.

The remainder of this paper is organized as follows: In Section 2, we describe the formal definition and security model. In Section 3, we propose the concrete SE-CKS scheme and analyse the security of the proposed generic construction. In Section 4, we describe the performance comparison. In Section 5, we present the conclusions.

2. Formal Definition and Security Model

2.1 Formal Definition of SE-CKS

The SE-CKS scheme contains six polynomial time algorithms: GlobalSetup, AASetup, [KeyGen.sub.CSP], EncIndex, Trapdoor and Test. These algorithms are presented as follows:

GlobalSetup(1 ([lambda])) [right arrow] GP : The algorithm is executed by the trusted authority center (AC) and it takes the security parameter [lambda] as input. It returns the global parameter GP.

AASetup(GP,U) [right arrow] (PK,MSK): It takes GP and keyword set U as inputs. It returns the AA's public key PK and master private key MSK, respectively.

[KeyGen.sub.CSP] (GP) [right arrow] ([pk.sub.CSP], [sk.sub.CSP]): It takes GP as input and returns the CSP's public key [pk.sub.CSP] and private key [sk.sub.CSP], respectively.

EncIndex(GP, PK, [pk.sub.CSP],W) [right arrow] CT : It takes GP, PK, [pk.sub.CSP], the search policies W based on keywords as inputs. It returns the ciphertext CT.

Trapdoor(GP, [pk.sub.CSP], MSK, L) [right arrow] [TD.sub.L]: It takes GP, [pk.sub.CSP], MSK, the keyword list L as inputs and outputs a trapdoor [TD.sub.L].

Test(GP, [sk.sub.CSP], CT, [TD.sub.L]) [right arrow] (0,1) : It takes GP. [sk.sub.CSP], CT, [TD.sub.L] as inputs and determines whether L satisfies W. If L satisfies W, it returns 1; Otherwise, it returns 0.

2.2 Security Model of SE-CKS

Definition 1. Consistency [15]. Assume that the adversary A wants to cause a failure in consistency. Consistency is formally defined as follows:

Setup: The simulator B executes GlobalSetup(1 ([lambda])), AASetup(GP, U), [KeyGen.sub.CSP] (GP).

Phase 1: A submits a keyword list L and a search policies W based on keywords, where L [not equal to] W. Then, EncIndex(GP, PK, [pk.sub.CSP], W) and Trapdoor(GP, [pk.sub.CSP], MSK, L) are executed.

Challenge: Test (GP, [sk.sub.CSP], CT, [TD.sub.L]) is executed, where L |[not equal to] W.

Guess: If Test (GP, [sk.sub.CSP], CT, [TD.sub.L]) [right arrow] 1, then the adversary A wins the game.

The advantage of A is defined as:

[Adv.sup.cons.sub.A] ([lambda]) := Pr[Test(GP, [sk.sub.CSP], CT, [TD.sub.L]) [right arrow] 1] (1)

If the advantage of all polynomial time adversaries is negligible in above game, then the SE-CKS scheme is computationally consistent.

Compared with traditional conjunctive keyword search, our scheme is based on CP-ABE. Therefore, the security model must be redefined. According to the definition of the CP-ABE security model and the characteristics of our scheme, this paper presents a new security game model for our conjunctive keyword search scheme. Note that there are two types of adversaries in this scheme, namely CSP and the outside attacker (including the receiver). Informally, indistinguishability of secure channel free against chosen keyword attack (IND-CF-CKA) guarantees the adversary, which has not obtained the trapdoors for given keywords, cannot distinguish the keywords. When the adversary A is the CSP, A can obtain the CSP's private key. When the adversary A is the outside attacker, the adversary A cannot obtain the CSP's private key. Therefore, the CSP has a stronger attack capability than the outside attacker. And this paper only proves that the CSP cannot attack the SE-CKS scheme. The definition of IND-CF-CKA is formalized according to a security game between the adversary A and the simulator B.

Definition 2. IND-CF-CKA. We consider the following game between A and B.

Setup: The simulator B executes GlobalSetup(1 ([lambda])), AASetup(GP,U), [KeyGen.sub.CSP] (GP) to obtain the global parameter GP, AA's public key PK and master private key MSK, CSP's public key [pk.sub.csp] and private key [sk.sub.CSP]. Then, B provides ([pk.sub.CSP], [sk.sub.CSP]) and PK to A.

Phase 1: The adversary A submits a keyword list L ina trapdoor query Trapdoor(GP, [pk.sub.CSP], MSK, L), where L |[not equal to] [W.sub.0] ^ L |[not equal to] [W.sub.1]. The simulator B answers with a trapdoor for the keyword list L. Note that these queries can be adaptively repeated.

Challenge: The simulator B chooses w [member of]{0,1} and executes EncIndex(GP, PK, [pk.sub.CSP], [W.sub.w]). The simulator B provides the ciphertext CT to A.

Phase 2: It is the same as Phase 1. A sends L' to the simulator B for a query. The simulator B answers with a trapdoor for the keyword list. Notice that L' |[not equal to] [W.sub.0] ^ L' |[not equal to] [W.sub.1].

Guess: A outputs the guess w' [member of]{0,1}. A wins if w' = w.

The advantage of A is defined as:

Ad[v.sub.A] ([lambda]):=|Pr(w ' = w) -1/2| (2)

The SE-CKS scheme is said to be IND-CF-CKA secure if the advantage of all polynomial time adversaries is negligible in above game

Definition 3. Off-Line Keyword Guessing Attacks on SE-CKS.

Because a trapdoor is sent without a secure channel, an outside adversary is capable of capturing the trapdoor and performing off-line keyword guessing attacks. The attacker may reveal the encrypted keyword list that is used by the receiver to search for a data. Similarly, an inside adversary (malicious server) can perform the attack to reveal the keyword in the trapdoor and execute the Test algorithm to determine the ciphertext that contains the keyword list. However, the outside adversary is unable to distinguish ciphertexts from encrypting a specific keyword list because the Test phase requires the server's private key.

A SE-CKS scheme that is secure against keyword guessing attacks, where the attacker is the server, cannot be constructed [16]. Therefore, in this work, we do not consider the keyword guessing attacks of an inside adversary.

3. SE-CKS Scheme

3.1 Search Policy

The access policy [13] is as follows: Assume that the set of attributes in universe U = {[att.sub.1], [att.sub.2],...,[att.sub.n]} contains n attributes. Each attribute [att.sub.i] can take two values: 1 and 0. Assume that L = [[L.sub.1], [L.sub.2], ... [L.sub.n]] is a set of attributes for a user, which is called the attribute list. AA generates a user's secret key through L = [[L.sub.1], [L.sub.2], *** [L.sub.n]]. Assume that W = [ [W.sub.1], [W.sub.2], ***, [W.sub.n]] is an access policy for a ciphertext. Formally, the attribute list L = [[L.sub.1], [L.sub.2], ***, [L.sub.n]] for a user and the access policy W = [[W.sub.1], [W.sub.2], ***, [W.sub.n] ] for a ciphertext are given. For all i (1 [less than or equal to] i [less than or equal to] n), if [L.sub.i] = [W.sub.i] or [W.sub.i] = *, L satisfies W, which is represented by the notation L |= W. Otherwise, L does not satisfy W, which is represented by the notation L |[not equal to] W. The wildcard "*" represents "do not care". For instance, we can let W = [[W.sub.1], [W.sub.2], [W.sub.n]] = [0,*,1,*,1,0], where n = 6. If a user has L = [0,1,1,0,1,0], he can obtain a secret key associated with L = [0,1,1,0,1,0] and decrypt the ciphertext encrypted with W = [0,*,1,*,1,0]. But the user with L = [0,1,1,0,1,1] cannot decrypt the ciphertext encrypted with W = [0,*,1,*,1,0].

Compared with the access policy [13], we let U = {[kw.sub.1], [kw.sub.2], ***, [kw.sub.n]} represent the set of keywords of data file that replace the attributes. W is the search policy based on the keywords. For all i (1 [less than or equal to] i [less than or equal to] n), each keyword [kw.sub.i] can take two or more values. More formally, assume that [mathematical expression not reproducible] is the set of all possible values for [kw.sup.i], where [n.sub.i] is the number of the possible values for [kw.sup.i], specifically [n.sub.i] =| [S.sub.i]|. When the encryptor specifies a wildcard * for [W.sub.i], this action corresponds to specify [W.sub.i] =[S.sub.i]. We achieve keyword privacy by hiding the subset [W.sub.i] for each keyword [kw.sup.i] that is specified in the search policy of the AND-gate of all keywords.

3.2 Concrete Construction

The six polynomial time algorithms of SE-CKS are as follows:

GlobalSetup(1 ([lambda])) [right arrow] GP : The AC generates the tuple G = [p,q,N = pq,G,[G.sub.T],e] with G x G [right arrow] [G.sub.T], where G and [G.sub.T] are cyclic groups of order N = pq . [g.sub.p] and [g.sub.q] are the generators of [G.sub.p] and [G.sub.q], respectively. The global parameter is GP = [p,r, [g.sub.p],[g.sub.q], N = pq,G,[G.sub.T],e].

AASetup(GP,U) [right arrow] (PK,MSK): Randomly choose [alpha] [member of] [Z*.sub.N], a', [g.sub.2] [member of] [G.sub.p], [R.sub.0], [R.sub.1] [member of] [G.sub.q] and compute [g.sub.1] =[g.sup.[alpha].sub.p]. For each keyword [kw.sub.i] [member of]U, where 1 [less than or equal to] i [less than or equal to] n, AA chooses random values [mathematical expression not reproducible] and [mathematical expression not reproducible]. AA's master private key is MSK = [[mathematical expression not reproducible]]. AA's public key is PK = [Y = e([g.sub.1], [g.sub.2]), [A.sub.0] = [g.sub.p] * [R.sub.0], A' = a' [R.sub.1], [mathematical expression not reproducible]].

[KeyGen.sub.CSP] (GP) [right arrow] ([pk.sub.CSP], [sk.sub.CSP]): Uniformly and randomly choose [beta] [member of] [Z*.sub.N] and compute B = [g.sup.[beta].sub. p]. The CSP's public key is [pk.sub.CSP] = [B]. The CSP's private key is [sk.sub.CSP] = [[beta]].

EncIndex(GP, PK, [pk.sub.CSP],W) [right arrow] CT : Choose a search policy based on the keywords W = [[W.sub.1], ***, [W.sub.n]]. The DO selects random values s [member of] [Z*.sub.N] and [R'.sub.0], [R'.sub.1] [member of] [G.sub.q], then the ciphertext is CT = [C = [Y.sub.s], [C.sub.0] = [A.sup.s.sub.0] * [B.sub.s] * [R'.sub.0], [C.sub.1] = [mathematical expression not reproducible] * [R'.sub.1]].

Trapdoor(GP,[pk.sub.CSP],MSK,L) [right arrow] [TD.sub.L] : The DU uses L = [[L.sub.1], ***, [L.sub.n]] = [mathematical expression not reproducible] to obtain the corresponding secret key for searching, which is regarded as the searching trapdoor. The AA selects a value r [member of] [Z*.sub.N]. The searching trapdoor is: [mathematical expression not reproducible].

Test (GP, [sk.sub.CSP], CT,[TD.sub.L]) [right arrow] (0,1) : The DU sends [TD.sub.L] to the CSP for implementing the search request. Then, the CSP tests whether e([D.sub.0], [C.sub.1]) * [C.sup.[beta]+1] = e([D.sub.1], [C.sub.0]) is true. If it is true, then return 1; Otherwise, return 0.

Note that in Trapdoor algorithm, this paper assumes [for all]L, L'(L [not equal to] L'), [mathematical expression not reproducible]. Emura et al. [17] gave the result that this assumption holds with overwhelming probability [P.sub.asuump] (> 1 - [N.sup.2.sub.0] ()/N), where [N.sub.0] =|[[S.sub.i]|.sup.n].

Correctness. Let the ciphertext be CT = [C, [C.sub.0], [C.sub.1]], which is associated with the search policy W = [[W.sub.1],[W.sub.2],***,[W.sub.n]] based on keywords. The trapdoor is [TD.sub.L] = [ [D.sub.0], [D.sub.1]]. This process produces the equation:

[mathematical expression not reproducible] (3)

That is e([D.sub.0], [C.sub.1]) * [C.sup.[beta]+1] =e([D.sub.1], [C.sub.0])

3.3 Security Analysis

Theorem 1. SE-CKS is computationally consistent.

Proof: Assume that an adversary A can attack the computational consistency of SE-CKS. Let (W, L) denote the search policy based on keywords and the keyword list for the DU. At the same time, assume that L does not satisfy W. The the consistency game is as follows:

Select random values s [member of] [Z*.sub.N] and [R'.sub.0], [R'.sub.1] [member of] [G.sub.q]. Compute C = [Y.sup.s], [C.sub.0]=[A.sup.s.sub.0] * [B.sup.s] * [R'.sub.0],

[mathematical expression not reproducible], [D.sup.0] = [g.sup.r.sub.p] * [B.sup.r], [[mathematical expression not reproducible], where r [member of] [Z*.sub.N].

If L does not satisfy W and e([D.sup.0], [C.sub.1]) * [C.sup.[beta]+1] = e([D.sub.1], [C.sub.0]) holds, then A wins the game. Assume that [L.sub.k] [??] [W.sub.k], then [mathematical expression not reproducible] in [L.sub.k] and [mathematical expression not reproducible] in [W.sub.k].

[mathematical expression not reproducible] (4)

Because the DU does not know the secret value [z.sub.1] and [z.sub.2] in [Z*.sub.N]. Hence, Pr[[z.sub.1] = [z.sub.2]] = 1 / (N - 1), where N - 1 is the total number of all elements in [Z*.sub.N]. When L [not equal to] W and Test (GP,[sk.sub.CSP],CT,[TD.sub.L]) [right arrow] 1, the advantage of the adversary A winning the above game is:

[Adv.sup.cons.sub.A] ([lambda]) = Pr[[z.sub.1] = [z.sub.2]] [less than or equal to] 1/( N -1) (5)

Theorem 2. Ifthe (1 - [N.sup.2.sub.0]/N)([epsilon]/16(n +1)0) DBDH assumption holds, then SE-CKS is (t,[theta],[epsilon])-IND-CF-CKA secure in the standard model, where [N.sub.0] = [|[S.sub.i]|.sup.n] is the number of all possible expressed search policies.

Proof: If an (t,[theta],[epsilon]) adversary A can break through SE-CKS, then a simulator B can be constructed to solve the DBDH problem with the advantage no less than (1 - [N.sup.2.sub.0]/N)([epsilon]/16(n + 1)0). The DBDH challenger C selects a,b,c [member of] [Z*.sub.N], v [member of] {0,1}, [g.sub.p], [g.sub.q], where <[g.sub.p]> = [G.sub.P], <[g.sub.q]> = [G.sub.q]. If v = 0, then Z = e[([g.sub.p],[g.sub.p]).sup.abc]; if v = 1, then Z = e[([g.sub.p],[g.sub.p]).sup.z]. The security game based on the tuple [[g.sub.p], [g.sub.r], [g.sup.a.sub.p], [g.sup.b.sub.p], [g.sup.c.sub.p], Z ] is simulated between the adversary A and the simulator B .

Setup: B computes u = 4[theta] and randomly chooses an value k [member of]{0,...,n}. Then B chooses [{[X.sub.i,t]}.sub.1[less than or equal to]i[less than or equal to]n,1[less than or equal to]t[less than or equal to]n], where [x.sub.i,t] [member of] (0,...,u - 1), x'[member of](0,...,u - 1). Additionally, B chooses y' [member of] [Z*.sub.N] and [{[Y.sub.i,t]}.sub.1[less than or equal to]i[less than or equal to]n,1[less than or equal to]t[less than or equal to]n] where [y.sub.i,t] [member of] [Z*.sub.N].

Define functions [mathematical expression not reproducible] (mod N) and [mathematical expression not reproducible] (mod N) for the attribute list L. Then, if [mathematical expression not reproducible] (mod u), we define a binary function B(L) = 0; Otherwise, B(L) = 1.

B assigns [g.sub.1] = [g.sup.a.sub.p], [g.sub.2] = [g.sup.b.sub.p] and chooses r' [member of] [Z*.sub.N], [r.sub.i,t] [member of] [Z*.sub.N], [R.sub.1] [member of] [G.sub.r]. Then it outputs the AA's PK parameters [mathematical expression not reproducible], Y = e([g.sub.1],[g.sub.2]), [A.sub.0] = [g.sub.p] * [R.sub.1], A' = [g.sup.p-uk+x'.sub.2] [g.sup.y'.sub.p][g.sup.r'.sub.q]. Here PK implies that [a.sub.i,t] = [bx.sub.i,t] + [y.sub.i,t]. B selects [delta] [member of] [Z*.sub.N] and computes B = [g.sup.[delta].sub.p]. Establish the CSP's public key [pk.sub.CSP] = (B) and the CSP's private key [pk.sub.CSP] = ([delta]). Finally, B provides (PK, [pk.sub.CSP], [sk.sub.CSP]) to A.

Phase 1: A submits the keyword list L = [[L.sub.1],...,[L.sub.n]] in a trapdoor query. If B(L) = 0, B stops the game and outputs a random value v' as the guess of v. Otherwise, B chooses r [member of] [Z*.sub.N] and computes:

[mathematical expression not reproducible] (6)

where [mathematical expression not reproducible].

Let [??] = r - a/F(L). Then we have:

[mathematical expression not reproducible] (7)

Then verify if [mathematical expression not reproducible].

Iff F(L) [not equal to] 0 mod N, B can complete the above calculation process. And only when B(L) [not equal to] 0 (B(L) [not equal to] 0 implies F(L) [not equal to] 0), the game continues.

Challenge: A submits two search policies [W.sub.0], [W.sub.1]. B randomly selects w [member of]{0,1}. If [mathematical expression not reproducible], B stops the game and outputs a random value v'; Otherwise, F([W.sub.w]) [equivalent to] 0(mod N) holds. Next, B chooses [R.sub.0] [member of] [G.sub.r], [r.sub.c] [member of] [Z*.sub.N]. [r.sub.c] can be written in the form [r.sub.c] = cr" + [r.sub.0] for some unknown [r.sub.c], where [mathematical expression not reproducible]. We let [mathematical expression not reproducible], then the ciphertext is [mathematical expression not reproducible].

The correctness of the ciphertext is verified as follows:

[C.sub.0] =[C.sup.[beta] + 1][R.sub.0] = [g.sup.c([beta]+1).sub.p][R.sub.k] = [g.sup.c.sub.p] * [g.sup.[beta]c.sub.p] * [R.sub.0] = [g.sup.c.sub.p] * [B.sup.c] * [R.sub.0] (8)

[mathematical expression not reproducible] (9)

Phase 2: It is the same as Phase 1.

Guess: A outputs the guess W' [member of]{0,1}. If w' = w, B outputs v = 0; Otherwise, B outputs v' = 1.

Analysis. If Z = e[([g.sub.p],[g.sub.p] ).sup.abc] then C = [([g.sup.a.sub.p], [g.sup.b.sub.p]).sup.c]. The CT is a valid ciphertext index based on [W.sub.w]. So, A has the advantage [epsilon] to solve the problem. Hence, Pr[w' = w|e[([g.sub.p], [g.sub.p]).sup.abc] = 1/2 + [epsilon]. If Z = e[([g.sub.p], [g.sub.p]).sup.z], the adversary A cannot distinguish w. Hence, Pr[w ' = w|e[([g.sub.p], [g.sub.p]).sup.z]] = 1/2. We can see that the game will not abort if

[mathematical expression not reproducible] (mod u) and [mathematical expression not reproducible] (mod N) hold.

Inspired by literature [18], B 's advantage is at least (1 - [N.sup.2.sub.0]/N)([epsilon]/16(n + 1)[theta]) in the above game.

Theorem 3. SE-CKS is secure against off-line keyword guessing attacks.

Proof: Suppose the outside adversary A exists who can intercept and capture the trapdoor [TD.sub.L]. A can obtain the parameter GP, AA's public key PK and CSP's public key [pk.sub.CSP] = (B) from the public network.

Aiming at obtaining the encrypted keywords, A selects the keyword list L and initiates the keyword guessing attacks as follows:

[mathematical expression not reproducible] (10)

In these derivations, A does not know the AA's private key [beta]. So, A cannot break SE-CKS through initiating keyword guessing attacks.

4. Performance Comparison

This section compares SE-CKS with other schemes in terms of the features, storage overhead and computational efficiency. In the comparison process, let | p | be the size of the element in

[Z.sub.p], let | N | be the size of the element in [Z.sub.N], let | [lambda] | be the size of the security parameter [lambda], let |S | be the number of attributes in an attribute set, let |g | and |[g.sub.T]| be the size of the element in G and [G.sub.T], respectively (|[g.sub.1]|and | [g.sub.2]| are denoted by |g|). Let n indicate the total number of keywords in the system, let l indicate the row number of M in the scheme [7].

4.1 Features Comparison

Table 1 shows a comparison of the features of certain aspects of the system. The schemes of Zhang and Liang are based on the prime order bilinear group. Lai's scheme and our scheme are based on the composite order bilinear group. Under the same security, the computational efficiency of the composite order group is lower than that of the prime order group. The security of Zhang's scheme and Liang's scheme is based on the strong assumptions of p-DDHI, q-BDHEA, respectively. The security of Lai's scheme is based on the static assumption of the composite order group. Our scheme's security is based in the simple assumption of DBDH. Zhang's scheme does not provide proof of security. Liang's scheme is selective security in the random oracle model (ROM). Lai's scheme and our scheme are adaptive security in the standard model. Therefore, our scheme is stronger than the other three schemes in terms of security. Liang's scheme does not support the multi-keywords search, which is supported in the other three schemes. In addition, our scheme removes the secure channel and can resist off-line keyword guessing attacks. The establishment of a secure channel requires a lot of computing resources.

4.2 Storage Overhead

Table 2 shows the comparison of the storage overhead on each entity in the system. To achieve the multi-user search, Liang's scheme and our scheme require the AA to generate a master private key, which generates a trapdoor for each receiver. The main storage overhead on the AA is generated by the master key. In our scheme, the AA must generate a master key for each keyword value. Liang's scheme only generates two elements in Z p and two elements in [G.sub.1]. All public parameters contribute to the storage overhead on the owner. The storage overhead of all schemes is almost the same, it is O(n) |g| +O{1) |[g.sub.T]|. The CSP is required to store the ciphertext. In our scheme, the CSP also needs to store a private key. In Zhang and Lai's schemes, the size of the ciphertext is linearly related to the number of keywords. Since Liang's scheme is based on the KP-ABE, the size of ciphertext is positively related to the size |S| of the attribute set. Our scheme is based on the CP-ABE, but the ciphertext length is a fixed value. Although the CSP requires an additional private key in our scheme, the storage overhead of the CSP is a fixed value O(1)|g| + O(1)|[g.sub.T]|. The storage overhead f each receiver is associated with the trapdoor

in the four scenarios. As with the situation of the ciphertext, the size of the trapdoor is linearly related to the number of keywords in Zhang and Lai's schemes. The size of trapdoor is positively related to the row number l of M in Liang's scheme. The size of the trapdoor is a fixed value O(1)|g| in our scheme. So the receiver has a smaller storage burden in our scheme.

4.3 Computational Efficiency

Experiment Setup: We conducted the experiment on a 64-bit Ubuntu 14.04 operating system with an Intel CoreTM i5-6200U (2.3 GHz) processor and 8 G RAM. The experimental code uses the Pairing-based Cryptography Library (PBC-0.5.14) and cpabe-0.11 to implement the schemes. We employ the 160-bit elliptic curve group in the hyper-singular curves [y.sup.2] = [x.sup.2] + x based on 512-bit finite fields. Specifically, the pairing operation time of the PBC library is approximately 1.27s, and the exponential operation times of G and [G.sub.T] are approximately 0.33s and 0.18s, respectively.

Table 3 shows a comparison of the execution time of Encryption, Trapdoor and Test. Because the time required for the multiplication operation is significantly smaller than the exponential operation, the multiplication time is omitted in Table 3. Assume that the keywords in the access structure are used for the phase of Test. The execution times of Encryption, Trapdoor and Test increase with an increase in the number of keywords in Lai's scheme. The time complexity of the Encryption, Trapdoor and Test in our scheme is a constant order. But Lai et al.'s scheme supports arbitrary monotone boolean predicates based on the linear secret sharing schemes (LSSS). And LSSS is a strong expressive access structure. Our scheme supports AND-gate access structure with multiple values. And the AND-gate access structure is a weak expressive access structure. In other words, Lai et al.'s scheme supports AND, OR and the threshold of keywords. Our scheme only supports AND of the keywords.

The simulation experiment system is built, and the operation time is tested in the system. In the simulation process, the relationship between the number of keywords and the execution time of Encryption, Trapdoor and Test is tested. We select a 1 MB file and encrypt the file with a different number of keywords. We test the execution time of the Encryption, Trapdoor and Test processes as the number of keywords changes (from 1 to 20). All simulation results are the mean of 30 trials. According to this method, Lai's scheme is simulated. The relationships are shown in Fig. 1. The horizontal axis represents the number of keywords in the search, and the vertical axis represents the execution time of Encryption, Trapdoor and Test.

Fig. 1(a) plots the executed time of Encryption, which is executed by the data owner. Fig. 1(b) shows the execution time of Trapdoor. Fig. 1(c) shows the execution time of Test, which is executed by the CSP. In Lai's scheme, the executed times of Encryption, Trapdoor and Test increase with the number of keywords. When the number of keywords changes from 1 to 20, the executed time is approximately linearly. But the executed time of Encryption, Trapdoor and Test is a fixed value in our scheme, which is not related to the number of keywords. It is consistent with the theoretical analysis in Table 3.

Through the experimental comparison, our scheme is superior to other schemes in terms of security. Our scheme is proved adaptively secure based on the simple assumption DBDH in the standard model. In terms of storage, the public key length of our scheme and other schemes is similar. But the sizes of ciphertext and trapdoor are smaller than other schemes, they are the fixed value in our scheme. In terms of efficiency, our scheme is constructed based on the composite order group, which is less efficient than the scheme based on the prime order group. But the operations of the Encryption, Trapdoor and Test are constant level, regardless of the number of keywords. When the keywords are more, the advantage of our scheme will be highlighted.

5. Conclusion

In this paper, we propose an efficient conjunctive keyword search scheme without a secure channel for the cloud storage environment, which is called SE-CKS. This scheme implements conjunctive keyword search based on CP-ABE. At the same time, we propose an efficient mechanism for removing the secure channel and resisting off-line keyword guessing attacks. The storage overhead of the CSP and DU are the fixed value and the amount of calculations of Encryption, Trapdoor and Test are constant level, regardless of the number of keywords. This scheme is proved adaptively secure based on the DBDH assumption in the standard model. Finally, the results of theoretical analysis and experimental simulation show that the proposed scheme has advantages in security, storage overhead and efficiency, and it is more suitable for practical application.

References

[1] Q. Yan, R. Yu, Q. Gong and et al, "Software-defined networking (SDN) and distributed denial of service (DDoS) attacks in cloud computing environments: A survey, some research issues, and challenges," IEEE Communications Surveys and Tutorials, vol. 18, no. 1, pp. 602-622, 2016. Article (CrossRef Link).

[2] F. Chen, T. Xiang, Y. Yang and et al, "Secure cloud storage meets with secure network coding," IEEE Transactions on Computers, vol. 65, no. 6, pp. 1936-1948, 2016. Article (CrossRef Link).

[3] D. X. Song, D. Wagner and A. Perrig, "Practical techniques for searches on encrypted data," in Proc. of IEEE Symposium on Security and Privacy, pp. 44-55, May 14-17, 2000. Article (CrossRef Link).

[4] D. Boneh, G. D. Crescenzo, R Ostrovsky and et al, "Public key encryption with keyword search," in Proc. of International Conference on the Theory and Applications of Cryptographic Techniques, pp. 506-522, May 2-6, 2004. Article (CrossRef Link).

[5] P. Golle, J. Staddon and B. Waters, "Secure conjunctive keyword search over encrypted data," in Proc. of the 2th International Conference on Applied Cryptography and Network Security, pp. 31-45, June 8-11, 2004. Article (CrossRef Link).

[6] B. Zhang and F. Zhang, "An efficient public key encryption with conjunctive-subset keywords search," Journal of Network and Computer Application, vol. 34, no. 1, pp. 262-267, 2011. Article (CrossRef Link).

[7] J. Lai, X. Zhou, R. H. Deng and et al, "Expressive search on encrypted data," in Proc. of the ACM SIGSAC symposium on Information, computer and communications securtiy, pp. 243-252, May 8-10, 2013. Article (CrossRef Link).

[8] J. Baek, R. Safavinaini and W. Susilo, "Public key encryption with keyword search revisited," in Proc. of' International Conference on Computational Science and Its Applications, pp. 1249-1259, June 30-July 3, 2008. Article (CrossRef Link).

[9] J. Byun, H. Rhee, H. Park and et al, "Off-line keyword guessing attacks on recent keyword search schemes over encrypted data," in Proc. of Workshop on Secure Data Management pp. 75-83, September 10-11, 2006. Article (CrossRef Link).

[10] H. Rhee, W. Susilo and H. Kim, "Secure searchable public key encryption scheme against keyword guessing attacks," IEICE Electron. Express, vol. 6, no. 5, pp. 237-243, 2009. Article (CrossRef Link).

[11] Y. Yang and M. Ma, "Conjunctive keyword search with designated tester and timing enabled proxy re-encryption function for e-health clouds," IEEE Transactions on Information Forensics and Securtiy, vol. 11, no. 4, pp. 746-759, 2016. Article (CrossRef Link).

[12] K. Liang and W. Susilo, "Searchable attribute-based mechanism with efficient data sharing for secure cloud storage," IEEE Transactions on Information Forensics and Securtiy, vol. 10, no. 9, pp. 1981-1992, 2015. Article (CrossRef Link).

[13] L. Cheung and C. Newport, "Provably secure ciphertext policy ABE," in Proc. of the 14th ACM conference on Computer and communications security, pp. 456-465, October 29-November 02, 2007. Article (CrossRef Link).

[14] J. Bethencourt, A. Sahai and B. Waters, "Ciphertext-policy attribute-based encryption," in Proc. of IEEE symposium on security and privacy, pp. 321-334, May 20-23, 2007. Article (CrossRef Link).

[15] M. Abdalla, M. Bellare, D. Catalano and et al, "Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions," in Proc. of the 25th Annual International Cryptology Conference, pp. 205-222, August 14-18, 2005. Article (CrossRef Link).

[16] L. Fang, W. Susilo, C. Ge and et al, "Public key encryption with keyword search secure against keyword guessing attacks without random oracle," Information Sciences, vol. 238, no. 7, pp. 221-241, 2013. Article (CrossRef Link).

[17] K. Emura, A. Miyaji, A. Nomura and et al, "A ciphertext-policy attribute-based encryption scheme with constant ciphertext length," International Journal of Applied Cryptography, vol. 2, no. 1, pp. 46-59, 2010. Article (CrossRef Link).

[18] B. Waters, "Efficient identity-based encryption without random oracles," in Proc. of the 24th International Conference on the Theory and Applications of Cryptographic Techniques, pp. 114-127, May 22-26, 2005. Article (CrossRef Link).

Jianhua Wang received a Ph.D. degree from Zhengzhou Information Science and Technology Institute, China in 2008 and became a Full Professor in 2006. His research interests primarily focus on information security. He has authored and co-authored more than 100 journal and conference papers.

Zhiyuan Zhao received an M.S. degree from Zhengzhou Information Science and Technology Institute, Zhengzhou, China in 2015. He is currently pursuing a Ph.D. degree at Zhengzhou Information Science and Technology Institute, China. His research interests include cryptograph theory, especially attribute-based encryption.

Lei Sun received the Ph.D. degree from the Department of Computer and Communication Engineering, Wuhan University in 2003. He became a Full Professor in 2013. His research interests include information security, cloud computing and computer network.

Zhiqiang Zhu received the Ph.D. degree from the Department of Information Security, Wuhan University in 2011 and became the Full Professor in 2011. His research interests lie in information management, cloud computing and access control.

Jianhua Wang (1), Zhiyuan Zhao (1*), Lei Sun (1), Zhiqiang Zhu (1)

(1) Zhengzhou Information Science and Technology Institute Zhengzhou 450001, Henan - P. R. China

[e-mail: zzy_taurus@foxmail.com]

(*) Corresponding author: Zhiyuan Zhao

Received April 15, 2018; revised November 13, 2018; accepted December 10, 2018; published May 31, 2019

http://doi.org/10.3837/tiis.2019.05.026

Table 1. Features Comparison Features Zhang [6] Lai [7] Liang [12] Ours Bilinear Maps Prime Composite Prime Composite Assumption P-DDHI Static Q-BDHE DBDH Secure Model - Standard ROM Standard Security - Adaptive Selective Adaptive Multi-Keywords Yes Yes No Yes SCF No No No Yes Off-line KGA No No No Yes Table 2. Comparison of Storage Overhead Schemes AA Owner (MSK) (All PK) Zhang[6] - O(n)|g| Lai [7] - O(n)|g| + O(1)|[g.sub.T]| Liang[12] O(1)|g|+O(1) |p| O(n) |g|+O(1)|[g.sub.T]| Ours O(n) |g|+O(1)|N| O(n) |g|+O(1)|[g.sub.T]| Schemes CSP Receiver (CT) (Trapdoor) Zhang[6] O(n) |g| + O(1) |p| O(n) |g| Lai [7] O(n) |g|+O(1) |[g.sub.T]| O(l)|g| Liang[12] O(|S|) |g|+O(1) |[lambda]|+O(1)|[g.sub.T]| O([l.sup.2])|g| Ours O(1) |g|+O(1) |[g.sub.T]| O(1)|g| Table 3. Comparison of Computational Efficiency Operation Time (s) Lai [7] Our scheme Encryption Trapdoor Test Exp in G 0.33 2 n+1 4l 0 Exp in [G.sub.T] 0.18 1 0 1 Bilinear Pairing 1.27 0 0 2l Total Time 0.66n+0.51 1.321 2.721 0.84 Operation Encryption Trapdoor Test Exp in G 2 4 0 Exp in [G.sub.T] 1 0 1 Bilinear Pairing 0 0 2 Total Time 1.32 2.72

Printer friendly Cite/link Email Feedback | |

Author: | Wang, Jianhua; Zhao, Zhiyuan; Sun, Lei; Zhu, Zhiqiang |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | May 1, 2019 |

Words: | 6583 |

Previous Article: | A Multi-Stage Encryption Technique to Enhance the Secrecy of Image. |

Next Article: | A Danger Theory Inspired Protection Approach for Hierarchical Wireless Sensor Networks. |

Topics: |