A remote sensing encrypted data search method based on a novel double-chain

Abstract

Remote sensing is considered to be a key technology for the development of smart cities. By analysing the data obtained by remote sensing, it is effective to manage and develop smart cities. However, with the rapid urbanisation and the increase in data capacity, how to store and retrieve remote sensing data which have more potential value and privacy with a more effective and safe method has become an imminent issue. In this paper, we propose an efficient verifiable and dynamic multi-keyword searchable encryption scheme for remote sensing data in smart cities. Moreover, we construct a double-chain index to support a multi-keyword search, where the Verification Index Chain is used to identify the users and the Keyword Index Chain is used to store the information of keywords. In addition, we adopt extended bitmap technology to realise update operations and verify the correctness and integrity of the search results. Experiments show that compared to the related existing schemes, the search time of the proposed scheme is reduced by 35% at most, the verification time is reduced by 14% at most and the update time is reduced by 57% at most.

KEYWORDS:

• Searchable encryption
• remote sensing data
• forward security
• smart cities
• privacy protection

Subject classification code:

• TP309

1. Introduction

In recent years, improving cities, especially metropolises, is an urgent and pressing demand as the urban problems come amid rapidly increasing urbanisation, such as environmental pollution, traffic jams, massive construction, etc (Sun et al., 2021; Zhang et al., 2022). The practice of smart cities will help alleviate the increasing burden caused by urbanisation and improve the quality of all aspects of the residents’ life. In the process of building a smart city, remote sensing technology plays a very important role in spatial information detection.

Remote sensing technology can be used to detect the city’s change information and capture images of the landscape from which a large amount of valuable data can be obtained, such as where the traffic is heavy, where there is a fire point and so on. These remote sensing data can be used for city management, urban planning, resource exploration and so on (S. C. Liu et al., 2022; Ye et al., 2021). But as the amount of data increases, local storage systems can not meet the massive storage requirements and cloud storage is seen as the proper method because of its affordability and convenience. However, how to ensure the security of the remote sensing data stored in the cloud, which may contain some private and valuable information, has become an important issue. Although encryption technology guarantees the confidentiality of data, it also poses some new challenges to the management of private data, such as ciphertext search. The proposed searchable encryption (SE) technology solves this problem well, which can obtain the desired data from huge amounts of encrypted data by querying keywords without retrieving all the encrypted data (Yan et al., 2022).

Due to the confidentiality and privacy of remote sensing data, it has higher requirements for searchable encryption schemes in terms of security, efficiency and functionality (Tang et al., 2021; Yan et al., 2022). In terms of efficiency, it will be essential to build indexes to improve search efficiency which is related to the number of keywords rather than the number of files. In terms of functionality, most of the previous SE schemes (Fu et al., 2019; Y. X. Li et al., 2018; Shao et al., 2022) are about static databases, but in practical applications, users need to update the privacy data in the cloud. At the same time, if the cloud is malicious, it may execute the portion of the search request or output part of the search results. Therefore, the correctness and integrity of the search results, it needs to be verified (Chen et al., 2021; H. Y. Wang et al., 2020b). In terms of security, when the index and database are updated, the previous search trapdoor can continue to query data and leak the updated information, so forward security needs to be considered (Song et al., 2020; Tang et al., 2021).

In some existing schemes (Q. Liu et al., 2017, June; Wu et al., 2019; Yu et al., 2013), the index structure is based on vectors or lists, which causes a drastic decrease in search efficiency as the number of files increases. Schemes (Q. Liu et al., 2017, June; Wu et al., 2019) require the cloud to access all files of the index to acquire the results. However, these schemes require a lot of time to access each file index, which leads to a linear increase in search time as the number of files increases. The indexes of schemes (Fu et al., 2019; Yu et al., 2013) are based on vectors that also traverse all file vectors during the search, resulting in a positive correlation between the search time and the number of files. In recent years, due to frequent incorrect or incomplete search results, some verifiable SE schemes have been proposed (Q. Liu et al., 2019; H. Wang et al., 2020a; Zhu et al., 2018). Schemes (Chen et al., 2021; Q. Liu et al., 2019) are both accumulator-based verification schemes, but the accumulator requires modulo-power operations which cost a large time overhead in verification. Schemes (H. Wang et al., 2020a; Zhu et al., 2018) are based on the Merkle tree, which results in a huge time overhead to maintain and manage the indexes. In addition, searchable encryption schemes (Hoang et al., 2021; Y. X. Li et al., 2018) supporting dynamic updates have been proposed, which can add and delete the uploaded files, but security problems come along, for example, scheme (Y. X. Li et al., 2018) does not consider whether the previous trapdoor is still valid after update operation.

In summary, verifiable SE schemes tend to require large time or space overheads and dynamic SE schemes either do not have guaranteed security or consume large local storage overheads. We introduce an efficient, verifiable and dynamic multi-keyword searchable encryption (EVDMSE), which optimises the search efficiency and achieves forward security. Then, the contributions of our scheme are presented as follows.

1. Storing and protecting the remote sensing data. The paper proposes a scheme for the storage and management of remote sensing data, in which the attackers and unwanted third parties can’t obtain the sensitive data arbitrarily.

2. Dynamic update. The proposed scheme supports the dynamic update of the files and also ensures forward security. When the user submits the updated information, the relative address information of the KIC changes accordingly. This way ensures that the address information contained in the previous search trapdoor is invalidated and the previous trapdoor cannot access the index.

3. Multi-keyword and verifiable search. We adopt extended bitmap technology to realise multi-keyword joint query and HMAC function to compress the bitmap for verifying the correctness and integrity of the search results (Shao et al., 2022). The extended bitmap technology is modified to support multi-keyword query and update operations compared with the traditional bitmap technology (Cong et al., 2019). HMAC function is utilised to compress the keywords and extended bitmap to verify whether the results are correct.

4. Efficient access. It is proved by theoretical analysis and simulation experiments that our scheme has obvious advantages in efficiency, such as saving at most 6 ms in search time, saving 5.9 ms in verification time and saving 0.16 ms in update time compared to the scheme (F. Li et al., 2021).

The organisation of the rest paper is as follows. We introduce the related work in Section 2. In Section 3, we introduce the preliminaries. We show the problem formulation in Section 4. In Section 5, the details of the algorithmic construction are described. Then, we analyse the security of the proposed scheme in Section 6. Next, the performance analysis of the program is detailed in Section 7. Ultimately, we summarise our article in Section 8.

2. Related work

Based on the remote sensing data, we propose a forward secure multi-keyword SE scheme in which the verification of search results and dynamic update of the database are implemented.

Dynamic update means that the user is allowed to add and delete the data after uploading it. To meet the demand for dynamic updates, Chang et al. (Chang & Mitzenmacher, 2005) first proposed a dynamic SE scheme that implements update operations in cloud servers. The drawback of the scheme is that it would leak additional information due to the newly added files associated with the previous query trapdoor. To reduce and even avoid such leakage, Stefanov et al. (Stefanov et al., 2014) proposed the notion of forward security in 2014. The goal of forward security is that the malicious cloud cannot obtain any information from the existing database during the update phase. They also proposed a forward security scheme similar to ORAM (Oblivious Random Access Machine), which explains that a recently added file may be associated with a previous trapdoor and the same trapdoor can leak the information when searching again. In 2016, Bost (Bost, 2016) proposed a forward secure SE scheme with low communication cost and low computational overhead, which hides the relation between file identifiers and keywords by trapdoor substitution. In recent years, with the widespread implementation of forward secure search encryption, the technique has been used in more scenarios. In 2020, Du and Wang (2020, December) applied the blockchain to forward secure search encryption, which not only improves the query efficiency but also achieves verification with the help of blockchain technology. In 2021, Tang et al. (2021) proposed a multi-user forward secure SE scheme in P2P, which solves the problems of ciphertext search and data update in the P2P environment. However, the index of the scheme relied on the number of files rather than the number of keywords, so the search efficiency decreased as the number of files increased.

Verification means how to verify the correctness and integrity of the query results returned by the cloud. Soleimanian et al.(Soleimanian & Khazaei, 2019) introduced a verifiable symmetric encryption scheme with the help of a third-party server. Q. Liu et al. (2019) proposed a verifiable SE scheme using bitmap and RSA accumulator, which has a performance penalty in modular exponentiation during the verification phase. Wang and Cheng (2019) proposed an efficient aggregated-key verifiable SE scheme that greatly saves computational overhead in the search and verification phases. However, it is anchored on public-key encryption, which requires more time costs and does not support dynamic updates. H. Wang et al. (2020a) introduced a verifiable and dynamic SE scheme that uses Merkle trees and a time-stamp chain to verify the results, but it requires a large computational cost to update the Merkle trees.

Based on the problems above, features such as verifiable multi-keyword search, supporting dynamic updates, ensuring update security and relying on the keyword are desirable in a SE scheme.  We list the functions of some mentioned schemes (Du, 2020, December; Tang, 2021; Soleimanian, 2019; Wang and Cheng, 2019; Wang, 2020a) in Table 1, it can be seen that the proposed scheme can satisfy all the required features.

Table 1. Functionality in various schemes.

Scheme	Verifiable	Security	Search type	Static/Dynamic	Index type
Du’s	√	FP/BP	Single Key	Dynamic	Keyword
Tang’s	×	FP	Single Key	Dynamic	File
Soleimanian’s	√	CKA	Single Key	Static	File
Wang&Cheng’s	√	CKA	Single Key	Static	File
Wang’s	√	FP/BP	Multi-Key	Dynamic	File
Ours	√	FP	Multi-Key	Dynamic	Keyword

Notes: FP/BP means forward/backward privacy and CKA means the security of choosing a keyword attack; Index Type means whether the index is built on the number of files or the number of keywords.

3. Preliminaries

3.1. Extended bitmap index

The extended bitmap index is a modification of the bitmap index that uses $n$ bits to represent a file instead of one bit. When there are $m$ files in a dataset, we use $n$ bits to represent a file and a $m\times n$-length string $bs$to denote the dataset. If file $f_i$ exists in the dataset, the strings of extended bitmap from $n\times (i-1)+1$ to $n\times i$ represent $f_i$, where the $n\times (i-1)+1$-th is set to 1. For example, when $m=5$,$n=3$, we present the creation, addition, deletion and joint search for the database in the form of an extended bitmap, as shown in Figure 1. (a) shows the creation of an extended bitmap index, which includes files $f_1$,$f_3$ and $f_5$; Figure 1(b) presents the add operation, which adds the file $f_2$ to the index; Figure 1(c) illustrates the delete operation, which removes the file $f_5$ from the index; Figure 1(d) indicates the joint search when the query keywords include the keywords $w_1$, $w_2$ and $w_3$, each keyword corresponds to an extended bitmap index $bs$. After the joint query, the three $bs$ corresponding to $w_1$, $w_2$ and $w_3$ are retrieved to do add operation, and if there exists the $3\times (i-1)+1$-th bit to $3\times i$-th bit is “011”, it means that the file $f_i$ contains both keywords $w_1$, $w_2$ and $w_3$. In Figure 1(d), the files $f_3$ and $f_5$ satisfy the query, and then they are returned.

Figure 1. (a) Set-up of the extended bitmap, (b) Add, (c) Delete, and (d) Joint search.

3.2. A double-chain index

We construct a double-chain index structure in the proposed scheme. One is called a Verification Index Chain (VIC), which applies a one-way hash function to encrypt the user’s identity and establishes a one-way chain to control the access and modification rights to the index for the user. The other chain is called Keyword Index Chain (KIC) which is used to establish the index between the keywords and the files. In addition, the KIC is attached to the VIC and the position of the KIC is recorded with the counter $C$. VIC utilises a one-way hash function to encrypt the user’s identity to realise that the current address cannot be inferred from the previous address. Each node of the KIC stores the current node address $Add\mathrm{\_}key$, the next node address $rt$ and information about the keyword $Inf(w)$ including keyword, bitmap and verification function, where the last node points to null, as shown in Figure 2.

Figure 2. Identity-keyword chain.

When an update operation is performed, the position of the KIC is moved to the next node of the VIC, that is, the address of the first node of the KIC and the counter is modified. Due to the one-way hash function, the previous trapdoor cannot access the updated KIC.

Based on the user’s identity, the system applies a hash function to create a VIC of length $Clen$ .$Clen$ is determined by the system, as shown in Equation (1). (1) $H^{Clen}(u),\cdots ,H^2(u),H^1(u)$(1) where $u$ means the user’s identity and $H(\cdot )$ means the one-way hash function, as shown in Equation (2). (2) $H^i(u)=\{\begin{array}{l}H(u),i=1,\\ H(H^{i-1}(u)),i\ge 2,\end{array}$(2)

Since $H^i()$ is a one-way hash function, when $H^i()$ is known, the hash value before $H^i()$ cannot be inferred, i.e. $H(u),\cdots ,H^{i-1}(u)$ cannot be inferred (He et al., 2020).

KIC is attached to a node of VIC, initially attached to the VIC’s first node. When updated, the KIC moves backward and the update counter records the position of the KIC. The KIC can be accessed only after the address of the KIC’s first node is obtained, and each node on the KIC contains keywords and related information. When updated, the address of the KIC is modified and the location of the KIC is recorded using $C$. Then, according to the update request, the node of the index is modified.

4. Problem formulation

4.1. System model

 Figure 3 presents the system model of the management of remote sensing data. The cluster head receives data from sensor nodes which can collect information about the surrounding situation, and then it sends the remote sensing data to the satellite through electromagnetic waves. The users gather the data obtained by the satellite, extract the data into the form of a file and then perform searchable encryption to ensure its security and privacy. In the management of remote sensing data, it is assumed that the cloud server is semi-honest and can record and analyse information about file ciphertext and trapdoors. In the encryption phase, users extract the index of the files about remote sensing data, encrypt the files and then upload them to the cloud server together. In this case, neither the cloud server nor the attackers nor unwanted third parties would obtain the sensitive data. When a user wants to retrieve the files, he can submit the query trapdoor generated by the query keywords. And then the cloud server performs the search operation and returns the search results that matched the query to the user.

Figure 3. System model.

4.2. Algorithm definition

Since the proposed scheme is for a two-party model, the data user is the same as the data owner who uploaded the data. In the model, the data owner shares the data with the cloud server to save local storage, and then they can access their own data and also add or delete their uploaded data when there is a need. The proposed scheme consists of five algorithms: $\text{Setup}$,$\text{GenToken}$,$\text{Search}$,$\text{Verify}$and $\text{Update}$, which are defined as follows.

1. $Setup(\lambda )\to (k_1,k_2,k_3,sk)$. The algorithm is executed by the system. The system selects security parameters $\lambda$ as inputz and output keyz $k_1$,$k_2$,$k_3$, private key $sk$.

2. $GenIndex(k_1,k_2,k_3,sk,F,u_l)\to (F^{\mathrm{\prime }},Index)$.The algorithm is executed by the user. The user encrypts the files set $F$ based on the identity $u_l$ to generate the ciphertexts set $F^{\mathrm{\prime }}$ and the $Index$.

3. $GenToken(k_2,sk,W_q)\to T_q$. The algorithm is executed by the user. The user enters $k_2$, $sk$ and the keywords set $W_q$ and outputs the search trapdoor $T_q$.

4. $Search(Index,T_q)\to (RES,F_q^{\mathrm{\prime }},W_q^{\mathrm{\prime }\mathrm{\prime }})$. The algorithm is executed by the cloud server. The cloud server enters $T_q$, outputs the node information $RES$, ciphertext $F_q^{\mathrm{\prime }}$ and the encrypted keywords set match successfully $W_q^{\mathrm{\prime }\mathrm{\prime }}$.

5. $Verify(RES,F_q^{\mathrm{\prime }},W_q^{\mathrm{\prime }\mathrm{\prime }})\to (0/1)$. The algorithm is executed by the user. The user enters $RES$, $F_q^{\mathrm{\prime }}$ and $W_q^{\mathrm{\prime }\mathrm{\prime }}$ and the algorithm would output the result $0/1$, 1 denotes the user accepts the search result, otherwise, rejects it. (reject/accept).

6. $Update(op,f_{up},W_{up},u_l)\to (ke{y}_{u_l},\{Kn{o}_{w_k}{\}}_{w_k\in W_{wp}})$.The algorithm is executed by the user. The user inputs the operation type $op$, the file $f_{up}$, the keywords in the file $W_{up}$ the user’s identity $u_l$ and outputs the address of KIC $ke{y}_{u_l}$ and information about each update node $\{Kn{o}_{w_k}{\}}_{w_k\in W_{up}}$.

4.3. Security model

There is an “honest but curious” cloud server in the proposed scheme that will execute search commands honestly as required, but will also record private data or analyse the search pattern. We demonstrate the security of the scheme through the real game $Rea{l}_A(\lambda )$ and the simulated game $Idea{l}_{A,S}(\lambda )$, where the leakage function is defined as $L=(L^{GenIn},L^{Src},L^{Updt})$. We define a query $q=(t,w)$ and an update operation $u=(t,op,(w,bs))$, where $t$ denotes the operation time, $w$ represents the keyword and $bs$ means the extended bitmap of files. We define the search pattern as $sp(q)=\{t:\{t,w{\}}_{w\in q}\}$ which can distinguish the same query and the resulting pattern as $rp(q)=\{bs{\}}_{w\in q}$ which can leak the search results. The update time leakage function for each keyword is defined as $Time(q)=\{t:\{t,(w,bs){\}}_{w\in q}\}$, where $A$ denotes the adaptive adversary and $S$ is a probabilistic polynomial time simulator. The definitions of the two games are as follows.

1. $Rea{l}_A(\lambda )$: Adversary $A$ selects files and then the system executes the encryption algorithm and returns ciphertext to $A$. The adversary $A$ can send three adaptive queries: the search query, the add query and the delete query. Eventually, $A$ outputs $b_1\in \{0,1\}$ as result.

2. $Idea{l}_{A,S}(\lambda )$: The adversary $A$ selects files, and then the simulator $S$ generates simulated ciphertext based on the leakage function $L^{GenIn}$, and then sends the ciphertext to $A$. The adversary $A$ can also send a polynomial number of adaptive queries. Based on the queries and leakage function $L^{Src}$ and $L^{Updt}$, $S$ generates search commands, adds commands deletes commands and sends them to $A$. Eventually, $A$ outputs $b_2\in \{0,1\}$ as result.

Definition 4.1:

For a polynomial-time adversary $A$, a scheme satisfies adaptive security, if $S$ can make $|Pr[Rea{l}_A(\lambda )=1]-Pr[Idea{l}_{A,S}(\lambda )=1]|\le negl(\lambda )$, where the function $negl(\lambda )$ is negligible.

4.4. Forward security

Forward security is a powerful property defined in dynamic symmetric searchable encryption (Tang et al., 2021). In a word, the cloud cannot query updated information using a previous search trapdoor.

Definition 4.2:

The adaptive secure scheme is said to satisfy forward security if the leakage function in the update phase is $L^{Updt}(op,in)=L^{\mathrm{\prime }}(op,\{(f_i,u_i)\})$, where $op$ denotes the type of operation, $(f_i,u_i)$ denotes the pair of updated file-keyword and $u_i$ denotes the number of keywords corresponding to the file $f_i$.

In the proposed scheme, since the update is based on an extended bitmap index, the add/delete operations are performed as a Modular Addition function so the cloud finds hard to distinguish the operations. The leakage function is defined as $L^{Updt}(op,w,bs)=L^{\mathrm{\prime }}(|w|,bs)$, where $|w|$ is the number of updated keywords.

5. Detailed scheme

1. $\text{Setup}(\lambda )$: The system generates the keys $k_1,k_2,k_3\leftarrow \{0,1{\}}^{\lambda }$ and the symmetric key $sk\leftarrow \text{SKE}\text{.Gen}(1^{\lambda })$, where $\text{SKE}$ is a secure symmetric encryption algorithm, and then sends $(k_1,k_2,k_3,sk)$ to the user. The system generates a pseudo-random function $F:\{0,1{\}}^{\lambda }\times \{0,1{\}}^{\ast }\to \{0,1{\}}^{\lambda }$ and a hash function $H_1=\{h|h:\{0,1{\}}^{\lambda }\to \{0,1{\}}^{\lambda }\}$.

2. $GenIndex(k_1,k_2,k_3,sk,F,u_l)$:The system confirms the identity of all users $U=\{u_1,u_2,\cdots ,u_l,\cdots u_m\}$, and the user retrieves the keyword set $W_F$ from the file set $F$. The user encrypts $F$ to get a set of ciphertexts $F^{\mathrm{\prime }}$ with the symmetric encryption algorithm $Enc()$. The user $u_l$ generates VIC and KIC with the method in Section 3.2. The VIC contains several nodes $H^1(k{u}_l),H^2(k{u}_l),\cdots ,H^C(k{u}_l),\cdots ,H^{Clen}(k{u}_l)$, of which $Clen$ is determined by the scale of files $Ke{y}_{u_l}$ indicating the position of KIC in VIC, $C$ is the counter. The node of KIC, shown in Figure 4, contains three types of information: the first is the current node address $Add\mathrm{\_}key$, the second is the next node address $rt$ and the third is the information about the keyword $w_k$ which includes the encrypted keyword $k{t}_{w_k}$, extended bitmap index $b{s}_{w_k}$, bitmap verification function $h_{b{s}_{w_k}}$ and the file verification function set $H_{w_k}$. In detail, the verification function $h_{b{s}_{w_k}}$ is used to verify the validity of $b{s}_{w_k}$. For each file $f_j^{\mathrm{\prime }}\in F_{w_k}^{\mathrm{\prime }}$, generate the file verification function $h_{j,w_k}$ and store it in the set $H_{w_k}$ for verifying the completeness of the results, in which $F_{w_k}^{\mathrm{\prime }}$ denotes the encrypted file set containing $w_k$. The user $u_l$ generates exclusive KIC $KI{C}_{u_l}$ which includes the keyword node $Kno$. The detailed index generation is shown as Algorithm 1. Eventually, the user $u_l$ sends the index $Index=(VI{C}_{u_l},KI{C}_{u_l})$ and ciphertext set $F^{\mathrm{\prime }}$ to the cloud, in which $VI{C}_{u_l}$ and $KI{C}_{u_l}$ denote exclusive VIC and KIC for the user $u_l$.

   Figure 4. Node of KIC.

   

   Table

   Algorithm 1 $\text{GenIndex}(k_1,k_2,k_3,sk,u_l)$
   1:	for $f_i\in F$ do
   2:	${f_i}^{\mathrm{\prime }}\leftarrow Enc(k_1,f_i)$
   3:	$F^{\mathrm{\prime }}\leftarrow {f_i}^{\mathrm{\prime }}$
   4:	$k{u}_l\leftarrow F(k_2,u_l)$
   5:	for $i=1$ to $CLen$ do
   6:	$VI{C}_{u_l}\leftarrow H^i(k{u}_l)$
   7:	$Ke{y}_{u_l}\leftarrow H^C(k{u}_l)$
   8:	$r{t}_1\leftarrow Ke{y}_{u_l}$
   9:	for $k=1$ to $|W_l|$ do
   10:	$Add\mathrm{\_}Ke{y}_k\leftarrow H_1(r{t}_k\Vert 0)$
   11:	$k{t}_{w_k}\leftarrow Enc(sk,w_k)$
   12:	if $k\ne |W_l|$ then
   13:	$r{t}_{k+1}\leftarrow \{0,1{\}}^{\lambda }$
   14:	else $r{t}_{k+1}=\mathrm{\perp }$
   15:	$nb{s}_{w_k}\leftarrow \{f_j{\}}_{f_j\in F_l}$
   16:	$h_{b{s}_{w_k}}\leftarrow HMAC(k_3,b{s}_{w_k},k{t}_{w_k})$
   17:	for $j=1$ to $|F_{w_k}^{\mathrm{\prime }}|$ do
   18:	$h_{j,w_k}\leftarrow HMAC(k_3,{f_j}^{\mathrm{\prime }},k{t}_{w_k})$
   19:	$H_{w_k}\leftarrow h_{j,w_k}$
   20:	$Kn{o}_{w_k}\leftarrow \{Add\mathrm{\_}Ke{y}_k,k{t}_{w_k},r{t}_{k+1},b{s}_{w_k},h_{b{s}_{w_k}},H_{w_k}\}$
   21:	$KI{C}_{u_l}=\{Kn{o}_{w_k}{\}}_{w_k\in W_l}$
   22:	$Index=(VI{C}_{u_l},KI{C}_{u_l})$
   23:	send $F^{\mathrm{\prime }}$,$Index$ to Server

3. $\text{GenToken}(k_2,sk,W_q)$: The algorithm is executed by the user and the detail is shown in Algorithm 2. The user applies the identity $u_l$ and the counter $C$ to generate $Key$, which locates the address of the VIC to access the KIC. The user encrypts each query keyword to generate a set $W_q^{\mathrm{\prime }}$. Set the threshold $Thr$, which is used to detect which files on $bs$ meet the query requirement in Algorithm 3. Finally, the user sends the query trapdoor $T_q$ to the cloud.

   Table

   Algorithm 2 $\text{GenToken}(k_2,sk,W_q)$
   1:	$k{u}_l\leftarrow F(k_2,u_l)$
   2:	$Key\leftarrow H^C(k{u}_l)$
   3:	for $w_j\in W_q$ do
   4:	$w_j^{\mathrm{\prime }}\leftarrow Enc(sk,w_j)$
   5:	${W_q}^{\mathrm{\prime }}\leftarrow w_j^{\mathrm{\prime }}$
   6:	$Thr\leftarrow (|W_q|{)}_2$
   7:	$T_q\leftarrow \{Key,W_q^{\mathrm{\prime }},Thr\}$
   8:	send $T_q$ to Server

4. $\text{Search}(T_q,Index)$: The algorithm is executed by the cloud and the details are shown in Algorithm 3. First, the cloud finds the corresponding VIC according to the $Key$, and then executes the search process with the nodes in turn in the associated KIC. Second, the cloud accesses each node according to the node address $Add\mathrm{\_}Key$ and determines whether the keyword of the node is a query keyword. If the match is successful, the keywords would be stored in the set $W_q^{\mathrm{\prime }\mathrm{\prime }}$, and the node information $\{b{s}_{w_j},h_{b{s}_{w_j}}\}$ is retrieved; otherwise, no node information is recorded and the next node is accessed according to $rt$. Then, the cloud server does the joint operation on all the retrieved $bs$ (See Section 3.1), if the associated bits in the computed $bs$ are equal to $Thr$, it means that the file that the matched bit represents satisfies the query requirement, and then stores the encrypted file in the set $F_q^{\mathrm{\prime }}$. For each encrypted keyword $w_k^{\mathrm{\prime }}\in W_q^{\mathrm{\prime }\mathrm{\prime }}$ and ciphertext $f_j^{\mathrm{\prime }}\in F_q^{\mathrm{\prime }}$ matched successfully, the function $h_{j,w_k}$ is retrieved from the $H_{w_j}$ and stored in the set $H_{w_k,bs}$. For each $w_k^{\mathrm{\prime }}\in W_q^{\mathrm{\prime }\mathrm{\prime }}$, the cloud server returns $RES=\{b{s}_{w_k},h_{b{s}_{w_k}},H_{w_k,bs}\}$ to the user.

   Table

   Algorithm 3 $\text{Search}(Tw,Index)$
   1:	$Ke{y}_{u_l}\leftarrow VI{C}_{u_l}$ , $Key\leftarrow Tw$,$W_q^{\mathrm{\prime }}\leftarrow Tw$
   2:	if $Ke{y}_{u_l}\ne Key$ then
   3:	Exit()
   4:	for $Kn{o}_{w_k}\in KI{C}_{u_l}$ do
   5:	$Add\mathrm{\_}Key\leftarrow H_1(Key\Vert 0)$
   6:	$k{t}_{w_k}\leftarrow Kn{o}_{w_k}$
   7:	if $k{t}_{w_k}\in W_q^{\mathrm{\prime }}$ then
   8:	$W_q^{\mathrm{\prime }\mathrm{\prime }}\leftarrow w_i^{\mathrm{\prime }}$
   9:	$re{s}_{w_k}\leftarrow \{b{s}_{w_k},h_{b{s}_{w_k}}\}$
   10:	$initializenbs$
   11:	for $b{s}_{w_k}\in RES$ do
   12:	$bs\leftarrow bs+b{s}_{w_k}$
   13:	if $bs[f_j]=Thr$ then
   14:	$F_q^{\mathrm{\prime }}\leftarrow f_j^{\mathrm{\prime }}$
   15:	for $w_k^{\mathrm{\prime }}\in W_q^{\mathrm{\prime }\mathrm{\prime }}$ do
   16:	for $f_j^{\mathrm{\prime }}\in F_q^{\mathrm{\prime }}$ do
   17:	$H_{w_k,bs}^{\mathrm{\prime }}\leftarrow h_{j,w_k}$
   18:	$re{s}_{w_k}\leftarrow H_{w_k,bs}^{\mathrm{\prime }}$
   19:	$re{s}_{w_k}=\{b{s}_{w_k},h_{b{s}_{w_k}},H_{w_k,bs}^{\mathrm{\prime }}\}$
   20:	$RES=\{res{\}}_{Tw}$
   21:	send $RES$,$F_q^{\mathrm{\prime }}$,$W_q^{\mathrm{\prime }\mathrm{\prime }}$ to the server

5. $\text{Verify}(RES,F_q^{\mathrm{\prime }},W_q^{\mathrm{\prime }\mathrm{\prime }})$: When the user receives the search results returned by the cloud, he can execute the verification algorithm, as shown in Algorithm 4. First, for each $w_k^{\mathrm{\prime }}\in W_q^{\mathrm{\prime }\mathrm{\prime }}$ of the returned results, verify whether Equation (2) holds. If the equation holds, it means that the returned $b{s}_{w_k}$ is correct. (3) $h_{b{s}_{w_k}}=HMAC(k_3,b{s}_{w_k},w_k^{\mathrm{\prime }})$(3) Then perform the joint operation on $bs$ about each $w_k^{\mathrm{\prime }}\in W_q^{\mathrm{\prime }\mathrm{\prime }}$ and determine whether the result is the same as $b{s}_{w_k}$from the returned $RES$. Finally, for each $w_k^{\mathrm{\prime }}\in W_q^{\mathrm{\prime }}$ and $f_j^{\mathrm{\prime }}\in F_q^{\mathrm{\prime }}$, verify whether Equation (4) holds. This program is to determine whether the files corresponding to the keyword are complete. (4) $h_{j,w_k}=HMAC(k_3,f_j^{\mathrm{\prime }},w_k^{\mathrm{\prime }})$(4) If the equation holds, the user accepts the results.

   Table

   Algorithm 4 $\text{Verify}(RES,{F_q}^{\mathrm{\prime }},{W_q}^{\mathrm{\prime }\mathrm{\prime }})$
   1:	for $w_k^{\mathrm{\prime }}\in W_q^{\mathrm{\prime }\mathrm{\prime }}$ do
   2:	$b{s}_{w_k},h_{b{s}_{w_k}}\leftarrow re{s}_{w_k}$
   3:	if $h_{nb{s}_{w_k}}\ne HMAC(k_3,b{s}_{w_k},w_k^{\mathrm{\prime }})$ then
   4:	Exit()
   5:	for $b{s}_{w_k}\in RES$ do
   6:	$bs\leftarrow bs+b{s}_{w_k}$
   7:	for $bs[f_i]\in bs$ do
   8:	$f_i^{\mathrm{\prime }}\leftarrow Enc(k_1,f_i)$
   9:	if $f_i^{\mathrm{\prime }}\notin F_q^{\mathrm{\prime }}$ then
   10:	Exit()
   11:	for $w_k^{\mathrm{\prime }}\in W_q^{\mathrm{\prime }\mathrm{\prime }}$ do
   12:	for $f_j^{\mathrm{\prime }}\in F_q^{\mathrm{\prime }}$ do
   13:	$H_{w_k,bs}^{\mathrm{\prime }}\leftarrow re{s}_{w_k}$
   14:	$h_{j,w_k}^{\mathrm{\prime }}\leftarrow H_{w_k,bs}$
   15:	if $h_{j,w_k}\ne HMAC(k_3,f_j^{\mathrm{\prime }},w_k^{\mathrm{\prime }})$ then
   16:	Exit()
   17:	accept $F_q^{\mathrm{\prime }}$

6. $\text{Update}(op,f_{up},u_l)$: $◯1$ Add: When the user wants to add the file $f_{up}$, extracts the keywords set $W_{up}$ from the file, and does the updating operation as Algorithm 5. The user first modifies the VIC according to the identity $u_l$, then modifies the node position of the KIC with the $Ke{y}_{u_l}$, meanwhile alters the counter $C$ and the address of the first node $Add\mathrm{\_}Key$in the KIC. For each $w_k\in W_{up}$, the user adds the $b{s}_{f_{up}}$ about the new file to the original $b{s}_{w_k}$ and also generates $h_{b{s}_{w_k}}^{\mathrm{\prime }}$. And then user generates a file verification function $h_{up,w_k}^{\mathrm{\prime }}$ and adds it to the new authentication set $H_{w_k}^{\mathrm{\prime }}$. At last, the user sends the updated address $Ke{y}_{u_l}$ and $\{Kn{o}_{w_k}{\}}_{w_k\in W_{up}}$ to the cloud. $◯2$ Delete : The operation is the same as add operation. The user first modifies the VIC and KIC. For each $w_k\in W_{up}$, the user performs an addition of the $b{s}_{w_k}$ after complement operation to obtain the updated $b{s}_{w_k}^{\mathrm{\prime }}$ and modifies $h_{b{s}_{w_k}}^{\mathrm{\prime }}$. The user removes $h_{up,w_k}^{\mathrm{\prime }}$ from $H_{w_k}$ and obtains the new authentication set $H_{w_k}^{\mathrm{\prime }}$. Finally, the user sends the updated address $Ke{y}_{u_l}$ and $\{Kn{o}_{w_k}{\}}_{w_k\in W_{up}}$ to the cloud.

   Table

   Algorithm 5 $\text{Update}(op,f_{up},u_l)$
   Client:
   1:	extract $W_{up}$ from $f_{up}$
   2:	for $w_k\in W_{up}$ do
   3:	$w_k^{\mathrm{\prime }}\leftarrow Enc(sk,w_k)$
   4:	$W_{up}^{\mathrm{\prime }}\leftarrow w_k^{\mathrm{\prime }}$
   5:	$C\leftarrow C-1$
   6:	$Ke{y}_{u_l}=H^{C_l}(k{u}_l)$
   7:	$Add\mathrm{\_}Ke{y}^{\mathrm{\prime }}\leftarrow H_1(H^{C_l}(k{u}_l)\Vert 0)$
   8:	$b{s}_{f_{up}}\leftarrow bs[f_{up}]$
   9:	if $op=Add$ then
   10:	for $w_k^{\mathrm{\prime }}\in W_{up}^{\mathrm{\prime }}$ do
   11:	$h_{b{s}_{w_k}}^{\mathrm{\prime }}=HMAC(k_3,b{s}_{w_k},w_k^{\mathrm{\prime }})$
   12:	$h_{up,w_k}^{\mathrm{\prime }}=HMAC(k_3,f_{up}^{\mathrm{\prime }},w_k^{\mathrm{\prime }})$
   13:	$H_{w_k}^{\mathrm{\prime }}\leftarrow H_{w_k}+\{h_{up,w_k}^{\mathrm{\prime }}\}$
   14:	$Kn{o}_{w_k}^{\mathrm{\prime }}\leftarrow \{w_k^{\mathrm{\prime }},b{s}_{f_{up}},h_{b{s}_{w_k}}^{\mathrm{\prime }},H_{w_k}^{\mathrm{\prime }}\}$
   15:	else if $op=Del$ then
   16:	for $w_k\in W_{up}$ do
   17:	$b{s}_{f_{up}}\leftarrow [b{s}_{f_{up}}{]}_{complement}$
   18:	$h_{b{s}_{w_k}}^{\mathrm{\prime }}=HMAC(k_3,b{s}_{w_k},w_k^{\mathrm{\prime }})$
   19:	$h_{up,w_k}^{\mathrm{\prime }}=HMAC(k_3,f_{up}^{\mathrm{\prime }},w_k^{\mathrm{\prime }})$
   20:	$H_{w_k}^{\mathrm{\prime }}\leftarrow H_{w_k}\mathrm{\setminus }\{h_{up,w_k}^{\mathrm{\prime }}\}$
   21:	$Kn{o}_{w_k}^{\mathrm{\prime }}\leftarrow \{w_k^{\mathrm{\prime }},b{s}_{f_{up}},h_{b{s}_{w_k}}^{\mathrm{\prime }},H_{w_k}^{\mathrm{\prime }}\}$
   22:	send $Ke{y}_{u_l}$,$Add\mathrm{\_}Ke{y}^{\mathrm{\prime }}$,$\{Kn{o}_{w_k}^{\mathrm{\prime }}{\}}_{w_k\in W_{up}}$ to the server
   Server:
   23:	Search $Ke{y}_{u_l}$
   24:	$Add\mathrm{\_}Ke{y}_k\leftarrow Add\mathrm{\_}Ke{y}^{\mathrm{\prime }}$
   25:	for $w_k^{\mathrm{\prime }}\in W_{up}^{\mathrm{\prime }}$ do
   26:	if $w_k^{\mathrm{\prime }}$ = $k{t}_{w_k}$ then
   27:	$b{s}_{w_k}\leftarrow b{s}_{w_k}+b{s}_{f_{up}}$
   28:	$h_{b{s}_{w_k}}\leftarrow h_{b{s}_{w_k}}^{\mathrm{\prime }}$
   29:	$H_{w_k}\leftarrow H_{w_k}^{\mathrm{\prime }}$

6. Security analysis

6.1. Adaptive security

The proposed scheme satisfies adaptive security under the random oracle model.

Theorem 6.1:

Given a CPA-secure symmetric encryption algorithm, a pseudo-random function $F$, a hash function $H_1$ and a one-way hash function $H$, if the leakage function $L=(L^{GenIn},L^{Src},L^{Updt})$ satisfies the following definitions: $L^{GenIn}(\lambda )=\mathrm{\perp }$, $L^{Src}(q)=L^{\mathrm{\prime }}(sp(q),rp(q),Time(q))$, $L^{Updt}(op,w,bs)=L^{\mathrm{\prime }\mathrm{\prime }}(|w|,bs)$, EVDMSE presented in section 5 is the adaptive security.

Proof:

A simulator $S$ is used to simulate the real algorithm, and no polynomial-time adversary can distinguish between the real and simulated algorithms. $S$ simulates the algorithm according to the leakage functions $L=(L^{GenIn},L^{Src},L^{Updt})$.

Game $G_0$: $G_0$ represents the real EVDMSE security game $Rea{l}_A(\lambda )$, so that $Pr[Rea{l}_A(\lambda )=1]=Pr[G_0=1]$Game $G_1$: $G_1$ simulates Algorithm 1 $GenIndex$ according to the leakage function $L^{Setup}$. When generating the key $k_2^{\mathrm{\prime }}$, $G_1$ picks a random string instead of calling $F$ (see line 5 of Algorithm 1). For each user’s identity $u$, $G_1$ encrypts the identity with $k_2^{\mathrm{\prime }}$ and records the result $ku$ with a table $\text{KEY}$. When the update is performed, the adversary $A$ can use the content in $\text{KEY}$. If the encrypted identity exists, it directly calls it; if not, $S$ generates encrypted identity and places it in $\text{KEY}$. $G_1$ and $G_0$ are indistinguishable by the indistinguishability between $F$ and random function. Therefore, there is an adversary $A$ meeting: $Pr[G_0=1]-Pr[G_1=1]\le Ad{v}_{F,A}^{prf}(\lambda )$Game $G_2$: $G_2$ simulates the Algorithm 5 $Update$ according to the leakage function $L^{Updt}$. Since the leakage functions of both add and delete operations are $L^{Updt}(op,w,bs)=L^{\mathrm{\prime }\mathrm{\prime }}(|w|,bs)$, which only leaks the number of keywords, so we discussed them together. $G_2$ is exactly as $G_1$ except that we apply random strings instead of the hash values $H_1(r{t}_k||0)$ and $H^{C_l}(k{u}_l)$ in the update phase, and record the value with the dictionaries ${\text{H}}_1$ and ${\text{H}}_2$ which are used to record the results of $H^i(ku)$ and $H_1(rt||0)$, respectively in random queries, and the table $\text{UT}$ is used to store the update requests and results. For each update operation, $G_2$ first generates $nbs$ for the update file and random key $k_3^{\mathrm{\prime }}$, then invokes the HMAC function to generate the authentication functions for $bs$ and keywords and finally deposits the value into the table $\text{UT}$. Under the random oracle model, if there is an adversary $A$ that can distinguish between $G_1$ and $G_2$, it can also distinguish between hash functions and random functions, which means $A$ can make: $Pr[G_1=1]-Pr[G_2=1]\le Ad{v}_{H,A}^{prf}(\lambda )$Game $G_3$: $G_3$ simulates the query trapdoor based on the leakage function $L^{Src}$. In addition, two tables $\text{S}$ and $\text{R}$ are used to record query trapdoors and search results, and the table ${\text{H}}_3$ records the hash value $Key$ during the trapdoor generation. During the search process, the simulator determines the duplication of the same keyword queries based on the leak function $sp(q)=\{t:\{t,w{\}}_{w\in q}{\}}_{q\in Q}$, but it works only before the update operation, because after the occurrence of the update, the previous trapdoors is invalid. The result pattern leak function is $rp(q)=\{bs{\}}_{w\in q}$, which only leaks the file identifier in the binary form $bs$ and then $\text{R}$ is used to record the file identifiers matching the query keywords. During the trapdoor generation, if the query keyword is issued for the first time, $G_3$ uses a random number instead of the encrypted identity $ku$ and then performs hash operations based on the counter $C$ instead of directly obtaining $H^C(k{u}_l)$, finally stores the hash results in ${\text{H}}_3$. Meanwhile, $G_3$ generates the position of KIC $Key$ with random numbers and random keys $k_4^{\mathrm{\prime }}$, encrypts the query keywords with symmetric encryption algorithms, stores the query trapdoors in $\text{S}$ and the search results in $\text{R}$. When performing the search, $A$ first checks table $\text{S}$. If there is a corresponding trapdoor, directly employ the trapdoor in $\text{S}$and get the search result from $\text{R}$; if not, generate a new query trapdoor and place it in the table $\text{S}$. The main difference between $G_3$ and $G_2$ is that the query trapdoor is generated randomly which is indistinguishable by the adversary $A$, so that we can make: $Pr[G_2=1]=Pr[G_3=1].$Simulator $S$: The difference between $G_3$ and $Idea{l}_{A,S}$ is that the simulator $S$ in $Idea{l}_{A,S}$ uses the leak function $sp(q)=\{t:\{t,w{\}}_{w\in q}{\}}_{q\in Q}$ to generate a query trapdoor without using the encrypted identity $ku$. For the adversary $A$, the simulator generates a search trapdoor of the same size which is perfectly indistinguishable from $G_3$, and thus $Pr[G_3=1]=Pr[Idea{l}_{A,S}(\lambda )=1]$Conclusion: Based on the above games and the simulator $S$, $F$ is a pseudo-random function and both $H$ and $H_1$ are hash functions, the following equation can be obtained: $Pr[Rea{l}_A(\lambda )]-Pr[Idea{l}_{A,S}(\lambda )]\le Ad{v}_{F,A}^{prf}(\lambda )+Ad{v}_{H,A}^{prf}(\lambda )$In summary, Theorem 1 stands.

6.2. Forward security

Corollary 6.1:

When $F$ is a pseudo-random function and $H$ and $H_1$ are hash functions, the $L-$adaptive scheme satisfies forward security when the leakage function satisfies $L^{Updt}(op,w,bs)=L^{\mathrm{\prime }}(|w|,bs)$.

Proof:

In the search protocol, the cloud can learn the encrypted keywords from the search trapdoor. But the keywords are encrypted by a secure symmetric encryption algorithm, so the cloud server can learn nothing except the number of encrypted keywords. In addition, the cloud can obtain the encrypted identity of the user during the search process, and since the identity is processed through a hash function, no information other than the encrypted identity is disclosed. In the update protocol, the cloud can obtain the number of updated keywords and the extended bitmap of the updated file. However, the first node address of KIC points to the next node of VIC and the first node address is processed by the one-way hash function, so that the current address cannot be inferred from the previous node address. Due to the change of address, the previous trapdoor is invalid after updating, which effectively avoids the association between the generated search trapdoor and the new file. In summary, the proposed scheme satisfies forward security.

7. Performance

7.1. Theoretical analysis

The proposed scheme will be compared with Chen’s scheme (Chen et al., 2021), Liu’s scheme (Q. Liu et al., 2019), Li’s scheme (F. Li et al., 2021) and Bost’s scheme (Bost, 2016) in terms of functional aspects such as keyword types, verifiability and time overheads such as search cost and update cost, as well as storage overheads such as client storage and index size, as shown in Table 2.

Table 2. Comparison of functionality and overhead.

	Function		Cost		Storage cost
Scheme	Multi-keyword verification		Search	Update	User	Index
Bost	×	×	$m\times (2H+T^{-1})$	$F+2H+m\times T$	$O(m\cdot n^{\mathrm{\prime }})$	$O(m)$
Chen	×	√	$H\times (m+m^{\mathrm{\prime }})$	$m^{\mathrm{\prime }}\times (F+H+2G)$	$O(m\cdot n^{\mathrm{\prime }})$	$O(m\cdot n^{\mathrm{\prime }})$
Liu	×	√	$m\times H$	$m^{\mathrm{\prime }}\times (5H+5G)$	$O(m\cdot n^{\mathrm{\prime }})$	$O(m\cdot n^{\mathrm{\prime }})$
Li	√	√	$m_q\times (H+e)$	$3F+H+E+m^{\mathrm{\prime }}\times (3F+H+e)$	$O(m\cdot n^{\mathrm{\prime }})$	$O(m+n)$
Ours	√	√	$m\times H$	$2H+m^{\mathrm{\prime }}\times (E+2M)$	$O(m)$	$O(m\cdot n^{\mathrm{\prime }})$

$m$ and $n$ denote the number of all keywords and all files, respectively; $m^{\mathrm{\prime }}$ indicates the average number of keywords contained in a file, where $m^{\mathrm{\prime }}\ll m$; $m_q$ represents the number of query keywords; $n^{\mathrm{\prime }}$ represents the average number of files corresponding to a keyword, where $n^{\mathrm{\prime }}\ll n$; $F$ means the pseudo-random function operation; $H$ means the hash function operation; $M$ denotes the HMAC function operation; $T/T^{-1}$ indicates the trapdoor function operation and its inverse operation; $e$ means the modulo exponentiation operation; $G$ means the obtaining address operation; $E$ is the symmetric encryption.

Functionality: (1) Search type. Bost’s scheme, Chen’s scheme and Liu’s scheme only support the single-keyword search, while Li’s scheme and the proposed scheme support the multi-keyword search. (2) Verifiability. Bost’s scheme does not support the verification, while other schemes support the verification of search results. Unlike the above three verifiable schemes, the proposed scheme does not use an RSA accumulator but employs the HMAC function which reduces some verification costs.

Time overhead: (1) Search overhead. From Table 2, it can be seen the search overhead of the proposed scheme is much smaller than that of Bost’s scheme and Chen’s scheme, and the same as that of Liu’s scheme. However, the time of Liu’s scheme only spends on searching a single keyword, while our scheme takes the same amount of time to finish a multi-keyword search. The search cost of Li’s scheme is associated with the number of query keywords, which is far smaller than the number of all keywords, but it has to traverse the keyword index for every query keyword, which requires hash function operations and modulo exponentiation operations that is very time-consuming. The required search time increases linearly with the number of query keywords. During the search process, the proposed scheme traverses the keyword nodes in KIC and retrieves information on the nodes that satisfy the query keywords, which does not require additional modulo exponentiation operations compared to Li’s scheme. (2) Update overhead. Bost’s scheme requires trapdoor function operation for all keywords in an index, while the other schemes are all concerned with the average number of keywords contained in a file, so the updating overhead is much more efficient than Bost’s scheme. Chen’s scheme is similar to Liu’s scheme, which performs a hash operation for each update keyword and then generates the corresponding update information for each update keyword, but Liu’s scheme, which requires more hash operations and addresses fetching operations, requires relatively more time overhead. Li’s scheme requires pseudo-random function operation, hash function operation and modulo exponentiation operation for each update keyword. The proposed scheme performs symmetric encryption and HMAC operations for each update keyword while hashing the user’s identity and calculating the address of the KIC.

Storage overhead: (1) User storage. Except for the proposed scheme, other schemes need to store $n^{\mathrm{\prime }}$ files contained in each keyword, so for all keywords, the storage overhead can reach $O(m\cdot n^{\mathrm{\prime }})$. In our scheme, the user only stores the keyword information for verification and the rest of the verification information is from the cloud. In the update phase, the user needs to store numeric strings $bs$ of each keyword, which saves the storage overhead from $O(m\cdot n^{\mathrm{\prime }})$ to $O(m)$ compared with other schemes. (2) Index size. In Bost’s scheme, the index was built according to all the keywords and the file information, which was processed by the hash function, was stored together with keywords. In Li’s scheme, the index stores information on all keywords and the verification information of all documents. The proposed scheme is similar to Liu’s scheme and Chen’s scheme in that the index needs to store each keyword and the corresponding file information, so that index size is determined by the number of keywords.

In summary, through the above analysis, our scheme has certain merits in terms of functionality, time overhead and storage overhead compared with the above four schemes.

7.2. Experimental analysis

7.2.1. Experimental environment

NSF Basic Research Awards which contains 129,000 files from 1990 to 2003 is used as the test dataset in this experiment. 5000 files are selected as test data and the 10 keywords with the highest frequency in each file that has been excluded. The experiments are based on AMD Ryzen 5 4600H CPU and 16G DDR4 RAM. The programs are implemented in Python 3.7 and compiled using PyCharm 2020.2.3.

7.2.2. Experimental results

Through the theoretical analysis in Table 1, it is clear that our scheme has certain advantages in terms of time overhead. For more accuracy in estimating the performance, we analyse the efficiency from the search time, update time and verification time through simulation experiments in this section.

 Figure 5(a) indicates the trend of search time with an increasing number of files for the single-keyword search. Our scheme is compared with Bost’s scheme and Chen’s scheme. The search time of Bost’s scheme increases linearly with the number of files in the database, and also has the fastest growth rate. The search time of Chen’s scheme also grows linearly with the number of files, but the rate is lower than that of Bost’s scheme. The search time of the proposed scheme is less affected by the number of files but related to the number of keywords, so the search time increases smoothly. As the number of documents grows, the search time grows slower. We can see that the rate from 2000 to 5000 is lower than the rate from 1000 to 2000.

Figure 5. Search time, (a) search time for single keyword, (b) search time with file set size = 1000, and (c) search time with file set size = 5000.

Figure 5(b,c) show the trend of the search time with the increase in the number of query keywords. Li’s scheme searches the index once and performs a modulo exponentiation operation for each query keyword, so the search time increases rapidly with increasing query keywords. The proposed scheme only traverses the index once during the whole search process, and when the query keyword is matched, the cloud accesses the verification information, so the search time grows slowly with increasing query keywords. With the number of query keywords increasing, the gap between the proposed scheme and Li’s scheme is widening, in which the gap can reach 6 ms when the number of query keywords is 5. When searching a single keyword, the search time of the proposed scheme increases from 9.4 to 16 ms when moving from 1000 to 5000 database files. When searching with 5 query keywords, the search time will increase from 10.2 to 17.3 ms. The growth of the search time for the proposed scheme stays within 7–8 ms as the number of files increases.

 Figure 6 shows the verification time. Figure 6(a) indicates the trend of the verification time for the single-keyword search with the increasing number of files. With the same number of documents, both Liu’s scheme and Chen’s scheme take more time to verify than the proposed scheme. When the number of files increases, the verification time of Liu’s scheme and Chen’s scheme grows rapidly, while our scheme grows at a slow rate because only the HMAC operations are required for the verification process.

Figure 6. Verification time, (a) verification time for single keyword, (b) verification time with file set size = 1000, and (c) verification time with file set size = 5000.

Figure 6(b,c) present the changing trend of the verification time with the different query keywords. The gap between the proposed scheme and Li’s scheme is widening with the increase of query keywords. When the number of database files is 1000, the gap goes from 1.2 to 5.9 ms. When the number of database files is 5000, the gap goes from 0.5 ms to 3.6 ms. When the number of keywords is 1 and the number of database files is 1000, Li’s scheme and the proposed scheme take 27 and 25.8 ms, respectively; when the number of database files is 5000, it takes 33 and 32.5 ms, respectively. When searching with 5 keywords in 1000 database files, the verification time needs 43 and 37.1 ms. When the number of database files grows up to 5000, the verification time needs 46.2 and 42.6 ms. We can see that the growth of the verification time in the proposed scheme stays within 6–7 ms when the number of files increases. With the number of query keywords increasing, the gaps between the proposed scheme and Li’s scheme are widening.

 Figure 7 indicates the trend of update time as the number of extracted keywords increases. Liu’s scheme takes more verification time than other schemes because it requires inserting the updated information into the verification matrix, it also needs to expand and move the array. Li’s scheme establishes an index for each updated keyword and uses the modulo exponentiation operation to create verification functions for the keywords, so it takes about the same time as the proposed scheme when the number of keywords is less, but the verification time grows rapidly as the number of keywords increases. In Chen’s scheme, buffers are used to store the updated information, thus it takes less time than that of Liu’s scheme. The proposed scheme modifies the extended bitmap index for each updated keyword node and generates a verification function when updating, which saves much time overhead.

Figure 7. Update search.

8. Conclusion

In this paper, we construct a verifiable forward security multi-keyword searchable encryption scheme which is based on remote sensing data in smart cities. The index of the proposed scheme not only achieves authentication but also improves search efficiency. To allow a multi-keyword search, we introduce an extended bitmap index that also supports updating. In addition, we prove the proposed scheme meets adaptive forward secure under the random oracle model. Last, through the theoretical and experimental analysis, the proposed scheme has certain advantages in efficiency compared to similar schemes. The scheme is suitable for ensuring the safety of remote sensing data and retrieving data from the cloud server effectively. However, our paper also has some limitations, such as when the keyword of the added file is not in the index, the added operation will fail because of inserting a new node into the index.

In future, we will continue the research on multi-keyword searchable encryption. We plan to store the index in a trusted service (e.g. blockchain), store the ciphertext in the cloud server, and make the trusted service manage the index. When the added keyword is not in the index, the trusted service can generate the node of the KIC, which ensures that the information is not leaked to the cloud server.

Acknowledgements

We would like to express our gratitude to the foundation for their generous support, and also thank the editors and reviewers for their efforts.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the Henan Key Laboratory of Network Cryptography Technology [grant number LNCT2022-A11].