# Edge-Cloud-Assisted Multiuser Forward Secure Searchable Encryption (EMFSSE) Scheme in the P2P Networking Environment

Authors: Yongli Tang; Jingran Li; Xixi Yan; Qiang Zhao
Journal: Mobile Information Systems
 (2021)

---

## Abstract

P2P network enables users to share resources effectively. However, with the advent of the big data era, the sensitive data of users in P2P network are also increasing dramatically. In order to solve the contradiction between the huge amount of sensitive data and the limited local storage space, an increasing number of users choose to encrypt their sensitive data and store them in the cloud server. For the problem of the secure storage and flexible access of large amounts of user data in P2P networks, an edge-cloud-assisted multiuser forward secure searchable encryption scheme is proposed. The scheme uses the proxy reencryption technique to optimize the multiuser searchable encryption and prevent the decryption key from being directly transmitted between users. By introducing an edge-cloud architecture, the system achieves efficient communication and timely response capabilities. The security analysis proves that our scheme achieves the CPA (chosen-plaintext attack) security based on DBDH assumption and the forward privacy. Finally, the theoretical and experimental comparisons between this scheme and other schemes show that our scheme has high efficiency in the process of data update, search, and trapdoor generation. In addition, due to the use of edge-cloud architecture, our scheme reduces about 90% and 75% of the user’s consumption in the encryption and token generation process.


---

## Body

## 1. Introduction

P2P network file sharing system has been widely used and has rapidly developed because of its various advantages, such as decentralization, good extendibility, strong robustness, high cost-effectiveness, and load balancing characteristics [1–3]. With the development of communication and computer technology [4–6], the amount of data owned by users is increasing, but the local storage space of users is limited. This contradiction has become one of the main reasons for restricting the development of P2P networks. The development of cloud storage [7] has brought about a turning point for this situation. Clients can choose to transfer a large amount of local data [8] to a cloud server and use the cloud server to store, manage, and utilize the data. In addition, searchable encryption technology can ensure data security and flexible access during remote storage, which not only reduces local storage and computational cost but also achieves more flexible and convenient data access. However, in reality, there is a huge physical and logical distance between the client and the cloud server, which reduces the efficiency of data collection, transmission, and analysis, causes the delay of the communication process, and hinders the timely response ability of the whole system. This brings new challenges to the combination of file transmission and searchable encryption technology in P2P networking environment. A lot of work has shown [9–11] that edge-cloud collaboration can successfully replace the only-cloud system and strike a balance between powerful computing power and rapid response. The edge-cloud architecture is an optimized cloud computing system that transforms cloud service from the “cloud” as the center to the Internet edge and cloud cooperative operation, which overcomes the problems of only-cloud computing such as distributed data collection, transmission and response delay, and poor data analysis efficiency. With the help of edge computing, clients store some data information on the nearest edge platform, and the edge platform retrieves the data according to authorization, thereby limiting unnecessary data upload to the cloud, saving communication costs, and providing more efficient and timely data search. In addition, the edge platform can also assist clients in some expensive operations and use the efficiency of edge computing to reduce the amount of calculation on the client side. Therefore, the edge-cloud architecture and the P2P network can be combined. Clients upload part of their data information to the edge-cloud architecture and enjoy the ability to share and use data in time.The combined use of searchable encryption and edge-cloud collaboration can largely solve the contradiction between data storage, data confidentiality, and data transmission efficiency. It ensures that neither the edge side nor the cloud side can learn any useful information without completely sacrificing searchability of the data or that search function can be improved with minimal disclosure. However, the search server is generally assumed to be an honest but curious entity in a searchable encryption scheme. In the real world, the malicious server will carry out illegal operation on its stored ciphertext. Attackers can even use a small amount of leakage to leak the user’s query. Particularly in dynamic databases, the attacker can inject new documents into the cloud server to gain more advantages, and the impact of file injection attacks can even be devastating. The searchable encryption scheme that realizes forward privacy can effectively resist such attacks [12]. Therefore, from the perspective of usage, it is very necessary to construct a forward secure searchable encryption scheme to solve the information security and privacy issues in the process of file updating. How to design a searchable encryption scheme with forward security under the edge-cloud architecture and apply it to P2P networks is the first goal of this paper.In the P2P network, a node can not only be the data user who sends the request to obtain the required information but also provide the data as the data owner. Specifically, the P2P network aims to share various services among users. But so far, only a few schemes extend forward secure searchable encryption scheme to multiuser [13, 14]. Wang et al. [13] introduce a semihonest proxy server that does not collude with the cloud server to solve the user query problem. Lu et al. [14] improve Wang’s scheme, remove the state value transfer between the data owner and the proxy server, and add the user authentication function. However, both schemes require the data owner to send the decryption key to the data user directly. In order to prevent the disclosure of the decryption key, this paper introduces the proxy reencryption technique. The authorized proxy (obtains the reencryption key generated by the data owner) transforms the ciphertext provided by the data owner into another ciphertext that can be decrypted by the data user. Then, the data user can download the ciphertext alone and decrypt it with his own private key to get the original plaintext. How to combine forward secure searchable encryption with proxy reencryption to provide secure file sharing between users is the second goal of this paper.


### 1.1. Contribution

In order to achieve the two goals mentioned above, we study a series of existing schemes. First of all, users in P2P network upload a large amount of data to the cloud for storage and search. However, the distance between clients and server causes serious operation delay in this process, which affects the performance of end-to-end communication in the P2P network. Inspired by the work [15], edge-cloud architecture can effectively realize timely response between client and edge platform and greatly improve communication efficiency. Secondly, malicious attackers may carry out a variety of attacks to damage the confidentiality of user data by using the information leaked in the communication process, for example, file injection attacks. Therefore, constructing a searchable encryption scheme with forward security is particularly important, which can effectively ensure that the file update process does not disclose data information. Finally, in order to combine P2P network with forward secure searchable encryption technology, it is necessary to implement forward secure searchable encryption technology among multiple users. However, the existing multiuser schemes need to transmit the decryption key directly [13, 14]. In order to prevent the decryption key from leaking, the proxy reencryption technique is introduced to optimize the security of file transmission of each node in the P2P network. In summary, we have constructed a multiuser forward secure searchable encryption scheme EMFSSE based on the edge-cloud architecture in the P2P network. In the scheme, we store part of the index information in the edge server nearest to the user and store encrypted files and encrypted indexes in the cloud server. The communication efficiency of the whole system is also enhanced because it can realize fast update, search, and transmission between the user and the server by making full use of the storage and computing capacity of cloud edge. The main contributions are as follows:(1)
This scheme combines the P2P network with the multiuser forward secure searchable encryption. It realizes the encryption storage, ciphertext search, and update function of user data in the P2P network environment. And it supports data transmission between users.(2)
Proxy reencryption technique is introduced to solve the decryption key leakage problem in the scheme [13, 14]. In our scheme, the edge server reencrypts the ciphertext, and then the data requester uses its own private key to decrypt the reencrypted ciphertext.(3)
We take advantage of edge-cloud collaborative computing to spread out the workload of only-cloud server and reduce the burden of users. Firstly, the edge server maintains part of the keyword information and assists the authorized data user to generate trapdoor. The data owner can authorize the data user to query the encrypted database dynamically and effectively. Secondly, because of the excellent computing power of edge server, it can be used to realize the reencryption process and convert part of the heavy encryption operations to the edge, which can ensure data confidentiality and reduce the computational cost of the client and cloud.(4)
The scheme satisfies the correctness and indistinguishable forward security under the adaptive attack model. And the scheme is proved to be against the chosen-plaintext attacks (CPA) based on the DBDH assumption during the reencryption process.(5)
Comparative analysis and experimental results show that the proposed scheme has a good efficiency in the process of encryption and searching. Compared with the scheme without edge computing, the proposed scheme can save about 92% of the computational costs of the client in the process of ciphertext generation. It can save about 75% of the computation cost in the token generation process.


### 1.2. Organization

The rest of this paper is organized as follows. In the next section, we introduce the related work. The description of symbols and related knowledge are introduced in Section3. Section 4 analyzes the design goals and basic model. Then the specific structure and safety analysis of the EMFSSE scheme are introduced in Section 5 and Section 6, respectively. Section 7 compares the EMFSSE scheme with other related schemes and evaluates its performance. In the end, Section 8 summarizes the full text.


## 1.1. Contribution

In order to achieve the two goals mentioned above, we study a series of existing schemes. First of all, users in P2P network upload a large amount of data to the cloud for storage and search. However, the distance between clients and server causes serious operation delay in this process, which affects the performance of end-to-end communication in the P2P network. Inspired by the work [15], edge-cloud architecture can effectively realize timely response between client and edge platform and greatly improve communication efficiency. Secondly, malicious attackers may carry out a variety of attacks to damage the confidentiality of user data by using the information leaked in the communication process, for example, file injection attacks. Therefore, constructing a searchable encryption scheme with forward security is particularly important, which can effectively ensure that the file update process does not disclose data information. Finally, in order to combine P2P network with forward secure searchable encryption technology, it is necessary to implement forward secure searchable encryption technology among multiple users. However, the existing multiuser schemes need to transmit the decryption key directly [13, 14]. In order to prevent the decryption key from leaking, the proxy reencryption technique is introduced to optimize the security of file transmission of each node in the P2P network. In summary, we have constructed a multiuser forward secure searchable encryption scheme EMFSSE based on the edge-cloud architecture in the P2P network. In the scheme, we store part of the index information in the edge server nearest to the user and store encrypted files and encrypted indexes in the cloud server. The communication efficiency of the whole system is also enhanced because it can realize fast update, search, and transmission between the user and the server by making full use of the storage and computing capacity of cloud edge. The main contributions are as follows:(1)
This scheme combines the P2P network with the multiuser forward secure searchable encryption. It realizes the encryption storage, ciphertext search, and update function of user data in the P2P network environment. And it supports data transmission between users.(2)
Proxy reencryption technique is introduced to solve the decryption key leakage problem in the scheme [13, 14]. In our scheme, the edge server reencrypts the ciphertext, and then the data requester uses its own private key to decrypt the reencrypted ciphertext.(3)
We take advantage of edge-cloud collaborative computing to spread out the workload of only-cloud server and reduce the burden of users. Firstly, the edge server maintains part of the keyword information and assists the authorized data user to generate trapdoor. The data owner can authorize the data user to query the encrypted database dynamically and effectively. Secondly, because of the excellent computing power of edge server, it can be used to realize the reencryption process and convert part of the heavy encryption operations to the edge, which can ensure data confidentiality and reduce the computational cost of the client and cloud.(4)
The scheme satisfies the correctness and indistinguishable forward security under the adaptive attack model. And the scheme is proved to be against the chosen-plaintext attacks (CPA) based on the DBDH assumption during the reencryption process.(5)
Comparative analysis and experimental results show that the proposed scheme has a good efficiency in the process of encryption and searching. Compared with the scheme without edge computing, the proposed scheme can save about 92% of the computational costs of the client in the process of ciphertext generation. It can save about 75% of the computation cost in the token generation process.


## 1.2. Organization

The rest of this paper is organized as follows. In the next section, we introduce the related work. The description of symbols and related knowledge are introduced in Section3. Section 4 analyzes the design goals and basic model. Then the specific structure and safety analysis of the EMFSSE scheme are introduced in Section 5 and Section 6, respectively. Section 7 compares the EMFSSE scheme with other related schemes and evaluates its performance. In the end, Section 8 summarizes the full text.


## 2. Related Work

This paper studies the multiuser forward secure searchable encryption technology optimized by proxy reencryption technique in the edge-cloud-assisted P2P network. Therefore, this section focuses on the research progress of forward secure searchable encryption, edge-cloud architecture, and proxy reencryption technique.


### 2.1. Forward Secure Searchable Encryption (FSSE)

The desired goal of forward secure searchable encryption (FSSE) is that the malicious server does not disclose any information of existing data in the database during the file update phase. The scheme of Chang Mitzenmacher [16] already supports forward security. This paper points out that when a file is updated, the newly added file may be related to the previously queried keywords, thereby leaking some information. Stefanov et al. [17] proposed the concept of FSSE and the concept of backward security. Subsequently, the first scheme with good communication costs and computational complexity was proposed by Bost [12], which hides the relationship between document identifiers and keywords through trapdoors replacement in the indexing process and does not disclose the information of previously queried files when new files are injected. Subsequently, scholars have successively proposed various forward secure searchable encryption schemes [18–20] on the basis of the ∑oϕoς scheme. The application of the FSSE scheme has also become a research hotspot recently. Chen et al. [21] proposed a blockchain-based forward secure searchable encryption scheme and applied it to vehicle trading websites. The scheme uses smart contract to replace the cloud server for search. Wang et al. [22] proposed a verifiable forward security ranking search scheme in P2P network environment. The scheme realizes ranking search and achieves forward security by changing the file vector structure and using modular residual computation. However, most of these schemes cannot realize file transfer between clients. Wang et al. [13] proposed an FSSE scheme to support multiuser search, which realizes data access by using proxy server to maintain keyword state information. However, this scheme directly transmits decryption key through secure channel, which not only causes the problem of decryption key leakage but also requires the data owner to keep online during the whole search phase.


### 2.2. Edge-Cloud Architecture

It is an effective way to optimize cloud computing by using cloud-edge collaboration instead of only-cloud system, which has become a research trend in the near future. The edge platform is closer to the underlying data source and has the geographical advantage of being closer to the real clients, so it can effectively reduce the system delay. And edge server can replace the client side or cloud side to perform some complex operations, which can improve the efficiency of the client and cloud server, and provide on-demand services. Ren et al. [23] proposed that the cloud-edge cooperation method can effectively improve the delay performance. Zhang et al. [24] used edge-cloud cooperation to construct a multidevice management service system and applied it to the industrial Internet of things. The system improved the response speed of data collected by basic equipment to a certain extent and reduced the network bandwidth load pressure brought by data transmission. Mollah et al. [25] combined cloud-edge collaboration with public key encryption to construct a secure data sharing scheme, which supports searching on encrypted data (searchable encryption), uses cloud-edge collaboration to reduce computing and communication costs, and provides privacy and confidentiality functions for outsourced data. Wang et al. [15] constructed a lightweight scheme of edge-cloud-assisted public key searchable encryption, using lightweight cryptography and edge-cloud computing to reduce the encryption cost of infrastructure equipment by 70%. But the previous schemes are all applied to the industrial Internet of things, and few schemes combine edge computing with P2P network.


### 2.3. Proxy Reencryption

Proxy reencryption technique means a trusted third party that converts data encrypted by the data owner with his public key into ciphertext data that can be decrypted by the data user with his private key, so as to complete data sharing. It is important to note that, during this process, no plaintext information should be disclosed to the proxy. In 1998, proxy reencryption technique was proposed by Blaze et al. [26]. With the development of cloud storage, a large number of researchers focus on the combination of proxy reencryption technique and cloud storage to achieve the purpose of cloud data sharing [27–29]. Early proxy reencryption schemes have the problem of reencryption key abuse. In 2005, [30] introduced the concept of nontransferability, but it was not until 2015 that Guo et al. [31] completed the instantiation of this concept using indistinguishable confusion and unforgeable authentication. On this basis, a public accountability proxy reencryption scheme was proposed by Guo et al. [32] in 2021. Different from the traditional reencryption key generation, the generation process of this scheme is noninteractive, which saves the communication cost, and the scheme can determine the operator of the decryption operation, which improves the security of the scheme.


## 2.1. Forward Secure Searchable Encryption (FSSE)

The desired goal of forward secure searchable encryption (FSSE) is that the malicious server does not disclose any information of existing data in the database during the file update phase. The scheme of Chang Mitzenmacher [16] already supports forward security. This paper points out that when a file is updated, the newly added file may be related to the previously queried keywords, thereby leaking some information. Stefanov et al. [17] proposed the concept of FSSE and the concept of backward security. Subsequently, the first scheme with good communication costs and computational complexity was proposed by Bost [12], which hides the relationship between document identifiers and keywords through trapdoors replacement in the indexing process and does not disclose the information of previously queried files when new files are injected. Subsequently, scholars have successively proposed various forward secure searchable encryption schemes [18–20] on the basis of the ∑oϕoς scheme. The application of the FSSE scheme has also become a research hotspot recently. Chen et al. [21] proposed a blockchain-based forward secure searchable encryption scheme and applied it to vehicle trading websites. The scheme uses smart contract to replace the cloud server for search. Wang et al. [22] proposed a verifiable forward security ranking search scheme in P2P network environment. The scheme realizes ranking search and achieves forward security by changing the file vector structure and using modular residual computation. However, most of these schemes cannot realize file transfer between clients. Wang et al. [13] proposed an FSSE scheme to support multiuser search, which realizes data access by using proxy server to maintain keyword state information. However, this scheme directly transmits decryption key through secure channel, which not only causes the problem of decryption key leakage but also requires the data owner to keep online during the whole search phase.


## 2.2. Edge-Cloud Architecture

It is an effective way to optimize cloud computing by using cloud-edge collaboration instead of only-cloud system, which has become a research trend in the near future. The edge platform is closer to the underlying data source and has the geographical advantage of being closer to the real clients, so it can effectively reduce the system delay. And edge server can replace the client side or cloud side to perform some complex operations, which can improve the efficiency of the client and cloud server, and provide on-demand services. Ren et al. [23] proposed that the cloud-edge cooperation method can effectively improve the delay performance. Zhang et al. [24] used edge-cloud cooperation to construct a multidevice management service system and applied it to the industrial Internet of things. The system improved the response speed of data collected by basic equipment to a certain extent and reduced the network bandwidth load pressure brought by data transmission. Mollah et al. [25] combined cloud-edge collaboration with public key encryption to construct a secure data sharing scheme, which supports searching on encrypted data (searchable encryption), uses cloud-edge collaboration to reduce computing and communication costs, and provides privacy and confidentiality functions for outsourced data. Wang et al. [15] constructed a lightweight scheme of edge-cloud-assisted public key searchable encryption, using lightweight cryptography and edge-cloud computing to reduce the encryption cost of infrastructure equipment by 70%. But the previous schemes are all applied to the industrial Internet of things, and few schemes combine edge computing with P2P network.


## 2.3. Proxy Reencryption

Proxy reencryption technique means a trusted third party that converts data encrypted by the data owner with his public key into ciphertext data that can be decrypted by the data user with his private key, so as to complete data sharing. It is important to note that, during this process, no plaintext information should be disclosed to the proxy. In 1998, proxy reencryption technique was proposed by Blaze et al. [26]. With the development of cloud storage, a large number of researchers focus on the combination of proxy reencryption technique and cloud storage to achieve the purpose of cloud data sharing [27–29]. Early proxy reencryption schemes have the problem of reencryption key abuse. In 2005, [30] introduced the concept of nontransferability, but it was not until 2015 that Guo et al. [31] completed the instantiation of this concept using indistinguishable confusion and unforgeable authentication. On this basis, a public accountability proxy reencryption scheme was proposed by Guo et al. [32] in 2021. Different from the traditional reencryption key generation, the generation process of this scheme is noninteractive, which saves the communication cost, and the scheme can determine the operator of the decryption operation, which improves the security of the scheme.


## 3. Preliminaries

This section mainly introduces the symbols and encryption-related knowledge used in this paper.


### 3.1. Notations

The notation information of this paper is given in the Table1Table 1
Notations description.
NotationDescriptionλ,μThe security parameterq,p,G1,G2,eThe bilinear parametersG,FThe one-way permutation functionsH1,H2,H3,H4The hash functions∑The map stored on the data owner sideTThe list stored on the edge server sideTThe tree stored on the cloud server sidepki,skii’s public/private keyfko,fko′,wkData owner’s secret keymThe plaintextindThe identifier ofmwThe keywordsWThe set of keywords associated withmopThe addition/deletion operationCThe ciphertext ofmTrawThe query trapdoorTrwThe search trapdoorbA data block stored in the treeT is used to store index informationb.id,b.keyAn identifier/key pair matches the data blockbqkc,qkuThe query key generated by the data owner for a data userrko⟶uThe reencryption key generated by the data owner for a data userEDBThe encrypted databasex←RXUniformly and randomly selectx from the finite set∥The concatenation operator⊕The XOR operatorCA chainWThe keyword dictionaryWThe number of keywords in the keyword dictionarynwThe number of files contained in a keywordw


### 3.2. Cryptography Materials

#### 3.2.1. Trapdoor One-Way Permutation Technique

We cite the definition of trapdoor one-way permutation in literature [33].The groupD based on trapdoor permutation family Π consists of three algorithms: Random generation algorithm (Gen): it inputs security parameter λ and outputs permutation description s and related trapdoor t. Evaluation algorithm (Eva): it inputs s and the original image x∈D and outputs the image of x, y∈D. Inverse algorithm (Inv): it inputs s, trapdoor t, and y and output the preimage of y in the permutation. And the one-way permutation function has the following properties:(i)
For allGen⟶Rs,t, the related Evas,⋅ should be a permutation of group D(ii)
For allx∈D, Invs,t,Evas,x=x


#### 3.2.2. Bilinear Pairing

According to literature [34], we briefly introduce the definition of bilinear pairing. Let G1 and G2 be two cyclic groups of the same prime order p≥2λ, g be the generator of G1, and λ be the security parameters. Let e:G1×G1⟶G2 denote a map to satisfy the following properties:(i)
Bilinear: For anyx,y∈G1 and a,b∈Zp, the equation exa,yb=ex,yab holds(ii)
Computable: forx,y∈G1 that meets the condition, an algorithm can be found to calculate the value of ex,y in polynomial time(iii)
Nondegenerate:eg,g≠1


#### 3.2.3. Decisional Bilinear Diffie–Hellman (DBDH) Assumption

According to literature [35], the description of DBDH assumption is given. The definitions of groups G1 and G2 and map e:G1×G1⟶G2 are the same as above. For any adversary B, its advantages are defined as AdvBDBDHλ=PrBg,ga,gb,gc,eg,gabc=1−PrBg,ga,gb,gc,eg,gz=1, where a,b,c,z←RZp. We say that the DBDH assumption holds if, for any probability polynomial time (PPT) adversary B, its advantage AdvBDBDHλ is negligible with security parameter λ.


#### 3.2.4. Forward Privacy Security

This paper cites the definition of forward privacy technology in literature [12].Common Leakage. We define the leak function L=LSetup,LSearch,LUpdate, which represents the amount of information leaked to the adversary in the searchable encryption scheme. The leak function L treats the query list Q (including all queries) as status. List Q stores each query for keyword w, and its element is i,w or i,op,in for an update query op with input in. The integer i represents the timestamp with the initial value of 0, which increases with the number of queries.(i)
Search pattern:spx=j:j,x∈Q (only matches search queries)(ii)
Query pattern:qpx=j:j,x∈Qorj,op, in∈QandxappearsininForward Privacy. A L-adaptively secure searchable encryption scheme ∑ is forward private if the update leakage function LUpdate can be expressed as (1)LUpdateop,in=L′op,indi,ui,where indi,ui represents the modified document set and ui represents the number of modified words.


#### 3.2.5. Binary Index Tree

We use the binary index tree in literature [18] to store the encrypted file information, as shown in Figure 1.Figure 1
Binary index treeT (stores index information of three keywords w1,w2,w3).Block. A block b is generated for each index w,ind. The block b is divided into two parts, the block address b.id and the block data b.data, where b.data stores the data value b.value (the information of one index w,ind in this paper), the previous block key denoted by b.pre.key, and the previous block address b.pre.id. To sum up, b=b.id,b.value,b.pre.key,b.pre.id.Blocks Chain. Connect the blocks with the same keyword w into a chain C. Chain C represents the index list related to w, and its length is equal to the number of file indexes nw containing w. The total number of chains is equal to the number of keywords W. There are three types of blocks on each chain C: the first block b.head, the last block b.tail, and the other blocks b.internal, where b.tail=b.id,b.value,⊥,⊥.Binary Index Tree. Each node of the binary index tree T stores a block b. The node indexed by id is denoted by b.id, and the stored data is denoted by b.data. The value of the data block stores all indexes w,ind containing the keyword w. Finally, the tree T has a total of W index lists (chains), including W⋅nw nodes, and the depth is logW⋅nw.


## 3.1. Notations

The notation information of this paper is given in the Table1Table 1
Notations description.
NotationDescriptionλ,μThe security parameterq,p,G1,G2,eThe bilinear parametersG,FThe one-way permutation functionsH1,H2,H3,H4The hash functions∑The map stored on the data owner sideTThe list stored on the edge server sideTThe tree stored on the cloud server sidepki,skii’s public/private keyfko,fko′,wkData owner’s secret keymThe plaintextindThe identifier ofmwThe keywordsWThe set of keywords associated withmopThe addition/deletion operationCThe ciphertext ofmTrawThe query trapdoorTrwThe search trapdoorbA data block stored in the treeT is used to store index informationb.id,b.keyAn identifier/key pair matches the data blockbqkc,qkuThe query key generated by the data owner for a data userrko⟶uThe reencryption key generated by the data owner for a data userEDBThe encrypted databasex←RXUniformly and randomly selectx from the finite set∥The concatenation operator⊕The XOR operatorCA chainWThe keyword dictionaryWThe number of keywords in the keyword dictionarynwThe number of files contained in a keywordw


## 3.2. Cryptography Materials

### 3.2.1. Trapdoor One-Way Permutation Technique

We cite the definition of trapdoor one-way permutation in literature [33].The groupD based on trapdoor permutation family Π consists of three algorithms: Random generation algorithm (Gen): it inputs security parameter λ and outputs permutation description s and related trapdoor t. Evaluation algorithm (Eva): it inputs s and the original image x∈D and outputs the image of x, y∈D. Inverse algorithm (Inv): it inputs s, trapdoor t, and y and output the preimage of y in the permutation. And the one-way permutation function has the following properties:(i)
For allGen⟶Rs,t, the related Evas,⋅ should be a permutation of group D(ii)
For allx∈D, Invs,t,Evas,x=x


### 3.2.2. Bilinear Pairing

According to literature [34], we briefly introduce the definition of bilinear pairing. Let G1 and G2 be two cyclic groups of the same prime order p≥2λ, g be the generator of G1, and λ be the security parameters. Let e:G1×G1⟶G2 denote a map to satisfy the following properties:(i)
Bilinear: For anyx,y∈G1 and a,b∈Zp, the equation exa,yb=ex,yab holds(ii)
Computable: forx,y∈G1 that meets the condition, an algorithm can be found to calculate the value of ex,y in polynomial time(iii)
Nondegenerate:eg,g≠1


### 3.2.3. Decisional Bilinear Diffie–Hellman (DBDH) Assumption

According to literature [35], the description of DBDH assumption is given. The definitions of groups G1 and G2 and map e:G1×G1⟶G2 are the same as above. For any adversary B, its advantages are defined as AdvBDBDHλ=PrBg,ga,gb,gc,eg,gabc=1−PrBg,ga,gb,gc,eg,gz=1, where a,b,c,z←RZp. We say that the DBDH assumption holds if, for any probability polynomial time (PPT) adversary B, its advantage AdvBDBDHλ is negligible with security parameter λ.


### 3.2.4. Forward Privacy Security

This paper cites the definition of forward privacy technology in literature [12].Common Leakage. We define the leak function L=LSetup,LSearch,LUpdate, which represents the amount of information leaked to the adversary in the searchable encryption scheme. The leak function L treats the query list Q (including all queries) as status. List Q stores each query for keyword w, and its element is i,w or i,op,in for an update query op with input in. The integer i represents the timestamp with the initial value of 0, which increases with the number of queries.(i)
Search pattern:spx=j:j,x∈Q (only matches search queries)(ii)
Query pattern:qpx=j:j,x∈Qorj,op, in∈QandxappearsininForward Privacy. A L-adaptively secure searchable encryption scheme ∑ is forward private if the update leakage function LUpdate can be expressed as (1)LUpdateop,in=L′op,indi,ui,where indi,ui represents the modified document set and ui represents the number of modified words.


### 3.2.5. Binary Index Tree

We use the binary index tree in literature [18] to store the encrypted file information, as shown in Figure 1.Figure 1
Binary index treeT (stores index information of three keywords w1,w2,w3).Block. A block b is generated for each index w,ind. The block b is divided into two parts, the block address b.id and the block data b.data, where b.data stores the data value b.value (the information of one index w,ind in this paper), the previous block key denoted by b.pre.key, and the previous block address b.pre.id. To sum up, b=b.id,b.value,b.pre.key,b.pre.id.Blocks Chain. Connect the blocks with the same keyword w into a chain C. Chain C represents the index list related to w, and its length is equal to the number of file indexes nw containing w. The total number of chains is equal to the number of keywords W. There are three types of blocks on each chain C: the first block b.head, the last block b.tail, and the other blocks b.internal, where b.tail=b.id,b.value,⊥,⊥.Binary Index Tree. Each node of the binary index tree T stores a block b. The node indexed by id is denoted by b.id, and the stored data is denoted by b.data. The value of the data block stores all indexes w,ind containing the keyword w. Finally, the tree T has a total of W index lists (chains), including W⋅nw nodes, and the depth is logW⋅nw.


## 3.2.1. Trapdoor One-Way Permutation Technique

We cite the definition of trapdoor one-way permutation in literature [33].The groupD based on trapdoor permutation family Π consists of three algorithms: Random generation algorithm (Gen): it inputs security parameter λ and outputs permutation description s and related trapdoor t. Evaluation algorithm (Eva): it inputs s and the original image x∈D and outputs the image of x, y∈D. Inverse algorithm (Inv): it inputs s, trapdoor t, and y and output the preimage of y in the permutation. And the one-way permutation function has the following properties:(i)
For allGen⟶Rs,t, the related Evas,⋅ should be a permutation of group D(ii)
For allx∈D, Invs,t,Evas,x=x


## 3.2.2. Bilinear Pairing

According to literature [34], we briefly introduce the definition of bilinear pairing. Let G1 and G2 be two cyclic groups of the same prime order p≥2λ, g be the generator of G1, and λ be the security parameters. Let e:G1×G1⟶G2 denote a map to satisfy the following properties:(i)
Bilinear: For anyx,y∈G1 and a,b∈Zp, the equation exa,yb=ex,yab holds(ii)
Computable: forx,y∈G1 that meets the condition, an algorithm can be found to calculate the value of ex,y in polynomial time(iii)
Nondegenerate:eg,g≠1


## 3.2.3. Decisional Bilinear Diffie–Hellman (DBDH) Assumption

According to literature [35], the description of DBDH assumption is given. The definitions of groups G1 and G2 and map e:G1×G1⟶G2 are the same as above. For any adversary B, its advantages are defined as AdvBDBDHλ=PrBg,ga,gb,gc,eg,gabc=1−PrBg,ga,gb,gc,eg,gz=1, where a,b,c,z←RZp. We say that the DBDH assumption holds if, for any probability polynomial time (PPT) adversary B, its advantage AdvBDBDHλ is negligible with security parameter λ.


## 3.2.4. Forward Privacy Security

This paper cites the definition of forward privacy technology in literature [12].Common Leakage. We define the leak function L=LSetup,LSearch,LUpdate, which represents the amount of information leaked to the adversary in the searchable encryption scheme. The leak function L treats the query list Q (including all queries) as status. List Q stores each query for keyword w, and its element is i,w or i,op,in for an update query op with input in. The integer i represents the timestamp with the initial value of 0, which increases with the number of queries.(i)
Search pattern:spx=j:j,x∈Q (only matches search queries)(ii)
Query pattern:qpx=j:j,x∈Qorj,op, in∈QandxappearsininForward Privacy. A L-adaptively secure searchable encryption scheme ∑ is forward private if the update leakage function LUpdate can be expressed as (1)LUpdateop,in=L′op,indi,ui,where indi,ui represents the modified document set and ui represents the number of modified words.


## 3.2.5. Binary Index Tree

We use the binary index tree in literature [18] to store the encrypted file information, as shown in Figure 1.Figure 1
Binary index treeT (stores index information of three keywords w1,w2,w3).Block. A block b is generated for each index w,ind. The block b is divided into two parts, the block address b.id and the block data b.data, where b.data stores the data value b.value (the information of one index w,ind in this paper), the previous block key denoted by b.pre.key, and the previous block address b.pre.id. To sum up, b=b.id,b.value,b.pre.key,b.pre.id.Blocks Chain. Connect the blocks with the same keyword w into a chain C. Chain C represents the index list related to w, and its length is equal to the number of file indexes nw containing w. The total number of chains is equal to the number of keywords W. There are three types of blocks on each chain C: the first block b.head, the last block b.tail, and the other blocks b.internal, where b.tail=b.id,b.value,⊥,⊥.Binary Index Tree. Each node of the binary index tree T stores a block b. The node indexed by id is denoted by b.id, and the stored data is denoted by b.data. The value of the data block stores all indexes w,ind containing the keyword w. Finally, the tree T has a total of W index lists (chains), including W⋅nw nodes, and the depth is logW⋅nw.


## 4. System Design

### 4.1. Design Goals

According to the information transmission requirements of P2P network and users, the scheme designed in this paper must meet the following goals:Efficiency: the index structure in the searchable encryption scheme has an important impact on search efficiency. We store the index in a tree structure to improve search efficiency. In the phase of ciphertext generation and search query, we utilize the edge-cloud architecture to improve the fast response capability of the whole system.Confidentiality: this is another key attribute. This scheme needs to ensure the confidentiality of data, index, and query. That is, the server cannot get the relevant information of the plaintext by analyzing the stored ciphertext or by reencrypting the ciphertext. And it also cannot get the relevant index information and data query when attacked by an adversary. In addition, this scheme provides forward privacy performance specifically against file injection attack [12].Dynamic update: this scheme supports the dynamic update of files including add, delete, and update functions. When the user wants to modify the data, he only needs to perform corresponding operations on the data index and the database.Correctness: correctness is the basic property of a searchable decryption scheme, which requires the system to provide services correctly. Specifically, as long as the correct trapdoor is provided and the system is executed sequentially in a legal manner, the search results must be correct.Multiusers: this attribute refers to the ability of the scheme to support data transmission between different users. And the data owner is able to authorize users and update their access rights at any time.


### 4.2. System Model

As shown in Figure2, our scheme has four entities: data owner (DO), edge server (ES), cloud server (CS), and data user (DU). DO needs to outsource data while keeping the confidentiality and operation ability of data. At the same time, DO wants to have the right to control other users’ access to the data. ES is responsible for storing part of the keyword information from the DO nearby, assisting the data user to generate trapdoor, and reencrypting the ciphertext found by CS. CS stores encrypted data, encrypts index, and responds to data queries. The scheme mainly includes the following processes:(1)
Step 1 (data update): DO first extracts index from the outsourced files and generates index information. He first uses a symmetric encryption algorithm to encrypt index and asymmetric encryption algorithm to encrypt documents. Then DO uploads part of the keyword information to ES and uploads the encrypted index and ciphertext to CS.(2)
Step 2 (user authorization). Whenever a new authorized user DU joins the system, the DO generates the query key and the reencryption key. DO sends the query key to DU and the reencryption key to the ES near the DU.(3)
Step 3 (search keyword). DU generates a query trapdoor containing the keyword. The query trapdoor is sent to the ES, and then the ES generates the trapdoor for search and sends it to the CS. CS decrypts the encrypted index from the search trapdoor to get the relevant document identifier and then obtains the required ciphertext from the searched file identifier. Finally, the CS sends the searched ciphertext to the ES near the DU.(4)
Step 4 (reencryption). After obtaining the matching ciphertext, the ES finds the stored reencryption key of the target user and reencrypts the ciphertext. Finally, the reencrypted ciphertext that the DU has the ability to decrypt is generated and sent to the DU.(5)
Step 5 (decryption). DU uses its private key to decrypt.Figure 2
System model.The basic framework of the FSSE scheme based on the edge-cloud architecture in P2P network EMFSSE is as follows:(1)
Setupλ: it takes security parameters λ/μ as input and outputs public parameters Para.(2)
KeyGenPara: enter the public parameter Para, and the ES and the DO generate the required key, respectively. Specifically, the ES generates its public/private keypke/ske. The DO generates its public/private keypko/sko, secret key of encryption index fko/fko′, and keyword encryption key wk.(3)
UpdatePara,m,ind,W,∑: this operation is performed by the DO. It inputs public parameters Para, ciphertext m, document identifier ind, key set W related to the document, and keyword status map ∑ and outputs index information table T′, encrypted index set B, and ciphertext C and updates the map ∑.(4)
RegisterPara: when a new data user joins the system, first, his/her own public/private key pku/sku is generated. Then, DO authorizes the added user, inputs the public parametersPara, and generates the query key qku, query-related information qkc, and reencryption key rko⟶u for the new user DU. Finally, qkc,rko⟶u is sent to the ES and qku is sent to the DU.(5)
TrapdoorPara,qku,w: the DU takes public parameters Para, its query key qku, and query keyword w as input and outputs the trapdoor Traw of w.(6)
SearchPara,Traw,T;T,EDB: this operation is performed by ES and CS in cooperation. ES inputs public parameters Para, trapdoor Traw, and index information table T, outputs query token token, and sends it to the CS. The CS inputs encrypted index tree T, encrypts database EDB, and finally outputs ciphertext set C.(7)
Re−Encryptionrko⟶u,C: the ES inputs reencryption key rko⟶u and ciphertext set C and outputs reencrypted ciphertext set C′.(8)
DecryptionC′,sku: the operation is performed by the DU, which inputs the key sku and the reencrypted ciphertext set C′ and outputs the plaintext m corresponding to each ciphertext C′ in C′.


## 4.1. Design Goals

According to the information transmission requirements of P2P network and users, the scheme designed in this paper must meet the following goals:Efficiency: the index structure in the searchable encryption scheme has an important impact on search efficiency. We store the index in a tree structure to improve search efficiency. In the phase of ciphertext generation and search query, we utilize the edge-cloud architecture to improve the fast response capability of the whole system.Confidentiality: this is another key attribute. This scheme needs to ensure the confidentiality of data, index, and query. That is, the server cannot get the relevant information of the plaintext by analyzing the stored ciphertext or by reencrypting the ciphertext. And it also cannot get the relevant index information and data query when attacked by an adversary. In addition, this scheme provides forward privacy performance specifically against file injection attack [12].Dynamic update: this scheme supports the dynamic update of files including add, delete, and update functions. When the user wants to modify the data, he only needs to perform corresponding operations on the data index and the database.Correctness: correctness is the basic property of a searchable decryption scheme, which requires the system to provide services correctly. Specifically, as long as the correct trapdoor is provided and the system is executed sequentially in a legal manner, the search results must be correct.Multiusers: this attribute refers to the ability of the scheme to support data transmission between different users. And the data owner is able to authorize users and update their access rights at any time.


## 4.2. System Model

As shown in Figure2, our scheme has four entities: data owner (DO), edge server (ES), cloud server (CS), and data user (DU). DO needs to outsource data while keeping the confidentiality and operation ability of data. At the same time, DO wants to have the right to control other users’ access to the data. ES is responsible for storing part of the keyword information from the DO nearby, assisting the data user to generate trapdoor, and reencrypting the ciphertext found by CS. CS stores encrypted data, encrypts index, and responds to data queries. The scheme mainly includes the following processes:(1)
Step 1 (data update): DO first extracts index from the outsourced files and generates index information. He first uses a symmetric encryption algorithm to encrypt index and asymmetric encryption algorithm to encrypt documents. Then DO uploads part of the keyword information to ES and uploads the encrypted index and ciphertext to CS.(2)
Step 2 (user authorization). Whenever a new authorized user DU joins the system, the DO generates the query key and the reencryption key. DO sends the query key to DU and the reencryption key to the ES near the DU.(3)
Step 3 (search keyword). DU generates a query trapdoor containing the keyword. The query trapdoor is sent to the ES, and then the ES generates the trapdoor for search and sends it to the CS. CS decrypts the encrypted index from the search trapdoor to get the relevant document identifier and then obtains the required ciphertext from the searched file identifier. Finally, the CS sends the searched ciphertext to the ES near the DU.(4)
Step 4 (reencryption). After obtaining the matching ciphertext, the ES finds the stored reencryption key of the target user and reencrypts the ciphertext. Finally, the reencrypted ciphertext that the DU has the ability to decrypt is generated and sent to the DU.(5)
Step 5 (decryption). DU uses its private key to decrypt.Figure 2
System model.The basic framework of the FSSE scheme based on the edge-cloud architecture in P2P network EMFSSE is as follows:(1)
Setupλ: it takes security parameters λ/μ as input and outputs public parameters Para.(2)
KeyGenPara: enter the public parameter Para, and the ES and the DO generate the required key, respectively. Specifically, the ES generates its public/private keypke/ske. The DO generates its public/private keypko/sko, secret key of encryption index fko/fko′, and keyword encryption key wk.(3)
UpdatePara,m,ind,W,∑: this operation is performed by the DO. It inputs public parameters Para, ciphertext m, document identifier ind, key set W related to the document, and keyword status map ∑ and outputs index information table T′, encrypted index set B, and ciphertext C and updates the map ∑.(4)
RegisterPara: when a new data user joins the system, first, his/her own public/private key pku/sku is generated. Then, DO authorizes the added user, inputs the public parametersPara, and generates the query key qku, query-related information qkc, and reencryption key rko⟶u for the new user DU. Finally, qkc,rko⟶u is sent to the ES and qku is sent to the DU.(5)
TrapdoorPara,qku,w: the DU takes public parameters Para, its query key qku, and query keyword w as input and outputs the trapdoor Traw of w.(6)
SearchPara,Traw,T;T,EDB: this operation is performed by ES and CS in cooperation. ES inputs public parameters Para, trapdoor Traw, and index information table T, outputs query token token, and sends it to the CS. The CS inputs encrypted index tree T, encrypts database EDB, and finally outputs ciphertext set C.(7)
Re−Encryptionrko⟶u,C: the ES inputs reencryption key rko⟶u and ciphertext set C and outputs reencrypted ciphertext set C′.(8)
DecryptionC′,sku: the operation is performed by the DU, which inputs the key sku and the reencrypted ciphertext set C′ and outputs the plaintext m corresponding to each ciphertext C′ in C′.


## 5. Scheme Construction

This section describes the structure of the scheme EMFSSE in detail.


### 5.1. System Initialization Phase

Setupλ,μ⟶Para: taking security parameters λ and μ as input, the algorithm generates bilinear mapping e:G1×G1⟶G2, where G1 and G2 are two cyclic groups of order p≥2λ. Then, it randomly chooses g,g1,g2,h1,h2←RG1, calculates L=eh1,h2, and lets P=g,g1,g2,h1,h2,L; meanwhile, it selects some secure hash functions H0:0,1∗⟶0,1λ+μ+1+logN, H1,1′:0,1∗⟶0,1μ, H2:0,1∗⟶0,1λ, and H3,4:0,1∗⟶0,1∗ and selects one-way permutation functions G and F. Finally, the DO initializes an empty map ∑ that stores its state, the ES initializes the empty index information table T, and the CS initializes an empty index tree T. Publish public parameters Para=P,G,F,H0,1,1′,2,3,4.


### 5.2. Key Generation Phase

KeyGenPara⟶ske,pke;sko,pko,fko,fko′′,wk: it inputs the public parameters Para.(1)
Step 1: the ES randomly selectsz←Rℤp and generates private key ske=z and public key pke=g2z.(2)
Step 2: the DO randomly selectsxo,yo←Rℤp, respectively, generates private key sko=xo,yo and public key pko=h1xo,g1yo, respectively, selects key fko,fko′′←R0,1λ of encryption index, and randomly selects key of encryption key wk←RZp∗.


### 5.3. Update Phase

UpdatePara,m,op,ind,W,∑⟶C,T′,B: when a new file is added, the DO input public parameters. Para, file m, operator op=add (op=add/del, resp., for add or delete operation), file identifier ind, the file related keyword set W, and DO’s status ∑, and then do operations as follows:(1)
Step 1 (documents encryption): the DO randomly selectsr←RZp and generates ciphertext C=Lr⋅m,g1r,eh1,g21/r,xor=c0,c1,c2,c3.(2)
Step 2 (index encryption): the DO initializes an empty setB and a table T′. For each keyword w∈W, DO first encrypts it to get Trw=H4eH3w,gwk and then uses function ReGen (as shown in Table 2) to calculate the identifier and key of the block currently indexed by keyword w, id,key←ReGenw,∑w=c. Then, DO makes pre.id=id, pre.key=key, and c++ and generates the identifier and key of the new block id,key←ReGenw,c. Finally, DO calculates the block key mask←H0id,key, encrypts the index block with it b←id,″ind‖op″‖pre.key‖pre.id⊕mask, stores the index information id,key in the table T′ indexed by Trw, where T′Trw=id,key, and stores the block b in the set B.(a)
The algorithm finally outputs index information tableT′, ciphertext C, and encrypted index set B. The table T′ is sent to the ES which stores its contents in an index information table. The ciphertext C and set B are sent to the CS which stores C in the encrypted database EDB and inserts the blocks into the encrypted index tree T.Table 2
ReGen algorithm (note: iw represents w or a unique identifier of w).
AlgorithmReGenw,∑w=c1:ifc==−1then id←⊥,key←⊥2:else3:Kw←Ffkow,Kw′←Ffko′w4:ST0w←Giw5:ifc==0then6:id←H1Kw,ST0w;key←H2Kw′,ST0w7:else8:STcw←H1′cST0w9:id←H1Kw,ST0w;key←H2Kw′,ST0w10:end if11:end if12:Returnid,key


### 5.4. Authorization Phase

RegisterPara⟶sku,pku;qku,qkc,rko⟶u: input the public parameter Para; the algorithm is completed by the new user DU and DO in order.(1)
Step 1: when a new user DU joins the system, it randomly selectsxu,yu←Rℤp to generate a private key sku=xu,yu and a public key pku=h1xu,g1yu. Then, publish public key, indicating that a new user has joined the system.(2)
Step 2: the new user DU sends his public key to DO and then is authorized by DO to access the data. The DO randomly selectsqku←RZp∗ as the query key, calculates qkc=gwk/qku, and generates the proxy reencryption key rko⟶u=h2g1yug2z1/xo of DU.


### 5.5. Trapdoor Generation Phase

TrapdoorPara,qku,w⟶Traw: the DU inputs the public parameter Para, the query key qku, and the query keyword w, then generates the query trapdoor Traw=H3wqku, and sends it to ES.


### 5.6. Search Phase

SearchPara,Traw,T;T,EDB⟶C: the algorithm is completed by the cooperation of ES and CS.(1)
Step 1: input the query trapdoorTraw and the encrypted keyword status table T, and the ES generates Trw=H4eTraw,qkc, then queries the table T to get the search trapdoor id,key←TTrw, and sends the search trapdoor token=id,key to the CS.(2)
Step 2: taking the search trapdoortoken, index tree T, and encryption database EDB as input, the CS first initializes the empty sets S and C and sets i←0. Then, CS finds the latest block b←Tid by trapdoor token, calculates the block key mask←H0key,id, decrypts the block with mask, and obtains ″ind‖op″‖pre.key‖pre.id←b.data⊕mask, where b.value=ind‖op. And the CS stores b.value in Si±± (merges the same ind in S according to op), sets id←pre.id and key←pre.key, and repeats the above process until id≠⊥ and key≠⊥. Finally, CS finds the corresponding encrypted data C in EDB by ind∈S, stores C in C, and sends the search result C to the ES.


### 5.7. Reencryption Phase

ReencryptionC,rko⟶u⟶C′: the ES finds the reencryption key rko⟶u corresponding to the DU, inputs it and set C, and initializes an empty set C′. For each C∈C, the ES reencrypts it to get reencrypted ciphertext C′=c0',c1',c2'=c0,c1,ec3,rko⟶u/c2z, stores the new ciphertext in C′, and then sends C′ to the DU.


### 5.8. Decryption Phase

DecryptionC′,sku⟶m: inputting reencrypted ciphertext C′ and private key sku, DU decrypts each C′∈C′ to get all the required ciphertext m=c0'⋅eh1,c1'yu/c2'. The algorithm can get the final plaintext files m.


## 5.1. System Initialization Phase

Setupλ,μ⟶Para: taking security parameters λ and μ as input, the algorithm generates bilinear mapping e:G1×G1⟶G2, where G1 and G2 are two cyclic groups of order p≥2λ. Then, it randomly chooses g,g1,g2,h1,h2←RG1, calculates L=eh1,h2, and lets P=g,g1,g2,h1,h2,L; meanwhile, it selects some secure hash functions H0:0,1∗⟶0,1λ+μ+1+logN, H1,1′:0,1∗⟶0,1μ, H2:0,1∗⟶0,1λ, and H3,4:0,1∗⟶0,1∗ and selects one-way permutation functions G and F. Finally, the DO initializes an empty map ∑ that stores its state, the ES initializes the empty index information table T, and the CS initializes an empty index tree T. Publish public parameters Para=P,G,F,H0,1,1′,2,3,4.


## 5.2. Key Generation Phase

KeyGenPara⟶ske,pke;sko,pko,fko,fko′′,wk: it inputs the public parameters Para.(1)
Step 1: the ES randomly selectsz←Rℤp and generates private key ske=z and public key pke=g2z.(2)
Step 2: the DO randomly selectsxo,yo←Rℤp, respectively, generates private key sko=xo,yo and public key pko=h1xo,g1yo, respectively, selects key fko,fko′′←R0,1λ of encryption index, and randomly selects key of encryption key wk←RZp∗.


## 5.3. Update Phase

UpdatePara,m,op,ind,W,∑⟶C,T′,B: when a new file is added, the DO input public parameters. Para, file m, operator op=add (op=add/del, resp., for add or delete operation), file identifier ind, the file related keyword set W, and DO’s status ∑, and then do operations as follows:(1)
Step 1 (documents encryption): the DO randomly selectsr←RZp and generates ciphertext C=Lr⋅m,g1r,eh1,g21/r,xor=c0,c1,c2,c3.(2)
Step 2 (index encryption): the DO initializes an empty setB and a table T′. For each keyword w∈W, DO first encrypts it to get Trw=H4eH3w,gwk and then uses function ReGen (as shown in Table 2) to calculate the identifier and key of the block currently indexed by keyword w, id,key←ReGenw,∑w=c. Then, DO makes pre.id=id, pre.key=key, and c++ and generates the identifier and key of the new block id,key←ReGenw,c. Finally, DO calculates the block key mask←H0id,key, encrypts the index block with it b←id,″ind‖op″‖pre.key‖pre.id⊕mask, stores the index information id,key in the table T′ indexed by Trw, where T′Trw=id,key, and stores the block b in the set B.(a)
The algorithm finally outputs index information tableT′, ciphertext C, and encrypted index set B. The table T′ is sent to the ES which stores its contents in an index information table. The ciphertext C and set B are sent to the CS which stores C in the encrypted database EDB and inserts the blocks into the encrypted index tree T.Table 2
ReGen algorithm (note: iw represents w or a unique identifier of w).
AlgorithmReGenw,∑w=c1:ifc==−1then id←⊥,key←⊥2:else3:Kw←Ffkow,Kw′←Ffko′w4:ST0w←Giw5:ifc==0then6:id←H1Kw,ST0w;key←H2Kw′,ST0w7:else8:STcw←H1′cST0w9:id←H1Kw,ST0w;key←H2Kw′,ST0w10:end if11:end if12:Returnid,key


## 5.4. Authorization Phase

RegisterPara⟶sku,pku;qku,qkc,rko⟶u: input the public parameter Para; the algorithm is completed by the new user DU and DO in order.(1)
Step 1: when a new user DU joins the system, it randomly selectsxu,yu←Rℤp to generate a private key sku=xu,yu and a public key pku=h1xu,g1yu. Then, publish public key, indicating that a new user has joined the system.(2)
Step 2: the new user DU sends his public key to DO and then is authorized by DO to access the data. The DO randomly selectsqku←RZp∗ as the query key, calculates qkc=gwk/qku, and generates the proxy reencryption key rko⟶u=h2g1yug2z1/xo of DU.


## 5.5. Trapdoor Generation Phase

TrapdoorPara,qku,w⟶Traw: the DU inputs the public parameter Para, the query key qku, and the query keyword w, then generates the query trapdoor Traw=H3wqku, and sends it to ES.


## 5.6. Search Phase

SearchPara,Traw,T;T,EDB⟶C: the algorithm is completed by the cooperation of ES and CS.(1)
Step 1: input the query trapdoorTraw and the encrypted keyword status table T, and the ES generates Trw=H4eTraw,qkc, then queries the table T to get the search trapdoor id,key←TTrw, and sends the search trapdoor token=id,key to the CS.(2)
Step 2: taking the search trapdoortoken, index tree T, and encryption database EDB as input, the CS first initializes the empty sets S and C and sets i←0. Then, CS finds the latest block b←Tid by trapdoor token, calculates the block key mask←H0key,id, decrypts the block with mask, and obtains ″ind‖op″‖pre.key‖pre.id←b.data⊕mask, where b.value=ind‖op. And the CS stores b.value in Si±± (merges the same ind in S according to op), sets id←pre.id and key←pre.key, and repeats the above process until id≠⊥ and key≠⊥. Finally, CS finds the corresponding encrypted data C in EDB by ind∈S, stores C in C, and sends the search result C to the ES.


## 5.7. Reencryption Phase

ReencryptionC,rko⟶u⟶C′: the ES finds the reencryption key rko⟶u corresponding to the DU, inputs it and set C, and initializes an empty set C′. For each C∈C, the ES reencrypts it to get reencrypted ciphertext C′=c0',c1',c2'=c0,c1,ec3,rko⟶u/c2z, stores the new ciphertext in C′, and then sends C′ to the DU.


## 5.8. Decryption Phase

DecryptionC′,sku⟶m: inputting reencrypted ciphertext C′ and private key sku, DU decrypts each C′∈C′ to get all the required ciphertext m=c0'⋅eh1,c1'yu/c2'. The algorithm can get the final plaintext files m.


## 6. Security Proof

In this section, some important design objectives mentioned in Section3 will be proved. Specifically, we will prove that the scheme can provide correctness, confidentiality, and forward security.


### 6.1. Correctness

An example is given to prove the correctness of the scheme. Suppose that there are filesm1,m2 with keyword w1, and their corresponding file identifiers are ind1,ind2.Firstly, plaintext and index information are encrypted, respectively. We randomly selectr1,r2←RZp, generate ciphertexts C1=Lr1⋅m1,g1r1,eh1,g21/r1,Xor1=c01,c11,c21,c31 and C2=Lr2⋅m2,g1r2,eh1,g21/r2,Xor2=c02,c12,c22,c32, and generate encrypted keyword information Trw1←H4eH3w1,gwk. We also generate index blocks b1=id1,ind‖op‖⊥‖⊥⊕mask1 and b2=id2,ind2‖op‖id1‖key1⊕mask2 and store the client status ∑w=c=1 (initialization value is −1) at this moment and encrypted keyword information list TTrw1=id2,key2.Secondly, we search for the file containing the keywordw1. The query token of w1 is generated Traw1=H3w1qku, the encrypted keyword information Trw1 is generated from the query token Trw1←H4eTraw1,qkc, and then the search token token=id2,key2 is obtained from the Trw1 query table T. Through token token, we find block b2 in the index. Then, we generate the decryption secret key mask2←Hkey2,id2 of b2 and do XOR operation to get the value of b2, where b2.value←Tid.data⊕mask, which contains the information of ind2 and the information of the previous index block id1,key1. Similarly, we get b1 and decrypt it to get ind1 and previous index block information ⊥,⊥ and then terminate the search. Through ind1,2, we can find the corresponding ciphertext C1,2. In this scheme, the ES is required to reencrypt the ciphertext, and the DU can decrypt it. Taking C1 as an example, we first generate the reencryption key rko⟶u=h2YuZ1/xo, then use it to encrypt the ciphertext, and get the reencrypted ciphertext C1′=c01′′,c11′′,c21′′=c01,c11,ec31,rko⟶u/c21z, where c21′′=ec31,rko⟶u/c21z=eh1xo⋅r1,h2g1yug2z1/xo/eh1,g21/r1⋅z=eh1,h2g1r12yu, and the final ciphertext form is C1′=eh1,h2r1⋅m1,g1r1,eh1,h2g1r12yu.Finally, we decrypt the final reencrypted ciphertext:c01′′⋅eh1,c11′′yu/c21′′=m1.To sum up, the scheme is correct.


### 6.2. Confidentiality

The EMFSSE scheme is proved to be secure according to the following theorem.Theorem 1.
In the process of reencryption, the EMFSSE scheme is CPA secure based on the DBDH assumption. Specifically, letA be the adversary of attacking EMFSSE scheme with ε advantage in CPA game, and then there is an adversary B who at least solves DBDH assumption with ε/qokg advantage.Proof.
B randomly selects five tuples T=g,A=ga,B=gb,C=gc,Z as input. The goal of B is to determine whether Z is random value eg,gz or eg,gabc by playing the following game with adversary A, where a,b,c,z←RZp.(1)
Setupλ: randomly select δ←RZp, set g1=g,g2=gδ,h1=ga,h2=gb,L=ega,gb, and return P=g1,g2,h1,h2,L. Run ES−KeyGenP: randomly select e←RZp, set ske=e and pke=g2e, and return pke.(2)
Phase1: A first performs polynomial private times key extraction query. When receiving the query from A, B replies as follows:(a)
Oekgλ: return the private key of ES ske=e.(b)
Ookgo: select xo,yo←RZp randomly.(i)
IfB guesses that it is the target user for this guess, that is, o′=o, then calculate pko′=h1xo′,h2−1gyo′=h1xo′,g1yo′−b and sko′=xo′,yo′−b, hide information sko′, and return pko′.(ii)
Otherwise,o′≠o, calculate pko=h1xo,g1yo and sko=xo,yo, hide information sko, and return pko.Oukgu: randomly select xu,yu←RZp, let sku=xu,yu and pku=h1xu,g1yu, and return sku,pku.Orkgpko,pku,pke, Ookg and Oukg generate pko and pku, respectively; B runs Reencryption−KeyGensko,pku,pke and returns reencryption key rko⟶u=h2g1yug2e1/xo.(3)
Challenge: when A decides to complete Phase1, it constructs two equal-length messages m0,1 and public key pko′ and sends them to B. B performs the following operations:(i)
Ifpko≠pko′, B outputs random string and terminates.(ii)
Otherwise,B randomly selects a value β∈0,1 and constructs a ciphertext C=c0′,c1′,c2′ for the challenge, where c0′=Z⋅mβ, c1′=g1r=gc, and c2′=ec3,W/c2e=eg,gab+1c2·yu′, and hides information r=c.Supposing thatA does Ookg queries at most qokg times, then in Challenge, the probability that B guesses the right o′ is at least 1/qokg.(4)
Phase2. B answers A’s question, just like in Phase1. A outputs its guess β′∈0,1. If β=β′, B outputs 1; otherwise, it outputs 0; then the advantage of B in solving the DBDH problem is at least ε/qokg. The proof is complete.


### 6.3. Forward Privacy

We refer to the form in the scheme [17] to prove the forward privacy of our scheme. The following is a simplified analysis:DefineHistw as the history of the keyword w which lists all the modifications to the DBw over a period of time. F is the pseudorandom function controlled by the key, inputs λ bit string and key fk, and outputs λ bit string. H0,1,1′,2 are secure hash functions defined on random oracle model.Theorem 2.
L−adaptively−secure of EMFSSE scheme. The leakage function L∑=L∑Srch,L∑Updt is defined. If L∑Srchw=spw,Histw and L∑Updtw=w,ind=⊥, EMFSSE is an L∑-adaptive security scheme with forward security.Proof.
Set security parametersλ and μ. Here, we use indistinguishable games derived from the real world to prove the theorem.(1)
GameG0: G0 is an SSE security game SSERealAERMFλ,μ in the real world. The relationship between the two can be expressed as PSSERealAERMFλ,μ=1=PG0=1.(2)
GameG1: G1 uses random selection instead of calling F to generate keys Kw and Kw∗ which are used for generating id and key in ReGen. When a new index w,ind is added, the keys Kw and Kw∗ are randomly selected and added to the key table KEY. The next time someone asks for the keyword w, it checks the table KEY first. If there is a corresponding key in the table, the stored key is called directly; if not, randomly select the keys Kw and Kw∗ and store them in the table. Thus, a reduction is established to distinguish F from real random functions. That is, there are effective adversaries A, PG0=1−PG1=1≤AdvF,Aprfλ,μ.(3)
GameG2: G2 and G1 have consistent behavior. Except for some inconsistent results of random oracle requests in G2, the inconsistent time is recorded as Bad. Because the random string u of H0 is generated in the update operation and updated in the search protocol, there is a time difference Bad. If the adversary asks H0 before searching, H0 randomly selects u′ to return to the adversary according to the properties of random oracle. After this request, u is programmed to H0.(a)
Through the consistent transition time nodeBad, we can limit the distinguishing advantage between G2 and G1: PG2=1−PG1=1≤PBad. Probability of Bad: if and only if the adversary queries H0 in the random oracle model with ind, because the output mask is randomly selected from 0,1λ+μ+1+logN, the probability of the adversary selecting the corresponding mask is 1/2λ+μ+1+logN. Suppose that a probabilistic polynomial time adversary can query with the random oracle for ployλ times at most; then we can know that PBad≤ployλ/2λ+μ+1+logN is negligible; that is, PG2=1=PG1=1.(4)
GameG3: G3 is similar to G2 in that it performs the same operation on H0 in G2 for H1,1′,2. The difference is the probability of Bad. If and only if the adversary can query H1,1′,2 in a random oracle model with correct input, the generated string length is μ,μ,λ, respectively. So the probability of the adversary choosing the right output value is 1/2μ, 1/2μ, and 1/2λ, respectively. Assuming that a probabilistic polynomial time adversary can perform ployγ queries at most with a random oracle, then PBad1≤ployγ/2μ, PBad2≤ployγ/2μ and PBad3≤ployγ/2λ are all negligible; that is, PG3=1=PG2=1.(5)
GameG4: G4 is similar to G3, but it removes information unrelated to hash functions H0,1,1′,2; that is, it is a single round trip protocol. Therefore, in the random oracle model, G4 and G3 cannot be distinguished; that is, PG4=1=PG3=1.(6)
SimulatorS: The code in G4 is divided into two parts: leak function and simulator. In G4, the statusu of the block is stored, which means that when the time is u, the values in tables Bmask∗, Bkey∗, and Bid∗ are mask, key, and id, respectively, and their essence is random string. The simulator uses the counter κ instead of the keyword w. Its initial value is 0, and the value is increased by 1 every time the update operation is performed. The new value is stored in tables Bmask∗κ, Bkey∗κ, and Bid∗κ. In the view of adversary A, the update protocol only outputs three random strings, while the search protocol outputs the same number of random strings (key, id, and mask, resp.). So we get the equation PG4=1−PSSEIdealA,S,L∑ERMF=1=0.Conclusion: According to the above games and simulatorS and hash functions H0,1,1′,2, the following formula can be obtained: PSSERealAERMFλ,ν=1−PSSEIdealA,S,L∑ERMF=1≤AdvF,Aprfλ,μ.


## 6.1. Correctness

An example is given to prove the correctness of the scheme. Suppose that there are filesm1,m2 with keyword w1, and their corresponding file identifiers are ind1,ind2.Firstly, plaintext and index information are encrypted, respectively. We randomly selectr1,r2←RZp, generate ciphertexts C1=Lr1⋅m1,g1r1,eh1,g21/r1,Xor1=c01,c11,c21,c31 and C2=Lr2⋅m2,g1r2,eh1,g21/r2,Xor2=c02,c12,c22,c32, and generate encrypted keyword information Trw1←H4eH3w1,gwk. We also generate index blocks b1=id1,ind‖op‖⊥‖⊥⊕mask1 and b2=id2,ind2‖op‖id1‖key1⊕mask2 and store the client status ∑w=c=1 (initialization value is −1) at this moment and encrypted keyword information list TTrw1=id2,key2.Secondly, we search for the file containing the keywordw1. The query token of w1 is generated Traw1=H3w1qku, the encrypted keyword information Trw1 is generated from the query token Trw1←H4eTraw1,qkc, and then the search token token=id2,key2 is obtained from the Trw1 query table T. Through token token, we find block b2 in the index. Then, we generate the decryption secret key mask2←Hkey2,id2 of b2 and do XOR operation to get the value of b2, where b2.value←Tid.data⊕mask, which contains the information of ind2 and the information of the previous index block id1,key1. Similarly, we get b1 and decrypt it to get ind1 and previous index block information ⊥,⊥ and then terminate the search. Through ind1,2, we can find the corresponding ciphertext C1,2. In this scheme, the ES is required to reencrypt the ciphertext, and the DU can decrypt it. Taking C1 as an example, we first generate the reencryption key rko⟶u=h2YuZ1/xo, then use it to encrypt the ciphertext, and get the reencrypted ciphertext C1′=c01′′,c11′′,c21′′=c01,c11,ec31,rko⟶u/c21z, where c21′′=ec31,rko⟶u/c21z=eh1xo⋅r1,h2g1yug2z1/xo/eh1,g21/r1⋅z=eh1,h2g1r12yu, and the final ciphertext form is C1′=eh1,h2r1⋅m1,g1r1,eh1,h2g1r12yu.Finally, we decrypt the final reencrypted ciphertext:c01′′⋅eh1,c11′′yu/c21′′=m1.To sum up, the scheme is correct.


## 6.2. Confidentiality

The EMFSSE scheme is proved to be secure according to the following theorem.Theorem 1.
In the process of reencryption, the EMFSSE scheme is CPA secure based on the DBDH assumption. Specifically, letA be the adversary of attacking EMFSSE scheme with ε advantage in CPA game, and then there is an adversary B who at least solves DBDH assumption with ε/qokg advantage.Proof.
B randomly selects five tuples T=g,A=ga,B=gb,C=gc,Z as input. The goal of B is to determine whether Z is random value eg,gz or eg,gabc by playing the following game with adversary A, where a,b,c,z←RZp.(1)
Setupλ: randomly select δ←RZp, set g1=g,g2=gδ,h1=ga,h2=gb,L=ega,gb, and return P=g1,g2,h1,h2,L. Run ES−KeyGenP: randomly select e←RZp, set ske=e and pke=g2e, and return pke.(2)
Phase1: A first performs polynomial private times key extraction query. When receiving the query from A, B replies as follows:(a)
Oekgλ: return the private key of ES ske=e.(b)
Ookgo: select xo,yo←RZp randomly.(i)
IfB guesses that it is the target user for this guess, that is, o′=o, then calculate pko′=h1xo′,h2−1gyo′=h1xo′,g1yo′−b and sko′=xo′,yo′−b, hide information sko′, and return pko′.(ii)
Otherwise,o′≠o, calculate pko=h1xo,g1yo and sko=xo,yo, hide information sko, and return pko.Oukgu: randomly select xu,yu←RZp, let sku=xu,yu and pku=h1xu,g1yu, and return sku,pku.Orkgpko,pku,pke, Ookg and Oukg generate pko and pku, respectively; B runs Reencryption−KeyGensko,pku,pke and returns reencryption key rko⟶u=h2g1yug2e1/xo.(3)
Challenge: when A decides to complete Phase1, it constructs two equal-length messages m0,1 and public key pko′ and sends them to B. B performs the following operations:(i)
Ifpko≠pko′, B outputs random string and terminates.(ii)
Otherwise,B randomly selects a value β∈0,1 and constructs a ciphertext C=c0′,c1′,c2′ for the challenge, where c0′=Z⋅mβ, c1′=g1r=gc, and c2′=ec3,W/c2e=eg,gab+1c2·yu′, and hides information r=c.Supposing thatA does Ookg queries at most qokg times, then in Challenge, the probability that B guesses the right o′ is at least 1/qokg.(4)
Phase2. B answers A’s question, just like in Phase1. A outputs its guess β′∈0,1. If β=β′, B outputs 1; otherwise, it outputs 0; then the advantage of B in solving the DBDH problem is at least ε/qokg. The proof is complete.


## 6.3. Forward Privacy

We refer to the form in the scheme [17] to prove the forward privacy of our scheme. The following is a simplified analysis:DefineHistw as the history of the keyword w which lists all the modifications to the DBw over a period of time. F is the pseudorandom function controlled by the key, inputs λ bit string and key fk, and outputs λ bit string. H0,1,1′,2 are secure hash functions defined on random oracle model.Theorem 2.
L−adaptively−secure of EMFSSE scheme. The leakage function L∑=L∑Srch,L∑Updt is defined. If L∑Srchw=spw,Histw and L∑Updtw=w,ind=⊥, EMFSSE is an L∑-adaptive security scheme with forward security.Proof.
Set security parametersλ and μ. Here, we use indistinguishable games derived from the real world to prove the theorem.(1)
GameG0: G0 is an SSE security game SSERealAERMFλ,μ in the real world. The relationship between the two can be expressed as PSSERealAERMFλ,μ=1=PG0=1.(2)
GameG1: G1 uses random selection instead of calling F to generate keys Kw and Kw∗ which are used for generating id and key in ReGen. When a new index w,ind is added, the keys Kw and Kw∗ are randomly selected and added to the key table KEY. The next time someone asks for the keyword w, it checks the table KEY first. If there is a corresponding key in the table, the stored key is called directly; if not, randomly select the keys Kw and Kw∗ and store them in the table. Thus, a reduction is established to distinguish F from real random functions. That is, there are effective adversaries A, PG0=1−PG1=1≤AdvF,Aprfλ,μ.(3)
GameG2: G2 and G1 have consistent behavior. Except for some inconsistent results of random oracle requests in G2, the inconsistent time is recorded as Bad. Because the random string u of H0 is generated in the update operation and updated in the search protocol, there is a time difference Bad. If the adversary asks H0 before searching, H0 randomly selects u′ to return to the adversary according to the properties of random oracle. After this request, u is programmed to H0.(a)
Through the consistent transition time nodeBad, we can limit the distinguishing advantage between G2 and G1: PG2=1−PG1=1≤PBad. Probability of Bad: if and only if the adversary queries H0 in the random oracle model with ind, because the output mask is randomly selected from 0,1λ+μ+1+logN, the probability of the adversary selecting the corresponding mask is 1/2λ+μ+1+logN. Suppose that a probabilistic polynomial time adversary can query with the random oracle for ployλ times at most; then we can know that PBad≤ployλ/2λ+μ+1+logN is negligible; that is, PG2=1=PG1=1.(4)
GameG3: G3 is similar to G2 in that it performs the same operation on H0 in G2 for H1,1′,2. The difference is the probability of Bad. If and only if the adversary can query H1,1′,2 in a random oracle model with correct input, the generated string length is μ,μ,λ, respectively. So the probability of the adversary choosing the right output value is 1/2μ, 1/2μ, and 1/2λ, respectively. Assuming that a probabilistic polynomial time adversary can perform ployγ queries at most with a random oracle, then PBad1≤ployγ/2μ, PBad2≤ployγ/2μ and PBad3≤ployγ/2λ are all negligible; that is, PG3=1=PG2=1.(5)
GameG4: G4 is similar to G3, but it removes information unrelated to hash functions H0,1,1′,2; that is, it is a single round trip protocol. Therefore, in the random oracle model, G4 and G3 cannot be distinguished; that is, PG4=1=PG3=1.(6)
SimulatorS: The code in G4 is divided into two parts: leak function and simulator. In G4, the statusu of the block is stored, which means that when the time is u, the values in tables Bmask∗, Bkey∗, and Bid∗ are mask, key, and id, respectively, and their essence is random string. The simulator uses the counter κ instead of the keyword w. Its initial value is 0, and the value is increased by 1 every time the update operation is performed. The new value is stored in tables Bmask∗κ, Bkey∗κ, and Bid∗κ. In the view of adversary A, the update protocol only outputs three random strings, while the search protocol outputs the same number of random strings (key, id, and mask, resp.). So we get the equation PG4=1−PSSEIdealA,S,L∑ERMF=1=0.Conclusion: According to the above games and simulatorS and hash functions H0,1,1′,2, the following formula can be obtained: PSSERealAERMFλ,ν=1−PSSEIdealA,S,L∑ERMF=1≤AdvF,Aprfλ,μ.


## 7. Comparisons and Evaluation

In this section, the proposed scheme is compared with other schemes. And then, we implement the EMFSSE scheme and evaluate its performance.


### 7.1. Comparisons

Table3 shows the differences in theoretical computation cost and other functions between EMRF and other schemes (Bost [12] scheme, Chen et al. [21] scheme, and Wang et al. [15] scheme). N is the number of indexes containing the keyword w; E1 and E2 represent the multiplication in groups G1 and G2, respectively; e is a bilinear pair; M represents secure map-to-point operation; H means the secure hash function; T/T−1 represents trapdoor function and its inverse operation (public key primitives, such as RSA), respectively; F/F−1 represents a pair of pseudorandom permutations (such as AES or DES).Table 3
Comparison with other schemes.
SchemeUpdateTrapdoorSearchForward privacyMultiuserBost [12]H+N×2h+THN×T−1+2H√×Chen et al. [21]2E1+e+M+F+6H+N×2He+M+E1+H4H+N×2H√×Wang et al. [15]2E1+e+H+N×E2E1+HN×e××EMFSSEe+E2+T+7H+2F+N×HE1+HN×H√√As shown in Table3, compared with other relevant schemes, the proposed scheme has better performance. For all schemes, in the update phase, the computational complexity is linearly related to the number of indexes N. Among them, the Bost scheme of [12] has a major flaw that it does public key operation T for N times. Because of its slow encryption, the scheme is limited in large data sets. The computational complexity of Wang’s scheme is 2E1+e+H+N×E2. Among them, operation e takes a lot of time, but it is independent of index. This scheme calls E2 once for each index, which leads to relatively high consumption. The computational complexity of Chen’s scheme and our scheme is 2E1+e+M+F+6H+N×2H and e+E2+T+7H+2F+N×H, respectively. The operation related to the index number is only the hash function, so it is more efficient than the previous two schemes. However, it is worth noting that Chen’s scheme uses map-to-point operation with high cost. To sum up, among the four schemes, our scheme has the best update efficiency.In the trapdoor generation phase, the complexity of each trapdoor generated by Bost’s scheme, Chen’s scheme, Wang’s scheme, and EMFSSE scheme isH, e+M+E1+H, E1+H, and E1+H, respectively. Obviously, Chen’s scheme has a relatively high complexity of generating a trapdoor, while Bost’s scheme has relatively optimal complexity. Wang’s scheme and our scheme have the same complexity, which is slightly higher than Bost’s scheme, but it is a must to extend functionality and improve security. In most cases, the diminished performance is acceptable.Similar to the update phase, the computational complexity of all schemes in the search phase is also linearly related toN. In order to get each search result, Wang’s scheme requires a time-consuming bilinear mapping, and Bost’s scheme requires RSA decryption T−1, both of them are expensive. Chen’s scheme and EMFSSE scheme only need to perform the corresponding hash function operation, which is less time-consuming. Obviously, the consumption of the EMFSSE scheme is lower.In terms of function, compared with other schemes, the EMFSSE scheme supports forward privacy and multiuser searchable encryption, which can resist file injection attacks and extend the performance of the scheme to multiuser. In conclusion, the EMFSSE scheme has relatively good performance and low computational costs.


### 7.2. Evaluation

We do the experiment on the personal computer with Intel Core i5-3337 CPU and 8 GB DDR3 RAM. We use C++ to realize the core function of EMFSSE.Specifically, we set the security parameters ofλ=128 bits and μ=64 bits, use HMAC to implement the hash function, and choose pseudorandom permutation (CBC model, 128-bit key). And we use the 128-bit security level MIRACL CryptoSDK in [36] to calculate the efficiency of pairings and exponentials operation of bilinear pairing. The time cost of the main operation is shown in Table 4. It takes 105.77 ms to compute bilinear pairs, 34.45 ms to compute exponents in G1, and 8.87 ms to compute exponents in G2. It takes 322.4 ms to perform map-to-point operations, and the hash operation takes 0.001 ms. AES algorithm takes 0.005 ms for both encryption and decryption. The execution time of the RSA encryption/decryption algorithm took 0.189 ms and 5.896 ms, respectively.Table 4
Time consumption of main operations.
OperationeE1E2MHF/F−1TT−1Time cost (ms)105.7734.458.87322.40.0010.0050.1895.896Figures3–5 show the approximate time costs of update algorithm, search algorithm, and token generation algorithm with different index numbers (1.5×104∼5.0×104).Update evaluation: Figure3 shows the time-consuming comparison of updating algorithms of Bost’s scheme, Chen’s scheme, and EMRF scheme. (Wang’s scheme is not shown in the figure due to its high computational complexity.) As shown in the figure, the abscissa is datasets containing 1×104∼5×104 indexes, respectively, with an interval of 0.5×104. When the number of indexes is 1×104, the cost of Bost’s scheme, Chen’s scheme, and EMFSSE scheme is 1.91 s, 0.52 s, and 0.12 s, respectively. Bost’s scheme has a higher time consumption, Chen’s scheme and EPMF have relatively lower time consumption, and EMFSSE has the lowest. The time-consuming of all three schemes increases as the number of indexes increases. Among them, the growth rate of Bost’s scheme is the fastest, while that of Chen and EPMF schemes is low and basically flat. In general, the EMFSSE scheme has a lower time-consuming and growth trend during the update phase.Search evaluation: Figure4 shows the time-consuming comparison of the search algorithms of Chen’s scheme and EMFSSE scheme. (Due to the large time consumption of the other two schemes, no comparison is made.) The abscissa is datasets containing 1×104∼5×104 indexes, respectively, with an interval of 0.5×104. When the number of indexes is 1×104, the cost of Chen’s scheme and EMFSSE scheme is 20 ms and 10 ms, respectively. Similar to the update algorithm, the time consumption of the search algorithm also increases with the number of indexes, and the EMFSSE scheme is better than Chen’s scheme in both time-consuming and growth trends.Token generation evaluation: Figure5 shows the time-consuming comparison of Bost’s scheme, Chen’s scheme, Wang’s scheme, and EMFSSE scheme in a single trapdoor generation algorithm. Chen’s scheme needs to do a map-to-point operation, so it is high time-consuming and inefficient. EMFSSE scheme consumes 140.222 ms to generate one trapdoor, but it is worth noting that EMFSSE transfers part of the operation of generating trapdoor to the edge platform, which saves about 75% of the computational costs of the user client. That is to say, the time consumed to generate trapdoor at the DU side is 34.451 ms, which is the same as Wang’s scheme. Moreover, compared with the EMFSSE scheme, Wang’s scheme can neither support data transmission between multiple users nor meet forward security. In addition, the time EMFSSE scheme consumes is significantly longer than that of Bost’s scheme, which only uses the hash function once to generate a trapdoor. But we think that it is necessary to construct a multiuser searchable scheme.Figure 3
Time consumption of update algorithm.Figure 4
Time consumption of search algorithm.Figure 5
Time consumption of token generation algorithm.In order to show the advantages of the EMFSSE scheme obtained by using edge computing, EMFSSE is compared with Wang’s scheme that also uses edge computing, and the proposed scheme that does not use edge computing. Figure6 shows the comparison of various schemes for generating a ciphertext. Firstly, the overall time of generating one ciphertext of the EMFSSE scheme is quicker than that of Wang’s scheme. Secondly, after using edge computing, the client efficiency of Wang’s scheme and the EMFSSE scheme are significantly improved compared to their corresponding schemes without using edge computing. Wang’s scheme saves about 57.6% of the client’s computing cost, and EMFSSE saves about 92% of the computing cost. As far as we know, in the real environment, edge computing will have better computing efficiency than personal computers, so in the real situation, the computing time of the ES side will be less than our experimental results.Figure 6
Time cost to generate one ciphertext.The results show that the EMFSSE scheme has good computational efficiency and security.


## 7.1. Comparisons

Table3 shows the differences in theoretical computation cost and other functions between EMRF and other schemes (Bost [12] scheme, Chen et al. [21] scheme, and Wang et al. [15] scheme). N is the number of indexes containing the keyword w; E1 and E2 represent the multiplication in groups G1 and G2, respectively; e is a bilinear pair; M represents secure map-to-point operation; H means the secure hash function; T/T−1 represents trapdoor function and its inverse operation (public key primitives, such as RSA), respectively; F/F−1 represents a pair of pseudorandom permutations (such as AES or DES).Table 3
Comparison with other schemes.
SchemeUpdateTrapdoorSearchForward privacyMultiuserBost [12]H+N×2h+THN×T−1+2H√×Chen et al. [21]2E1+e+M+F+6H+N×2He+M+E1+H4H+N×2H√×Wang et al. [15]2E1+e+H+N×E2E1+HN×e××EMFSSEe+E2+T+7H+2F+N×HE1+HN×H√√As shown in Table3, compared with other relevant schemes, the proposed scheme has better performance. For all schemes, in the update phase, the computational complexity is linearly related to the number of indexes N. Among them, the Bost scheme of [12] has a major flaw that it does public key operation T for N times. Because of its slow encryption, the scheme is limited in large data sets. The computational complexity of Wang’s scheme is 2E1+e+H+N×E2. Among them, operation e takes a lot of time, but it is independent of index. This scheme calls E2 once for each index, which leads to relatively high consumption. The computational complexity of Chen’s scheme and our scheme is 2E1+e+M+F+6H+N×2H and e+E2+T+7H+2F+N×H, respectively. The operation related to the index number is only the hash function, so it is more efficient than the previous two schemes. However, it is worth noting that Chen’s scheme uses map-to-point operation with high cost. To sum up, among the four schemes, our scheme has the best update efficiency.In the trapdoor generation phase, the complexity of each trapdoor generated by Bost’s scheme, Chen’s scheme, Wang’s scheme, and EMFSSE scheme isH, e+M+E1+H, E1+H, and E1+H, respectively. Obviously, Chen’s scheme has a relatively high complexity of generating a trapdoor, while Bost’s scheme has relatively optimal complexity. Wang’s scheme and our scheme have the same complexity, which is slightly higher than Bost’s scheme, but it is a must to extend functionality and improve security. In most cases, the diminished performance is acceptable.Similar to the update phase, the computational complexity of all schemes in the search phase is also linearly related toN. In order to get each search result, Wang’s scheme requires a time-consuming bilinear mapping, and Bost’s scheme requires RSA decryption T−1, both of them are expensive. Chen’s scheme and EMFSSE scheme only need to perform the corresponding hash function operation, which is less time-consuming. Obviously, the consumption of the EMFSSE scheme is lower.In terms of function, compared with other schemes, the EMFSSE scheme supports forward privacy and multiuser searchable encryption, which can resist file injection attacks and extend the performance of the scheme to multiuser. In conclusion, the EMFSSE scheme has relatively good performance and low computational costs.


## 7.2. Evaluation

We do the experiment on the personal computer with Intel Core i5-3337 CPU and 8 GB DDR3 RAM. We use C++ to realize the core function of EMFSSE.Specifically, we set the security parameters ofλ=128 bits and μ=64 bits, use HMAC to implement the hash function, and choose pseudorandom permutation (CBC model, 128-bit key). And we use the 128-bit security level MIRACL CryptoSDK in [36] to calculate the efficiency of pairings and exponentials operation of bilinear pairing. The time cost of the main operation is shown in Table 4. It takes 105.77 ms to compute bilinear pairs, 34.45 ms to compute exponents in G1, and 8.87 ms to compute exponents in G2. It takes 322.4 ms to perform map-to-point operations, and the hash operation takes 0.001 ms. AES algorithm takes 0.005 ms for both encryption and decryption. The execution time of the RSA encryption/decryption algorithm took 0.189 ms and 5.896 ms, respectively.Table 4
Time consumption of main operations.
OperationeE1E2MHF/F−1TT−1Time cost (ms)105.7734.458.87322.40.0010.0050.1895.896Figures3–5 show the approximate time costs of update algorithm, search algorithm, and token generation algorithm with different index numbers (1.5×104∼5.0×104).Update evaluation: Figure3 shows the time-consuming comparison of updating algorithms of Bost’s scheme, Chen’s scheme, and EMRF scheme. (Wang’s scheme is not shown in the figure due to its high computational complexity.) As shown in the figure, the abscissa is datasets containing 1×104∼5×104 indexes, respectively, with an interval of 0.5×104. When the number of indexes is 1×104, the cost of Bost’s scheme, Chen’s scheme, and EMFSSE scheme is 1.91 s, 0.52 s, and 0.12 s, respectively. Bost’s scheme has a higher time consumption, Chen’s scheme and EPMF have relatively lower time consumption, and EMFSSE has the lowest. The time-consuming of all three schemes increases as the number of indexes increases. Among them, the growth rate of Bost’s scheme is the fastest, while that of Chen and EPMF schemes is low and basically flat. In general, the EMFSSE scheme has a lower time-consuming and growth trend during the update phase.Search evaluation: Figure4 shows the time-consuming comparison of the search algorithms of Chen’s scheme and EMFSSE scheme. (Due to the large time consumption of the other two schemes, no comparison is made.) The abscissa is datasets containing 1×104∼5×104 indexes, respectively, with an interval of 0.5×104. When the number of indexes is 1×104, the cost of Chen’s scheme and EMFSSE scheme is 20 ms and 10 ms, respectively. Similar to the update algorithm, the time consumption of the search algorithm also increases with the number of indexes, and the EMFSSE scheme is better than Chen’s scheme in both time-consuming and growth trends.Token generation evaluation: Figure5 shows the time-consuming comparison of Bost’s scheme, Chen’s scheme, Wang’s scheme, and EMFSSE scheme in a single trapdoor generation algorithm. Chen’s scheme needs to do a map-to-point operation, so it is high time-consuming and inefficient. EMFSSE scheme consumes 140.222 ms to generate one trapdoor, but it is worth noting that EMFSSE transfers part of the operation of generating trapdoor to the edge platform, which saves about 75% of the computational costs of the user client. That is to say, the time consumed to generate trapdoor at the DU side is 34.451 ms, which is the same as Wang’s scheme. Moreover, compared with the EMFSSE scheme, Wang’s scheme can neither support data transmission between multiple users nor meet forward security. In addition, the time EMFSSE scheme consumes is significantly longer than that of Bost’s scheme, which only uses the hash function once to generate a trapdoor. But we think that it is necessary to construct a multiuser searchable scheme.Figure 3
Time consumption of update algorithm.Figure 4
Time consumption of search algorithm.Figure 5
Time consumption of token generation algorithm.In order to show the advantages of the EMFSSE scheme obtained by using edge computing, EMFSSE is compared with Wang’s scheme that also uses edge computing, and the proposed scheme that does not use edge computing. Figure6 shows the comparison of various schemes for generating a ciphertext. Firstly, the overall time of generating one ciphertext of the EMFSSE scheme is quicker than that of Wang’s scheme. Secondly, after using edge computing, the client efficiency of Wang’s scheme and the EMFSSE scheme are significantly improved compared to their corresponding schemes without using edge computing. Wang’s scheme saves about 57.6% of the client’s computing cost, and EMFSSE saves about 92% of the computing cost. As far as we know, in the real environment, edge computing will have better computing efficiency than personal computers, so in the real situation, the computing time of the ES side will be less than our experimental results.Figure 6
Time cost to generate one ciphertext.The results show that the EMFSSE scheme has good computational efficiency and security.


## 8. Conclusion

In this paper, we construct a forward secure searchable encryption scheme supporting multiuser in the P2P network environment. We extend the traditional single-user scheme to multiuser to meet the application requirements of the P2P network environment. And the proxy reencryption technique is used to improve the multiuser scheme. Through reencrypting the searched ciphertext by the proxy party (edge platform), the data user can decrypt the ciphertext with his own private key to avoid direct transmission of the decryption key. In addition, this scheme also uses edge-cloud architecture to replace only-cloud computing and transfers part of the computing to the edge platform, realizing the lightweight computing of this scheme. In terms of security, this scheme satisfies CPA security based on the DBDH assumption in the ciphertext generation process and forward privacy in the index generation process. Theoretical and practical performance analyses show that, compared with the related schemes, this scheme has relatively better efficiency in update operation, search operation, and trapdoor generation operation, and our scheme rarely implements forward security that supports multiuser. In addition, this scheme saves the user’s consumption in different degrees in the encryption process or in the token generation process. In the future, we will carry out researches on how to optimize the performance of multiuser searchable encryption scheme by using an attribute-based encryption method.



---

*Source: 7003252-2021-09-20.xml*