# Blockchain-Enabled Public Key Encryption with Multi-Keyword Search in Cloud Computing

Authors: Zhenwei Chen; Axin Wu; Yifei Li; Qixuan Xing; Shengling Geng
Journal: Security and Communication Networks
 (2021)

---

## Abstract

The emergence of the cloud storage has brought great convenience to people’s life. Many individuals and enterprises have delivered a large amount of data to the third-party server for storage. Thus, the privacy protection of data retrieved by the user needs to be guaranteed. Searchable encryption technology for the cloud environment is adopted to ensure that the user information is secure with retrieving data. However, most schemes only support single-keyword search and do not support file updates, which limit the flexibility of the scheme. To eliminate these problems, we propose a blockchain-enabled public key encryption scheme with multi-keyword search (BPKEMS), and our scheme supports file updates. In addition, smart contract is used to ensure the fairness of transactions between data owner and user without introducing a third party. At the data storage stage, our scheme realizes the verifiability by numbering the files, which ensures that the ciphertext received by the user is complete. In terms of security and performance, our scheme is secure against inside keyword guessing attacks (KGAs) and has better computation overhead than other related schemes.


---

## Body

## 1. Introduction

Cloud storage is a removable storage method that brings great convenience to people. Therefore, the problem of data security is increasingly important. Generally speaking, cloud storage has three structures. First, public cloud storage service provides a wealth of resources, such as network services and storage, and users can access these resources through the Internet at low prices. Second, internal cloud storage is located inside the corporate firewall, and users have independent storage control rights. Third, hybrid cloud storage provides both public cloud services and internal cloud services. The core is to meet the visits required by customers. While eliminating the user’s local storage hardware and management overhead, the data are out of the user’s physical control, so data security is greatly threatened. When users upload data to cloud storage media, they need to solve the security problem of the data, and people often upload it after encryption. Secure search usually refers to the effective search of encrypted data; to solve the problem of how to use the server to complete the secure keyword search when the encrypted data are stored in the cloud under the premise of incomplete trust, scholars proposed the searchable encryption (SE) as the core technology of secure search.SE is a new technology that supports users to search for keywords in ciphertexts. It mainly solves how to use untrusted servers to implement secure keyword search in a cloud storage environment so that users can securely search data in ciphertext state, specifically, search the keywords according to the keywords of interest. SE systems are divided into symmetric [1] and asymmetric [2–4] forms. Although the calculation amount of public key SE is greater than that of symmetric SE, data owners and users do not need to pass the key negotiation before searching, which is more secure and has greater practical value.In terms of the usability of SE scheme, multi-keyword search [4, 5] is more in line with the user’s search experience. Compared with single-keyword search, it can locate the search more accurately. In the actual scenario, the server may be honest but curious and will want to obtain some sensitive information. Therefore, it is very important to verify the correctness of the results [6]. However, this scheme is static and cannot operate data dynamically. Although some SE schemes [7, 8] support dynamic update of files and verifiability of ciphertext, they will bring a lot of computational overhead. Therefore, the practical SE scheme needs to be designed and proposed.In this paper, we propose the BPKEMS scheme in the blockchain scenario; the main contributions are as follows.(1)
Multi-Keyword Search. The BPKEMS scheme has some good features, such as multi-keyword search and file updates. In addition, the data owner and data user can generate a shared key when encrypting files. By using the Diffie–Hellman (DH) key exchange protocol, they can get the shared key without any interaction.(2)
Fairness. In this scheme, the blockchain mechanism is used to ensure the fairness of the transaction between data owner and user without a third party.3Verifiability. On the blockchain platform, we use smart contract to store index and trapdoor information and perform search services to ensure the accuracy of search results. In addition, we number the files, and the user can verify the ciphertext of the file after receiving the result, which can avoid some malicious behavior of the cloud server.


## 2. Related Work

In recent years, cloud computing technology has been rapidly developed, and a series of studies have been done on security issues. In order to enhance the security of data on the server, Dawn et al. [1] first proposed a symmetric SE scheme, but it was in one-to-one mode, which has triggered people’s research on SE because the one-to-one mode cannot meet people’s needs. For the many-to-one model, Boneh et al. [2] first proposed the public key SE scheme and gave the concept of SE security based on public key encryption in 2004. But in certain environments, the many-to-one mode is not practical. In 2011, Curtmola et al. [9] constructed a one-to-many SE model based on Naor broadcast encryption technology [10], but the user’s key replacement in this model requires a great deal of overhead. In a large-scale network environment, data transmission is complicated. Wang et al. [11] constructed a many-to-many mode encryption scheme based on Shamir’s secret sharing technology [12] and the identity-based encryption technology in [2] to realize the interaction retrieval of multiple users in the server. In order to effectively solve the problem of interactive retrieval when there are multiple recipients, Yuan et al. [13] proposed a one-to-many public key ciphertext time release searchable encryption cryptographic model. In the one-to-many model, only authenticated users can enjoy the search service, and the queried keywords are specified, and they can decrypt it when it knows that it will be released in the future. Zhong et al. [14] proposed a many-to-one homomorphic encryption scheme, which overcomes the limitations of traditional one-to-one mode.In terms of the security of SE, about the scheme [2] proposed by Boneh, only the semantic security of index ciphertext can be achieved, but it cannot resist KGAs. In 2009, Tang and Chen [15] put forward a public key SE scheme. The keywords should be registered before using, which can resist KGAs, but the keywords must be registered in advance, which makes the performance of the scheme not high. In 2013, Fang et al. [16] presented the scheme belonging to public key cryptography, which can resist KGAs; the scheme defines a public key SE model and two important security concepts: one is for inside attacks and the other is for external attacks. However, a large number of bilinear pairing calculations result in a low efficiency of Fang’s scheme [16].In recent years, scholars have conducted a lot of research on inside attacks. In 2013, Xu et al. [17] proposed a scheme with two trapdoors (fuzzy trapdoor and precision trapdoor) and claimed that the scheme can resist inside KGAs. In this scheme, the adversary intelligently obtains the fuzzy trapdoor, but some keyword information about the trapdoor is not known, and it is restricted in terms of security and efficiency. In 2015, Chen et al. [18] introduced a new framework to prevent inside KGAs. They used two servers to realize the scheme, but the limitation is that the two servers cannot be associated. However, anyone can generate legal trapdoors for keywords, which will make data privacy issues easy to discover. Shao et al. proposed a method [19] that can resist KGAs. In the SE scheme of a designated tester, the security of the scheme is redefined as IND-KGA-SERVER. In the presence of a digital signature, it can resist the server’s KGAs. In 2016, Chen et al. [20] proposed a scheme using two servers to resist inside KGAs, and the scheme has high efficiency. However, due to the two assumptions that two cloud servers cannot be connected, this is difficult to achieve in practice. In 2017, Huang and Li [21] proposed a public key authentication encryption scheme based on keyword search. The ciphertext generation process of this scheme requires the key of the data owner. Although the scheme can resist the inside KGAs, it cannot achieve the chosen keyword ciphertext indistinguishability. Kang and Liu [22] proposed a completely secure public key encryption scheme composed of bilinear pairing and TF/IDF algorithm. This scheme achieves security under static assumptions. By comparing with previous SE schemes, their scheme’s performance is superior to other schemes. In terms of security, this scheme can avoid revealing privacy due to the curiosity of the adversary. In 2018, Wu et al. [23] proposed an efficient and secure public key SE scheme with privacy protection. This scheme uses a DH shared key and is proven to resist KGAs.In the Internet of Things (IoT) environment, Wu et al. [24] proposed a certificateless searchable public key authentication encryption scheme, which can resist KGAs at the same time and also has a higher efficiency. Ma et al. [25] designed a new multi-keyword certificateless public key encryption scheme for IoT deployment. Lu and Li [26] proposed a new PEKS scheme, which not only can resist the existing three types of KGAs but also improves the shortcomings of the designated server. With the development of blockchain [27, 28], the combination of searchable encryption technology and blockchain technology solves the problem of trusted third party in traditional schemes and greatly improves the practicability of searchable encryption. Li et al. [30] proposed a searchable encryption system model of blockchain and designed a practical scheme for the system model. In 2019, Li et al. put forward a scheme [31] based on [30], which also improved enablement. In order to be suitable for the electronic medical scene, Chen et al. [32] proposed a SE scheme suitable for this scene under the blockchain technology. This scheme also adopts symmetric encryption method and uses smart contract as the authoritative entity to ensure the credibility of the server in the scheme. Zheng et al. [6] proposed an SE scheme which can verify the correctness of the results, but it cannot support data update operation. The SE scheme proposed by Sun et al. [7] and Xia et al. [8] can not only support dynamic update but also verify the results, and it also has low computational efficiency. Therefore, we are committed to solving these problems.


## 3. Preliminaries

In this section, we review the relevant background materials required in understanding our scheme and introduce some notations in Table1.Table 1
Main symbols.
SymbolMeaningpko,skoPublic/secret key pair of data ownerpku,skuPublic/secret key pair of data userpks,sksPublic/secret key pair of cloud serverKShared key for data owner and data userNiEncrypted file indexNsEncrypted file index setF=fii∈1,tFile index setF′Returned file setC=Cii∈1,tCiphertext set ofFC′=Ci′i∈1,tPacked ciphertextW=wii∈1,mKeyword dictionaryI=I0,I1,I2,Ijj∈1,mIndex set forFσ2′The intermediate valueσ2The final valueW′=wi′i∈1,lQueried keyword setTW′=TW,1′,TW,2′Trapdoor forW′L=ρ1ττ∈1,lLocation set ofW′ in W


### 3.1. Bilinear Pairing

LetG1, G2 be two multiplicative cycle groups. A map e:G1×G1⟶G2 is called a symmetric bilinear pairing if it has the following properties:(1)
Bilinear. eua,vb=eu,vab, ∀u,v∈G1, and ∀a,b∈Zp.(2)
Nondegenerate. eg,g≠1. Let 1∈G2 be the identity element of G2 group.(3)
Computable. ∀u,v∈G1, eu,v; there is a polynomial time algorithm that can easily calculate e.


### 3.2. Decisional Diffie–Hellman (DDH) Problem

Given a generatorg of G1, then g,ga,gb,gc∈G1, where a,b,c∈Zp. The DDH problem is to determine whether gc is equal to gab. Assuming that the DDH problem is difficult, it means that no adversary can solve the problem with a probability that cannot be ignored.


### 3.3. Blockchain

In this section, let us briefly describe the smart contract, gas system, system model, threat model, and security model.


#### 3.3.1. Smart Contract

Blockchain is important and has a wide range of applications, such as the Internet of Things and edge computing, and blockchain can be used in 5G handover authentication [33]. The smart contract (SC) is considered as the core technology of the second-generation blockchain, which was proposed by Szabo [34]. The carrier of the SC is the blockchain, and its essence is an automatically executed computer code. The code describes the terms of the agreement between the buyer and the seller and is directly written into the code of the blockchain. Satisfying the predetermined terms is the trigger condition for the code to be executed. Since the execution of the code does not require human intervention, it is called automatic execution.As a computer program, a SC is a part of application software and a digitally represented program [35]. Although it is a code representation of contract terms, it is not a contract in the legal sense. In addition, the construction of SC comes from the blockchain framework, which is a public billing system, which can carry out secure value transfer without a trusted third party, and the correctness of the contract code execution is guaranteed by the consensus mechanism. Therefore, SC can be understood as a computer protocol, which can be executed automatically without human intervention.


#### 3.3.2. Gas System

In Ethereum, once the SC is set, it is forbidden to modify it. In order to prevent malicious users from setting up an infinite loop running contract, Ethereum requires users to pay for each step of the deployment contract. The basic unit of cost is gas. Gas is equivalent to the fuel needed to deploy and execute SC. Without fuel, SC cannot be used. This mechanism maintains the operation of the economic system of Ethereum.In a gas system, there are some important parameters. Gas price means that users need to pay for each unit of gas. Each block has a gas limit, that is, the maximum amount of gas allowed in a single block, which can be used to determine how many transactions can be packaged in a single block. Both gas price and gas limit are set by the transaction sender itself. If the total amount of gas consumed by the operation exceeds gas limit, the operation will be voided, the transaction is not packaged in the block and the transaction amount is refunded, and the gas fee that has been performed will still be charged [36]. Only if the user’s current amount is greater than gas limit times gas price, the transaction will be executed successfully. For gas price, if the value is too high, the transaction may be executed first, and if it is too low, the transaction speed will be slow.


### 3.4. System Model

In this section, we introduce the system model of the scheme, as shown in Figure1.(1)
Data Owner (DO). The main work of data owner is to calculate the keyword index and the file ciphertext and then send the file ciphertext to the cloud server and the keyword index to the smart contract.(2)
Data User (DU). The main work is to calculate the trapdoor and upload it to the smart contract. Then, data user gets the corresponding file ciphertext from cloud server and verifies it. Finally, data user decrypts the file ciphertext.(3)
Cloud Server (CS). The main work of the cloud server is to store the data uploaded by the data owner and receive the file index from smart contract. Next, the cloud server forwards the corresponding file ciphertext to the data user.(4)
Smart Contract (SC). Smart contract’s main job is to receive indexes and trapdoors to match and then send the search result to the cloud server through a transaction.(5)
Trusted Authority (TA). The trusted authority is responsible for generating public/private key pairs for data owner, data user, and the cloud server.Figure 1
The system model.


### 3.5. Algorithms in System Model

Here, we introduce the six algorithms in our scheme: Setup, KeyGen, Enc, Trap, Search, and Verification and Decryption.(1)
Setup1λ. The algorithm inputs a public parameter λ and outputs a global public parameter SP.(2)
KeyGenSP. This algorithm takes SP as inputs, and it outputs the DO’s public key pko and private key sko. The public and private keys of DU and CS are generated in a manner similar to DO.(3)
EncSP,pku,sko,F. This algorithm inputs SP, pku, and sko. Then, it outputs the keyword indexes I, file ciphertext C, packed ciphertext C′, and encrypted file index set Ns.(4)
TrapW′,pks,pko,sku. This algorithm takes queried keyword set W′, CS’s public key pks, DO’s public key pko, and DU’s private key sku as input and it outputs the corresponding trapdoor TW′ and location information L.(5)
SearchI,TW′,L,sks. This algorithm inputs I,TW′,L, the CS’s private key sks. Then, it outputs the encrypted file index set Ns. Note that the search process is run in the blockchain, using the privacy key of CS. Therefore, in the execution of smart contract, there will be an interaction with CS first.(6)
Verification and DecryptionSP,C,C′,Ns. The algorithm takes SP, Ns, file ciphertext set C, and packed ciphertext C′ as input and it outputs the verification results and file set F′.


### 3.6. Threat Model and Security Model

In this scheme, TA is completely trusted, the DU is malicious, and the CS is semitrusted. For example, the semitrusted CS may want to learn the original file information or return partial search results. DU may also maliciously accuse the CS not returning correct search results. In the payment phase, the CS may want to obtain the search fee from the DU without providing the search result. In addition, a malicious DU may want to get the correct search results from the CS without paying the search fee. Next, we introduce the security model of our scheme.We define that our scheme needs to satisfy two security goals, one is trapdoor indistinguishability and the other is index indistinguishability. Two games are needed to prove them.(1)
In Game 1, we assume the adversary A is a semitrusted CS or a malicious DU. Therefore, A can get the private key of CS or DU, but he cannot perform trapdoor query on the selected challenge keywordsw0, w1. The scheme does not get an effective trapdoor, which can ensure the indistinguishability of the index if there is no adversary to distinguish the index of the keyword w0 or w1.(2)
In Game 2, A may be a semitrusted CS, and A may get the private key of CS. The trapdoor of the scheme requires that A cannot distinguishw0W0 or w1W1.Definition 1.
In Game 1 and Game 2, the scheme can resist inside KGAs if there is no adversary to break the indistinguishability of indexes and trapdoors with a nonignorable advantage. The sequence of games is the interaction between challengerC and adversary A; pay attention to the semitrusted CS acting as A’s role.


## 3.1. Bilinear Pairing

LetG1, G2 be two multiplicative cycle groups. A map e:G1×G1⟶G2 is called a symmetric bilinear pairing if it has the following properties:(1)
Bilinear. eua,vb=eu,vab, ∀u,v∈G1, and ∀a,b∈Zp.(2)
Nondegenerate. eg,g≠1. Let 1∈G2 be the identity element of G2 group.(3)
Computable. ∀u,v∈G1, eu,v; there is a polynomial time algorithm that can easily calculate e.


## 3.2. Decisional Diffie–Hellman (DDH) Problem

Given a generatorg of G1, then g,ga,gb,gc∈G1, where a,b,c∈Zp. The DDH problem is to determine whether gc is equal to gab. Assuming that the DDH problem is difficult, it means that no adversary can solve the problem with a probability that cannot be ignored.


## 3.3. Blockchain

In this section, let us briefly describe the smart contract, gas system, system model, threat model, and security model.


### 3.3.1. Smart Contract

Blockchain is important and has a wide range of applications, such as the Internet of Things and edge computing, and blockchain can be used in 5G handover authentication [33]. The smart contract (SC) is considered as the core technology of the second-generation blockchain, which was proposed by Szabo [34]. The carrier of the SC is the blockchain, and its essence is an automatically executed computer code. The code describes the terms of the agreement between the buyer and the seller and is directly written into the code of the blockchain. Satisfying the predetermined terms is the trigger condition for the code to be executed. Since the execution of the code does not require human intervention, it is called automatic execution.As a computer program, a SC is a part of application software and a digitally represented program [35]. Although it is a code representation of contract terms, it is not a contract in the legal sense. In addition, the construction of SC comes from the blockchain framework, which is a public billing system, which can carry out secure value transfer without a trusted third party, and the correctness of the contract code execution is guaranteed by the consensus mechanism. Therefore, SC can be understood as a computer protocol, which can be executed automatically without human intervention.


### 3.3.2. Gas System

In Ethereum, once the SC is set, it is forbidden to modify it. In order to prevent malicious users from setting up an infinite loop running contract, Ethereum requires users to pay for each step of the deployment contract. The basic unit of cost is gas. Gas is equivalent to the fuel needed to deploy and execute SC. Without fuel, SC cannot be used. This mechanism maintains the operation of the economic system of Ethereum.In a gas system, there are some important parameters. Gas price means that users need to pay for each unit of gas. Each block has a gas limit, that is, the maximum amount of gas allowed in a single block, which can be used to determine how many transactions can be packaged in a single block. Both gas price and gas limit are set by the transaction sender itself. If the total amount of gas consumed by the operation exceeds gas limit, the operation will be voided, the transaction is not packaged in the block and the transaction amount is refunded, and the gas fee that has been performed will still be charged [36]. Only if the user’s current amount is greater than gas limit times gas price, the transaction will be executed successfully. For gas price, if the value is too high, the transaction may be executed first, and if it is too low, the transaction speed will be slow.


## 3.3.1. Smart Contract

Blockchain is important and has a wide range of applications, such as the Internet of Things and edge computing, and blockchain can be used in 5G handover authentication [33]. The smart contract (SC) is considered as the core technology of the second-generation blockchain, which was proposed by Szabo [34]. The carrier of the SC is the blockchain, and its essence is an automatically executed computer code. The code describes the terms of the agreement between the buyer and the seller and is directly written into the code of the blockchain. Satisfying the predetermined terms is the trigger condition for the code to be executed. Since the execution of the code does not require human intervention, it is called automatic execution.As a computer program, a SC is a part of application software and a digitally represented program [35]. Although it is a code representation of contract terms, it is not a contract in the legal sense. In addition, the construction of SC comes from the blockchain framework, which is a public billing system, which can carry out secure value transfer without a trusted third party, and the correctness of the contract code execution is guaranteed by the consensus mechanism. Therefore, SC can be understood as a computer protocol, which can be executed automatically without human intervention.


## 3.3.2. Gas System

In Ethereum, once the SC is set, it is forbidden to modify it. In order to prevent malicious users from setting up an infinite loop running contract, Ethereum requires users to pay for each step of the deployment contract. The basic unit of cost is gas. Gas is equivalent to the fuel needed to deploy and execute SC. Without fuel, SC cannot be used. This mechanism maintains the operation of the economic system of Ethereum.In a gas system, there are some important parameters. Gas price means that users need to pay for each unit of gas. Each block has a gas limit, that is, the maximum amount of gas allowed in a single block, which can be used to determine how many transactions can be packaged in a single block. Both gas price and gas limit are set by the transaction sender itself. If the total amount of gas consumed by the operation exceeds gas limit, the operation will be voided, the transaction is not packaged in the block and the transaction amount is refunded, and the gas fee that has been performed will still be charged [36]. Only if the user’s current amount is greater than gas limit times gas price, the transaction will be executed successfully. For gas price, if the value is too high, the transaction may be executed first, and if it is too low, the transaction speed will be slow.


## 3.4. System Model

In this section, we introduce the system model of the scheme, as shown in Figure1.(1)
Data Owner (DO). The main work of data owner is to calculate the keyword index and the file ciphertext and then send the file ciphertext to the cloud server and the keyword index to the smart contract.(2)
Data User (DU). The main work is to calculate the trapdoor and upload it to the smart contract. Then, data user gets the corresponding file ciphertext from cloud server and verifies it. Finally, data user decrypts the file ciphertext.(3)
Cloud Server (CS). The main work of the cloud server is to store the data uploaded by the data owner and receive the file index from smart contract. Next, the cloud server forwards the corresponding file ciphertext to the data user.(4)
Smart Contract (SC). Smart contract’s main job is to receive indexes and trapdoors to match and then send the search result to the cloud server through a transaction.(5)
Trusted Authority (TA). The trusted authority is responsible for generating public/private key pairs for data owner, data user, and the cloud server.Figure 1
The system model.


## 3.5. Algorithms in System Model

Here, we introduce the six algorithms in our scheme: Setup, KeyGen, Enc, Trap, Search, and Verification and Decryption.(1)
Setup1λ. The algorithm inputs a public parameter λ and outputs a global public parameter SP.(2)
KeyGenSP. This algorithm takes SP as inputs, and it outputs the DO’s public key pko and private key sko. The public and private keys of DU and CS are generated in a manner similar to DO.(3)
EncSP,pku,sko,F. This algorithm inputs SP, pku, and sko. Then, it outputs the keyword indexes I, file ciphertext C, packed ciphertext C′, and encrypted file index set Ns.(4)
TrapW′,pks,pko,sku. This algorithm takes queried keyword set W′, CS’s public key pks, DO’s public key pko, and DU’s private key sku as input and it outputs the corresponding trapdoor TW′ and location information L.(5)
SearchI,TW′,L,sks. This algorithm inputs I,TW′,L, the CS’s private key sks. Then, it outputs the encrypted file index set Ns. Note that the search process is run in the blockchain, using the privacy key of CS. Therefore, in the execution of smart contract, there will be an interaction with CS first.(6)
Verification and DecryptionSP,C,C′,Ns. The algorithm takes SP, Ns, file ciphertext set C, and packed ciphertext C′ as input and it outputs the verification results and file set F′.


## 3.6. Threat Model and Security Model

In this scheme, TA is completely trusted, the DU is malicious, and the CS is semitrusted. For example, the semitrusted CS may want to learn the original file information or return partial search results. DU may also maliciously accuse the CS not returning correct search results. In the payment phase, the CS may want to obtain the search fee from the DU without providing the search result. In addition, a malicious DU may want to get the correct search results from the CS without paying the search fee. Next, we introduce the security model of our scheme.We define that our scheme needs to satisfy two security goals, one is trapdoor indistinguishability and the other is index indistinguishability. Two games are needed to prove them.(1)
In Game 1, we assume the adversary A is a semitrusted CS or a malicious DU. Therefore, A can get the private key of CS or DU, but he cannot perform trapdoor query on the selected challenge keywordsw0, w1. The scheme does not get an effective trapdoor, which can ensure the indistinguishability of the index if there is no adversary to distinguish the index of the keyword w0 or w1.(2)
In Game 2, A may be a semitrusted CS, and A may get the private key of CS. The trapdoor of the scheme requires that A cannot distinguishw0W0 or w1W1.Definition 1.
In Game 1 and Game 2, the scheme can resist inside KGAs if there is no adversary to break the indistinguishability of indexes and trapdoors with a nonignorable advantage. The sequence of games is the interaction between challengerC and adversary A; pay attention to the semitrusted CS acting as A’s role.


## 4. Construction of the BPKEMS Scheme

### 4.1. Setup

Input a security parameterλ, and then TA runs the Setup algorithm to generate the system parameters SP=g,h,H1. We set g as a generator of G1, and h and H1 are two collision-resistant hash functions, where h:0,1∗⟶Zp, H1:0,1∗×0,1∗⟶0,1∗. Then, TA publishes the public parameters SP.


### 4.2. Key Generation

The scheme runs the KeyGen algorithm to generate the public/private key pair for DO, DU, and CS. The detailed generation process is as follows:(1)
KeyGeno: randomly choose an element a∈Zp as the private key sko and then compute the public key pko=ga.(2)
KeyGenu: pick an element b∈Zp as the DU’s private key sku and compute the public key eg,g1/b, gb. The DU’s public key has two parts, which we define as pku=pku1,pku2, where pku1=eg,g1/b, pku2=gb.(3)
KeyGens: choose an element c∈Zp as the private key sks and then compute the CS’s public key pks=gc.


### 4.3. Ciphertext Generation

Before generating a keyword index, DO first defines the reward$ offer to be paid per search to himself and sends this setting to the SC. Upon receiving the file set F=f1,…,ft, we define the keyword dictionary as W=w1,…,wn. DO extracts the keywords in each file. The DO uses the Enc algorithm to output the indexes I, file ciphertexts C, and packed ciphertext C′.(1)
First, DO needs to generate keyword indexIi=I0,I1,I2,Ij, where i∈1,t. DO randomly chooses an element r∈Zp. Next, he calculates the Ii,0=eg,gr, Ii,1=pku2r=gbr, Ii,2=eg,gar/b, Ii,j=g−rhwj, where j∈1,n.(2)
Second, DO encrypts each filefi∈F. Here, we use a symmetric encryption algorithm when encrypting files. The difference is that we use the idea of DH key exchange to share the key K for DO and DU, and DO uses its own private key sko and DU’s public key pku2 to calculate it, where K=pku2sko=gba. Then, for each file fi, Ci=EncKfi.(3)
Third, DO numbers the filefi, encrypts the file index i with the key K, obtains the encrypted file index Ni=EncKi, stores the Ni and the ciphertext Ci together, and then performs a hash operation to obtain the result Mi=H1Ni,Ci.The file indexesNi, Mi are packed as ciphertext Ci′. Next, upload the encrypted file index set Ns and ciphertext set C to the CS. Then, send the packed ciphertext set C′ and index set I to the SC for querying operation.


### 4.4. Ciphertext Update

In this part, we describe how to update files, for example, modify, insert, and delete operations. For modification and insertion of files, blockchain and encryption protect the index and encrypted files from leaking sensitive information. The detailed file update operations are shown in Figure2.(1)
Modification. Suppose a file mk needs to be changed to mk′, and DO needs to recalculate its ciphertext, that is, ck′=EncKmk′.(2)
Insertion. When adding a new file at the k-th position, add the ciphertext at the corresponding position with ck′.(3)
Deletion. When a file needs to be deleted, only the file and index value need to be deleted from the CS.Figure 2
The update operations of files.


### 4.5. Trapdoor

In this section, the Trap algorithm was run by DU. When a DU wants to query keywordsW′=w1′,…,wl′, he needs to generate trapdoor TW′ for these keywords. The trapdoor consists of two parts, one is TW′,1 and the other is TW′,2.(1)
DU randomly selects an elementφ∈Zp, let TW′,1=φ.(2)
DU computesTW′,2=pks−φpko1/b1/b−∑π=1lhwπ′.We need to record the keyword locationL, which expresses the location from W′ to W. We define a mapping function ρ:wπ′=wρπ. After the user generates the trapdoor TW′, the user sets a time limit node T1, uploads the trapdoor with the location L=ρ1,…,ρl to the SC, and performs the deposit operation from his account. Then, the user sends the trapdoor TW′ and the time limit node T1 to the SC. Next, he uploads his own identity ID to request the SC to perform the search service.


### 4.6. Search

The Search algorithm is run by SC. SC and blockchain are combined for search service. Here, we give the definition of some symbols.$ owner and $ user represent the respective accounts of DO and DU. $ userdeposit expresses the current deposit in blockchain. DU deposits his account balance into the blockchain system $ user⟶$ userdeposit. The price per unit of gasoline is denoted by $ gasprice. The total cost of each complete search operation is expressed as $ cost. Gaslsrch and Gassrch, respectively, express the gas limit and the cost of calling the search algorithm. After receiving the DU’s ID and requesting the search service, perform the following algorithm.(1)
First, check whether the current timeT2 is less than T1. If yes, perform the following steps. If no, process is stopped.(2)
Check whether$ userdeposit is greater than Gaslsrch×$ gasprice+$ offer; if yes, the user’s current deposit $ userdeposit can complete the next search service, and the SC starts to run. If no, stop it.(3)
The SC computes the intermediate valueσ2′=Ii,0TW′,1. Then, σ2′ is sent to CS. CS calculates the final value σ2=σ2′c and returns it to SC.(4)
Computeσ1=eIi,1·Πτ=1lIi,ρτ,TW′,2 and σ3=Ii,2.(5)
Calculate whether equationσ1·σ2=σ3 is true. If so, output 1 to indicate that the search was successful. Then, the SC sends the search results to the CS. Otherwise, output 0, indicating failure, and the search service will be stopped. Finally, the SC will record the encrypted file index Ni and then start the next query until all files are retrieved. Finally, SC sends the file index set Ns to CS. We describe the transaction during search in Algorithm 1.Algorithm 1: Ciphertexts retrieval.
(1)
ifT2<T1 and $userdeposit > Gaslsrch × $gasprice + $offer then;(2)
Computeσ1, σ2, σ3;(3)
ifσ1·σ2 is the same as σ3 then;(4)
Return the file indexesNi to CS;(5)
else;(6)
Return 0;(7)
Set$cost=$offer+Gassrch×$gasprice;(8)
Send$offer to $owner. Then, send Gassrch×$gasprice to executor of a deal;(9)
Finally, set$userdeposit=$userdeposit-$cost;(10)
else;(11)
Send$userdeposit to $user;(12)
end;


### 4.7. Verification and Decryption Phase

In this section, DU performs the verification and decryption algorithms. The SC sends file index setNs and DU’s ID that satisfies the search request to CS. Then, CS transmits the file ciphertext set C and encrypted file index set Ns to the DU according to Ni. In Algorithm 1, we describe the search process for each round.During the interaction between SC and DU, the packed ciphertextCi′ is obtained by the DU after the SC is successfully retrieved. Then, the user verifies NSC=NCS, where NSC represents the file index sent by the SC and NCS represents the file index sent by CS. If above indexes are the same, it proves that the CS did not send wrong files, and then verify M′=H1Ni,Ci, M=?M′.If the file indexNi and ciphertext Ci are hashed and the result is equal, it proves that the CS has not tampered with the ciphertext data. Finally, DU uses its own private key sku and DO’s public key pko to generate the shared key K=pkosku=gab of the encrypted file and decrypts the file ciphertext Ci, where fi=DecKCi. Finally, DU gets the decrypted file set F′.


### 4.8. Correctness

Formula (1) indicates that the index and trapdoor match successfully.(1)eIi,1·∏τ=1lIi,ρτ,TW′,2Ii,0cTW′,1=egbr·∏τ=1lg−vhwρ1τ,ga/bgc−φ1/b−∑τ=1lhwτ′eg,grcφ=egr,ga/b−cφeg,grcφ=eg,gar/b−rcφeg,grcφ=eg,gar/b=Ii,2.


## 4.1. Setup

Input a security parameterλ, and then TA runs the Setup algorithm to generate the system parameters SP=g,h,H1. We set g as a generator of G1, and h and H1 are two collision-resistant hash functions, where h:0,1∗⟶Zp, H1:0,1∗×0,1∗⟶0,1∗. Then, TA publishes the public parameters SP.


## 4.2. Key Generation

The scheme runs the KeyGen algorithm to generate the public/private key pair for DO, DU, and CS. The detailed generation process is as follows:(1)
KeyGeno: randomly choose an element a∈Zp as the private key sko and then compute the public key pko=ga.(2)
KeyGenu: pick an element b∈Zp as the DU’s private key sku and compute the public key eg,g1/b, gb. The DU’s public key has two parts, which we define as pku=pku1,pku2, where pku1=eg,g1/b, pku2=gb.(3)
KeyGens: choose an element c∈Zp as the private key sks and then compute the CS’s public key pks=gc.


## 4.3. Ciphertext Generation

Before generating a keyword index, DO first defines the reward$ offer to be paid per search to himself and sends this setting to the SC. Upon receiving the file set F=f1,…,ft, we define the keyword dictionary as W=w1,…,wn. DO extracts the keywords in each file. The DO uses the Enc algorithm to output the indexes I, file ciphertexts C, and packed ciphertext C′.(1)
First, DO needs to generate keyword indexIi=I0,I1,I2,Ij, where i∈1,t. DO randomly chooses an element r∈Zp. Next, he calculates the Ii,0=eg,gr, Ii,1=pku2r=gbr, Ii,2=eg,gar/b, Ii,j=g−rhwj, where j∈1,n.(2)
Second, DO encrypts each filefi∈F. Here, we use a symmetric encryption algorithm when encrypting files. The difference is that we use the idea of DH key exchange to share the key K for DO and DU, and DO uses its own private key sko and DU’s public key pku2 to calculate it, where K=pku2sko=gba. Then, for each file fi, Ci=EncKfi.(3)
Third, DO numbers the filefi, encrypts the file index i with the key K, obtains the encrypted file index Ni=EncKi, stores the Ni and the ciphertext Ci together, and then performs a hash operation to obtain the result Mi=H1Ni,Ci.The file indexesNi, Mi are packed as ciphertext Ci′. Next, upload the encrypted file index set Ns and ciphertext set C to the CS. Then, send the packed ciphertext set C′ and index set I to the SC for querying operation.


## 4.4. Ciphertext Update

In this part, we describe how to update files, for example, modify, insert, and delete operations. For modification and insertion of files, blockchain and encryption protect the index and encrypted files from leaking sensitive information. The detailed file update operations are shown in Figure2.(1)
Modification. Suppose a file mk needs to be changed to mk′, and DO needs to recalculate its ciphertext, that is, ck′=EncKmk′.(2)
Insertion. When adding a new file at the k-th position, add the ciphertext at the corresponding position with ck′.(3)
Deletion. When a file needs to be deleted, only the file and index value need to be deleted from the CS.Figure 2
The update operations of files.


## 4.5. Trapdoor

In this section, the Trap algorithm was run by DU. When a DU wants to query keywordsW′=w1′,…,wl′, he needs to generate trapdoor TW′ for these keywords. The trapdoor consists of two parts, one is TW′,1 and the other is TW′,2.(1)
DU randomly selects an elementφ∈Zp, let TW′,1=φ.(2)
DU computesTW′,2=pks−φpko1/b1/b−∑π=1lhwπ′.We need to record the keyword locationL, which expresses the location from W′ to W. We define a mapping function ρ:wπ′=wρπ. After the user generates the trapdoor TW′, the user sets a time limit node T1, uploads the trapdoor with the location L=ρ1,…,ρl to the SC, and performs the deposit operation from his account. Then, the user sends the trapdoor TW′ and the time limit node T1 to the SC. Next, he uploads his own identity ID to request the SC to perform the search service.


## 4.6. Search

The Search algorithm is run by SC. SC and blockchain are combined for search service. Here, we give the definition of some symbols.$ owner and $ user represent the respective accounts of DO and DU. $ userdeposit expresses the current deposit in blockchain. DU deposits his account balance into the blockchain system $ user⟶$ userdeposit. The price per unit of gasoline is denoted by $ gasprice. The total cost of each complete search operation is expressed as $ cost. Gaslsrch and Gassrch, respectively, express the gas limit and the cost of calling the search algorithm. After receiving the DU’s ID and requesting the search service, perform the following algorithm.(1)
First, check whether the current timeT2 is less than T1. If yes, perform the following steps. If no, process is stopped.(2)
Check whether$ userdeposit is greater than Gaslsrch×$ gasprice+$ offer; if yes, the user’s current deposit $ userdeposit can complete the next search service, and the SC starts to run. If no, stop it.(3)
The SC computes the intermediate valueσ2′=Ii,0TW′,1. Then, σ2′ is sent to CS. CS calculates the final value σ2=σ2′c and returns it to SC.(4)
Computeσ1=eIi,1·Πτ=1lIi,ρτ,TW′,2 and σ3=Ii,2.(5)
Calculate whether equationσ1·σ2=σ3 is true. If so, output 1 to indicate that the search was successful. Then, the SC sends the search results to the CS. Otherwise, output 0, indicating failure, and the search service will be stopped. Finally, the SC will record the encrypted file index Ni and then start the next query until all files are retrieved. Finally, SC sends the file index set Ns to CS. We describe the transaction during search in Algorithm 1.Algorithm 1: Ciphertexts retrieval.
(1)
ifT2<T1 and $userdeposit > Gaslsrch × $gasprice + $offer then;(2)
Computeσ1, σ2, σ3;(3)
ifσ1·σ2 is the same as σ3 then;(4)
Return the file indexesNi to CS;(5)
else;(6)
Return 0;(7)
Set$cost=$offer+Gassrch×$gasprice;(8)
Send$offer to $owner. Then, send Gassrch×$gasprice to executor of a deal;(9)
Finally, set$userdeposit=$userdeposit-$cost;(10)
else;(11)
Send$userdeposit to $user;(12)
end;


## 4.7. Verification and Decryption Phase

In this section, DU performs the verification and decryption algorithms. The SC sends file index setNs and DU’s ID that satisfies the search request to CS. Then, CS transmits the file ciphertext set C and encrypted file index set Ns to the DU according to Ni. In Algorithm 1, we describe the search process for each round.During the interaction between SC and DU, the packed ciphertextCi′ is obtained by the DU after the SC is successfully retrieved. Then, the user verifies NSC=NCS, where NSC represents the file index sent by the SC and NCS represents the file index sent by CS. If above indexes are the same, it proves that the CS did not send wrong files, and then verify M′=H1Ni,Ci, M=?M′.If the file indexNi and ciphertext Ci are hashed and the result is equal, it proves that the CS has not tampered with the ciphertext data. Finally, DU uses its own private key sku and DO’s public key pko to generate the shared key K=pkosku=gab of the encrypted file and decrypts the file ciphertext Ci, where fi=DecKCi. Finally, DU gets the decrypted file set F′.


## 4.8. Correctness

Formula (1) indicates that the index and trapdoor match successfully.(1)eIi,1·∏τ=1lIi,ρτ,TW′,2Ii,0cTW′,1=egbr·∏τ=1lg−vhwρ1τ,ga/bgc−φ1/b−∑τ=1lhwτ′eg,grcφ=egr,ga/b−cφeg,grcφ=eg,gar/b−rcφeg,grcφ=eg,gar/b=Ii,2.


## 5. Security Analysis

In order to show that our scheme is practical in terms of security and performance, we introduced the security and performance analysis in detail.


### 5.1. Fairness

Because the blockchain interacts with each entity on a transaction basis and each transaction is transparent, it can be guaranteed that the results of each query are correct and there will be no malicious tampering. Fairness is achieved through the use of SC. In Ethereum, all operations or transactions are associated with gas, and each operation will consume some of the gas on SC, and the person who provides the data (such as DO) will be rewarded accordingly. At the same time, users also need to pay for the files they retrieve. Without the involvement of a third party, the blockchain can ensure that users get correct and complete search results, and malicious operations will be detected. In addition, the user has determined a limited time to ensure the fairness of the transaction because the transaction needs to be completed within the specified time node. If the time limit is exceeded, the user will stop the search service.


### 5.2. Credibility

The search results given by the blockchain must be honest and credible. The operations on SC are transparent and cannot be tampered, so we can be confident that the results returned by the SC are credible. At the same time, it effectively prevents malicious server from attacking this scheme. In addition, the transparency of the blockchain can ensure the correctness of the results, and the verification on the user side can also achieve the same effect. Nothing can be used as a malicious tamper with the search results. Entities connected to the blockchain can verify the actions of other entities at any time.


### 5.3. Confidentiality

This scheme can resist KGAs in theory. The security of this scheme should realize the indistinguishability of index and trapdoor. Note that in Game 1, adversaryA can query both the private key and trapdoor. Importantly, trapdoor queries need to exclude previously defined challenge keywords. Corresponding to the definition of Game 2, we can get that A can query the index ciphertext and CS’s private key, the limitation is that A cannot query the challenge keywords w0 and w1.Theorem 1.
Through the proof analysis under the random oracle model, we can see that if the adversary solves the corresponding difficult problem with a negligible probability for both Game 1 and Game 2, then our scheme can resist KGAs.Proof.
The proof of theorem is supported by the following two lemmas. As long as their security requirements can be satisfied, our scheme is secure in the description of theorem. The detailed process is as follows. In Game 1, if the DDH assumption holds, the scheme achieves index indistinguishability. In Game 2, the scheme can ensure that it can resist chosen keyword attacks under the random oracle model.(1)
In Game 1, we analyze the symmetric key used to encrypt files between DO and DU, which is generated through negotiation between the two entities. The CS must obtain the private key of one before it can generate a shared key or intercept it during the transmission of the public channel. However, our scheme does not require transmission. Therefore, the CS must obtain the private key of one of them to decrypt the ciphertext of the filefi. Therefore, in our scheme, the shared key K is secure.(2)
The security of our scheme can be analyzed from two parts. The first is the generation of the index. Assuming that a DU wants to query a keyword setW′, CS must generate a valid index I˜=I˜o,I˜1,I˜2,I˜j. CS first needs to obtain the private key sko=a∈Zp of DO. The private key of DO is kept secret; CS can only assume that it has obtained a private key a˜ of the DU. But the size of Zp is p, which is a large prime number. Therefore, the probability of selecting the right one is 1/p, which is negligible. On the other hand, CS assumes that the keyword set W′=w1′,…,wl′=W′˜=w˜1,…,w˜l selected by CS is equal to the keyword set that DU wants to query, which is equivalent to randomly selecting l equal sets from n keywords, with a probability of 1/Cnl. Assuming that the range of the key set n is large enough, the above probability is also small enough. In summary, CS cannot perform inside KGAs.(3)
In Game 2, given a valid indexI=I0,I1,I2,Ij, CS cannot generate a valid trapdoor for matching. The generation of the trapdoor requires the use of the private key sku of the DU. We assume that the private key of the DU is sku=b. CS randomly selects a element b˜∈Zp as the private key of the DU. The equal probability is 1/p, so the probability can be ignored. Through the above analysis, our scheme can resist inside KGAs.
Here, we introduce the location privacy of keywords. In the paper, we use the location mapping functionρ·. The location privacy of queried keywords can be protected using random mask technology, for example, pseudorandom functions. The pseudorandom function confuses the position of the real keyword so as not to riot the position of the real keyword. Try not to let users know more information. For cloud server, the index location is exposed, but the keywords are encrypted, so the security of the scheme will not be affected.


## 5.1. Fairness

Because the blockchain interacts with each entity on a transaction basis and each transaction is transparent, it can be guaranteed that the results of each query are correct and there will be no malicious tampering. Fairness is achieved through the use of SC. In Ethereum, all operations or transactions are associated with gas, and each operation will consume some of the gas on SC, and the person who provides the data (such as DO) will be rewarded accordingly. At the same time, users also need to pay for the files they retrieve. Without the involvement of a third party, the blockchain can ensure that users get correct and complete search results, and malicious operations will be detected. In addition, the user has determined a limited time to ensure the fairness of the transaction because the transaction needs to be completed within the specified time node. If the time limit is exceeded, the user will stop the search service.


## 5.2. Credibility

The search results given by the blockchain must be honest and credible. The operations on SC are transparent and cannot be tampered, so we can be confident that the results returned by the SC are credible. At the same time, it effectively prevents malicious server from attacking this scheme. In addition, the transparency of the blockchain can ensure the correctness of the results, and the verification on the user side can also achieve the same effect. Nothing can be used as a malicious tamper with the search results. Entities connected to the blockchain can verify the actions of other entities at any time.


## 5.3. Confidentiality

This scheme can resist KGAs in theory. The security of this scheme should realize the indistinguishability of index and trapdoor. Note that in Game 1, adversaryA can query both the private key and trapdoor. Importantly, trapdoor queries need to exclude previously defined challenge keywords. Corresponding to the definition of Game 2, we can get that A can query the index ciphertext and CS’s private key, the limitation is that A cannot query the challenge keywords w0 and w1.Theorem 1.
Through the proof analysis under the random oracle model, we can see that if the adversary solves the corresponding difficult problem with a negligible probability for both Game 1 and Game 2, then our scheme can resist KGAs.Proof.
The proof of theorem is supported by the following two lemmas. As long as their security requirements can be satisfied, our scheme is secure in the description of theorem. The detailed process is as follows. In Game 1, if the DDH assumption holds, the scheme achieves index indistinguishability. In Game 2, the scheme can ensure that it can resist chosen keyword attacks under the random oracle model.(1)
In Game 1, we analyze the symmetric key used to encrypt files between DO and DU, which is generated through negotiation between the two entities. The CS must obtain the private key of one before it can generate a shared key or intercept it during the transmission of the public channel. However, our scheme does not require transmission. Therefore, the CS must obtain the private key of one of them to decrypt the ciphertext of the filefi. Therefore, in our scheme, the shared key K is secure.(2)
The security of our scheme can be analyzed from two parts. The first is the generation of the index. Assuming that a DU wants to query a keyword setW′, CS must generate a valid index I˜=I˜o,I˜1,I˜2,I˜j. CS first needs to obtain the private key sko=a∈Zp of DO. The private key of DO is kept secret; CS can only assume that it has obtained a private key a˜ of the DU. But the size of Zp is p, which is a large prime number. Therefore, the probability of selecting the right one is 1/p, which is negligible. On the other hand, CS assumes that the keyword set W′=w1′,…,wl′=W′˜=w˜1,…,w˜l selected by CS is equal to the keyword set that DU wants to query, which is equivalent to randomly selecting l equal sets from n keywords, with a probability of 1/Cnl. Assuming that the range of the key set n is large enough, the above probability is also small enough. In summary, CS cannot perform inside KGAs.(3)
In Game 2, given a valid indexI=I0,I1,I2,Ij, CS cannot generate a valid trapdoor for matching. The generation of the trapdoor requires the use of the private key sku of the DU. We assume that the private key of the DU is sku=b. CS randomly selects a element b˜∈Zp as the private key of the DU. The equal probability is 1/p, so the probability can be ignored. Through the above analysis, our scheme can resist inside KGAs.
Here, we introduce the location privacy of keywords. In the paper, we use the location mapping functionρ·. The location privacy of queried keywords can be protected using random mask technology, for example, pseudorandom functions. The pseudorandom function confuses the position of the real keyword so as not to riot the position of the real keyword. Try not to let users know more information. For cloud server, the index location is exposed, but the keywords are encrypted, so the security of the scheme will not be affected.


## 6. Performance Analysis

In order to show that our scheme is effective, in this part, we compare three schemes in terms of functions. In addition, we discuss the computation overhead and communication overhead of our scheme with two other schemes: Yang’s scheme [5] and Xu’s scheme [37].First, we compare the functions of the three schemes, as shown in Table2. We can see that by comparing the functions of the four aspects, we can see the functional differences between those schemes. The check mark means that this condition is satisfied, and the wrong sign means that the condition is not satisfied. It is compared by whether it supports multi-keyword retrieval, whether it supports dynamic update of files, whether it supports blockchain, and whether it supports fair payment between users. We can see that our scheme supports the four functions, scheme [37] only supports multi-keyword search, and scheme [5] only does not support dynamic update of files. The dynamic update of files can ensure the flexibility of the scheme. By using the blockchain, you can take advantage of the transparency, immutability, and traceability. Especially the SC running on the blockchain can ensure fair payment between users.Table 2
Functional comparison.
Our schemeYang’s scheme [5]Xu’s scheme [37]Multi-keyword✓✓✓Update✓××Blockchain✓✓×Fair payment✓✓×


### 6.1. Theoretical Analysis

In Table3, we compare the computation overhead of our scheme with the other two schemes [5, 37]. In terms of computation overhead, we mainly consider some time-consuming operations; TM represents a multiplication operation, TH represents a hash operation, TE represents an exponential operation, and TP represents a pair operation. In Table 4, we compare our scheme with other schemes [5, 37] in terms of communication overhead. We define the element length of G1, G2, Zp as G1, G2, Zp. In addition, we define m to represent the number of keywords contained in each file and l to represent the number of queried keywords.Table 3
Computation overhead.
Our schemeYang’s scheme [5]Xu’s scheme [37]KeyGen4TE+Tp2TH+4TE3TEEnc3+mTE+mTH+TPmTM+mTH+2m+3TEmTM+3mTH+2m+2TETrapdoor3TE+lTH+TMl+1TM+lTH+2l+3TE3lTH+2l+1TESearchTM+TE+TPTM+3TPTM+TE+3TPTable 4
Communication overhead.
Our schemeYang’s scheme [5]Xu’s scheme [37]pk sizeG1G1G1Enc sizem+1G1+2G2m+3G1m+2G1+mZpTrapdoor sizeG1+Zp3G13G1+lZpRegarding the computation overhead, we compare the characteristics of each scheme in Table3. In the key generation stage, we can see that our scheme is in the middle of the three at this stage, and the efficiency is higher than that of scheme [5] and lower than that of scheme [37]. In the keyword encryption and trapdoor generation phases, the calculation amount of the three schemes increases linearly with the number of encrypted keywords and queried keywords, but our scheme is the most efficient among the three, which are 3+mTE+mTH+TP and 3TE+lTH+TM, respectively. In the search stage, we set the number of keywords to be queried to 1. It can be seen from the table that the calculation amount of the three schemes is constant, but our scheme has the highest efficiency. Therefore, based on the above theoretical analysis, our scheme has the highest efficiency.Regarding communication overhead, we compare the public key size, encryption size, and trapdoor size with the other two schemes. We can see from Table4 that the size of the public key generated by the three schemes remains unchanged. In the encryption phase, the size of the storage of our scheme is almost the same as scheme [5] but is smaller than the storage size of scheme [37]. In the trapdoor generation stage, in scheme [37] the size of trapdoor increases linearly with the number of queried keywords, and therefore, it will consume a lot of storage resources. Our scheme and scheme [5] are constant and therefore have good storage characteristics.


### 6.2. Empirical Analysis

In this part, we emulate our scheme, Yang’s scheme [5], and Xu’s scheme [37]. We use the Java Pairing-Based Cryptography (JPBC) Library. The implementation equipment of the scheme is a HP desktop computer with a 3.00 GHz Intel Core i5-8500 processor and 8 GB memory. In the experiment, we used the Type A elliptic curve. We analyzed three schemes by comparing Enc, Trap, and Search algorithms. In the Enc algorithm, we set the number of keywords in steps of 10, increasing from 1 to 50 in turn. In Trap and Search, the number of keywords we set is also increasing from 10 to 50 in steps of 10. In each of the above experiments, after 50 cycles, the average value of the calculation cost is calculated to ensure that the results are relatively valid. It can be seen from Figures 3–5 that our scheme is the most effective. Below we briefly explain the content of the icon.Figure 3
The computation overhead of Enc algorithm.Figure 4
The computation overhead of Trap algorithm.Figure 5
The computation overhead of Search algorithm.In Figure3, we can see that our scheme has the smallest slope, which has great advantages compared with the other two schemes. Due to the frequent hashing operations and exponential operations, the coefficients of our scheme (m and 3+m) are larger, so the structure of the scheme is simpler. With the increase of keywords, the advantages will become more and more obvious.In Figure4, we can find that the time consumed is constant with the number of keywords that users query. In the process of generating trapdoors of our scheme, exponential operations and multiplication operations are constants, and hash operations increase linearly with the increase of keywords. However, you can see that in the other two schemes, the slope of growth is much larger than that of our scheme, and it takes time to hash to Zp which is much shorter than hashing to group G.In Figure5, the efficiency gap between our scheme and the other two schemes is not obvious. Because of the pair operation, the number of operations of exponential operation is almost constant. For the operation after hashing the keyword, whether it is the aggregation of addition or the aggregation of multiplication, the time consumed by a single operation is very small. Therefore, as the number of keywords increases, the trend of time changes is not obvious. But judging from the change trend in Figure 5, our scheme still has some advantages.


## 6.1. Theoretical Analysis

In Table3, we compare the computation overhead of our scheme with the other two schemes [5, 37]. In terms of computation overhead, we mainly consider some time-consuming operations; TM represents a multiplication operation, TH represents a hash operation, TE represents an exponential operation, and TP represents a pair operation. In Table 4, we compare our scheme with other schemes [5, 37] in terms of communication overhead. We define the element length of G1, G2, Zp as G1, G2, Zp. In addition, we define m to represent the number of keywords contained in each file and l to represent the number of queried keywords.Table 3
Computation overhead.
Our schemeYang’s scheme [5]Xu’s scheme [37]KeyGen4TE+Tp2TH+4TE3TEEnc3+mTE+mTH+TPmTM+mTH+2m+3TEmTM+3mTH+2m+2TETrapdoor3TE+lTH+TMl+1TM+lTH+2l+3TE3lTH+2l+1TESearchTM+TE+TPTM+3TPTM+TE+3TPTable 4
Communication overhead.
Our schemeYang’s scheme [5]Xu’s scheme [37]pk sizeG1G1G1Enc sizem+1G1+2G2m+3G1m+2G1+mZpTrapdoor sizeG1+Zp3G13G1+lZpRegarding the computation overhead, we compare the characteristics of each scheme in Table3. In the key generation stage, we can see that our scheme is in the middle of the three at this stage, and the efficiency is higher than that of scheme [5] and lower than that of scheme [37]. In the keyword encryption and trapdoor generation phases, the calculation amount of the three schemes increases linearly with the number of encrypted keywords and queried keywords, but our scheme is the most efficient among the three, which are 3+mTE+mTH+TP and 3TE+lTH+TM, respectively. In the search stage, we set the number of keywords to be queried to 1. It can be seen from the table that the calculation amount of the three schemes is constant, but our scheme has the highest efficiency. Therefore, based on the above theoretical analysis, our scheme has the highest efficiency.Regarding communication overhead, we compare the public key size, encryption size, and trapdoor size with the other two schemes. We can see from Table4 that the size of the public key generated by the three schemes remains unchanged. In the encryption phase, the size of the storage of our scheme is almost the same as scheme [5] but is smaller than the storage size of scheme [37]. In the trapdoor generation stage, in scheme [37] the size of trapdoor increases linearly with the number of queried keywords, and therefore, it will consume a lot of storage resources. Our scheme and scheme [5] are constant and therefore have good storage characteristics.


## 6.2. Empirical Analysis

In this part, we emulate our scheme, Yang’s scheme [5], and Xu’s scheme [37]. We use the Java Pairing-Based Cryptography (JPBC) Library. The implementation equipment of the scheme is a HP desktop computer with a 3.00 GHz Intel Core i5-8500 processor and 8 GB memory. In the experiment, we used the Type A elliptic curve. We analyzed three schemes by comparing Enc, Trap, and Search algorithms. In the Enc algorithm, we set the number of keywords in steps of 10, increasing from 1 to 50 in turn. In Trap and Search, the number of keywords we set is also increasing from 10 to 50 in steps of 10. In each of the above experiments, after 50 cycles, the average value of the calculation cost is calculated to ensure that the results are relatively valid. It can be seen from Figures 3–5 that our scheme is the most effective. Below we briefly explain the content of the icon.Figure 3
The computation overhead of Enc algorithm.Figure 4
The computation overhead of Trap algorithm.Figure 5
The computation overhead of Search algorithm.In Figure3, we can see that our scheme has the smallest slope, which has great advantages compared with the other two schemes. Due to the frequent hashing operations and exponential operations, the coefficients of our scheme (m and 3+m) are larger, so the structure of the scheme is simpler. With the increase of keywords, the advantages will become more and more obvious.In Figure4, we can find that the time consumed is constant with the number of keywords that users query. In the process of generating trapdoors of our scheme, exponential operations and multiplication operations are constants, and hash operations increase linearly with the increase of keywords. However, you can see that in the other two schemes, the slope of growth is much larger than that of our scheme, and it takes time to hash to Zp which is much shorter than hashing to group G.In Figure5, the efficiency gap between our scheme and the other two schemes is not obvious. Because of the pair operation, the number of operations of exponential operation is almost constant. For the operation after hashing the keyword, whether it is the aggregation of addition or the aggregation of multiplication, the time consumed by a single operation is very small. Therefore, as the number of keywords increases, the trend of time changes is not obvious. But judging from the change trend in Figure 5, our scheme still has some advantages.


## 7. Conclusion

With the development of cloud computing, a secure search cryptography scheme is becoming increasingly important. In this paper, we present a BPKEMS scheme in the blockchain scenario, which supports secure retrieval of conjunctive keywords, dynamic update of files, and verification of ciphertext. In addition, our scheme can resist KGAs. In terms of efficiency, we implemented this scheme through simulation and compared it with other schemes [5, 37], and it shows that our scheme is more practical.



---

*Source: 6619689-2021-01-21.xml*