# Verifiable Data Search with Fine-Grained Authorization in Edge Computing

Authors: Jianwei Li; Xiaoming Wang; Qingqing Gan
Journal: Security and Communication Networks
 (2022)

---

## Abstract

In the research of searchable encryption, fine-grained data authorization is a convenient way to manage the search rights for users. Recently, Liu et al. proposed a fine-grained searchable scheme with verification, which can control the search authorization and verify the results. In this paper, we first present a forgery attack against Liu et al.’s scheme and then propose a novel scheme of verifiable data search with fine-grained authorization in edge environment. Based on the key aggregate mechanism and Merkle hash tree, our proposed scheme not only achieves file-oriented search permission management but also implements the correctness and completeness verification of search results. In addition, with the assistance of edge server, resource-constrained users can easily perform the tasks of search and verification. Finally, we prove our scheme is secure based on the decisionl-bilinear Diffie–Hellman exponent problem. The performance analysis and experiment results demonstrate that our proposed scheme has lower computation, communication, and storage costs contrast to the existing schemes.


---

## Body

## 1. Introduction

With the high growth of Internet technique, cloud storage and computing services have been used extensively to business and individuals [1]. While cloud services bring convenience to people, there are still many problems to be solved, such as the security and retrievability of data [2]. To satisfy these requirements, the primitive of searchable encryption (SE) [3, 4] is proposed; as a promising technology, SE allows users to search encrypted data while protecting the privacy. Traditional SE schemes are always deployed in cloud environment (such as [5–7]), which are more suitable for the users of personal computer, that the clients can deal with computationally intensive works, such as encrypting and decrypting files and configuring a large number of attributes.In the era of mobile Internet, terminal users are developing towards diversification. In addition to computer, more and more people are using mobiles, tablets, wearables, and other devices to perceive and receive data. Constrained by limited resources, these devices cannot bear complex computations and tasks. Therefore, it is urgent to find a more friendly environment for resource-constrained terminals. Recently, edge computing has been proposed as a new paradigm [8, 9]. It configures the storage, computing, and network devices between the users and cloud, which assists users to complete tedious tasks, or sink the cloud service functions to a favorable position, providing the real-time data processing and intelligent analysis nearby. Apparently, edge computing can not only reduce the burden of terminals and decrease the service response latency but also avoid the congestion of core network. Therefore, deploying SE technology in edge environment may have wider applications.SE technology includes symmetric encryption retrieval [3] and public key encryption retrieval [4], in which the public key encryption retrieval is mostly utilized for multiple users. In the multiuser scenario, users can share data and cooperate and communicate with each other, which is suitable for most mobile applications. For instance, in a music sharing platform, the user who publishes data is called publisher, and the user who purchases and applies data is called data user. In this system, the data users can buy the music content from publisher, and the users change dynamically, so does the purchased content. In previous studies [10–12], data authorization is user-oriented, where the users can be authorized or revoked completely. In practical applications, more fine-grained management of data authorization is required. For example, when a user purchases new content or the purchased content expires, then the publisher must distribute a new authorization or revoke the previous search rights. Therefore, file-oriented search permission management should be introduced.In an outsourced storage environment, sometimes the user needs to deal with a malicious server. For example, the server storage data is corrupted, or the server saves computing resources during the peak time. In these situations, the server may not want to process the whole database when responding to queries. From the perspective of users, they pay for the data and then always expect to receive guaranteed services. Therefore, the function of data verification for user is required when necessary. Recently, some schemes (e.g., [13, 14]) have been proposed to verify the search results. However, these schemes can only verify the correctness of return data but not the completeness. If the cloud returns an insufficient number of files, the user cannot discover it. Later, Liu et al. [15] proposed a searchable scheme to verify the completeness of search results. Unfortunately, this scheme involves forgery attack so that the users cannot correctly verify the completeness of search results.In this paper, we propose an efficient verifiable data search with file-oriented authorization scheme in edge computing, in which the publishers can distribute fine-grained search permissions, and the data users can search the favorite data and verify the correctness and completeness of results with the assistance of edge server. Our contributions are as follows:(i)
We analyze and show an attack against Liu et al.’s scheme [15].(ii)
We propose a novel privacy-preserving file-oriented search scheme in edge computing. Based on the key aggregate mechanism, our proposed scheme implements fine-grained authorization and facilitates the distribution of massive data search rights. Through the design of Merkle hash tree, it achieves the correctness and completeness verification of search results. In addition, with the assistance of edge server, the resource-constrained users can easily query the data and verify the search results.(iii)
We optimize the costs of the proposed scheme. In the keyword ciphertext process, it uploads one Bloom filter value instead of all the encrypted keywords, and then the communication and storage costs are related to the number of files, instead of the keyword number.(iv)
Based on the decisionl-BDHE problem, we prove our scheme can meet the secure features. Performance evaluation and experiments demonstrate that our scheme is more practical and efficient than the available schemes.The rest paper is organized into seven sections. The related studies and reviews are described in Section2. The relevant knowledge is introduced in Section 3. Section 4 discusses the attack of Liu et al.’s scheme. Section 5 states the details of our proposed scheme. Then we show the requirements analysis in Section 6 and the performance evaluation in Section 7. The last section is a summary.


## 2. Related Work

To address the issues of data searchability and privacy preserving, Song et al. [3] proposed the primitive of searchable symmetric encryption, which can search the data with encryption form. Later, Boneh et al. [4] proposed the Public Key Searchable Encryption (PKSE) and applied it to mail system. Since then, PKSE has become a research hotspot, and many solutions have been proposed such as the proxy reencryption PKSE [16], attribute-based PKSE [17], certificateless PKSE [18], and PKSE based on primes [19]. However, these schemes are suitable for the personal computer clients, which are computation-intensive and unfriendly to resource-constrained terminals.To reduce the computing and storage overhead in the client side, Guo et al. [20] proposed a keyword search encryption framework under the edge environment, which offloads the computation-intensive tasks of the sensor to the edge server. However, they only propose a framework without a specific implementation. Chen et al. [21] presented a privacy-preserving searchable encryption scheme in the edge computing, which designs an S-HashMap index structure and supports the fuzzy search of multikeywords. Yet in their scheme, the user needs to calculate all keyword indexes and generate index access tree, which requires a large amount of computation. Scheme [22] puts forward a PKSE solution based on the witness system in cloud-edge computing to resist the keyword guessing attack, while the scheme can only resist the external attackers but not the internal attackers like the curious cloud server. Wang et al. [23] proposed an image retrieval scheme with mobile edge computing, which introduced a cloud-guided image feature extraction method, thus reducing network traffic and improving retrieval accuracy, but this solution cannot be applied to keyword search scenario. Scheme [24] proposed a user-centered data search framework, which uses the edge computing to make intelligent prediction of the user’s search pattern, tailoring the search space so as to reduce the processing time. However, the framework is user-centered and is not suitable for the numerous files sharing scenario.In the scenes of numerous searchable files sharing (such as [25–27]), the data owner can distribute the file-oriented retrieval rights to other users. In these schemes, the data owner uses different keys to encrypt different documents and shares the corresponding keys to the legitimate user. Obviously, such a key management mechanism has high cost in aspects of communication and storage, and the size of search token increases with the number of share files. Scheme [28] introduced a proxy server to transform the user’s search token into a instance, so as to reduce the key cost of user side. However, this method does not fundamentally solve the problem of inefficient key management. To solve the key management overhead problem, Cui et al. [29] presented a key aggregate searchable encryption in the cloud storage environment. In this scheme, the client can search for multiple files with one single key shared by the data owner. However, Zhou et al. [30] referred that the scheme [29] suffered from keyword guessing attack. Later, Li et al. [31] proposed a multiowner key aggregate searchable encryption scheme that the user can submit one single trapdoor to search across multiple data owners’ file records. Yet the scheme does not consider the dynamic search right management.For the verification mechanism, Zhang et al. [32] proposed that a scheme can verify the single keyword search ranking results of the data uploaded by multiple users. However, all the users need to share the sorting data interactively to obtain the final ranking order, which reduces the practicability. Jianfeng Wang et al. [33] proposed a method to verify the query results of multiple keywords, which is suitable for the large scalable database, but this scheme uses an accumulator to implement verification and makes it difficult for mobile clients to bear the computing overhead. Recently, schemes [13, 14] have been proposed to verify the aggregate search results, but these schemes can only verify the correctness but not the completeness. A scheme [15] is proposed which can verify the completeness of results; however, it suffers from forgery attack so that the users cannot correctly verify the completeness of search results.


## 3. Preliminaries

### 3.1. Bilinear Pairing

Let two multiplicative cyclic groupsG and G1 have the identical order p, bilinear pairing e is a map: G×G⟶G1 which has the attributes as follows:(1)
Bilinearity: Fora,b∈G and m,n∈ℤP, we have eam,bn=ea,bmn(2)
Computability: There is an efficiency algorithm to calculateea,b for any a,b∈G(3)
Nondegeneracy: Letϑ be a generator of G, then eϑ,ϑ≠1


### 3.2. Merkle Hash Tree

The Merkle hash tree (MHT) is a data structure based on the hash function which is a hash binary tree. In MHT, each leaf node stores the hash value of the data block, and each nonleaf node’s value is calculated by hashing its children.In MHT construction, we first calculate the hash value of each data, and then fill them as the lowest leaf nodes. Next, we establish the upper layer, and the value of each node in this layer is calculated by hashing its left and right children. Then we continuously establish the upper layer until the root.MHT is recursively calculated layer by layer through hash computation, while hash is a one-way function; that is, the value of the parent node can only be calculated by its children, and the value of the child node cannot be deduced from the parent node. Therefore, when the value of the root node is determined, the correctness of all other nodes’ value can be guaranteed, namely the change of any node’s value will cause the value of root node to be different.For example, a data setD=d1,d2,d3,d4 is input, then the output of MHTD is the root node’s value Lroot, then we show the construction in Figure 1. First, we compute the hash value Li=Hdii=1,2,3,4 for each leaf node, then calculate the nonleaf nodes’ values L5=HL1L2 and L6=HL3L4, and at last, we output the root node’ value Lroot=HL5L6.Figure 1
Merkle hash tree.


### 3.3. Bloom Filter

Bloom filter is a data structure used to represent collections, and it has three operations as follows:(1)
BFInit: This operation creates an empty Bloom filter, which is a l-bit array with value 0(2)
BFAddH1,…,Hk,bf,s: This operation adds an element s to the Bloom filter bf. It first hashes the element with k functions as His=φi∈0,1,…,l−1, and then sets the φi-th bit value to 1(3)
BFQueryH1,…,Hk,bf,s: This operation queries whether the element s is a membership data. It first computes the k hash functions to s, and then checks whether all the corresponding bits are equal to 1. If it holds true, s is a membership data; otherwise, s is not in the collection.


### 3.4. Keyed Hash Function

The keyed hash function is a verification and encryption mechanism used by communication entities, and it ensures the integrity and confidentiality of message data, and its security depends on the hash function. The keyed hash function inputs a message and a key and then outputs a hash value used for data authentication and integrity verification.In this paper, we use the keyed hash function HMAC [34] to process keywords, and the calculation method is as follows:(1)HEm=HE⊕opadHE⊕ipadm,where m is a message, E is the key which is a 64 bits string, H is a hash function, opad and ipad are strings composed of several “0x5c” and “0x36,” respectively, ⊕ represents XOR operation, and ‖ represents join operation.


### 3.5. Complexity Assumption

The complexity assumption is defined as follows:(1)
Decisionl-bilinear Diffie–Hellman exponent (Decision l-BDHE) problem: The problem [35] in group G is worked as below. Given a vector of 2l+2 elements h,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,Z as input, where h,ϑ∈G, Z∈G1, and ϑai for i=1,2,…,l,l+2,…2l, note that ϑal+1 is missing, and a had not given. Then decide if Z=eϑ,hal+1 or Z is a random value in G1. For a polynomial time adversary Ad, the advantages obtained from the problem are defined as(2)ADVAdDecisionl−BDHE=PrAh,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,Z=eϑ,hal+1=0−PrAh,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,Z≠eϑ,hal+1=0.(2)
Decisionl-BDHE assumption: For the adversary Ad with any polynomial time t, the advantage to Decision l-BDHE problem is defined as ADVAdDecisionl−BDHE≤ε, then we say that the t,ε,l-BDHE problem is difficult to be solved.


## 3.1. Bilinear Pairing

Let two multiplicative cyclic groupsG and G1 have the identical order p, bilinear pairing e is a map: G×G⟶G1 which has the attributes as follows:(1)
Bilinearity: Fora,b∈G and m,n∈ℤP, we have eam,bn=ea,bmn(2)
Computability: There is an efficiency algorithm to calculateea,b for any a,b∈G(3)
Nondegeneracy: Letϑ be a generator of G, then eϑ,ϑ≠1


## 3.2. Merkle Hash Tree

The Merkle hash tree (MHT) is a data structure based on the hash function which is a hash binary tree. In MHT, each leaf node stores the hash value of the data block, and each nonleaf node’s value is calculated by hashing its children.In MHT construction, we first calculate the hash value of each data, and then fill them as the lowest leaf nodes. Next, we establish the upper layer, and the value of each node in this layer is calculated by hashing its left and right children. Then we continuously establish the upper layer until the root.MHT is recursively calculated layer by layer through hash computation, while hash is a one-way function; that is, the value of the parent node can only be calculated by its children, and the value of the child node cannot be deduced from the parent node. Therefore, when the value of the root node is determined, the correctness of all other nodes’ value can be guaranteed, namely the change of any node’s value will cause the value of root node to be different.For example, a data setD=d1,d2,d3,d4 is input, then the output of MHTD is the root node’s value Lroot, then we show the construction in Figure 1. First, we compute the hash value Li=Hdii=1,2,3,4 for each leaf node, then calculate the nonleaf nodes’ values L5=HL1L2 and L6=HL3L4, and at last, we output the root node’ value Lroot=HL5L6.Figure 1
Merkle hash tree.


## 3.3. Bloom Filter

Bloom filter is a data structure used to represent collections, and it has three operations as follows:(1)
BFInit: This operation creates an empty Bloom filter, which is a l-bit array with value 0(2)
BFAddH1,…,Hk,bf,s: This operation adds an element s to the Bloom filter bf. It first hashes the element with k functions as His=φi∈0,1,…,l−1, and then sets the φi-th bit value to 1(3)
BFQueryH1,…,Hk,bf,s: This operation queries whether the element s is a membership data. It first computes the k hash functions to s, and then checks whether all the corresponding bits are equal to 1. If it holds true, s is a membership data; otherwise, s is not in the collection.


## 3.4. Keyed Hash Function

The keyed hash function is a verification and encryption mechanism used by communication entities, and it ensures the integrity and confidentiality of message data, and its security depends on the hash function. The keyed hash function inputs a message and a key and then outputs a hash value used for data authentication and integrity verification.In this paper, we use the keyed hash function HMAC [34] to process keywords, and the calculation method is as follows:(1)HEm=HE⊕opadHE⊕ipadm,where m is a message, E is the key which is a 64 bits string, H is a hash function, opad and ipad are strings composed of several “0x5c” and “0x36,” respectively, ⊕ represents XOR operation, and ‖ represents join operation.


## 3.5. Complexity Assumption

The complexity assumption is defined as follows:(1)
Decisionl-bilinear Diffie–Hellman exponent (Decision l-BDHE) problem: The problem [35] in group G is worked as below. Given a vector of 2l+2 elements h,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,Z as input, where h,ϑ∈G, Z∈G1, and ϑai for i=1,2,…,l,l+2,…2l, note that ϑal+1 is missing, and a had not given. Then decide if Z=eϑ,hal+1 or Z is a random value in G1. For a polynomial time adversary Ad, the advantages obtained from the problem are defined as(2)ADVAdDecisionl−BDHE=PrAh,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,Z=eϑ,hal+1=0−PrAh,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,Z≠eϑ,hal+1=0.(2)
Decisionl-BDHE assumption: For the adversary Ad with any polynomial time t, the advantage to Decision l-BDHE problem is defined as ADVAdDecisionl−BDHE≤ε, then we say that the t,ε,l-BDHE problem is difficult to be solved.


## 4. Discuss of Liu et al.’s Scheme

### 4.1. Liu et al.’s Scheme

We simply describe Liu et al.’s scheme [15] as follows:(1)
Init1λ,n: The system initializes parameters described below.(a)
Generates a bilinear map group systemB=p,G,G1,e⋅,⋅ and sets n as the maximum number of documents(b)
Randomly picksg∈G and a∈ℤp and computes gi=gai, for i=1,2,…,n,n+2,…2n(c)
Selects one-way hash functionsH0:0,1∗⟶G , H1:G1⟶0,1m and H1′,…,Hk′:0,1∗⟶0,…,m−1(2)
KeyGen: The data owner chooses a randomγ∈ℤp and sets the private key sk=γ and public key v=gγ(3)
Encrypti,Wi: For the i-th document i∈=1,…,n, the data owner does those as given below.(a)
Generates a Bloom filter for this document’s keyword set by computingBFi=BFGenH1′,…,Hk′,Wi(b)
Picks a randomt∈ℤp, M∈G1 and then computes the ciphertexts and sends to cloud:c1,c2,c3,c4=gt,v⋅git,H1M⊕BFi,M⋅eg1,gnt and cw=eg,H0wt/eg1,gnt(4)
ShareS: For subset S⊆1,…,n, the data owner computes Ka=∏j∈Sgn+1−jγ and sends to user(5)
Trapdoorw: The user generates the trapdoor Tr=Ka⋅H0w and sends to the cloud(6)
RetrieveTr,S:(a)
The cloud tests the trapdoor for all files inS, and Test:cw=eTr⋅∏j∈S,j≠ign+1−j+i,c1/e∏j∈Sgn+1−j,c2(b)
The cloud generates the verification proofs as(3)proofi=p1,p2,p3=c4⋅∏j∈S,j≠ign+1−j+i,c1e∏j∈Sgn+1−j,c2,c1,c3.(7)
Verifyw,proof: The user verifies the results as follows:(4)M′=p1⋅eKa,p2,BFi′=H1M′⊕p3,BFverifyH1′,…,Hk′,BFi′,w=1.


### 4.2. Analysis

Liu et al.’s scheme realizes that an authorized user can retrieve multiple encrypted files by one shared key and verifies the completeness of search results, but we find that the user cannot correctly verify the completeness of search results. In their scheme, the verification proof is calculated and transmitted by the cloud, and then it has the opportunity to forge the proof, which the users could not detect.Let us look at a specific case. Suppose authorized subsetS=f1,f2,…,fs, with the user queries keyword w, then the honest cloud will return the complete search results I=f1,f2,…,ft,t≤s, and the verification proofs are(5)proofi=p1,p2,p3=c4⋅∏j∈S,j≠ign+1−j+i,c1e∏j∈Sgn+1−j,c2,c1,c3.For eachi∈S (3), subsequently the user could check whether the return files are correct when receive the proofs (4).However, if the cloud forges the proofs, we get(6)proofi=p1,p2,p3,i∈S−I′,p1,p2,p3¯,i∈I′,and returns the result I−I′ to the user, which can also pass the user’s verify algorithm, where p3¯ is a fake value as long as it is not equal to p3, and I′=f1,f2,…,fkk≤t is the file set lost by the cloud.For eachi∈I′, the user computes(7)M′=p1⋅eKa,p2,BFi¯=H1M′⊕p3¯,and verifies(8)BFverifyH1′,…,Hk′,BFi¯,w≠1.Becausep3¯ is forged by the cloud server, and BFi¯ will be an incorrect value, so (4) would not hold true. While for each i∈I−I′, p3 is correct, so (4) holds true. Thus, the user believes that the search result I−I′ is complete.Therefore, Liu et al.’s scheme cannot correctly verify the completeness of search results.


## 4.1. Liu et al.’s Scheme

We simply describe Liu et al.’s scheme [15] as follows:(1)
Init1λ,n: The system initializes parameters described below.(a)
Generates a bilinear map group systemB=p,G,G1,e⋅,⋅ and sets n as the maximum number of documents(b)
Randomly picksg∈G and a∈ℤp and computes gi=gai, for i=1,2,…,n,n+2,…2n(c)
Selects one-way hash functionsH0:0,1∗⟶G , H1:G1⟶0,1m and H1′,…,Hk′:0,1∗⟶0,…,m−1(2)
KeyGen: The data owner chooses a randomγ∈ℤp and sets the private key sk=γ and public key v=gγ(3)
Encrypti,Wi: For the i-th document i∈=1,…,n, the data owner does those as given below.(a)
Generates a Bloom filter for this document’s keyword set by computingBFi=BFGenH1′,…,Hk′,Wi(b)
Picks a randomt∈ℤp, M∈G1 and then computes the ciphertexts and sends to cloud:c1,c2,c3,c4=gt,v⋅git,H1M⊕BFi,M⋅eg1,gnt and cw=eg,H0wt/eg1,gnt(4)
ShareS: For subset S⊆1,…,n, the data owner computes Ka=∏j∈Sgn+1−jγ and sends to user(5)
Trapdoorw: The user generates the trapdoor Tr=Ka⋅H0w and sends to the cloud(6)
RetrieveTr,S:(a)
The cloud tests the trapdoor for all files inS, and Test:cw=eTr⋅∏j∈S,j≠ign+1−j+i,c1/e∏j∈Sgn+1−j,c2(b)
The cloud generates the verification proofs as(3)proofi=p1,p2,p3=c4⋅∏j∈S,j≠ign+1−j+i,c1e∏j∈Sgn+1−j,c2,c1,c3.(7)
Verifyw,proof: The user verifies the results as follows:(4)M′=p1⋅eKa,p2,BFi′=H1M′⊕p3,BFverifyH1′,…,Hk′,BFi′,w=1.


## 4.2. Analysis

Liu et al.’s scheme realizes that an authorized user can retrieve multiple encrypted files by one shared key and verifies the completeness of search results, but we find that the user cannot correctly verify the completeness of search results. In their scheme, the verification proof is calculated and transmitted by the cloud, and then it has the opportunity to forge the proof, which the users could not detect.Let us look at a specific case. Suppose authorized subsetS=f1,f2,…,fs, with the user queries keyword w, then the honest cloud will return the complete search results I=f1,f2,…,ft,t≤s, and the verification proofs are(5)proofi=p1,p2,p3=c4⋅∏j∈S,j≠ign+1−j+i,c1e∏j∈Sgn+1−j,c2,c1,c3.For eachi∈S (3), subsequently the user could check whether the return files are correct when receive the proofs (4).However, if the cloud forges the proofs, we get(6)proofi=p1,p2,p3,i∈S−I′,p1,p2,p3¯,i∈I′,and returns the result I−I′ to the user, which can also pass the user’s verify algorithm, where p3¯ is a fake value as long as it is not equal to p3, and I′=f1,f2,…,fkk≤t is the file set lost by the cloud.For eachi∈I′, the user computes(7)M′=p1⋅eKa,p2,BFi¯=H1M′⊕p3¯,and verifies(8)BFverifyH1′,…,Hk′,BFi¯,w≠1.Becausep3¯ is forged by the cloud server, and BFi¯ will be an incorrect value, so (4) would not hold true. While for each i∈I−I′, p3 is correct, so (4) holds true. Thus, the user believes that the search result I−I′ is complete.Therefore, Liu et al.’s scheme cannot correctly verify the completeness of search results.


## 5. System Model and Definitions

In this section, we first present the model and definition, then describe the requirements.


### 5.1. System Model

The system model is shown in Figure2, which contains four entities: publisher, cloud server, edge server, and data user.(i)
Publisher. When the publisher has the shared data, it encrypts the data and outsources to the cloud. After the purchase action, the publisher distributes the corresponding keys to user and edge for the data query and verification.(ii)
Cloud Server. The cloud stores the uploading data and responds on the query. The cloud is not fully trustworthy.(iii)
Edge Server. The edge assists users with the query and verification operation. It is trusted and like a front-end server on the user side.(iv)
Data User. The users purchase data and obtain the search authorization, who can query data with the assistance of edge server.Figure 2
System model.


### 5.2. Formal Definition

(1)
Init1λ,n⟶PP: This algorithm is operated by the publisher. The algorithm inputs a security parameter λ and the maximum file number n and then outputs the system public parameters PP(2)
KeyGenPP⟶E,sk,PK: This algorithm is run by the publisher. The algorithm inputs the parameters PP and then outputs hash key E, publisher’s secret key sk, and public key PK(3)
EncryptPP,PK,W⟶C,BF,Lroot: This algorithm is run by the publisher, and it inputs parameters PP, public key PK, and keyword set W and then outputs the ciphertext set C, Bloom filter value set BF, and the root node value of a Merkle hash tree Lroot(4)
AuthorizationPP,sk,id,S⟶Aid,Kid: This algorithm is run by the publisher. The algorithm inputs parameters PP, secret key sk, user’s public identity id, and a subset SS⊆N and then outputs the authorization key Aid and identity key Kid(5)
TrapdoorE,Aid,w,Kid⟶Tr: The algorithm is operated by the data user and edge server. It takes the authorization key Aid, hash key E, keyword w, and identity key Kid as the input and then outputs the trapdoor Tr(6)
SearchPP,C,BF,Tr⟶I,PFS: This algorithm inputs parameters PP, the ciphertext set C, Bloom filter value set BF, and trapdoor Tr and then outputs the search result I and verification proof PFS(7)
VerificationPP,I,PFS,BF,Lroot⟶1/0: This algorithm takes public parameters PP, search result I, verification proof PFS, and publisher’s public key BF,Lroot as the input and then outputs 1 if the result is correct and complete; otherwise, it outputs 0Definition 1.
Our proposed scheme includes the below seven algorithms.


### 5.3. Requirements

#### 5.3.1. Security

In our proposed scheme, the system should satisfy indistinguishability against selective-file chosen keyword attack (IND-SF-CKA) security [30].We used a game between a Challenger Cha and a polynomial-time Adversary Ad to define the model of IND-SF-CKA.(1)
Initial. Ad publishes the file set S∗ to be attacked.(2)
Setup. Cha builds the system and generates the public parameter and then sends the parameters and keyword space W to Ad.(3)
Process 1. Ad carries out a series of Authorized and Trapdoor queries as follows:Authorized query: Ad sends any file set S to Cha which cannot have any intersection with S∗ and receives the keys Aid,Kid computed by Cha through the algorithm Authorize PP,sk,id,S.Trapdoor query: Ad can adaptively enquire to Cha with any keyword w∈W in S and then Cha runs the algorithm Trapdoor E,Aid,w,Kid to generate the trapdoor Tr and sends it to Ad.(4)
Challenge. When Ad wants to finish Process 1, it generates two keywords of the same length in plain text w0,w1∈W. Cha randomly selects u∈0,1 and i∈S∗ and then operates the Encrypt algorithm to output the challenge ciphertext cw∗=EncryptPP,PK,wb and sends cw∗ to Ad.(5)
Process 2. Ad continuously sends the queries of Authorize and Trapdoor algorithms as in Process 1, the limit is the Authorize queries of S cannot have any intersection with S∗, and the Trapdoor query of w0 or w1 cannot be in S∗.(6)
Guess. Ad guesses the value ofu and outputs u′. Ad wins the game if u′=u. Set that Ad’s advantages over this game is(9)AdvAdscheme=Pru′=u−12.Definition 2.
The proposed scheme is IND-SF-CKA secure ifAdvAdscheme is negligible.


#### 5.3.2. Consistency

Besides the security, the proposed scheme should satisfy the consistency when using the trapdoor for query [36].(10)PrSearchTrapdoorE,Aid,w′,Kid,EncryptPP,PK,w=1=0.Definition 3.
For all distinct keywordsw,w′∈0,1∗, the trapdoor with w′ and the cipher text for encrypting w is consistent if and only if the following probability holds true.T algorithm Search is always rejected when the keywordw′ contained in Trapdoor is different from the keyword w in Encrypt.


#### 5.3.3. Correctness and Completeness

The proposed scheme should satisfy that the search result is correct and complete, which is defined as follows based on the definition in [37].(1)
Correctness:w⊂f1∧w⊂f2∧…∧w⊂ft(2)
Completeness:f1−Q∩f2−Q∩…∩fs−Q=∅, where Q=f1∩f2∩…∩ftDefinition 4.
For authorized file setS=1,2,,…,s and a keyword w for the query, the search result with I=f1,f2,…,ft is correct and complete when the below two terms are true.The correctness condition ensures that the search result contains keywordw, and the completeness condition guarantees the search result which includes all files containing keyword w. When the search result is correct and complete, the Verification algorithm would output 1; otherwise, it would output 0.


### 5.4. The Proposed Scheme

#### 5.4.1. Overview

In scheme [15], the fundamental reason why the cloud can launch forgery attacks is that the verification process requires cloud to participate in calculation, and the flow is “publisher computing - > cloud computing - > user computing, so the users will not know whether the cloud has forged proof. In our design, we changed the verification flow to “publisher computing - > public proof - > user computing,” And the cloud does not participate in computing but only forwards the data. Besides, in the phase of “public proof,” we use the Merkle hash tree to ensure that the proof is not tampered with by the cloud, thus guaranteeing the correctness and completeness of search data.Secondly, in the index encryption phase of existing researches [13–15, 29–31], they encrypt every keyword associated with each file and then upload them. Consequently, the search function needs to match whether the query value is equal to each keyword, which will greatly affect the search efficiency. In our design, we store each file’s keyword set in a Bloom filter; that is, only one string is uploaded for one file. Hence, during the keyword processing, the communication and storage cost is greatly reduced, and the overhead is related to the number of files but not to the number of keywords.Thirdly, in the existing works [13–15, 32, 33], the verification process are mostly based on the cloud computing environment, and users need to perform generous calculations to verify, which is unacceptable for some resource-constrained clients. In this paper, the edge server is introduced to assist users in search and verification, which greatly reduces the computation overhead for users and make them more comfortable.


#### 5.4.2. Construction

Based on the definition described in 5.2, we propose a concrete construction as follows:(1)
Init1λ,n⟶PP: The publisher generates the public parameters as given below.Generates a bilinear map systemB=p,G,G1,e⋅,⋅, where p is the order of G and 2λ≤p≤2λ+1.Setsn as the maximum number of files and then the complete file index set N=1,…,n.Picks a random generatorϑ∈G and a random number a∈ℤp and computes ϑi=ϑai, for i=1,2,…,n,n+2,…,2n.Chooses a collision-free hash function used for the Merkle hash tree:H0:0,1∗⟶G.Choosesl as the maximum length of Bloom filter, and k independent universal hash functions: H1,…,Hk:0,1∗⟶0,1l.Chooses a keyed hash functionH:0,1∗⟶G.Then the system public parameters are(11)PP=B,ϑ,ϑ1,…,ϑn,ϑn+2,…,ϑ2n,H0,H1,…,Hk,Hkey.(2)
KeyGenPP⟶E,sk,PK: The publisher generates a random string E as the hash key and chooses a random number γ∈ℤp as the secret key, then the public key is(12)PK=υ=ϑγ.(3)
EncryptPP,PK,W⟶C,BF,Lroot: The publisher encrypts the files and keywords as follows:Firstly, for each file indexi∈N, we get those as follows:Generates an empty Bloom filterBFi=BFInit.Randomly chooses an integert∈ℤp and computes two encryption auxiliary values:(13)ci,1=ϑt,ci,2=υ⋅ϑit.For the keywordswijj∈1,…,x contained by the i-th file, we getThen setBF=BFi,i∈N.Secondly, the publisher generates a MHT withn leaf nodes to guarantee the correctness of the file auxiliary values. Then the MHT is built as follows:Each leaf node’s value is a hash of two auxiliary values such as(14)Li=H0ci,1ci,2,i∈N.Each nonleaf node’s value is a hash of its two children nodes and then the root node’s valueLroot can also be determined.Finally, the publisher uploadsC=ci,1,ci,2i∈N to the cloud and adds BF and Lroot to his/her public key as(15)PK=υ,BF,Lroot.Note that the cloud can rebuilt the MHT since it has the encryption auxiliary valuesC.(4)
AuthorizationPP,sk,id,S⟶Aid,Kid: For user’s public identity id and authorization file subset S⊆N, the publisher computes as(16)Aid=idγ,Kid=∏j∈Sϑn+1−jγAid,and then sends the authorization keyE,Aid to user and identity key Kid to edge.(5)
TrapdoorE,Aid,w,Kid⟶Tr: For the keyword w, the user generates the search query Q and sends to edge server as(17)Q=HEw⋅Aid.When the search query is recieved, the edge first verifies the user’s public identity, then uses the corresponding identity key to compute the trapdoor, and sends to cloud:(18)Tr=Kid⋅Q.(6)
SearchPP,C,BF,Tr⟶I,PFS: On receiving Tr, the cloud server does the following works.Firstly, for each file indexi∈S:Computes the corresponding ciphertext for thei-th file as(19)cwi=eTr⋅∏j∈S,j≠iϑn+1−j+i,c1,ie∏j∈Sϑn+1−j,c2,i.Gets the matching result of thei-th file through the Bloom filter asIftesti=1, the file fi is added to the result set I.Secondly, the cloud server constructs the verification proofPFS as follows:Auxiliary valuesC=ci,1,ci,2,i∈S.Merkle hash tree proof is denoted aspfS:wherepathi is a list of nodes that denotes the path from leaf node i to the root node of Merkle hash tree. Let nodeN−S be a list of leaf nodes excluding subset S. If there are sibling nodes in nodeN−S, then the sibling nodes are replaced by their parent nodes, which is denoted as nodeN−Smin. While LnodeN−Smin is the list containing the hashes of the nodes in nodeN−Smin, which can calculate Lroot with the hashes of the nodes in set S, then the verification proof is (20)PFS=C,pfS.Finally, the cloud sends the search result and proofI,PFS to the edge.Take the case ofn = 8 as an example, as shown in Figure 3. Assume S = 1,2,8 and search result I = f2,f8, then the verification proof is generated as follows:Auxiliary values:C=c1,1,c1,2,c2,1,c2,2,c8,1,c8,2.Thepathi from the node i to the root node is generated such thatLeaf nodei=1, pathi=1=1,9,13,rootLeaf nodei=2, pathi=2=2,9,13,rootLeaf nodei=8, pathi=8=8,12,14,rootThennodeN−Smin is computed as(21)nodeN−Smin=noden1,…,n8−n1,n2,n8min=noden3,n4,n5,n6,n7min=n10,n11,n7.Finally, we get(22)pfS=pathi,i∈S,L,nodeN−Smin=path1,path2,path8,L10,L11,L7.(7)
VerificationPP,I,PFS,BF,Lroot⟶1/0: Whenthe search proofs are recieved, the edge server does the following work.Figure 3
Merkle hash tree.Firstly, for each file indexi∈S, the edge computes Li′=H0ci,1ci,2, recovers Lroot′ based on pfS, and then verifies if Lroot′=Lroot. If holds, then C is correct. Otherwise, it is ⊥.Secondly, fori∈S, the edge computes the auxiliary verification value as(23)cwi=eTr⋅∏j∈S,j≠iϑn+1−j+i,c1,ie∏j∈Sϑn+1−j,c2,i,i∈S.Finally, the edge sends the search resultI and auxiliary verification value CW=cwi,i∈S to user.After receives the auxiliary verification value, the user can verify the search result:(24)verifyi=BFQueryH1,…,Hk,BFi,cwi,i∈S.If for eachi∈I, verifyi=1, and for each i∈S−I, verifyi=0, and then it outputs 1, which means the search result is correct and complete. Otherwise, it outputs 0.


## 5.1. System Model

The system model is shown in Figure2, which contains four entities: publisher, cloud server, edge server, and data user.(i)
Publisher. When the publisher has the shared data, it encrypts the data and outsources to the cloud. After the purchase action, the publisher distributes the corresponding keys to user and edge for the data query and verification.(ii)
Cloud Server. The cloud stores the uploading data and responds on the query. The cloud is not fully trustworthy.(iii)
Edge Server. The edge assists users with the query and verification operation. It is trusted and like a front-end server on the user side.(iv)
Data User. The users purchase data and obtain the search authorization, who can query data with the assistance of edge server.Figure 2
System model.


## 5.2. Formal Definition

(1)
Init1λ,n⟶PP: This algorithm is operated by the publisher. The algorithm inputs a security parameter λ and the maximum file number n and then outputs the system public parameters PP(2)
KeyGenPP⟶E,sk,PK: This algorithm is run by the publisher. The algorithm inputs the parameters PP and then outputs hash key E, publisher’s secret key sk, and public key PK(3)
EncryptPP,PK,W⟶C,BF,Lroot: This algorithm is run by the publisher, and it inputs parameters PP, public key PK, and keyword set W and then outputs the ciphertext set C, Bloom filter value set BF, and the root node value of a Merkle hash tree Lroot(4)
AuthorizationPP,sk,id,S⟶Aid,Kid: This algorithm is run by the publisher. The algorithm inputs parameters PP, secret key sk, user’s public identity id, and a subset SS⊆N and then outputs the authorization key Aid and identity key Kid(5)
TrapdoorE,Aid,w,Kid⟶Tr: The algorithm is operated by the data user and edge server. It takes the authorization key Aid, hash key E, keyword w, and identity key Kid as the input and then outputs the trapdoor Tr(6)
SearchPP,C,BF,Tr⟶I,PFS: This algorithm inputs parameters PP, the ciphertext set C, Bloom filter value set BF, and trapdoor Tr and then outputs the search result I and verification proof PFS(7)
VerificationPP,I,PFS,BF,Lroot⟶1/0: This algorithm takes public parameters PP, search result I, verification proof PFS, and publisher’s public key BF,Lroot as the input and then outputs 1 if the result is correct and complete; otherwise, it outputs 0Definition 1.
Our proposed scheme includes the below seven algorithms.


## 5.3. Requirements

### 5.3.1. Security

In our proposed scheme, the system should satisfy indistinguishability against selective-file chosen keyword attack (IND-SF-CKA) security [30].We used a game between a Challenger Cha and a polynomial-time Adversary Ad to define the model of IND-SF-CKA.(1)
Initial. Ad publishes the file set S∗ to be attacked.(2)
Setup. Cha builds the system and generates the public parameter and then sends the parameters and keyword space W to Ad.(3)
Process 1. Ad carries out a series of Authorized and Trapdoor queries as follows:Authorized query: Ad sends any file set S to Cha which cannot have any intersection with S∗ and receives the keys Aid,Kid computed by Cha through the algorithm Authorize PP,sk,id,S.Trapdoor query: Ad can adaptively enquire to Cha with any keyword w∈W in S and then Cha runs the algorithm Trapdoor E,Aid,w,Kid to generate the trapdoor Tr and sends it to Ad.(4)
Challenge. When Ad wants to finish Process 1, it generates two keywords of the same length in plain text w0,w1∈W. Cha randomly selects u∈0,1 and i∈S∗ and then operates the Encrypt algorithm to output the challenge ciphertext cw∗=EncryptPP,PK,wb and sends cw∗ to Ad.(5)
Process 2. Ad continuously sends the queries of Authorize and Trapdoor algorithms as in Process 1, the limit is the Authorize queries of S cannot have any intersection with S∗, and the Trapdoor query of w0 or w1 cannot be in S∗.(6)
Guess. Ad guesses the value ofu and outputs u′. Ad wins the game if u′=u. Set that Ad’s advantages over this game is(9)AdvAdscheme=Pru′=u−12.Definition 2.
The proposed scheme is IND-SF-CKA secure ifAdvAdscheme is negligible.


### 5.3.2. Consistency

Besides the security, the proposed scheme should satisfy the consistency when using the trapdoor for query [36].(10)PrSearchTrapdoorE,Aid,w′,Kid,EncryptPP,PK,w=1=0.Definition 3.
For all distinct keywordsw,w′∈0,1∗, the trapdoor with w′ and the cipher text for encrypting w is consistent if and only if the following probability holds true.T algorithm Search is always rejected when the keywordw′ contained in Trapdoor is different from the keyword w in Encrypt.


### 5.3.3. Correctness and Completeness

The proposed scheme should satisfy that the search result is correct and complete, which is defined as follows based on the definition in [37].(1)
Correctness:w⊂f1∧w⊂f2∧…∧w⊂ft(2)
Completeness:f1−Q∩f2−Q∩…∩fs−Q=∅, where Q=f1∩f2∩…∩ftDefinition 4.
For authorized file setS=1,2,,…,s and a keyword w for the query, the search result with I=f1,f2,…,ft is correct and complete when the below two terms are true.The correctness condition ensures that the search result contains keywordw, and the completeness condition guarantees the search result which includes all files containing keyword w. When the search result is correct and complete, the Verification algorithm would output 1; otherwise, it would output 0.


## 5.3.1. Security

In our proposed scheme, the system should satisfy indistinguishability against selective-file chosen keyword attack (IND-SF-CKA) security [30].We used a game between a Challenger Cha and a polynomial-time Adversary Ad to define the model of IND-SF-CKA.(1)
Initial. Ad publishes the file set S∗ to be attacked.(2)
Setup. Cha builds the system and generates the public parameter and then sends the parameters and keyword space W to Ad.(3)
Process 1. Ad carries out a series of Authorized and Trapdoor queries as follows:Authorized query: Ad sends any file set S to Cha which cannot have any intersection with S∗ and receives the keys Aid,Kid computed by Cha through the algorithm Authorize PP,sk,id,S.Trapdoor query: Ad can adaptively enquire to Cha with any keyword w∈W in S and then Cha runs the algorithm Trapdoor E,Aid,w,Kid to generate the trapdoor Tr and sends it to Ad.(4)
Challenge. When Ad wants to finish Process 1, it generates two keywords of the same length in plain text w0,w1∈W. Cha randomly selects u∈0,1 and i∈S∗ and then operates the Encrypt algorithm to output the challenge ciphertext cw∗=EncryptPP,PK,wb and sends cw∗ to Ad.(5)
Process 2. Ad continuously sends the queries of Authorize and Trapdoor algorithms as in Process 1, the limit is the Authorize queries of S cannot have any intersection with S∗, and the Trapdoor query of w0 or w1 cannot be in S∗.(6)
Guess. Ad guesses the value ofu and outputs u′. Ad wins the game if u′=u. Set that Ad’s advantages over this game is(9)AdvAdscheme=Pru′=u−12.Definition 2.
The proposed scheme is IND-SF-CKA secure ifAdvAdscheme is negligible.


## 5.3.2. Consistency

Besides the security, the proposed scheme should satisfy the consistency when using the trapdoor for query [36].(10)PrSearchTrapdoorE,Aid,w′,Kid,EncryptPP,PK,w=1=0.Definition 3.
For all distinct keywordsw,w′∈0,1∗, the trapdoor with w′ and the cipher text for encrypting w is consistent if and only if the following probability holds true.T algorithm Search is always rejected when the keywordw′ contained in Trapdoor is different from the keyword w in Encrypt.


## 5.3.3. Correctness and Completeness

The proposed scheme should satisfy that the search result is correct and complete, which is defined as follows based on the definition in [37].(1)
Correctness:w⊂f1∧w⊂f2∧…∧w⊂ft(2)
Completeness:f1−Q∩f2−Q∩…∩fs−Q=∅, where Q=f1∩f2∩…∩ftDefinition 4.
For authorized file setS=1,2,,…,s and a keyword w for the query, the search result with I=f1,f2,…,ft is correct and complete when the below two terms are true.The correctness condition ensures that the search result contains keywordw, and the completeness condition guarantees the search result which includes all files containing keyword w. When the search result is correct and complete, the Verification algorithm would output 1; otherwise, it would output 0.


## 5.4. The Proposed Scheme

### 5.4.1. Overview

In scheme [15], the fundamental reason why the cloud can launch forgery attacks is that the verification process requires cloud to participate in calculation, and the flow is “publisher computing - > cloud computing - > user computing, so the users will not know whether the cloud has forged proof. In our design, we changed the verification flow to “publisher computing - > public proof - > user computing,” And the cloud does not participate in computing but only forwards the data. Besides, in the phase of “public proof,” we use the Merkle hash tree to ensure that the proof is not tampered with by the cloud, thus guaranteeing the correctness and completeness of search data.Secondly, in the index encryption phase of existing researches [13–15, 29–31], they encrypt every keyword associated with each file and then upload them. Consequently, the search function needs to match whether the query value is equal to each keyword, which will greatly affect the search efficiency. In our design, we store each file’s keyword set in a Bloom filter; that is, only one string is uploaded for one file. Hence, during the keyword processing, the communication and storage cost is greatly reduced, and the overhead is related to the number of files but not to the number of keywords.Thirdly, in the existing works [13–15, 32, 33], the verification process are mostly based on the cloud computing environment, and users need to perform generous calculations to verify, which is unacceptable for some resource-constrained clients. In this paper, the edge server is introduced to assist users in search and verification, which greatly reduces the computation overhead for users and make them more comfortable.


### 5.4.2. Construction

Based on the definition described in 5.2, we propose a concrete construction as follows:(1)
Init1λ,n⟶PP: The publisher generates the public parameters as given below.Generates a bilinear map systemB=p,G,G1,e⋅,⋅, where p is the order of G and 2λ≤p≤2λ+1.Setsn as the maximum number of files and then the complete file index set N=1,…,n.Picks a random generatorϑ∈G and a random number a∈ℤp and computes ϑi=ϑai, for i=1,2,…,n,n+2,…,2n.Chooses a collision-free hash function used for the Merkle hash tree:H0:0,1∗⟶G.Choosesl as the maximum length of Bloom filter, and k independent universal hash functions: H1,…,Hk:0,1∗⟶0,1l.Chooses a keyed hash functionH:0,1∗⟶G.Then the system public parameters are(11)PP=B,ϑ,ϑ1,…,ϑn,ϑn+2,…,ϑ2n,H0,H1,…,Hk,Hkey.(2)
KeyGenPP⟶E,sk,PK: The publisher generates a random string E as the hash key and chooses a random number γ∈ℤp as the secret key, then the public key is(12)PK=υ=ϑγ.(3)
EncryptPP,PK,W⟶C,BF,Lroot: The publisher encrypts the files and keywords as follows:Firstly, for each file indexi∈N, we get those as follows:Generates an empty Bloom filterBFi=BFInit.Randomly chooses an integert∈ℤp and computes two encryption auxiliary values:(13)ci,1=ϑt,ci,2=υ⋅ϑit.For the keywordswijj∈1,…,x contained by the i-th file, we getThen setBF=BFi,i∈N.Secondly, the publisher generates a MHT withn leaf nodes to guarantee the correctness of the file auxiliary values. Then the MHT is built as follows:Each leaf node’s value is a hash of two auxiliary values such as(14)Li=H0ci,1ci,2,i∈N.Each nonleaf node’s value is a hash of its two children nodes and then the root node’s valueLroot can also be determined.Finally, the publisher uploadsC=ci,1,ci,2i∈N to the cloud and adds BF and Lroot to his/her public key as(15)PK=υ,BF,Lroot.Note that the cloud can rebuilt the MHT since it has the encryption auxiliary valuesC.(4)
AuthorizationPP,sk,id,S⟶Aid,Kid: For user’s public identity id and authorization file subset S⊆N, the publisher computes as(16)Aid=idγ,Kid=∏j∈Sϑn+1−jγAid,and then sends the authorization keyE,Aid to user and identity key Kid to edge.(5)
TrapdoorE,Aid,w,Kid⟶Tr: For the keyword w, the user generates the search query Q and sends to edge server as(17)Q=HEw⋅Aid.When the search query is recieved, the edge first verifies the user’s public identity, then uses the corresponding identity key to compute the trapdoor, and sends to cloud:(18)Tr=Kid⋅Q.(6)
SearchPP,C,BF,Tr⟶I,PFS: On receiving Tr, the cloud server does the following works.Firstly, for each file indexi∈S:Computes the corresponding ciphertext for thei-th file as(19)cwi=eTr⋅∏j∈S,j≠iϑn+1−j+i,c1,ie∏j∈Sϑn+1−j,c2,i.Gets the matching result of thei-th file through the Bloom filter asIftesti=1, the file fi is added to the result set I.Secondly, the cloud server constructs the verification proofPFS as follows:Auxiliary valuesC=ci,1,ci,2,i∈S.Merkle hash tree proof is denoted aspfS:wherepathi is a list of nodes that denotes the path from leaf node i to the root node of Merkle hash tree. Let nodeN−S be a list of leaf nodes excluding subset S. If there are sibling nodes in nodeN−S, then the sibling nodes are replaced by their parent nodes, which is denoted as nodeN−Smin. While LnodeN−Smin is the list containing the hashes of the nodes in nodeN−Smin, which can calculate Lroot with the hashes of the nodes in set S, then the verification proof is (20)PFS=C,pfS.Finally, the cloud sends the search result and proofI,PFS to the edge.Take the case ofn = 8 as an example, as shown in Figure 3. Assume S = 1,2,8 and search result I = f2,f8, then the verification proof is generated as follows:Auxiliary values:C=c1,1,c1,2,c2,1,c2,2,c8,1,c8,2.Thepathi from the node i to the root node is generated such thatLeaf nodei=1, pathi=1=1,9,13,rootLeaf nodei=2, pathi=2=2,9,13,rootLeaf nodei=8, pathi=8=8,12,14,rootThennodeN−Smin is computed as(21)nodeN−Smin=noden1,…,n8−n1,n2,n8min=noden3,n4,n5,n6,n7min=n10,n11,n7.Finally, we get(22)pfS=pathi,i∈S,L,nodeN−Smin=path1,path2,path8,L10,L11,L7.(7)
VerificationPP,I,PFS,BF,Lroot⟶1/0: Whenthe search proofs are recieved, the edge server does the following work.Figure 3
Merkle hash tree.Firstly, for each file indexi∈S, the edge computes Li′=H0ci,1ci,2, recovers Lroot′ based on pfS, and then verifies if Lroot′=Lroot. If holds, then C is correct. Otherwise, it is ⊥.Secondly, fori∈S, the edge computes the auxiliary verification value as(23)cwi=eTr⋅∏j∈S,j≠iϑn+1−j+i,c1,ie∏j∈Sϑn+1−j,c2,i,i∈S.Finally, the edge sends the search resultI and auxiliary verification value CW=cwi,i∈S to user.After receives the auxiliary verification value, the user can verify the search result:(24)verifyi=BFQueryH1,…,Hk,BFi,cwi,i∈S.If for eachi∈I, verifyi=1, and for each i∈S−I, verifyi=0, and then it outputs 1, which means the search result is correct and complete. Otherwise, it outputs 0.


## 5.4.1. Overview

In scheme [15], the fundamental reason why the cloud can launch forgery attacks is that the verification process requires cloud to participate in calculation, and the flow is “publisher computing - > cloud computing - > user computing, so the users will not know whether the cloud has forged proof. In our design, we changed the verification flow to “publisher computing - > public proof - > user computing,” And the cloud does not participate in computing but only forwards the data. Besides, in the phase of “public proof,” we use the Merkle hash tree to ensure that the proof is not tampered with by the cloud, thus guaranteeing the correctness and completeness of search data.Secondly, in the index encryption phase of existing researches [13–15, 29–31], they encrypt every keyword associated with each file and then upload them. Consequently, the search function needs to match whether the query value is equal to each keyword, which will greatly affect the search efficiency. In our design, we store each file’s keyword set in a Bloom filter; that is, only one string is uploaded for one file. Hence, during the keyword processing, the communication and storage cost is greatly reduced, and the overhead is related to the number of files but not to the number of keywords.Thirdly, in the existing works [13–15, 32, 33], the verification process are mostly based on the cloud computing environment, and users need to perform generous calculations to verify, which is unacceptable for some resource-constrained clients. In this paper, the edge server is introduced to assist users in search and verification, which greatly reduces the computation overhead for users and make them more comfortable.


## 5.4.2. Construction

Based on the definition described in 5.2, we propose a concrete construction as follows:(1)
Init1λ,n⟶PP: The publisher generates the public parameters as given below.Generates a bilinear map systemB=p,G,G1,e⋅,⋅, where p is the order of G and 2λ≤p≤2λ+1.Setsn as the maximum number of files and then the complete file index set N=1,…,n.Picks a random generatorϑ∈G and a random number a∈ℤp and computes ϑi=ϑai, for i=1,2,…,n,n+2,…,2n.Chooses a collision-free hash function used for the Merkle hash tree:H0:0,1∗⟶G.Choosesl as the maximum length of Bloom filter, and k independent universal hash functions: H1,…,Hk:0,1∗⟶0,1l.Chooses a keyed hash functionH:0,1∗⟶G.Then the system public parameters are(11)PP=B,ϑ,ϑ1,…,ϑn,ϑn+2,…,ϑ2n,H0,H1,…,Hk,Hkey.(2)
KeyGenPP⟶E,sk,PK: The publisher generates a random string E as the hash key and chooses a random number γ∈ℤp as the secret key, then the public key is(12)PK=υ=ϑγ.(3)
EncryptPP,PK,W⟶C,BF,Lroot: The publisher encrypts the files and keywords as follows:Firstly, for each file indexi∈N, we get those as follows:Generates an empty Bloom filterBFi=BFInit.Randomly chooses an integert∈ℤp and computes two encryption auxiliary values:(13)ci,1=ϑt,ci,2=υ⋅ϑit.For the keywordswijj∈1,…,x contained by the i-th file, we getThen setBF=BFi,i∈N.Secondly, the publisher generates a MHT withn leaf nodes to guarantee the correctness of the file auxiliary values. Then the MHT is built as follows:Each leaf node’s value is a hash of two auxiliary values such as(14)Li=H0ci,1ci,2,i∈N.Each nonleaf node’s value is a hash of its two children nodes and then the root node’s valueLroot can also be determined.Finally, the publisher uploadsC=ci,1,ci,2i∈N to the cloud and adds BF and Lroot to his/her public key as(15)PK=υ,BF,Lroot.Note that the cloud can rebuilt the MHT since it has the encryption auxiliary valuesC.(4)
AuthorizationPP,sk,id,S⟶Aid,Kid: For user’s public identity id and authorization file subset S⊆N, the publisher computes as(16)Aid=idγ,Kid=∏j∈Sϑn+1−jγAid,and then sends the authorization keyE,Aid to user and identity key Kid to edge.(5)
TrapdoorE,Aid,w,Kid⟶Tr: For the keyword w, the user generates the search query Q and sends to edge server as(17)Q=HEw⋅Aid.When the search query is recieved, the edge first verifies the user’s public identity, then uses the corresponding identity key to compute the trapdoor, and sends to cloud:(18)Tr=Kid⋅Q.(6)
SearchPP,C,BF,Tr⟶I,PFS: On receiving Tr, the cloud server does the following works.Firstly, for each file indexi∈S:Computes the corresponding ciphertext for thei-th file as(19)cwi=eTr⋅∏j∈S,j≠iϑn+1−j+i,c1,ie∏j∈Sϑn+1−j,c2,i.Gets the matching result of thei-th file through the Bloom filter asIftesti=1, the file fi is added to the result set I.Secondly, the cloud server constructs the verification proofPFS as follows:Auxiliary valuesC=ci,1,ci,2,i∈S.Merkle hash tree proof is denoted aspfS:wherepathi is a list of nodes that denotes the path from leaf node i to the root node of Merkle hash tree. Let nodeN−S be a list of leaf nodes excluding subset S. If there are sibling nodes in nodeN−S, then the sibling nodes are replaced by their parent nodes, which is denoted as nodeN−Smin. While LnodeN−Smin is the list containing the hashes of the nodes in nodeN−Smin, which can calculate Lroot with the hashes of the nodes in set S, then the verification proof is (20)PFS=C,pfS.Finally, the cloud sends the search result and proofI,PFS to the edge.Take the case ofn = 8 as an example, as shown in Figure 3. Assume S = 1,2,8 and search result I = f2,f8, then the verification proof is generated as follows:Auxiliary values:C=c1,1,c1,2,c2,1,c2,2,c8,1,c8,2.Thepathi from the node i to the root node is generated such thatLeaf nodei=1, pathi=1=1,9,13,rootLeaf nodei=2, pathi=2=2,9,13,rootLeaf nodei=8, pathi=8=8,12,14,rootThennodeN−Smin is computed as(21)nodeN−Smin=noden1,…,n8−n1,n2,n8min=noden3,n4,n5,n6,n7min=n10,n11,n7.Finally, we get(22)pfS=pathi,i∈S,L,nodeN−Smin=path1,path2,path8,L10,L11,L7.(7)
VerificationPP,I,PFS,BF,Lroot⟶1/0: Whenthe search proofs are recieved, the edge server does the following work.Figure 3
Merkle hash tree.Firstly, for each file indexi∈S, the edge computes Li′=H0ci,1ci,2, recovers Lroot′ based on pfS, and then verifies if Lroot′=Lroot. If holds, then C is correct. Otherwise, it is ⊥.Secondly, fori∈S, the edge computes the auxiliary verification value as(23)cwi=eTr⋅∏j∈S,j≠iϑn+1−j+i,c1,ie∏j∈Sϑn+1−j,c2,i,i∈S.Finally, the edge sends the search resultI and auxiliary verification value CW=cwi,i∈S to user.After receives the auxiliary verification value, the user can verify the search result:(24)verifyi=BFQueryH1,…,Hk,BFi,cwi,i∈S.If for eachi∈I, verifyi=1, and for each i∈S−I, verifyi=0, and then it outputs 1, which means the search result is correct and complete. Otherwise, it outputs 0.


## 6. Requirements Analysis

### 6.1. Security

We will prove that our scheme is IND-SF-CKA secure under the standard model based on the Decisionl-BDHE assumption. The security is verified by the below theorem.Theorem 1.
If the decisionl-BDHE problem is hard to solve, then our proposed scheme satisfies the IND-SF-CKA security.Proof.
Suppose there is an Adversary Ad which can destroy the IND-SF-CKA security of the proposed scheme, then a Challenger Cha can build an AlgorithmD to solve the decision l-BDHE problem. This contradicts our hypothesis that the decision l-BDHE problem is hard to solve; thus, it is proved that the scheme is IND-SF-CKA secure.
SupposeD is given as an instance of decision l-BDHE problem, which includes a bilinear pairing system e:B=p,G,G1,e⋅,⋅ and parameters ϑi=ϑai, for i=1,2,…,l,l+2,…,2l, where a is unknown. Then D is further given as h∈G, Z∈G1. At last, the input is h,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,Z, and D needs to decide if Z=eϑal+1,h or Z is a random value in G1.
D simulates the Challenger Cha to begin a game with Ad as follows:(1)
Initial:D receives the file set S∗ that Ad wants to be challenged. Then D gets the parameters h,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,Z of the decision l-BDHE problem.(2)
Setup:D generates some other parameters and then provides them with the given parameters to Ad as follows:(1)
Chooses a hash functionH:0,1∗⟶G.(2)
SetsW as the keyword space.(3)
Randomly choosesr∈ℤp, a file index i∈S∗, and sets PK=ϑr/ϑi, where ϑi is from the given parameters ϑai, which is corresponding to the chosen class i, then the sk is r−ai which is unknown.ThenD sends B,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,HW,PK to Ad.(3)
Process 1: Ad carries out a series of adaptive queries:Authorize query: Ad can query any file setS, where S∩S∗=0. Then D computes(25)Aid=idγ,Kid=∏j∈Sϑn+1−jγ−ai=∏j∈Sϑn+1−jγ/ϑn+1−j+iAid,and sendsAid,Kid back.Trapdoor query: Ad can query any file setS and any keyword w, where S∩S∗=0, w∈W. Then D generates Tr=Aid⋅HEw⋅Kid, and sends Tr to Ad.(4)
Challenge: When Ad determines to finish Process 1, it sends two equal length keywordsw0,w1∈W to D, which cannot be the same as the Trapdoor query of Process 1 before. Then D performs the following operations:(1)
Randomly picks a coinu∈0,1.(2)
Setsh=ϑt, where t is unknown, thusHere,PK=ϑr/ϑi, then C∗=c1=h,c2=hr,cw=eHEwu,h/Z is sent to Ad. Notice that if Z=eϑal+1,h, then cw=eHEwb,h/eϑal+1,h, and C∗ is a valid ciphertext of encrypting the keyword wu with the class i. Otherwise, Z is a random element in G1.(5)
Process 2: Similar to Process 1, Ad continues to conduct Authorize and Trapdoor queries, andD adopts the same strategy to reply.(6)
Guess: Ad guesses the value ofu and outputs u′. If u′=u, then D outputs 1, which means Z=eϑal+1,h. Otherwise, the output is 0 implies Z is a random value in G1.(7)
Probability analysis: IfZ=eϑal+1,h, then C∗ is valid. Otherwise, Z is a random value in G1, and C∗ is an invalid ciphertext. In such case, the advantage of Ad is equal to 1/2. If Ad successfully implements IND-SF-CKA to the scheme by the advantage of ε as Pru′=u−1/2≥ε, then D can solve the decision l-BDHE problem by the advantage ADVDDecisionl−BDHE=|PrDh,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,Z,0−PrDh,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,Z≠eϑ,hal+1=0|≥ε=eϑ,hal+1. However, this is contrary to Definition 2, so Ad cannot implement IND-SF-CKA to the scheme by the advantage of ε.
Therefore, the proposed scheme satisfies the IND-SF-CKA security.


### 6.2. Consistency

Proof.IfHkey is collision-free, then there must be different keywords w,w′∈W so that HEw≠HEw′. According to equations (3)–(5), we can get(26)cwi=eTr⋅∏j∈S,j≠iϑn+1−j+i,c1,ie∏j∈Sϑn+1−j,c2,i,=eAid⋅HEw⋅Kid⋅∏j∈S,j≠iϑn+1−j+i,ϑte∏j∈Sϑn+1−j,υ⋅ϑit,=e∏j∈Sϑn+1−jγ⋅HEw⋅∏j∈S,j≠iϑn+1−j+i,ϑte∏j∈Sϑn+1−j,υt⋅e∏j∈Sϑn+1−j,ϑit,=e∏j∈Sϑn+1−jγ,ϑte∏j∈S,j≠iϑn+1−j+i,ϑteHEw,ϑte∏j∈Sϑn+1−j,υt⋅e∏j∈Sϑn+1−j,ϑit,=eHEw,ϑteϑ1,ϑnt.Theorem 2.
IfHkey is a collision-free hash function, then the proposed scheme is consistent.Then for the same keyword, the cloud uses TrapdoorTr to generate the matching ciphertext cwi, which is equal to the encrypted keyword generated by the publisher, then(27)PrSearchTrapdoorE,Aid,w,Kid,EncryptPP,PK,w=1=0.Therefore, the proposed scheme is consistent.


### 6.3. Correctness and Completeness

Theorem 3.
IfH1,…,Hk are random and the Bloom filter has a low false-positive rate, then the user can verify whether the result is correct and complete.Proof.
Correctness: In Theorem2, our scheme is proved to be consistent. Then (27) can be used to ensure the return files are correct. Suppose the Bloom filter has a low false-positive rate, when (27) is equal to 1, it means the i-th file contains the keyword w: w⊂fi.
Completeness: In our scheme, for the file setS=f1,f2,,…,fs, and given a query keyword w from a user, the cloud returns the search result I=f1,f2,…,ft,t≤s. With equations (7) and (8), if for each i∈I, it satisfies verifyi=1, and for each i∈S−I, it satisfies verifyi=0, then f1−Q∩f2−Q∩…∩fs−Q=∅, where Q=f1∩f2∩…∩ft, so that the search result is complete; that is, the cloud server returns all files that include the keyword w and does not return the files that do not include the keyword w. Otherwise, it is incomplete. Meanwhile, the correction of the encryption auxiliary value is guaranteed by the Merkle hash tree, which the cloud cannot forge.
Therefore, the user can verify whether the result is correct and complete.


## 6.1. Security

We will prove that our scheme is IND-SF-CKA secure under the standard model based on the Decisionl-BDHE assumption. The security is verified by the below theorem.Theorem 1.
If the decisionl-BDHE problem is hard to solve, then our proposed scheme satisfies the IND-SF-CKA security.Proof.
Suppose there is an Adversary Ad which can destroy the IND-SF-CKA security of the proposed scheme, then a Challenger Cha can build an AlgorithmD to solve the decision l-BDHE problem. This contradicts our hypothesis that the decision l-BDHE problem is hard to solve; thus, it is proved that the scheme is IND-SF-CKA secure.
SupposeD is given as an instance of decision l-BDHE problem, which includes a bilinear pairing system e:B=p,G,G1,e⋅,⋅ and parameters ϑi=ϑai, for i=1,2,…,l,l+2,…,2l, where a is unknown. Then D is further given as h∈G, Z∈G1. At last, the input is h,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,Z, and D needs to decide if Z=eϑal+1,h or Z is a random value in G1.
D simulates the Challenger Cha to begin a game with Ad as follows:(1)
Initial:D receives the file set S∗ that Ad wants to be challenged. Then D gets the parameters h,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,Z of the decision l-BDHE problem.(2)
Setup:D generates some other parameters and then provides them with the given parameters to Ad as follows:(1)
Chooses a hash functionH:0,1∗⟶G.(2)
SetsW as the keyword space.(3)
Randomly choosesr∈ℤp, a file index i∈S∗, and sets PK=ϑr/ϑi, where ϑi is from the given parameters ϑai, which is corresponding to the chosen class i, then the sk is r−ai which is unknown.ThenD sends B,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,HW,PK to Ad.(3)
Process 1: Ad carries out a series of adaptive queries:Authorize query: Ad can query any file setS, where S∩S∗=0. Then D computes(25)Aid=idγ,Kid=∏j∈Sϑn+1−jγ−ai=∏j∈Sϑn+1−jγ/ϑn+1−j+iAid,and sendsAid,Kid back.Trapdoor query: Ad can query any file setS and any keyword w, where S∩S∗=0, w∈W. Then D generates Tr=Aid⋅HEw⋅Kid, and sends Tr to Ad.(4)
Challenge: When Ad determines to finish Process 1, it sends two equal length keywordsw0,w1∈W to D, which cannot be the same as the Trapdoor query of Process 1 before. Then D performs the following operations:(1)
Randomly picks a coinu∈0,1.(2)
Setsh=ϑt, where t is unknown, thusHere,PK=ϑr/ϑi, then C∗=c1=h,c2=hr,cw=eHEwu,h/Z is sent to Ad. Notice that if Z=eϑal+1,h, then cw=eHEwb,h/eϑal+1,h, and C∗ is a valid ciphertext of encrypting the keyword wu with the class i. Otherwise, Z is a random element in G1.(5)
Process 2: Similar to Process 1, Ad continues to conduct Authorize and Trapdoor queries, andD adopts the same strategy to reply.(6)
Guess: Ad guesses the value ofu and outputs u′. If u′=u, then D outputs 1, which means Z=eϑal+1,h. Otherwise, the output is 0 implies Z is a random value in G1.(7)
Probability analysis: IfZ=eϑal+1,h, then C∗ is valid. Otherwise, Z is a random value in G1, and C∗ is an invalid ciphertext. In such case, the advantage of Ad is equal to 1/2. If Ad successfully implements IND-SF-CKA to the scheme by the advantage of ε as Pru′=u−1/2≥ε, then D can solve the decision l-BDHE problem by the advantage ADVDDecisionl−BDHE=|PrDh,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,Z,0−PrDh,ϑ,ϑa,ϑa2,…,ϑal,ϑal+2,…,ϑa2l,Z≠eϑ,hal+1=0|≥ε=eϑ,hal+1. However, this is contrary to Definition 2, so Ad cannot implement IND-SF-CKA to the scheme by the advantage of ε.
Therefore, the proposed scheme satisfies the IND-SF-CKA security.


## 6.2. Consistency

Proof.IfHkey is collision-free, then there must be different keywords w,w′∈W so that HEw≠HEw′. According to equations (3)–(5), we can get(26)cwi=eTr⋅∏j∈S,j≠iϑn+1−j+i,c1,ie∏j∈Sϑn+1−j,c2,i,=eAid⋅HEw⋅Kid⋅∏j∈S,j≠iϑn+1−j+i,ϑte∏j∈Sϑn+1−j,υ⋅ϑit,=e∏j∈Sϑn+1−jγ⋅HEw⋅∏j∈S,j≠iϑn+1−j+i,ϑte∏j∈Sϑn+1−j,υt⋅e∏j∈Sϑn+1−j,ϑit,=e∏j∈Sϑn+1−jγ,ϑte∏j∈S,j≠iϑn+1−j+i,ϑteHEw,ϑte∏j∈Sϑn+1−j,υt⋅e∏j∈Sϑn+1−j,ϑit,=eHEw,ϑteϑ1,ϑnt.Theorem 2.
IfHkey is a collision-free hash function, then the proposed scheme is consistent.Then for the same keyword, the cloud uses TrapdoorTr to generate the matching ciphertext cwi, which is equal to the encrypted keyword generated by the publisher, then(27)PrSearchTrapdoorE,Aid,w,Kid,EncryptPP,PK,w=1=0.Therefore, the proposed scheme is consistent.


## 6.3. Correctness and Completeness

Theorem 3.
IfH1,…,Hk are random and the Bloom filter has a low false-positive rate, then the user can verify whether the result is correct and complete.Proof.
Correctness: In Theorem2, our scheme is proved to be consistent. Then (27) can be used to ensure the return files are correct. Suppose the Bloom filter has a low false-positive rate, when (27) is equal to 1, it means the i-th file contains the keyword w: w⊂fi.
Completeness: In our scheme, for the file setS=f1,f2,,…,fs, and given a query keyword w from a user, the cloud returns the search result I=f1,f2,…,ft,t≤s. With equations (7) and (8), if for each i∈I, it satisfies verifyi=1, and for each i∈S−I, it satisfies verifyi=0, then f1−Q∩f2−Q∩…∩fs−Q=∅, where Q=f1∩f2∩…∩ft, so that the search result is complete; that is, the cloud server returns all files that include the keyword w and does not return the files that do not include the keyword w. Otherwise, it is incomplete. Meanwhile, the correction of the encryption auxiliary value is guaranteed by the Merkle hash tree, which the cloud cannot forge.
Therefore, the user can verify whether the result is correct and complete.


## 7. Performance

### 7.1. Performance Analysis

In this section, we compare the other two related schemes [14, 15, 29] in terms of various costs so as to analyze the performance. We define the below notations in Table 1.Table 1
Notations.
NotationMeaningMulGMultiplication manipulation inG or G1ExGExponentiation manipulation inG or G1ExℤpExponentiation manipulation inℤppairPairing operationHHash operationnTotal file numberrThe average number of keywords per filelThe length of an element in Bloom filtermThe length of Merkle hash tree nodepThe size of an element inGqThe size of an element inG1


#### 7.1.1. Functionality

We show the function comparison in Table2, and we can see that all schemes realize the function of fine-grained authorization. In the verification function, scheme [14] can only verify the correctness, and scheme [15] can verify the correctness and completeness but exists security defect, and scheme [29] does not consider the verification module, while our scheme implements all the verification in the cloud-edge environment.Table 2
Functionality comparison.
SchemeFine-grained authorizationCompletenessEnvironmentScheme [14]YesYes/noCloudScheme [15]YesSecurity defectCloudScheme [29]YesNo/noCloudOur schemeYesYes/yesCloud-edge


#### 7.1.2. Computation Cost

The comparison results of computation cost for several schemes are shown in Table3, and it demonstrates that our scheme has less computation overhead than schemes [14, 15] on the whole.Table 3
Computation cost comparison.
SchemeInitKeyGenScheme [14]2nExℤp+ExGExGScheme [15]2nExℤp+ExGExGScheme [29]2nExℤp+ExGExGOur scheme2nExℤp+ExGExGSchemeAuthorizationEncryptScheme [14]nExG4nr⋅ExG+3n⋅MulG+2nr⋅pairScheme [15]nExG3n+nrExG+2nr+npairScheme [29]nExG2n+nrExG+2nr⋅pairOur schemen+1ExG2n+nrExG+2nr⋅pairSchemeTrapdoorSearchScheme [14]MulG2n+1MulG+ExG+4n⋅pairScheme [15]MulG6n⋅MulG+4n⋅pairScheme [29]MulG3n⋅MulG+2n⋅pairOur schemeMulG3n⋅MulG+2n⋅pairSchemeVerificationuserVerificationuserScheme [14]n⋅MulG+n⋅pairScheme [15]n⋅MulG+n⋅pair—Scheme [29]——Our schemen⋅H3n⋅MulG+2n⋅pairIn the phases of Init, KeyGen, Extract, and Trapdoor, all four schemes have the same efficiency, which is because the parameters and data generated are alike. Note that the hash computation overhead isO1, which is far more cheaper than others, so we did not include it to the statistic.In the Encrypt phase, our scheme generates2n parameters and nr ciphertexts, which is the same as scheme [29]. While scheme [14] needs to generate 3n parameters and nr ciphertexts, and scheme [15] generates 4n parameters and nr ciphertexts, so the Encrypt process overhead of our scheme is less than schemes [14, 15].In the Search phase, the overhead of our scheme is the same as scheme [29] and is less than schemes [14, 15].In the Verification phases, the user overhead of our scheme is less than schemes [14, 15], which is because the edge server undertakes most calculations.Then, the total computational cost of our scheme is less than schemes [14, 15].


#### 7.1.3. Communication Cost

Table4 shows the communication overhead comparison as it can be seen that our scheme has less communication overhead than other schemes overall.Table 4
Communication cost comparison.
SchemeEncryptTrapdoorSearchScheme [14]2np+nrq+nrppn+np+nrqScheme [15]2np+nq+nrq+nlpn+np+nq+nlScheme [29]2np+nrqpnOur scheme2np+nlpn+2np+nmIn the Encrypt phase, our scheme has less cost than other schemes and that is because our scheme uploads only one Bloom filter value for one file, and other schemes need to upload all the encrypted keywords. Then the communication cost of our scheme for keyword cipher text processing is related to the number of files but not to the number of keywords. Note that the number of files isn and the number of keywords in each file is k, then our scheme only needs to pass n Bloom filter values and 2n elements in G to the cloud. While scheme [29] needs to transmit 2n elements in G and nr elements in G1, scheme [14] needs to transmit 2n+nr elements in G and nr elements in G1, and scheme [15] has the the biggest overhead which needs to transmit 2n elements in G, n+nr elements in G1, and n elements of Bloom filter.In the Trapdoor phase, all schemes have the same communication overhead.In the Search phase, all four schemes need to returnn-bits search results, and scheme [14] still needs to transmit two auxiliary values np+nrq for verification, and scheme [15] still needs to transmit three auxiliary values np+nq+nl for verification, while our scheme needs two auxiliary values 2np+nm.Since the scheme [29] has no verification function, the communication cost of our scheme is higher than scheme [29] but is less than schemes [14, 15].


#### 7.1.4. Storage Cost

We display the storage cost comparison in Table5, which demonstrates that our scheme has less storage overhead than other two schemes in general.Table 5
Storage cost comparison.
SchemePublisherUserCloudScheme [14]pp2np+nrq+nrpScheme [15]pp2np+nq+nrq+nlScheme [29]pp2np+nrqOur schemep2p2np+nlIn the publisher/data owner side, all schemes store one key, and then they have the same cost withp.In the user side, our scheme stores two keys, and other schemes only need to store one key.In the cloud side, our scheme has less storage cost than other three schemes. In our scheme, the cloud server only needs to store one Bloom filter value for one file, while other two schemes need to store all the encrypted keywords. Therefore, the cloud’s storage cost in our scheme is only related to the number of files and others are related to the number of keywords. Then our scheme needs2n elements in G and n elements of Bloom filter to store, while scheme [29] stores 2n elements in G and nr elements in G1, scheme [14] stores 2n+nr elements in G and nr elements in G1, and scheme [15] stores 2n elements in G, n+nr elements in G1, and n elements of Bloom filter.Therefore, our scheme has less storage cost than other three schemes.


### 7.2. Experimental Results

To assess the actual performance, we carry out the comparison experiments with schemes [14, 15, 29]. We use the latest JPBC library to deploy the archetypes of these schemes. Our experiments run on a computer with Intel Core i5-6550 CPU working in theWindows 7 system. We used the Enron database as the source, which extracted 10 thousands documents, 6 thousands keywords, and 80 thousands keyword-document pairs, of which most files matched fewer than 10 keywords. We selected the Type-A pairing to complete the specific algorithm, and then experimented with different number of files and keywords within four schemes. The experiment results are consistent with our performance analysis, as shown in Figure 4.Figure 4
Time cost comparison. (a) Time cost of Init. (b) Time cost of Keygen. (c) Time cost of Authorization. (d) Time cost of Encrypt. (e) Time cost of Trapdoor. (f) Time cost of search. (g) Time cost of verification.
(a)(b)(c)(d)(e)(f)(g)In the Init and Authorization phases, all schemes have the same computation cost, which is liner increasing with the number of files, as shown in Figures4(a) and 4(c).In the KeyGen and Trapdoor phases, all schemes have the same operation time for different numbers of files, as shown in Figures4(b) and 4(e).In the the Encrypt and Search phases, our scheme has the same operation time as scheme [29], which is less than schemes [14, 15], as shown in Figures 4(d) and 4(f).In the Verification phase, Figure4(g) shows that the user side of our scheme has less computational time than schemes [14, 15], which is because the edge completes most of the calculations, and the user only need to hash to get the verification results. Note that scheme [29] cannot achieve the verification function.To sum up the experiments, the overall operation time of our scheme is lower than schemes [14, 15] with all processes.


## 7.1. Performance Analysis

In this section, we compare the other two related schemes [14, 15, 29] in terms of various costs so as to analyze the performance. We define the below notations in Table 1.Table 1
Notations.
NotationMeaningMulGMultiplication manipulation inG or G1ExGExponentiation manipulation inG or G1ExℤpExponentiation manipulation inℤppairPairing operationHHash operationnTotal file numberrThe average number of keywords per filelThe length of an element in Bloom filtermThe length of Merkle hash tree nodepThe size of an element inGqThe size of an element inG1


### 7.1.1. Functionality

We show the function comparison in Table2, and we can see that all schemes realize the function of fine-grained authorization. In the verification function, scheme [14] can only verify the correctness, and scheme [15] can verify the correctness and completeness but exists security defect, and scheme [29] does not consider the verification module, while our scheme implements all the verification in the cloud-edge environment.Table 2
Functionality comparison.
SchemeFine-grained authorizationCompletenessEnvironmentScheme [14]YesYes/noCloudScheme [15]YesSecurity defectCloudScheme [29]YesNo/noCloudOur schemeYesYes/yesCloud-edge


### 7.1.2. Computation Cost

The comparison results of computation cost for several schemes are shown in Table3, and it demonstrates that our scheme has less computation overhead than schemes [14, 15] on the whole.Table 3
Computation cost comparison.
SchemeInitKeyGenScheme [14]2nExℤp+ExGExGScheme [15]2nExℤp+ExGExGScheme [29]2nExℤp+ExGExGOur scheme2nExℤp+ExGExGSchemeAuthorizationEncryptScheme [14]nExG4nr⋅ExG+3n⋅MulG+2nr⋅pairScheme [15]nExG3n+nrExG+2nr+npairScheme [29]nExG2n+nrExG+2nr⋅pairOur schemen+1ExG2n+nrExG+2nr⋅pairSchemeTrapdoorSearchScheme [14]MulG2n+1MulG+ExG+4n⋅pairScheme [15]MulG6n⋅MulG+4n⋅pairScheme [29]MulG3n⋅MulG+2n⋅pairOur schemeMulG3n⋅MulG+2n⋅pairSchemeVerificationuserVerificationuserScheme [14]n⋅MulG+n⋅pairScheme [15]n⋅MulG+n⋅pair—Scheme [29]——Our schemen⋅H3n⋅MulG+2n⋅pairIn the phases of Init, KeyGen, Extract, and Trapdoor, all four schemes have the same efficiency, which is because the parameters and data generated are alike. Note that the hash computation overhead isO1, which is far more cheaper than others, so we did not include it to the statistic.In the Encrypt phase, our scheme generates2n parameters and nr ciphertexts, which is the same as scheme [29]. While scheme [14] needs to generate 3n parameters and nr ciphertexts, and scheme [15] generates 4n parameters and nr ciphertexts, so the Encrypt process overhead of our scheme is less than schemes [14, 15].In the Search phase, the overhead of our scheme is the same as scheme [29] and is less than schemes [14, 15].In the Verification phases, the user overhead of our scheme is less than schemes [14, 15], which is because the edge server undertakes most calculations.Then, the total computational cost of our scheme is less than schemes [14, 15].


### 7.1.3. Communication Cost

Table4 shows the communication overhead comparison as it can be seen that our scheme has less communication overhead than other schemes overall.Table 4
Communication cost comparison.
SchemeEncryptTrapdoorSearchScheme [14]2np+nrq+nrppn+np+nrqScheme [15]2np+nq+nrq+nlpn+np+nq+nlScheme [29]2np+nrqpnOur scheme2np+nlpn+2np+nmIn the Encrypt phase, our scheme has less cost than other schemes and that is because our scheme uploads only one Bloom filter value for one file, and other schemes need to upload all the encrypted keywords. Then the communication cost of our scheme for keyword cipher text processing is related to the number of files but not to the number of keywords. Note that the number of files isn and the number of keywords in each file is k, then our scheme only needs to pass n Bloom filter values and 2n elements in G to the cloud. While scheme [29] needs to transmit 2n elements in G and nr elements in G1, scheme [14] needs to transmit 2n+nr elements in G and nr elements in G1, and scheme [15] has the the biggest overhead which needs to transmit 2n elements in G, n+nr elements in G1, and n elements of Bloom filter.In the Trapdoor phase, all schemes have the same communication overhead.In the Search phase, all four schemes need to returnn-bits search results, and scheme [14] still needs to transmit two auxiliary values np+nrq for verification, and scheme [15] still needs to transmit three auxiliary values np+nq+nl for verification, while our scheme needs two auxiliary values 2np+nm.Since the scheme [29] has no verification function, the communication cost of our scheme is higher than scheme [29] but is less than schemes [14, 15].


### 7.1.4. Storage Cost

We display the storage cost comparison in Table5, which demonstrates that our scheme has less storage overhead than other two schemes in general.Table 5
Storage cost comparison.
SchemePublisherUserCloudScheme [14]pp2np+nrq+nrpScheme [15]pp2np+nq+nrq+nlScheme [29]pp2np+nrqOur schemep2p2np+nlIn the publisher/data owner side, all schemes store one key, and then they have the same cost withp.In the user side, our scheme stores two keys, and other schemes only need to store one key.In the cloud side, our scheme has less storage cost than other three schemes. In our scheme, the cloud server only needs to store one Bloom filter value for one file, while other two schemes need to store all the encrypted keywords. Therefore, the cloud’s storage cost in our scheme is only related to the number of files and others are related to the number of keywords. Then our scheme needs2n elements in G and n elements of Bloom filter to store, while scheme [29] stores 2n elements in G and nr elements in G1, scheme [14] stores 2n+nr elements in G and nr elements in G1, and scheme [15] stores 2n elements in G, n+nr elements in G1, and n elements of Bloom filter.Therefore, our scheme has less storage cost than other three schemes.


## 7.1.1. Functionality

We show the function comparison in Table2, and we can see that all schemes realize the function of fine-grained authorization. In the verification function, scheme [14] can only verify the correctness, and scheme [15] can verify the correctness and completeness but exists security defect, and scheme [29] does not consider the verification module, while our scheme implements all the verification in the cloud-edge environment.Table 2
Functionality comparison.
SchemeFine-grained authorizationCompletenessEnvironmentScheme [14]YesYes/noCloudScheme [15]YesSecurity defectCloudScheme [29]YesNo/noCloudOur schemeYesYes/yesCloud-edge


## 7.1.2. Computation Cost

The comparison results of computation cost for several schemes are shown in Table3, and it demonstrates that our scheme has less computation overhead than schemes [14, 15] on the whole.Table 3
Computation cost comparison.
SchemeInitKeyGenScheme [14]2nExℤp+ExGExGScheme [15]2nExℤp+ExGExGScheme [29]2nExℤp+ExGExGOur scheme2nExℤp+ExGExGSchemeAuthorizationEncryptScheme [14]nExG4nr⋅ExG+3n⋅MulG+2nr⋅pairScheme [15]nExG3n+nrExG+2nr+npairScheme [29]nExG2n+nrExG+2nr⋅pairOur schemen+1ExG2n+nrExG+2nr⋅pairSchemeTrapdoorSearchScheme [14]MulG2n+1MulG+ExG+4n⋅pairScheme [15]MulG6n⋅MulG+4n⋅pairScheme [29]MulG3n⋅MulG+2n⋅pairOur schemeMulG3n⋅MulG+2n⋅pairSchemeVerificationuserVerificationuserScheme [14]n⋅MulG+n⋅pairScheme [15]n⋅MulG+n⋅pair—Scheme [29]——Our schemen⋅H3n⋅MulG+2n⋅pairIn the phases of Init, KeyGen, Extract, and Trapdoor, all four schemes have the same efficiency, which is because the parameters and data generated are alike. Note that the hash computation overhead isO1, which is far more cheaper than others, so we did not include it to the statistic.In the Encrypt phase, our scheme generates2n parameters and nr ciphertexts, which is the same as scheme [29]. While scheme [14] needs to generate 3n parameters and nr ciphertexts, and scheme [15] generates 4n parameters and nr ciphertexts, so the Encrypt process overhead of our scheme is less than schemes [14, 15].In the Search phase, the overhead of our scheme is the same as scheme [29] and is less than schemes [14, 15].In the Verification phases, the user overhead of our scheme is less than schemes [14, 15], which is because the edge server undertakes most calculations.Then, the total computational cost of our scheme is less than schemes [14, 15].


## 7.1.3. Communication Cost

Table4 shows the communication overhead comparison as it can be seen that our scheme has less communication overhead than other schemes overall.Table 4
Communication cost comparison.
SchemeEncryptTrapdoorSearchScheme [14]2np+nrq+nrppn+np+nrqScheme [15]2np+nq+nrq+nlpn+np+nq+nlScheme [29]2np+nrqpnOur scheme2np+nlpn+2np+nmIn the Encrypt phase, our scheme has less cost than other schemes and that is because our scheme uploads only one Bloom filter value for one file, and other schemes need to upload all the encrypted keywords. Then the communication cost of our scheme for keyword cipher text processing is related to the number of files but not to the number of keywords. Note that the number of files isn and the number of keywords in each file is k, then our scheme only needs to pass n Bloom filter values and 2n elements in G to the cloud. While scheme [29] needs to transmit 2n elements in G and nr elements in G1, scheme [14] needs to transmit 2n+nr elements in G and nr elements in G1, and scheme [15] has the the biggest overhead which needs to transmit 2n elements in G, n+nr elements in G1, and n elements of Bloom filter.In the Trapdoor phase, all schemes have the same communication overhead.In the Search phase, all four schemes need to returnn-bits search results, and scheme [14] still needs to transmit two auxiliary values np+nrq for verification, and scheme [15] still needs to transmit three auxiliary values np+nq+nl for verification, while our scheme needs two auxiliary values 2np+nm.Since the scheme [29] has no verification function, the communication cost of our scheme is higher than scheme [29] but is less than schemes [14, 15].


## 7.1.4. Storage Cost

We display the storage cost comparison in Table5, which demonstrates that our scheme has less storage overhead than other two schemes in general.Table 5
Storage cost comparison.
SchemePublisherUserCloudScheme [14]pp2np+nrq+nrpScheme [15]pp2np+nq+nrq+nlScheme [29]pp2np+nrqOur schemep2p2np+nlIn the publisher/data owner side, all schemes store one key, and then they have the same cost withp.In the user side, our scheme stores two keys, and other schemes only need to store one key.In the cloud side, our scheme has less storage cost than other three schemes. In our scheme, the cloud server only needs to store one Bloom filter value for one file, while other two schemes need to store all the encrypted keywords. Therefore, the cloud’s storage cost in our scheme is only related to the number of files and others are related to the number of keywords. Then our scheme needs2n elements in G and n elements of Bloom filter to store, while scheme [29] stores 2n elements in G and nr elements in G1, scheme [14] stores 2n+nr elements in G and nr elements in G1, and scheme [15] stores 2n elements in G, n+nr elements in G1, and n elements of Bloom filter.Therefore, our scheme has less storage cost than other three schemes.


## 7.2. Experimental Results

To assess the actual performance, we carry out the comparison experiments with schemes [14, 15, 29]. We use the latest JPBC library to deploy the archetypes of these schemes. Our experiments run on a computer with Intel Core i5-6550 CPU working in theWindows 7 system. We used the Enron database as the source, which extracted 10 thousands documents, 6 thousands keywords, and 80 thousands keyword-document pairs, of which most files matched fewer than 10 keywords. We selected the Type-A pairing to complete the specific algorithm, and then experimented with different number of files and keywords within four schemes. The experiment results are consistent with our performance analysis, as shown in Figure 4.Figure 4
Time cost comparison. (a) Time cost of Init. (b) Time cost of Keygen. (c) Time cost of Authorization. (d) Time cost of Encrypt. (e) Time cost of Trapdoor. (f) Time cost of search. (g) Time cost of verification.
(a)(b)(c)(d)(e)(f)(g)In the Init and Authorization phases, all schemes have the same computation cost, which is liner increasing with the number of files, as shown in Figures4(a) and 4(c).In the KeyGen and Trapdoor phases, all schemes have the same operation time for different numbers of files, as shown in Figures4(b) and 4(e).In the the Encrypt and Search phases, our scheme has the same operation time as scheme [29], which is less than schemes [14, 15], as shown in Figures 4(d) and 4(f).In the Verification phase, Figure4(g) shows that the user side of our scheme has less computational time than schemes [14, 15], which is because the edge completes most of the calculations, and the user only need to hash to get the verification results. Note that scheme [29] cannot achieve the verification function.To sum up the experiments, the overall operation time of our scheme is lower than schemes [14, 15] with all processes.


## 8. Conclusion

In the edge computing environment, we proposed a new scheme of verifiable data search with fine-grained authorization, which not only realizes file-oriented search authority management but also verifies the correctness and completeness of results. In addition, with the assistance of edge server, clients with limited resource can easily carry out the tasks of search and verification. Besides, we proved that our scheme is verifiable and secure, and the secure model did not rely on the Random Oracle. To assess the practicability of the proposed scheme, we implemented it and conducted experiments in a simulated environment. As expected, our scheme effectively reduced the computation, communication, and storage costs. In the future, we intend to focus on the dynamic management of users and files, as well as the further authorization to prevent the key abuse. Also, we want to instantiate the data sharing model with the blockchain technology.



---

*Source: 4252466-2022-11-10.xml*