# A Lightweight Blockchain-based Public-Key Authenticated Encryption with Multi-Keyword Search for Cloud Computing

Authors: Haorui Du; Jianhua Chen; Fei Lin; Cong Peng; Debiao He
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Cloud computing can provide users with sufficient computing resources, storage, and bandwidth to meet their needs. Data security and privacy protection are among the new threats faced by users. Searchable encryption is the combination of search technology and encryption technology. Searchable encryption can upload the user’s data to the cloud server after special encryption, and can realize the function of retrieving according to keywords. Comparatively to symmetric searchable encryption (SSE), public key searchable encryption (PEKS) simplifies key management greatly. However, most existing public key authenticated encryption with keyword search (PAEKS) schemes are based bilinear pairing, making them computationally expensive. Apart from this, complex retrieval requirements and the integrity of the results had not been considered. To address these problems, we propose a blockchain-based PAEKS schemes supporting multi-keyword queries and integrity verification. In addition, we provide security proofs for the PAEKS scheme under the decisional oracle Diffie-Hellman (DODH) assumption. This scheme a scheme that requires less storage and computational power than other schemes of the same kind.


---

## Body

## 1. Introduction

With the rapid development of mobile Internet, cloud computing is also gradually changing people’s lifestyles. A service provider aggregates a large amount of computing and storage resources to the cloud. It provides services on-demand to users with limited resources to facilitate a variety of diverse and personalized applications. Based on the high efficiency and low cost that cloud computing can provide, cloud computing has attracted a great deal of attention from academia as well as industry in the past decade. However, third-party service providers are not completely trustworthy, and storing data in plaintext will definitely pose a serious threat to the privacy of data leakage.The data on an untrusted server must be encrypted before it can be accessed. Data encryption ensures that nobody can access information without a key. Moreover, the data owner also loses the ability to retrieve the data. A conventional approach is to download all the files locally, decrypt them, and then search for them. It is not practical for users to use this method. Another approach is to delegate retrieval to the server, which finds the file and returns it to the user. However, it is a challenge for the server to find what it needs from the encrypted file. To query the encrypted file, the server needs the user’s key to decrypt it. Thus, encryption is rendered ineffective. As a result, it is hoped the server side has access to as much search functionality as possible without having to decrypt the data. Researchers proposed a technique called searchable encryption (SE), which could be used for private encryption and search.There are two types of searchable encryption: symmetric searchable encryption (SSE) and public key encryption with keyword search (PEKS). Song et al. [1] introduced the first practical scheme for searchable encryption, allowing text search without compromising confidentiality. In 2004, Boneh et al. [2] published the first study studying the search problem of data encrypted by the public key system, used as the prototype of all PEKS. It mainly solved how to find the mail required by users from the massive mail system. We must therefore understand the PEKS model clearly. As depicted in Figure 1, a PEKS scheme works as follows:(i)
The user Alice encrypts the file with a symmetric key. Then the user encrypts the keywordw1,w2,w3 with Bob’s public key and sends them to the mail server. Finally, the user sends the encrypted file and keyword ciphertext to the mail server.(ii)
The user Bob generates a search trapdoor ofw1 using his secret key, and sends a query to the mail server. Data users who wish to search for data on the cloud server generate search trapdoor information using their secret keys. Bob sends the search trapdoor to the cloud server.(iii)
By matching the ciphertext of the keywords, the mail server delivers the search results to Bob.Figure 1
Models of PEKS.SE is invalid, however, when you cannot securely share a secret key over e-mail. The PEKS can effectively solve the key transfer and key management problems in symmetric searchable encryption. Researchers strived to design efficient and effective mechanisms to perform searches on encrypted data. However, PEKS naturally has two major shortcomings.(i)
Having to deal with an ever-growing dataset size and requiring many public key operations limits the usefulness of PEKS.(ii)
Keyword guessing attacks (KGA) and inside keyword guessing attacks (IKGA) can be applied when the space of keywords is smaller than the space of keys.To resist keyword guessing attacks (KGA) from outside, Rhee et al. [3] constructed a public key encryption scheme for keyword searches of a specified searcher by introducing random numbers in the trapdoor, making it possible to run the test algorithm only on a specified server, thus preventing KGA by external adversaries. Further, the researchers considered the case where the adversary is a malicious server. As a result, the methods are divided into two categories roughly. A potential solution is to expand the range of keywords, which will make keyword guesses more difficult [4]. The other solution is to limit the adversary’s ability to create ciphertexts and trapdoors, so that keyword guessing attacks cannot be tested in large numbers by Huang and Li [5]. The methods are resistant to IKGA, but they ignore the fact that trapdoors are algorithmically generated deterministically, which can give away the user’s search habits. To meet this goal, the first challenge is to design a searchable encryption scheme that is resistant to IKGA and protects user search patterns and access patterns.As far as practicality and efficiency are concerned, Xu et al. [6] presented a lightweight PEKS scheme that was quite similar to some practical SSE schemes in terms of search performance. Similarly, those schemes [7–9] also designed the storage structure of ciphertext to improve the retrieval efficiency. Their approach was effective in terms of efficiency. However, we take another perspective is to reduce the consumption of public key operations, thus improving the retrieval efficiency and enhancing the utility. In addition, the current PAEKS schemes do not take into account multi-keyword search, which can affect the user’s experience. The second challenging goal of this scheme is to design an effective searchable encryption scheme that can be searched by multiple keywords.Third-party servers often benefit in practice from providing retrieval services with a risk that ciphertext data may be tampered with by malicious parties or that the server may fail. As a consequence, the integrity of search results is also a concern that cannot be overlooked. Azraoui et al. [10] combined polynomial-based accumulators and merkle trees to implement conjunctive keyword verification. The results of multi-keyword searches used by Wan and Deng [11] were verified using homomorphic Mac. Verifying search results in a flexible and feasible manner was possible by using a blockchain, which proved the reliability and fairness of the process by its non-repudiable property [12–15]. Therefore, designing a PAEKS that supports integrity verification of the retrieved results is the third challenge goal.


### 1.1. Motivation and Contributions

We analyzed the problems in existing schemes to establish the basis for achieving the above goals. First, the cloud server can perform unlimited trapdoor testing and cipher text matching. The server is too powerful for users to moniton, which can reveal the user’s access patterns. Therefore, we prefer that the recipient sends the file identifier to the server itself. In addition, trapdoors for the same keyword are identical, which may reveal the user’s search pattern. We introduce random numbers in trapdoor generation to blind trapdoors, and we can also use multiple keywords to reduce the risk of leakage. Secondly, most existing PAEKS algorithm is based on the bilinear map. The generation of ciphertexts and the high overhead of trapdoor computation can affect the experience of computationally constrained users. At the same time, the cloud server has to perform matching test for each ciphertext one by one in the trapdoor retrieval phase, which leads to a large computational burden on the cloud server. This makes the overall utility of the solution low. Besides, most existing PAEKS either do not consider the extension of multi-keyword search or the cost of extending to multiple keywords is costly. Therefore, we use a computationally inexpensive public key cryptographic primitive with support for multi-keyword search. Finally, the integrity of the search results is not considered. Therefore, we should use some new tools to solve this problem efficiently. Following the analysis above, we constructed a new PAEKS scheme based on our design goals. The contributions of this research are as follows:(i)
Firstly, we design a blockchain-based public key authenticated encryption scheme. Data sender and data receiver can naturally share a common initial key based on Diffie-Hellman key agreement, which can resist IKGA. The search and access pattern are not compromised.(ii)
Secondly, our scheme greatly reduces the computational cost and improves the practicability of the scheme. Specifically, it can reduce the computational cost of ciphertext and trapdoor without using bilinear pairs. In the testing phase, we use the inner product relation of two vectors to determine the set inclusion.(iii)
Finally, our scheme supports the integrity verification of the results. It ensures the reliability of search results by using the tamper proof characteristics of blockchain. We demonstrate that the scheme has adaptive security for CKA, and we perform a series of experiments to evaluate its performance.


### 1.2. Organization

We introduce a review of the related works in Section2. Preliminaries containing some cryptographic notations and the system model of our proposed system are introduced in Section 3. We introduce the basic BB-PAKES scheme in Section 4. We give the security proof of scheme in Section 5. We show the comparison of time consumption with other schemes in Section 6. Finally, we conclude this paper in Section 7.


## 1.1. Motivation and Contributions

We analyzed the problems in existing schemes to establish the basis for achieving the above goals. First, the cloud server can perform unlimited trapdoor testing and cipher text matching. The server is too powerful for users to moniton, which can reveal the user’s access patterns. Therefore, we prefer that the recipient sends the file identifier to the server itself. In addition, trapdoors for the same keyword are identical, which may reveal the user’s search pattern. We introduce random numbers in trapdoor generation to blind trapdoors, and we can also use multiple keywords to reduce the risk of leakage. Secondly, most existing PAEKS algorithm is based on the bilinear map. The generation of ciphertexts and the high overhead of trapdoor computation can affect the experience of computationally constrained users. At the same time, the cloud server has to perform matching test for each ciphertext one by one in the trapdoor retrieval phase, which leads to a large computational burden on the cloud server. This makes the overall utility of the solution low. Besides, most existing PAEKS either do not consider the extension of multi-keyword search or the cost of extending to multiple keywords is costly. Therefore, we use a computationally inexpensive public key cryptographic primitive with support for multi-keyword search. Finally, the integrity of the search results is not considered. Therefore, we should use some new tools to solve this problem efficiently. Following the analysis above, we constructed a new PAEKS scheme based on our design goals. The contributions of this research are as follows:(i)
Firstly, we design a blockchain-based public key authenticated encryption scheme. Data sender and data receiver can naturally share a common initial key based on Diffie-Hellman key agreement, which can resist IKGA. The search and access pattern are not compromised.(ii)
Secondly, our scheme greatly reduces the computational cost and improves the practicability of the scheme. Specifically, it can reduce the computational cost of ciphertext and trapdoor without using bilinear pairs. In the testing phase, we use the inner product relation of two vectors to determine the set inclusion.(iii)
Finally, our scheme supports the integrity verification of the results. It ensures the reliability of search results by using the tamper proof characteristics of blockchain. We demonstrate that the scheme has adaptive security for CKA, and we perform a series of experiments to evaluate its performance.


## 1.2. Organization

We introduce a review of the related works in Section2. Preliminaries containing some cryptographic notations and the system model of our proposed system are introduced in Section 3. We introduce the basic BB-PAKES scheme in Section 4. We give the security proof of scheme in Section 5. We show the comparison of time consumption with other schemes in Section 6. Finally, we conclude this paper in Section 7.


## 2. Related Works

In the cloud environment, searchable encryption provides a robust solution for retrieving ciphertexts under privacy protection. In this case, the cloud server can search among the ciphertext data uploaded by users and return ciphertext data matching the search criteria when the plaintext information is unavailable. Boneh et al. [2] introduced the public key encryption with keyword search, which is of great significance. The performance of SSE is generally better than the performance of PEKS. Beak et al. [16] pointed out [2] scheme utilized a secure channel between communication parties. The cost of building a secure channel made it not suitable for certain applications. Meanwhile, the adversary could intercept the trapdoor transmitted using a non-secure channel, creating security problems. Reference [16] used the server’s public key to encrypt the trapdoor to avoid these drawbacks, and proposed an improved keyword search public key encryption scheme to ensure the security of the trapdoor in the transmission process. There is only one server that can perform the search, and it was the first searchable public key encryption with designated tester (dPEKS) that improved the security of PEKS.In contrast, Byun et al. [17] observed that the keyword space was much smaller than the ciphertext space, and that we could brute force keywords with low entropy content more easily. Based on these facts, [17] pointed out that [2] could not resist (outside) keyword guessing attacks (KGA). Reference [17] provided specific methods of obtaining keyword information from any captured query message. Yau et al. [18] based on the attack by [17], and presented an attack method against the scheme by [16]. The above literature analysis showed that it was not possible to simply combine keywords and secret keys to generate a trapdoor that was resistant to keyword guessing attacks. This means that any insider/outsider attacker can associate the combination with the public key through pairing, which leads to an offline keyword guessing attack.To resist KGA, Rhee et al. [3] constructed a designated searcher keyword search public key encryption scheme, which restricted external adversaries from running the test algorithm. Hu and Liu [19] pointed out that [3] could not resist the outside keyword guessing attack of the server, and described the specific attack method and two improvements. They reserved the nature that the designated server can only carry out the keyword search and extended the dPEKS scheme to a bidirectional searchable proxy re-encryption with a designated tester scheme (Re-dPEKS).To achieve IKGA security against inside attacker, Huang and Liu [5] introduced the concept of public key authenticated encryption with keyword search (PAEKS). In PAEKS, the data sender not only encrypts the keyword, but also authenticates it, so that the verifier will believe that the encrypted keyword can only be generated by the sender. Specifically, Qin et al. [20, 21] concluded that [5] efficient was not adequate to capture a realistic threat, called for outside chosen multi-ciphertext attacks, and provided a new PAEKS model, which captured both (outside) chosen multi-ciphertext attacks and (inside) keyword guessing attacks. However, The trapdoor had been fixed, which would reveal the user’s retrieval patterns. On the basis of the above research, we considered several issues.Additionally, some researchers had suggested some encryption schemes that can support complex retrieval such as conjunctive keyword search, subset search, range query, and semantic keyword search [22–25], which improved retrieval accuracy and provided more complex retrieval expressions for the user. Abdelraheem et al. [26] presented a query evaluation scheme that combined SSE with Bitmap indexes. However, it required two rounds of interaction with the cloud server. Katz et al. [27] constructed a scheme for evaluating inner products based on predicates, which evaluated disjunctions, polynomials, thresholds, and more. It was possible to increase query efficiency by reducing the bilinear pairing during the search process [28–30]. Zhang et al. [31] proposed a public key encryption scheme based on a tree-based index structure. However, there was a keyword arrangement table between the data sender and the data receiver by default. Otherwise, the probability of successful retrieval was very low.Integrity verification aspects, Cheng et al. [32] proposed a symmetric searchable encryption scheme with verifiable integrity, which applies indistinguishable obfuscation techniques to counter server attacks. It achieved that a malicious server cannot tamper with the search results arbitrarily, but the indistinguishable obfuscation technique was too ideal. Therefore, it was difficult to implement in practical applications and did not have application value. Wang and Fan [33] proposed a lightweight symmetric searchable encryption scheme that implements support for search result integrity detection and also enables dynamic updating of ciphertexts corresponding to search keywords. They mainly used a tree structure to improve the update efficiency, but only single-user uploading and retrieval of ciphertexts is possible.


## 3. Preliminaries

As part of this section, we describe notations, cryptography materials, blockchains, the Bloom Filter, and system goals.


### 3.1. Notations

There is a description of the notations in Table1.Table 1
Summary of notations.
SymbolDescriptionG1The cyclic group of prime orderpgThe generator of groupG1H1,H2,H3Hash functionsPK,SKParticipant’s public and private keysWThe keywords setDocThe files setLThe number of values in the range0,L−1JThe number of the hash functionsBFBloom filterBF⟶L-dimensional vectorℋThe hash function family with keyindwA set of file identifiers containing keywordwEDBKeyword ciphertext setAccHash check list of ciphertextRltSearch result set−,−Vector inner productθ⟶The euclidean norm of anl-vector θ⟶


### 3.2. Blockchain

Decentralization, public verification, transparency, open audit, and antitampering are characteristics of blockchain, a technology that is gaining attention from academia and industry alike. All nodes have access to the data stored on the blockchain since blockchain runs without a central server. Each node participates and generates calculations, which are stored on the blockchain. Blockchains maintain the same data between all nodes thanks to the consensus mechanism, meaning that no single node can change the recorded data. Given these characteristics, the blockchain can act as a trusted third party for fair verification.


### 3.3. Bloom Filter

The bloom filter (BF) is a probabilistic data structure. It is very useful for performing collection membership tests quickly and in a space-saving manner, but it has the drawback that false positives do occur [34–36]. False positives are rare enough that many applications outweigh this disadvantage. Particularly, the BF in consists of three polynomial-time algorithms BF=BF.Gen,BF.Upd,BF.Check:(i)
BF.GenL,J: It requires two integers as inputs L,J∈N, and selects a collection of hash functions ℋ=hj−,kj∈J, where hj−,k:0,1∗⟶L is from 0,1∗ to a set L, and k is key. Finally, it outputs ℋ and an initial L-bit array BF=0L with each bit BFi for i∈L set to 0.(ii)
BF.Updℋ,BF,Meg: It takes ℋ=hjMeg,kj∈J, BF∈0,1L and an element Meg∈0,1∗, updates the current array BF by setting BFhjMeg,k←1 for all j∈J, and finally outputs the updated BF.(iii)
BF.Checkℋ,BF,Meg: It takes ℋ=hjMeg,kj∈J, BF∈0,1L and an element Meg∈0,1∗, and checks if BFhjMeg,k=1 for all j∈J. If ture, it outputs 1, otherwise returns 0.


### 3.4. Set Containment Search and Vector Scalar Product

One solution to perform aggregate containment search on outsourced data is to transform the aggregate records into a set of binary vectors with fixed dimensions. Based on the scalar product of the set containment problem, one can transform it into a vector search problem [37].


### 3.5. Pattern Leakage

LetQ be a q-query set whose element is a pair i,w, where i denotes the timestamp of a query, and w denotes a keyword. The leakage can be represented as follows [38]:(i)
Access Pattern. An access pattern describes whether a document contains a query keyword. For each query keyword w, an access pattern is defined as apw=IDw, where IDw represents the document’s ID number.(ii)
Search Pattern. It shows the query patterns for every keyword w. The search pattern for each keyword is spw=i|i,w∈Q.


### 3.6. Inverted Index

Database indexes store maps between content (such as words or numbers) and their location in a table, or in a file or group of files.(i)
Create Inverted Index. First, all the raw data are numbered to form a list of documents. Then the document data is extracted to obtain a large number of keywords, which are indexed by entry. The numbering information of the documents containing these entries is kept. It can also be referred to as an index matrix. As depicted in Figure 2.(ii)
Search Process. The user enters any keyword and brings the keyword to an inverted index list for matching. By looking up these terms, the numbers of all documents containing them can be found. Documents are then found in the document list based on these numbers.Figure 2
Inverted index. (a) Extract keywords from files. (b) Index matrix.
(a)(b)


### 3.7. The Computational Diffie-Hellman Assumption (CDH)

LetG be a cyclic group. The order is p. The generator is g. Given two elements of G, ga and gb, it is required to compute gab. CDH is intractable in the underlying group G.


### 3.8. The Decisional Oracle Diffie-Hellman (DODH)

TheG is a group. The order is p. The g is a random generator of G. The H:0,1∗⟶0,1hLen is hash function. The DODH assumption means that the advantage of A is negligible i AdvADODHλ=PrAg,ga,gb,R=1−PrAg,ga,gb,Hgab=1 where a,b∈Zp,R∈0,1hLen for any PPT adversary A.


### 3.9. The Definition of BB-PAEKS

ABB−PAEKS scheme is consisted of eight PPT algorithms, namely, Setup, KeyGen, PAEKS, Trapdoor, Search, Verify, Dec, Update. The formal constructions are as follows:The formal constructions are as follows:(i)
pp←Setupλ: This algorithm generates global parameters. Input a security parameter λ, and outputsa global public parameter pp.(ii)
PK,SK←KeyGenpp: It is responsible for maintaining the public and private keys for participants.(a)PKDS,SKDS←KeyGenpp: An algorithm that produces public and private keys for a sender. Input pp, and generates PKDS,SKDS for the sender.(b)PKDR,SKDR←KeyGenpp: This algorithm generates the public/private key pair for the receiver using input pp and outputs PKDR,SKDR.(iii)
Cw←PAKESPKDR,SKDS,w: The process is carried out by a data sender. Input PKDR,SKDS,w , and returns corresponding keyword’s ciphertext Cw.(iv)
Tw′←TrapdoorPKDS,SKDR,w′: It is performed by a data user. Input PKDS,SKDR,w′ , and returns corresponding keyword’s trapdoor Tw′.(v)
0,1←SearchCw,Tw: The algorithm is run by a SP.(vi)
proof←VerifyRlt,Acc: The algorithm is run by Blockchain.(vii)
indw←DecRlt,SKDR: The algorithm is run by DR.(viii)
Cw1,Cw2←Updatew,k: The algorithm is run by DR.


#### 3.9.1. Correctness

For a PAEKS scheme, GivenCw and Tw′, it can be converted into two vectors Cw⟶,Tw′⟶. We formulate consistency as below:Ifw=w′, then Cw⟶,Tw′⟶=Cw⟶ ; else w≠w′, then Cw⟶,Tw′⟶≠Cw⟶.


### 3.10. The Security Models of BB-PAKES

ForBB−PAEKS, the semantic security model incorporates both the indistinguishability of cipher-keywords and the indistinguishability of trapdoors. Our ciphertext indistinguishable security (CI-security) and Trapdoor indistinguishable security (TI-security) definition is identical to that of [5, 20, 21] in settings.


#### 3.10.1. CI-Security Model

AssumeA is an adversary, while λ is the security parameter.(i)
Initialization. A challenger generates the system parameter pp by running the setup algorithm Setupλ . Then, it runs KeyGenpp to generate the target DS’s public/private key pairs PKDS,SKDS, DR’s public/private key pairs PKDR,SKDR respectively. The challenger provides pp and PKDS and PKDR to A.(ii)
Phase 1. In this adaptive attack, the adversary asks PPT questions to the cipher oracle OC and trapdoor oracle OT, and receives the cipher and trapdoor for query keywords.(iii)
Challenge. After Phase 1, it outputs two challenge keywords w0∗ and w1∗. A coin b∈0,1 is flipped by the challenger. It sends the cipher-keyword Cwb∗← PAKES PKDR,SKDS,wb∗ to A.(iv)
Phase 2. While the adversary may use the Phase 1 oracle to continue to query the oracles, they may not access OC and OT with w0∗ and w1∗.(v)
Guess. Finally, A returns a bit b′∈0,1 as the guess of b and wins the game if b′=b.The adversaryA wins in the above game if he guesses b′=b. The A’s advantage in winning this game is defined as,(1)AdvAIND−CKAλ=Prb′=b−12.Definition 1.
(CI-security)ABB−PAEKSscheme satisfies cipher-keyword indistinguishable against chosen keywords attacks if for any PPT adversaryA, the advantageAdvAIND−CKAλof succeeding in the above game is negligible.


#### 3.10.2. TI-Security Model

The adversaryA and the security parameter λ.(i)
Initialization. Challenger C generates the system parameter pp by running the setup algorithm Setupλ . Then, it runs KeyGenpp to generate the target DS’s public/private key pairs PKDS,SKDS, DR’s public/private key pairs PKDR,SKDR respectively. The C provides pp, PKDS and PKDR to A.(ii)
Phase 1. The adversary adaptively performs PPT queries on password-keyword oracles PAEKS and trapdoor oracles, and obtain cipher and trapdoors for the query keywords.(iii)
Challenge. After the first phase, it outputs two challenge keywords w0∗ and w1∗ with the constraints w0∗ and w1∗. In the first stage, w0∗ and w1∗ are never queried by A for the cryptographic keyword oracle and the trapdoor oracle. The challenger then picks a coin b∈0,1 and sends the trapdoor Twb∗. Sends the trapdoor Twb∗← Trapdoor PKDS,SKDR,wb∗ to A.(iv)
Phase 2. As Phase 1, the adversary can continue to query the oracles, but cannot query OC and OT with w0∗ and w1∗.(v)
Guess. Finally, A returns a bit b′∈0,1 as the guess of b and wins the game if b′=b.The adversaryA wins in the above game if he guesses b′=b. The advantage of A winning this game is defined as,(2)AdvAIND−KGAλ=Prb′=b−12.Definition 2.
(TI-security)ABB−PAEKSscheme satisfies trapdoor indistinguishability against chosen keywords attacks if for any PPT adversaryA, the advantageAdvAIND−KGAλof succeeding in the above game is negligible.


### 3.11. System Model

The system includes the following parties: Storage Provider (SP), Data Sender (DS), Data Receiver (DR) and Blockchain as depicted in Figure3. The characteristic and function of each party are depicted as follows.(i)
Storage Provider (SP): Service providers have strong computing and storage capabilities. The SP stores encrypted data on behalf of the data sender, and SP retrieves the corresponding ciphertext when DR submits a retrieval request. The final step involves returning the retrieval result to the DR and blockchain.(ii)
Data Sender (DS): The DS collectsfle documents with identifiers ID=id1,id2,,…,idfle. Each document idi contains a set of keywords Wi, which is a subset of the collection of all keywords W=w1,w2,…,wnum, i.e., Wi⊂W. As a measure of improving query efficiency, DS creates an inverted index database DB for his keywords. For different keywords Wi, there is a set of document identifiers, denoted by indi. After that, DS encrypts all files, keyword and ind. The DS outsources the keyword ciphertext TB and document ciphertext T to the SP. At the same time, the DS performs a hash operation on the encrypted file identifier set B and sends it to the blockchain.(iii)
Data Receiver (DR): The DR generates search token according to the keywords and then sends the trapdoor to SP and BlockChain, respectively.(iv)
Blockchain: The blockchain is composed of various nodes (such as recruitment companies, candidates, and other identities). Its primary responsibility is to maintain the blockchain network that supports smart contracts, which can be utilized for storing user data and inspecting documents.Figure 3
The system model of BB-PAEKS.The detailed procedures ofBB−PAEKS are as follows: ① The DS extracts keyword set W from documents Doc and builds a checklist B from files. At the same time, encrypt keyword index Cw and documents CDoc. ② The DS sends encrypted keyword index Cw to the SP. Meanwhile, the DS sends checklist Acc to the Blockchain. ③ The SP registers Cw and CDoc to the database. ④ The DR computes trapdoor Tw of queried keywords Wq. ⑤ The DR sends trapdoor Tw to the SP and Blockchain. ⑥ The SP searches keyword index Cw in the database by using trapdoor Tw. ⑦ The SP returns the result to the DR and blockchain for verification. ⑧ As soon as the SP returns the results, the blockchain calculates the hash value of every result. From the identity information of DS in the checklist Acc, the blockchain gets the corresponding hash values of files. Finally, the blockchain compares two hash value to generate the proof. ⑨ The blockchain sends the proof to DR.


### 3.12. Threat Model

In this paper, it suppose that DS honestly follow thePAEKS algorithm to produce searchable ciphertexts for DO and transmits these ciphertexts to the SP. DR honestly follow the Trapdoor algorithm to produce trapdoor and transmits these to the SP. The SP is supposed to be honest and curious, who will honestly perform Test algorithm, and is interested in query results and frequency information of ciphertext. Blockchain is trusted and executes the protocols in the system honestly.


### 3.13. Design Goals

According to the most basic requirements of public key searchable encryption, our scheme must meet the following characteristics:(i)
Correctness: If the DR provides the correct trapdoor and the scheme is executed in the correct way, the received search results must be correct.(ii)
Confidentiality: The scheme needs to protect the confidentiality of keywords, files, indexes and trapdoors. In other words, the scheme can resist KGA and IKGA.(iii)
Integrity: The scheme supports multi-keyword retrieval and integrity verification of search results.


## 3.1. Notations

There is a description of the notations in Table1.Table 1
Summary of notations.
SymbolDescriptionG1The cyclic group of prime orderpgThe generator of groupG1H1,H2,H3Hash functionsPK,SKParticipant’s public and private keysWThe keywords setDocThe files setLThe number of values in the range0,L−1JThe number of the hash functionsBFBloom filterBF⟶L-dimensional vectorℋThe hash function family with keyindwA set of file identifiers containing keywordwEDBKeyword ciphertext setAccHash check list of ciphertextRltSearch result set−,−Vector inner productθ⟶The euclidean norm of anl-vector θ⟶


## 3.2. Blockchain

Decentralization, public verification, transparency, open audit, and antitampering are characteristics of blockchain, a technology that is gaining attention from academia and industry alike. All nodes have access to the data stored on the blockchain since blockchain runs without a central server. Each node participates and generates calculations, which are stored on the blockchain. Blockchains maintain the same data between all nodes thanks to the consensus mechanism, meaning that no single node can change the recorded data. Given these characteristics, the blockchain can act as a trusted third party for fair verification.


## 3.3. Bloom Filter

The bloom filter (BF) is a probabilistic data structure. It is very useful for performing collection membership tests quickly and in a space-saving manner, but it has the drawback that false positives do occur [34–36]. False positives are rare enough that many applications outweigh this disadvantage. Particularly, the BF in consists of three polynomial-time algorithms BF=BF.Gen,BF.Upd,BF.Check:(i)
BF.GenL,J: It requires two integers as inputs L,J∈N, and selects a collection of hash functions ℋ=hj−,kj∈J, where hj−,k:0,1∗⟶L is from 0,1∗ to a set L, and k is key. Finally, it outputs ℋ and an initial L-bit array BF=0L with each bit BFi for i∈L set to 0.(ii)
BF.Updℋ,BF,Meg: It takes ℋ=hjMeg,kj∈J, BF∈0,1L and an element Meg∈0,1∗, updates the current array BF by setting BFhjMeg,k←1 for all j∈J, and finally outputs the updated BF.(iii)
BF.Checkℋ,BF,Meg: It takes ℋ=hjMeg,kj∈J, BF∈0,1L and an element Meg∈0,1∗, and checks if BFhjMeg,k=1 for all j∈J. If ture, it outputs 1, otherwise returns 0.


## 3.4. Set Containment Search and Vector Scalar Product

One solution to perform aggregate containment search on outsourced data is to transform the aggregate records into a set of binary vectors with fixed dimensions. Based on the scalar product of the set containment problem, one can transform it into a vector search problem [37].


## 3.5. Pattern Leakage

LetQ be a q-query set whose element is a pair i,w, where i denotes the timestamp of a query, and w denotes a keyword. The leakage can be represented as follows [38]:(i)
Access Pattern. An access pattern describes whether a document contains a query keyword. For each query keyword w, an access pattern is defined as apw=IDw, where IDw represents the document’s ID number.(ii)
Search Pattern. It shows the query patterns for every keyword w. The search pattern for each keyword is spw=i|i,w∈Q.


## 3.6. Inverted Index

Database indexes store maps between content (such as words or numbers) and their location in a table, or in a file or group of files.(i)
Create Inverted Index. First, all the raw data are numbered to form a list of documents. Then the document data is extracted to obtain a large number of keywords, which are indexed by entry. The numbering information of the documents containing these entries is kept. It can also be referred to as an index matrix. As depicted in Figure 2.(ii)
Search Process. The user enters any keyword and brings the keyword to an inverted index list for matching. By looking up these terms, the numbers of all documents containing them can be found. Documents are then found in the document list based on these numbers.Figure 2
Inverted index. (a) Extract keywords from files. (b) Index matrix.
(a)(b)


## 3.7. The Computational Diffie-Hellman Assumption (CDH)

LetG be a cyclic group. The order is p. The generator is g. Given two elements of G, ga and gb, it is required to compute gab. CDH is intractable in the underlying group G.


## 3.8. The Decisional Oracle Diffie-Hellman (DODH)

TheG is a group. The order is p. The g is a random generator of G. The H:0,1∗⟶0,1hLen is hash function. The DODH assumption means that the advantage of A is negligible i AdvADODHλ=PrAg,ga,gb,R=1−PrAg,ga,gb,Hgab=1 where a,b∈Zp,R∈0,1hLen for any PPT adversary A.


## 3.9. The Definition of BB-PAEKS

ABB−PAEKS scheme is consisted of eight PPT algorithms, namely, Setup, KeyGen, PAEKS, Trapdoor, Search, Verify, Dec, Update. The formal constructions are as follows:The formal constructions are as follows:(i)
pp←Setupλ: This algorithm generates global parameters. Input a security parameter λ, and outputsa global public parameter pp.(ii)
PK,SK←KeyGenpp: It is responsible for maintaining the public and private keys for participants.(a)PKDS,SKDS←KeyGenpp: An algorithm that produces public and private keys for a sender. Input pp, and generates PKDS,SKDS for the sender.(b)PKDR,SKDR←KeyGenpp: This algorithm generates the public/private key pair for the receiver using input pp and outputs PKDR,SKDR.(iii)
Cw←PAKESPKDR,SKDS,w: The process is carried out by a data sender. Input PKDR,SKDS,w , and returns corresponding keyword’s ciphertext Cw.(iv)
Tw′←TrapdoorPKDS,SKDR,w′: It is performed by a data user. Input PKDS,SKDR,w′ , and returns corresponding keyword’s trapdoor Tw′.(v)
0,1←SearchCw,Tw: The algorithm is run by a SP.(vi)
proof←VerifyRlt,Acc: The algorithm is run by Blockchain.(vii)
indw←DecRlt,SKDR: The algorithm is run by DR.(viii)
Cw1,Cw2←Updatew,k: The algorithm is run by DR.


### 3.9.1. Correctness

For a PAEKS scheme, GivenCw and Tw′, it can be converted into two vectors Cw⟶,Tw′⟶. We formulate consistency as below:Ifw=w′, then Cw⟶,Tw′⟶=Cw⟶ ; else w≠w′, then Cw⟶,Tw′⟶≠Cw⟶.


## 3.9.1. Correctness

For a PAEKS scheme, GivenCw and Tw′, it can be converted into two vectors Cw⟶,Tw′⟶. We formulate consistency as below:Ifw=w′, then Cw⟶,Tw′⟶=Cw⟶ ; else w≠w′, then Cw⟶,Tw′⟶≠Cw⟶.


## 3.10. The Security Models of BB-PAKES

ForBB−PAEKS, the semantic security model incorporates both the indistinguishability of cipher-keywords and the indistinguishability of trapdoors. Our ciphertext indistinguishable security (CI-security) and Trapdoor indistinguishable security (TI-security) definition is identical to that of [5, 20, 21] in settings.


### 3.10.1. CI-Security Model

AssumeA is an adversary, while λ is the security parameter.(i)
Initialization. A challenger generates the system parameter pp by running the setup algorithm Setupλ . Then, it runs KeyGenpp to generate the target DS’s public/private key pairs PKDS,SKDS, DR’s public/private key pairs PKDR,SKDR respectively. The challenger provides pp and PKDS and PKDR to A.(ii)
Phase 1. In this adaptive attack, the adversary asks PPT questions to the cipher oracle OC and trapdoor oracle OT, and receives the cipher and trapdoor for query keywords.(iii)
Challenge. After Phase 1, it outputs two challenge keywords w0∗ and w1∗. A coin b∈0,1 is flipped by the challenger. It sends the cipher-keyword Cwb∗← PAKES PKDR,SKDS,wb∗ to A.(iv)
Phase 2. While the adversary may use the Phase 1 oracle to continue to query the oracles, they may not access OC and OT with w0∗ and w1∗.(v)
Guess. Finally, A returns a bit b′∈0,1 as the guess of b and wins the game if b′=b.The adversaryA wins in the above game if he guesses b′=b. The A’s advantage in winning this game is defined as,(1)AdvAIND−CKAλ=Prb′=b−12.Definition 1.
(CI-security)ABB−PAEKSscheme satisfies cipher-keyword indistinguishable against chosen keywords attacks if for any PPT adversaryA, the advantageAdvAIND−CKAλof succeeding in the above game is negligible.


### 3.10.2. TI-Security Model

The adversaryA and the security parameter λ.(i)
Initialization. Challenger C generates the system parameter pp by running the setup algorithm Setupλ . Then, it runs KeyGenpp to generate the target DS’s public/private key pairs PKDS,SKDS, DR’s public/private key pairs PKDR,SKDR respectively. The C provides pp, PKDS and PKDR to A.(ii)
Phase 1. The adversary adaptively performs PPT queries on password-keyword oracles PAEKS and trapdoor oracles, and obtain cipher and trapdoors for the query keywords.(iii)
Challenge. After the first phase, it outputs two challenge keywords w0∗ and w1∗ with the constraints w0∗ and w1∗. In the first stage, w0∗ and w1∗ are never queried by A for the cryptographic keyword oracle and the trapdoor oracle. The challenger then picks a coin b∈0,1 and sends the trapdoor Twb∗. Sends the trapdoor Twb∗← Trapdoor PKDS,SKDR,wb∗ to A.(iv)
Phase 2. As Phase 1, the adversary can continue to query the oracles, but cannot query OC and OT with w0∗ and w1∗.(v)
Guess. Finally, A returns a bit b′∈0,1 as the guess of b and wins the game if b′=b.The adversaryA wins in the above game if he guesses b′=b. The advantage of A winning this game is defined as,(2)AdvAIND−KGAλ=Prb′=b−12.Definition 2.
(TI-security)ABB−PAEKSscheme satisfies trapdoor indistinguishability against chosen keywords attacks if for any PPT adversaryA, the advantageAdvAIND−KGAλof succeeding in the above game is negligible.


## 3.10.1. CI-Security Model

AssumeA is an adversary, while λ is the security parameter.(i)
Initialization. A challenger generates the system parameter pp by running the setup algorithm Setupλ . Then, it runs KeyGenpp to generate the target DS’s public/private key pairs PKDS,SKDS, DR’s public/private key pairs PKDR,SKDR respectively. The challenger provides pp and PKDS and PKDR to A.(ii)
Phase 1. In this adaptive attack, the adversary asks PPT questions to the cipher oracle OC and trapdoor oracle OT, and receives the cipher and trapdoor for query keywords.(iii)
Challenge. After Phase 1, it outputs two challenge keywords w0∗ and w1∗. A coin b∈0,1 is flipped by the challenger. It sends the cipher-keyword Cwb∗← PAKES PKDR,SKDS,wb∗ to A.(iv)
Phase 2. While the adversary may use the Phase 1 oracle to continue to query the oracles, they may not access OC and OT with w0∗ and w1∗.(v)
Guess. Finally, A returns a bit b′∈0,1 as the guess of b and wins the game if b′=b.The adversaryA wins in the above game if he guesses b′=b. The A’s advantage in winning this game is defined as,(1)AdvAIND−CKAλ=Prb′=b−12.Definition 1.
(CI-security)ABB−PAEKSscheme satisfies cipher-keyword indistinguishable against chosen keywords attacks if for any PPT adversaryA, the advantageAdvAIND−CKAλof succeeding in the above game is negligible.


## 3.10.2. TI-Security Model

The adversaryA and the security parameter λ.(i)
Initialization. Challenger C generates the system parameter pp by running the setup algorithm Setupλ . Then, it runs KeyGenpp to generate the target DS’s public/private key pairs PKDS,SKDS, DR’s public/private key pairs PKDR,SKDR respectively. The C provides pp, PKDS and PKDR to A.(ii)
Phase 1. The adversary adaptively performs PPT queries on password-keyword oracles PAEKS and trapdoor oracles, and obtain cipher and trapdoors for the query keywords.(iii)
Challenge. After the first phase, it outputs two challenge keywords w0∗ and w1∗ with the constraints w0∗ and w1∗. In the first stage, w0∗ and w1∗ are never queried by A for the cryptographic keyword oracle and the trapdoor oracle. The challenger then picks a coin b∈0,1 and sends the trapdoor Twb∗. Sends the trapdoor Twb∗← Trapdoor PKDS,SKDR,wb∗ to A.(iv)
Phase 2. As Phase 1, the adversary can continue to query the oracles, but cannot query OC and OT with w0∗ and w1∗.(v)
Guess. Finally, A returns a bit b′∈0,1 as the guess of b and wins the game if b′=b.The adversaryA wins in the above game if he guesses b′=b. The advantage of A winning this game is defined as,(2)AdvAIND−KGAλ=Prb′=b−12.Definition 2.
(TI-security)ABB−PAEKSscheme satisfies trapdoor indistinguishability against chosen keywords attacks if for any PPT adversaryA, the advantageAdvAIND−KGAλof succeeding in the above game is negligible.


## 3.11. System Model

The system includes the following parties: Storage Provider (SP), Data Sender (DS), Data Receiver (DR) and Blockchain as depicted in Figure3. The characteristic and function of each party are depicted as follows.(i)
Storage Provider (SP): Service providers have strong computing and storage capabilities. The SP stores encrypted data on behalf of the data sender, and SP retrieves the corresponding ciphertext when DR submits a retrieval request. The final step involves returning the retrieval result to the DR and blockchain.(ii)
Data Sender (DS): The DS collectsfle documents with identifiers ID=id1,id2,,…,idfle. Each document idi contains a set of keywords Wi, which is a subset of the collection of all keywords W=w1,w2,…,wnum, i.e., Wi⊂W. As a measure of improving query efficiency, DS creates an inverted index database DB for his keywords. For different keywords Wi, there is a set of document identifiers, denoted by indi. After that, DS encrypts all files, keyword and ind. The DS outsources the keyword ciphertext TB and document ciphertext T to the SP. At the same time, the DS performs a hash operation on the encrypted file identifier set B and sends it to the blockchain.(iii)
Data Receiver (DR): The DR generates search token according to the keywords and then sends the trapdoor to SP and BlockChain, respectively.(iv)
Blockchain: The blockchain is composed of various nodes (such as recruitment companies, candidates, and other identities). Its primary responsibility is to maintain the blockchain network that supports smart contracts, which can be utilized for storing user data and inspecting documents.Figure 3
The system model of BB-PAEKS.The detailed procedures ofBB−PAEKS are as follows: ① The DS extracts keyword set W from documents Doc and builds a checklist B from files. At the same time, encrypt keyword index Cw and documents CDoc. ② The DS sends encrypted keyword index Cw to the SP. Meanwhile, the DS sends checklist Acc to the Blockchain. ③ The SP registers Cw and CDoc to the database. ④ The DR computes trapdoor Tw of queried keywords Wq. ⑤ The DR sends trapdoor Tw to the SP and Blockchain. ⑥ The SP searches keyword index Cw in the database by using trapdoor Tw. ⑦ The SP returns the result to the DR and blockchain for verification. ⑧ As soon as the SP returns the results, the blockchain calculates the hash value of every result. From the identity information of DS in the checklist Acc, the blockchain gets the corresponding hash values of files. Finally, the blockchain compares two hash value to generate the proof. ⑨ The blockchain sends the proof to DR.


## 3.12. Threat Model

In this paper, it suppose that DS honestly follow thePAEKS algorithm to produce searchable ciphertexts for DO and transmits these ciphertexts to the SP. DR honestly follow the Trapdoor algorithm to produce trapdoor and transmits these to the SP. The SP is supposed to be honest and curious, who will honestly perform Test algorithm, and is interested in query results and frequency information of ciphertext. Blockchain is trusted and executes the protocols in the system honestly.


## 3.13. Design Goals

According to the most basic requirements of public key searchable encryption, our scheme must meet the following characteristics:(i)
Correctness: If the DR provides the correct trapdoor and the scheme is executed in the correct way, the received search results must be correct.(ii)
Confidentiality: The scheme needs to protect the confidentiality of keywords, files, indexes and trapdoors. In other words, the scheme can resist KGA and IKGA.(iii)
Integrity: The scheme supports multi-keyword retrieval and integrity verification of search results.


## 4. Construction

This section presents a basic construction of PAEKS followed by an extension of the base version. It supports multi-keyword retrieval. Inverted index-based data structures, as illustrated in Figure2, are better suited to our construction. Our discussion in this paper does not include the topic of how to encrypt files, which is not the focus of our discussion.


### 4.1. Basic Construction

Our scheme is consisted of eight PPT algorithms, namely,Setup, KeyGen, PAEKS, Trapdoor, Search, Verify, DEC, Update. The formal constructions are as follows:(i)
pp←Setupλ: Choose a G1 is cyclic groups with prime order p. Select three hash functions H1:G1×0,1∗⟶Zp∗, H2:0,1∗⟶0,1∗, H3:Zp∗×0,1∗⟶Zp∗ and a collection of hash functions ℋ=hjk,− with key k, where j∈J. Choose a random generator g of G1. Output the public parameters pp=G1,p,g,H1,H2,H3,ℋ.(ii)
PK,SK←KeyGenpp: It is responsible for the public and private key pair of participants.(a)The DS chooses a random elementy∈Zp∗, and sets to PKDS=gymodp, SKDS=y.(b)The DR selects randomlyx∈Zp∗, and sets to PKDR=gxmodp, SKDR=x.(iii)
Cw1,Cw2←PAEKSSKDS,PKDR,w:(a)Data Sender.Version serial numberVerInfo∈Zp∗.DS runsBF.GenL,J.Computeu=gyx, and k=H1u,w, which the key is updated with the version information.Inputk and w, run BF.Updℋ,BFDR,w algorithm, and output the updated bloom filter BFDS, where a collection of hash functions ℋ=hjk,w with key k and keyword w for j∈J.indw=idi|w∈idi.Choose randomr1∈Zp∗, C1=gr1, C2=gxr1⋅indw, C3=H2C2.Send theCw1=BFDS,C1,C2,VerInfo to SP, and send the Cw2=C3,VerInfo to Blockchain.(b)Storage Provider.StoreCw1 to EDB.(c)BlockchainStoreCw2 to Acc.(iv)
Tw←TrapdoorSKDR,PKDS,w: The algorithm is run by a DR.(a)Data Recriver.DR runsBF.GenL,J.Computeu=gyx, and k=H1u,w, which the key is updated with the version information.Inputk and w, run BF.Updℋ,BFDR,w algorithm, and output the updated bloom filter BFDR, where a collection of hash functions ℋ=hjk,w with key k and keyword w for j∈J.Randomly selectJ random numbers num1,num2,…,numJ∈0,1∗, and the corresponding position of the bloom filter BFDR is set to 1, where J means the number of pseudo-random functions in bloom filter.Tw=BFDR.SendTw to SP and Blockchain.(v)
0,1←SearchCw,Tw: The algorithm is run by a SP.(a)IfBFDS⟶,BFDR⟶=BFDS⟶, the search algorithm returns 1. Otherwise, it returns 0.(b)Puts the matching ciphertextCw1 into the map Rlt.(c)Sends the resultRlt to the DR and Bolckchain.(vi)
proof←VerifyRlt,Acc: The algorithm is run by Blockchain.(a)Gets the search resultRlt, obtains the hash value of each file in the result from B, and gets the Acc.(b)For all ciphertextsCw1∈Rlt, blockchain computes the hash value of C2, gets H2C2.(c)Blockchain comparesH2C2 and Acc, if they are equal, the proof is true, otherwise false.(d)The search resultsRlt and proof are sent to DR.(vii)
indw←DecRlt,SKDR: The algorithm is run by DR.(a)Gets the search resultRlt.(b)Computeindw=C2/C1x.(viii)
Cw1,Cw2←Updatew,k: The algorithm is run by DR.(a)Data Receiver. The ciphertext update algorithm here is the same asPAKES, except for the key generation methodVersion serial numberVerInfo∗∈Zp∗.DS runsBF.GenL,J.Computeu=gyx, and k1=H1u,w, k2=H3k1,w.Inputk2 and w, run BF.Updℋ,BFDS,w algorithm, and output the updated bloom filter BFDS.indw=idi|w∈idi.Choose randomr1∈Zp∗, C1=gr1, C2=gxr1⋅indw, C3=H2C2.Send theCw1=BFDS,C1,C2,VerInfo∗ to SP, and send the Cw2=C3,VerInfo∗ to Blockchain.(b)Storage Provider.StoreCw1 to EDB.(c)BlockchainStoreCw2 to Acc.


### 4.2. Derived Constructions

On the basis of schemeBB−PAEKS, it can be easily extended to public key authenticated encryption with multi-keyword search. The Setup, KeyGen, PAEKS, Search, Verify, Update these algorithms are the same as those of the basic scheme, except that the Trapdoor and Dec algorithms are different. In order to save space, please refer to the basic scheme settings for details of specific schemes.(i)TrapdoorSKDR,PKDR,PKSP,w:(a)Data Receiver.DR runsBF.GenL,J.ForWQ=w1,w2,..,wq Compute u=gyx, For each keyword wi in set WQ=w1,w2,..,wq, perform the following steps, and finally add them to the bloom filter.ki=H1u,wi.Inputki and wi, run BF.Updℋ,BFDR,wi algorithm, and output the updated bloom filter BFDR.Choose randomJ∈0,1∗, and set BFDR to 1, where J means the number of pseudo-random functions in bloom filter.Tw=BFDR.SendTw to SP and Blockchain.(ii)DecRlt,SKDR: The algorithm is run by DR.(a)Gets the search resultRlt.(b)RunDecRlt,SKDR, get indw1,indw2,…,indwq.(c)It can get the results of different keyword combinations locally(conjunction and disjunction).


#### 4.2.1. Remark

(1)
It is not linear that the ciphertext and trapdoor size grow with keywords in our scheme. The trapdoor is the same size as the single keyword trapdoor.(2)
Search Index can be executed with a linear search, but a binary tree search is more efficient because we do not have to test all indexes in a binary tree search.(3)
Several factors need to be considered prior to using the bloom filter, including the length and number of pseudo-random functions. We can determine these parameters by usingn and fp, where n means the maximum number of characters and fp represents the maximum likelihood of false-positive fp [35, 39]. We select 2000 keywords, the length of the mapping bit array is 20000, the number of hash functions is 5, and the error rate is 0.00943. According to the parameter standard provided by [40].


## 4.1. Basic Construction

Our scheme is consisted of eight PPT algorithms, namely,Setup, KeyGen, PAEKS, Trapdoor, Search, Verify, DEC, Update. The formal constructions are as follows:(i)
pp←Setupλ: Choose a G1 is cyclic groups with prime order p. Select three hash functions H1:G1×0,1∗⟶Zp∗, H2:0,1∗⟶0,1∗, H3:Zp∗×0,1∗⟶Zp∗ and a collection of hash functions ℋ=hjk,− with key k, where j∈J. Choose a random generator g of G1. Output the public parameters pp=G1,p,g,H1,H2,H3,ℋ.(ii)
PK,SK←KeyGenpp: It is responsible for the public and private key pair of participants.(a)The DS chooses a random elementy∈Zp∗, and sets to PKDS=gymodp, SKDS=y.(b)The DR selects randomlyx∈Zp∗, and sets to PKDR=gxmodp, SKDR=x.(iii)
Cw1,Cw2←PAEKSSKDS,PKDR,w:(a)Data Sender.Version serial numberVerInfo∈Zp∗.DS runsBF.GenL,J.Computeu=gyx, and k=H1u,w, which the key is updated with the version information.Inputk and w, run BF.Updℋ,BFDR,w algorithm, and output the updated bloom filter BFDS, where a collection of hash functions ℋ=hjk,w with key k and keyword w for j∈J.indw=idi|w∈idi.Choose randomr1∈Zp∗, C1=gr1, C2=gxr1⋅indw, C3=H2C2.Send theCw1=BFDS,C1,C2,VerInfo to SP, and send the Cw2=C3,VerInfo to Blockchain.(b)Storage Provider.StoreCw1 to EDB.(c)BlockchainStoreCw2 to Acc.(iv)
Tw←TrapdoorSKDR,PKDS,w: The algorithm is run by a DR.(a)Data Recriver.DR runsBF.GenL,J.Computeu=gyx, and k=H1u,w, which the key is updated with the version information.Inputk and w, run BF.Updℋ,BFDR,w algorithm, and output the updated bloom filter BFDR, where a collection of hash functions ℋ=hjk,w with key k and keyword w for j∈J.Randomly selectJ random numbers num1,num2,…,numJ∈0,1∗, and the corresponding position of the bloom filter BFDR is set to 1, where J means the number of pseudo-random functions in bloom filter.Tw=BFDR.SendTw to SP and Blockchain.(v)
0,1←SearchCw,Tw: The algorithm is run by a SP.(a)IfBFDS⟶,BFDR⟶=BFDS⟶, the search algorithm returns 1. Otherwise, it returns 0.(b)Puts the matching ciphertextCw1 into the map Rlt.(c)Sends the resultRlt to the DR and Bolckchain.(vi)
proof←VerifyRlt,Acc: The algorithm is run by Blockchain.(a)Gets the search resultRlt, obtains the hash value of each file in the result from B, and gets the Acc.(b)For all ciphertextsCw1∈Rlt, blockchain computes the hash value of C2, gets H2C2.(c)Blockchain comparesH2C2 and Acc, if they are equal, the proof is true, otherwise false.(d)The search resultsRlt and proof are sent to DR.(vii)
indw←DecRlt,SKDR: The algorithm is run by DR.(a)Gets the search resultRlt.(b)Computeindw=C2/C1x.(viii)
Cw1,Cw2←Updatew,k: The algorithm is run by DR.(a)Data Receiver. The ciphertext update algorithm here is the same asPAKES, except for the key generation methodVersion serial numberVerInfo∗∈Zp∗.DS runsBF.GenL,J.Computeu=gyx, and k1=H1u,w, k2=H3k1,w.Inputk2 and w, run BF.Updℋ,BFDS,w algorithm, and output the updated bloom filter BFDS.indw=idi|w∈idi.Choose randomr1∈Zp∗, C1=gr1, C2=gxr1⋅indw, C3=H2C2.Send theCw1=BFDS,C1,C2,VerInfo∗ to SP, and send the Cw2=C3,VerInfo∗ to Blockchain.(b)Storage Provider.StoreCw1 to EDB.(c)BlockchainStoreCw2 to Acc.


## 4.2. Derived Constructions

On the basis of schemeBB−PAEKS, it can be easily extended to public key authenticated encryption with multi-keyword search. The Setup, KeyGen, PAEKS, Search, Verify, Update these algorithms are the same as those of the basic scheme, except that the Trapdoor and Dec algorithms are different. In order to save space, please refer to the basic scheme settings for details of specific schemes.(i)TrapdoorSKDR,PKDR,PKSP,w:(a)Data Receiver.DR runsBF.GenL,J.ForWQ=w1,w2,..,wq Compute u=gyx, For each keyword wi in set WQ=w1,w2,..,wq, perform the following steps, and finally add them to the bloom filter.ki=H1u,wi.Inputki and wi, run BF.Updℋ,BFDR,wi algorithm, and output the updated bloom filter BFDR.Choose randomJ∈0,1∗, and set BFDR to 1, where J means the number of pseudo-random functions in bloom filter.Tw=BFDR.SendTw to SP and Blockchain.(ii)DecRlt,SKDR: The algorithm is run by DR.(a)Gets the search resultRlt.(b)RunDecRlt,SKDR, get indw1,indw2,…,indwq.(c)It can get the results of different keyword combinations locally(conjunction and disjunction).


### 4.2.1. Remark

(1)
It is not linear that the ciphertext and trapdoor size grow with keywords in our scheme. The trapdoor is the same size as the single keyword trapdoor.(2)
Search Index can be executed with a linear search, but a binary tree search is more efficient because we do not have to test all indexes in a binary tree search.(3)
Several factors need to be considered prior to using the bloom filter, including the length and number of pseudo-random functions. We can determine these parameters by usingn and fp, where n means the maximum number of characters and fp represents the maximum likelihood of false-positive fp [35, 39]. We select 2000 keywords, the length of the mapping bit array is 20000, the number of hash functions is 5, and the error rate is 0.00943. According to the parameter standard provided by [40].


## 4.2.1. Remark

(1)
It is not linear that the ciphertext and trapdoor size grow with keywords in our scheme. The trapdoor is the same size as the single keyword trapdoor.(2)
Search Index can be executed with a linear search, but a binary tree search is more efficient because we do not have to test all indexes in a binary tree search.(3)
Several factors need to be considered prior to using the bloom filter, including the length and number of pseudo-random functions. We can determine these parameters by usingn and fp, where n means the maximum number of characters and fp represents the maximum likelihood of false-positive fp [35, 39]. We select 2000 keywords, the length of the mapping bit array is 20000, the number of hash functions is 5, and the error rate is 0.00943. According to the parameter standard provided by [40].


## 5. Security Proof

In this section, we show that our basic scheme is compatible with the design goals, in other words, our construction is reliable. It can resist IKGA and reduce the possibility of access pattern and search pattern disclosure.


### 5.1. Correctness

#### 5.1.1. Correctness

The sender and receiver computeu=gyx, α=H2wu, k=H1α,w. They run BF.GenL,J and BF.Updℋ,BF,w algorithm and get BFDS and BFDR about keyword w. Then, it can be proved to be correct according to bloom filter and set intersection property.


#### 5.1.2. Remark

Our scheme does not consider malicious man in the middle attack and malicious tampering by external enemies. It can be guaranteed by public key encryption system and algorithms.


### 5.2. Confidentiality

The following theorems illustrate how our scheme satisfies IND-CKA and IND-KGA security.Theorem 1.
Our schemeBB−PAEKSimplements IND-CKA security if the DODH assumption holds.Lemma 1.
The advantageAdvACKAis negligible for any PPT adversaryA.Proof.
Suppose the adversary guesses the key words in the game, and the correct event is recorded asb′=b. We define games as follows:
Game0. It is the original IND-CKA game.(i)Setupλ: The challenger C runs Setupλ and KeyGenpp to generate the public parameter pp and public/private key pair of participants PKDS,SKDS=gymodp, y of DS, PKDR,SKDR=gxmodp, x of DR. Then, the challenger C sends pp,PKDS,PKDR to the adversary A. Hash functions H1,H2,H3 and ℋ should be collision resistant and secure.(ii)Phase1: In this adaptive attack, the adversary asks PPT questions to the cipher-keyword oracle OC and the trapdoor oracle OT, and C is simulated as follows:(a)OC: Run BF.GenL,J. Compute u=gyx and k=H1u,w. Input k and w, run BF.Updℋ,BFDS,w algorithm, and output the updated bloom filter BFDS. Send the BFDS to A.(b)OT: Run BF.GenL,J. Compute u=gyx, and k=H1u,w. Input k and w, run BF.Updℋ,BFDR,w algorithm, and output the updated bloom filter BFDR. Choose random J∈0,1∗, and set BFDR to 1, where J means the number of pseudo-random functions in bloom filter. Send trapdoor BFDR to A.(iii)Challenge: As the adversary A chooses keywords w0∗,w1∗, and sends them to C. The challenger C picks a random bit b∈0,1, and encrypts the keyword wb∗. The ciphertext of the challenge keyword wb∗ as follows:(a)Choose a randomu=gyx, and k=H1u,wb∗. RunBF.Updℋ,BFDS∗,wb∗, output BFDS∗.(b)Finally, the challengeC sends Cwb∗∗ to adversary.(iv)Phase2: The adversary A proceeds to query oracles during Phase1. It cannot query the ciphertext and trapdoor of w0,w1.(v)Guess: If b′=b then C wins the game. The adversary A has the advantage that is(3)AdvAGame0λ=AdvACKAλ.
Game1. Let Game1 be the same game as Game0, except that the challenger chooses r1∈G1 instead of computing u=gyx. The challenger sends the ciphertext Cwb∗∗. We have AdvAGame0−AdvAGame1<AdvADODHλ, where AdvADODHλ is negligible if the DODH assumption holds.
Game2. Let Game2 be the same game as Game1, except that the challenger random chooses r1′ instead of k=H1α,wb∗. Due to r1 and r1′ are random. From adversary’s view, the ciphertext Cwb∗ of Game1 and Game2 are the identical distribution.
We have,(4)AdvAGame2λ=AdvAGame1λ.
We conclude that the adversary can only win with probability inGame2 because Cwb∗ is independent of b. Thus, the advantage,(5)AdvAGame2λ=12−12=0.
Finally, according to theGame0, Game1,Game2 we have,(6)AdvAGame2λ−AdvAIND−CKAλ≤AdvADODHλ.
whereAdvADODHλ are negligible. Therefore, the adversary A′ advantage in winning can be ignored in the IND-KGA game.Theorem 2.
Our schemeBB−PAEKSimplements IND-KGA security if the DODH assumption holds.Lemma 2.
The advantageAdvAKGAis negligible for any PPT adversaryA.Proof.
Suppose the adversary guesses the key words in the game, and the correct event is recorded asb′=b. We define games as follows:
Game0. IND-KGA is the original version of this game.(i)Setupλ: The challenger C runs Setupλ and KeyGenpp to generate the public parameter pp and public/private key pair of participants PKDS,SKDS=gymodp,y of DS, PKDR,SKDR=gxmodp,x of DR, of PKSP,SKSP=gzmodp,z of SP. Then, the challenger C sends pp,PKDS,PKDR,PKSP to the adversary A. Based on what we know so far about hash functions, we assume H1,H2,H3 and ℋ are secure and collision-resistant.(ii)Phase1: In this adaptive attack, the adversary asks PPT questions to the cipher-keyword oracle OC and the trapdoor oracle OT, and C is simulated as follows:(a)OC: Run BF.GenL,J. Compute u=gyx and k=H1u,w. Input k and w, run BF.Updℋ,BFDS,w algorithm, and output the updated bloom filter BFDS. Send the BFDS to A.(b)OT: Run BF.GenL,J. Compute u=gyx, k=H1u,w. Input k and w, run BF.Updℋ,BFDR,w algorithm, and output the updated bloom filter BFDR. Choose random J∈0,1∗, and set BFDR to 1, where J means the number of pseudo-random functions in bloom filter. Send trapdoor BFDR to A.(iii)Challenge: The adversary A selects two keywords w0∗,w1∗ and sends them to C. The challenger C picks a random bit b∈0,1, and encrypts the keyword wb∗. The trapdoor of the challenge keyword wb∗ as follows:(a)Choose a randomu=gyx and k=H1u,wb∗. RunBF.Updℋ,BFDR∗,wb∗, output BFDR∗. Choose random J∈0,1∗, and set BFDR to 1, where J means the number of pseudo-random functions in bloom filter. Finally, the challenge C sends Twb∗∗ to adversary.(iv)Phase2: Phase1 continues to be issued by the adversary A as queries to Oracles. There is only one restriction is that w0,w1 cannot be chosen for the ciphertext and trapdoor query.(v)Guess: If b′=b then C wins the game. According to the IND-KGA definition, adversary A has the advantage that is(7)AdvAGame0λ=AdvAKGAλ.
Game1. Let Game1 be the same game as Game0, except that the challenger chooses r1∈G1 instead of computing u=gyx. The challenger sends the ciphertext Cwb∗∗. We have AdvAGame0−AdvAGame1<AdvADODHλ, where AdvADODHλ is negligible if the DODH assumption holds.
Game2. Let Game2 be the same game as Game1, except that the challenger random chooses r1′ instead of k=H1u,wb∗. Due to r1 and r1′ are random, which the ciphertext Cwb∗ of Game1 and Game2 are the same distribution from adversary’s view.
We have,(8)AdvAGame2λ=AdvAGame1λ.
As we know, the adversary can only winGame2 with probability since Cwb∗ is independent of b. Thus, the advantage,(9)AdvAGame2λ=12−12=0.
Finally, according to theGame0, Game1,Game2 we have,(10)AdvAGame2λ−AdvAKGAλ≤AdvADODHλ,where AdvADODHλ are negligible. Therefore, the advantage of adversary A wins in the IND-KGA game is negligible.


### 5.3. Security

This study, adversary a is mainly aimed at the curious server. That’s because resisting external adversary can be easily solved by introducing the server public key. In other words, IKGA is mainly considered. In addition,PAKES and Trapdoor algorithms are most likely to disclose keyword information, So we focused on the analysis PAKES and Trapdoor algorithms.(i)Resistance against IKGA. In PAEKS, only the DS can generate the legal ciphertext of keyword. The adversary executes thePAEKS algorithm, it cannot generate k. Similarly, the adversary cannot generate the trapdoor of keyword. Finally, the adversary cannot obtain any information by running the Test algorithm. Thus, our scheme can resist the IKGA.(ii)Access pattern. We use DR’s public key to encrypt the file identifierindw that meets the keyword w. The SP returns the result to DR, who decrypts the file identifier information with his private key. Finally, the DR submits file identifier to SP according to his actual needs. By adding a round of communication, we ensure the privacy of the matching relationship between keywords and file identifiers. Thus, our scheme protects the access pattern of DS.(iii)Search pattern. The trapdoors of our scheme are generated randomly, that is, the trapdoors of the same keyword are different. Thus, our scheme protects the search pattern.


## 5.1. Correctness

### 5.1.1. Correctness

The sender and receiver computeu=gyx, α=H2wu, k=H1α,w. They run BF.GenL,J and BF.Updℋ,BF,w algorithm and get BFDS and BFDR about keyword w. Then, it can be proved to be correct according to bloom filter and set intersection property.


### 5.1.2. Remark

Our scheme does not consider malicious man in the middle attack and malicious tampering by external enemies. It can be guaranteed by public key encryption system and algorithms.


## 5.1.1. Correctness

The sender and receiver computeu=gyx, α=H2wu, k=H1α,w. They run BF.GenL,J and BF.Updℋ,BF,w algorithm and get BFDS and BFDR about keyword w. Then, it can be proved to be correct according to bloom filter and set intersection property.


## 5.1.2. Remark

Our scheme does not consider malicious man in the middle attack and malicious tampering by external enemies. It can be guaranteed by public key encryption system and algorithms.


## 5.2. Confidentiality

The following theorems illustrate how our scheme satisfies IND-CKA and IND-KGA security.Theorem 1.
Our schemeBB−PAEKSimplements IND-CKA security if the DODH assumption holds.Lemma 1.
The advantageAdvACKAis negligible for any PPT adversaryA.Proof.
Suppose the adversary guesses the key words in the game, and the correct event is recorded asb′=b. We define games as follows:
Game0. It is the original IND-CKA game.(i)Setupλ: The challenger C runs Setupλ and KeyGenpp to generate the public parameter pp and public/private key pair of participants PKDS,SKDS=gymodp, y of DS, PKDR,SKDR=gxmodp, x of DR. Then, the challenger C sends pp,PKDS,PKDR to the adversary A. Hash functions H1,H2,H3 and ℋ should be collision resistant and secure.(ii)Phase1: In this adaptive attack, the adversary asks PPT questions to the cipher-keyword oracle OC and the trapdoor oracle OT, and C is simulated as follows:(a)OC: Run BF.GenL,J. Compute u=gyx and k=H1u,w. Input k and w, run BF.Updℋ,BFDS,w algorithm, and output the updated bloom filter BFDS. Send the BFDS to A.(b)OT: Run BF.GenL,J. Compute u=gyx, and k=H1u,w. Input k and w, run BF.Updℋ,BFDR,w algorithm, and output the updated bloom filter BFDR. Choose random J∈0,1∗, and set BFDR to 1, where J means the number of pseudo-random functions in bloom filter. Send trapdoor BFDR to A.(iii)Challenge: As the adversary A chooses keywords w0∗,w1∗, and sends them to C. The challenger C picks a random bit b∈0,1, and encrypts the keyword wb∗. The ciphertext of the challenge keyword wb∗ as follows:(a)Choose a randomu=gyx, and k=H1u,wb∗. RunBF.Updℋ,BFDS∗,wb∗, output BFDS∗.(b)Finally, the challengeC sends Cwb∗∗ to adversary.(iv)Phase2: The adversary A proceeds to query oracles during Phase1. It cannot query the ciphertext and trapdoor of w0,w1.(v)Guess: If b′=b then C wins the game. The adversary A has the advantage that is(3)AdvAGame0λ=AdvACKAλ.
Game1. Let Game1 be the same game as Game0, except that the challenger chooses r1∈G1 instead of computing u=gyx. The challenger sends the ciphertext Cwb∗∗. We have AdvAGame0−AdvAGame1<AdvADODHλ, where AdvADODHλ is negligible if the DODH assumption holds.
Game2. Let Game2 be the same game as Game1, except that the challenger random chooses r1′ instead of k=H1α,wb∗. Due to r1 and r1′ are random. From adversary’s view, the ciphertext Cwb∗ of Game1 and Game2 are the identical distribution.
We have,(4)AdvAGame2λ=AdvAGame1λ.
We conclude that the adversary can only win with probability inGame2 because Cwb∗ is independent of b. Thus, the advantage,(5)AdvAGame2λ=12−12=0.
Finally, according to theGame0, Game1,Game2 we have,(6)AdvAGame2λ−AdvAIND−CKAλ≤AdvADODHλ.
whereAdvADODHλ are negligible. Therefore, the adversary A′ advantage in winning can be ignored in the IND-KGA game.Theorem 2.
Our schemeBB−PAEKSimplements IND-KGA security if the DODH assumption holds.Lemma 2.
The advantageAdvAKGAis negligible for any PPT adversaryA.Proof.
Suppose the adversary guesses the key words in the game, and the correct event is recorded asb′=b. We define games as follows:
Game0. IND-KGA is the original version of this game.(i)Setupλ: The challenger C runs Setupλ and KeyGenpp to generate the public parameter pp and public/private key pair of participants PKDS,SKDS=gymodp,y of DS, PKDR,SKDR=gxmodp,x of DR, of PKSP,SKSP=gzmodp,z of SP. Then, the challenger C sends pp,PKDS,PKDR,PKSP to the adversary A. Based on what we know so far about hash functions, we assume H1,H2,H3 and ℋ are secure and collision-resistant.(ii)Phase1: In this adaptive attack, the adversary asks PPT questions to the cipher-keyword oracle OC and the trapdoor oracle OT, and C is simulated as follows:(a)OC: Run BF.GenL,J. Compute u=gyx and k=H1u,w. Input k and w, run BF.Updℋ,BFDS,w algorithm, and output the updated bloom filter BFDS. Send the BFDS to A.(b)OT: Run BF.GenL,J. Compute u=gyx, k=H1u,w. Input k and w, run BF.Updℋ,BFDR,w algorithm, and output the updated bloom filter BFDR. Choose random J∈0,1∗, and set BFDR to 1, where J means the number of pseudo-random functions in bloom filter. Send trapdoor BFDR to A.(iii)Challenge: The adversary A selects two keywords w0∗,w1∗ and sends them to C. The challenger C picks a random bit b∈0,1, and encrypts the keyword wb∗. The trapdoor of the challenge keyword wb∗ as follows:(a)Choose a randomu=gyx and k=H1u,wb∗. RunBF.Updℋ,BFDR∗,wb∗, output BFDR∗. Choose random J∈0,1∗, and set BFDR to 1, where J means the number of pseudo-random functions in bloom filter. Finally, the challenge C sends Twb∗∗ to adversary.(iv)Phase2: Phase1 continues to be issued by the adversary A as queries to Oracles. There is only one restriction is that w0,w1 cannot be chosen for the ciphertext and trapdoor query.(v)Guess: If b′=b then C wins the game. According to the IND-KGA definition, adversary A has the advantage that is(7)AdvAGame0λ=AdvAKGAλ.
Game1. Let Game1 be the same game as Game0, except that the challenger chooses r1∈G1 instead of computing u=gyx. The challenger sends the ciphertext Cwb∗∗. We have AdvAGame0−AdvAGame1<AdvADODHλ, where AdvADODHλ is negligible if the DODH assumption holds.
Game2. Let Game2 be the same game as Game1, except that the challenger random chooses r1′ instead of k=H1u,wb∗. Due to r1 and r1′ are random, which the ciphertext Cwb∗ of Game1 and Game2 are the same distribution from adversary’s view.
We have,(8)AdvAGame2λ=AdvAGame1λ.
As we know, the adversary can only winGame2 with probability since Cwb∗ is independent of b. Thus, the advantage,(9)AdvAGame2λ=12−12=0.
Finally, according to theGame0, Game1,Game2 we have,(10)AdvAGame2λ−AdvAKGAλ≤AdvADODHλ,where AdvADODHλ are negligible. Therefore, the advantage of adversary A wins in the IND-KGA game is negligible.


## 5.3. Security

This study, adversary a is mainly aimed at the curious server. That’s because resisting external adversary can be easily solved by introducing the server public key. In other words, IKGA is mainly considered. In addition,PAKES and Trapdoor algorithms are most likely to disclose keyword information, So we focused on the analysis PAKES and Trapdoor algorithms.(i)Resistance against IKGA. In PAEKS, only the DS can generate the legal ciphertext of keyword. The adversary executes thePAEKS algorithm, it cannot generate k. Similarly, the adversary cannot generate the trapdoor of keyword. Finally, the adversary cannot obtain any information by running the Test algorithm. Thus, our scheme can resist the IKGA.(ii)Access pattern. We use DR’s public key to encrypt the file identifierindw that meets the keyword w. The SP returns the result to DR, who decrypts the file identifier information with his private key. Finally, the DR submits file identifier to SP according to his actual needs. By adding a round of communication, we ensure the privacy of the matching relationship between keywords and file identifiers. Thus, our scheme protects the access pattern of DS.(iii)Search pattern. The trapdoors of our scheme are generated randomly, that is, the trapdoors of the same keyword are different. Thus, our scheme protects the search pattern.


## 6. Comparison and Analysis

In this section, we compare our scheme with the authentication based searchable schemes (HL17 [5], QC + 20 [20], QC + 21 [21] and PL21 [41]), which are mainly focused on security comparison. Then, we count the number of different operations of other schemes and conduct an empirical performance evaluation using the Relic and GMP library.


### 6.1. Comparative Analysis of Security

A comparison of the security guarantees provided by these PAEKS schemes is shown in Table2. Reference [21] introduced the definition of fully CI-security, fullyTI-security. The mDLIN, DBDH and BDHI stand for modified Decision Linear (mDLIN) assumption, Decisional Bilinear Diffie-Hellman (DBDH) assumption and Bilinear Diffie-Hellman Inversion (BDHI) assumption respectively. The BDH and CODH stand for Bilinear DiffieHellman and Computational Oracle Diffie-Hellman. HL17 [5], QC + 20 [20], QC + 21 [21] and PL21 [41] have a common feature that they use the DR’s public key in ciphertext generation and the DR’s private key in trapdoor generation, which can naturally resist IKGA. A comparison of Table 2 shows that only our scheme has fully CI-security and fully TI-security in PAEKS. Specifically, in our scheme, the ciphertext with the same keyword is encrypted with different keys, and the trapdoor is blinded with random numbers. In their CI-security model, HL17 and PL21 still prohibited adversaries from querying cipher-keyword oracles with challenge keywords. QC + 21 and QC + 20 are fully CI-security. Trapdoors are generated by deterministic algorithms, so they are not fully TI-security. In other words, the trapdoor generation algorithm of their scheme will leak the retrieval habit. We reduce the possibility of access pattern leakage by adding a round of communication. Because the server does not know the specific index entries that meet the keyword. In addition, only our scheme also meets the result integrity verification.Table 2
Comparative security.
SchemesFully CI-securityFully TI-securityIntegrityAssumptionHL 17 [5]XXXmDLLN and DBDHQC + 20 [20]√XXBDHQC + 21 [21]√XXBDH and CODHPL21 [41]XXXBDHIOurs√√√DODH√: Schemes supporting corresponding features are supported. X: The scheme cannot support the corresponding feature.


### 6.2. Time Complexity

Table3 shows the number of operations of each algorithm. E, P, H, F denotes the operation of exponentiation, the pairing operation, hash function, pseudo-random function respectively. In the table, we disregard operations with low costs, such as normal hashing. Considering that Setup and KeyGen of different schemes have no significant difference in computational costs and the common algorithm, we only consider Encrypt/PAEKS, Trapdoor, and Test/Search algorithms. The schemes of HL17 and PL21 be slightly faster than that of QC + 20 and QC + 21, as they only calculated the hash to point operation in the keyword encryption algorithm. However, our solution is much faster than theirs. Our scheme is the fastest compared with the schemes of HL17, QC + 20, QC + 21 and PL21 in the Trapdoor algorithm, because it does not need pairing. For Test generation algorithm, our scheme requires one time inner product operation. This is almost optimal among these Test schemes.Table 3
Operations comparison of PAEKS schemes.
SchemesPAEKSTrapdoorTestHL 17 [5]3E+H3E+P+H2PQC + 20 [20]3E+P+2H2E+HH+PQC + 21 [21]3E+P+H2E+HPPL21 [41]3E+H3E+P+H2POurs3E+2HE+H2DH: denoting a hash-to-point operation. P: denoting a bilinear pairing operation. E: denoting a modular exponentiation. D: denoting a dot product.


### 6.3. Evaluation

By incorporating Relic and GMP, we are able to evaluate the effectiveness of the various schemes (HL17, QC + 20, QC + 21 and PL21). Platforms used in this experiment include Ubuntu 18.04.5 LTS with Intel (R) Xeon (R) CPU E5-2620 v4 @ 2.10 GHz and 16.00 GB of RAM. The pseudo random permutation was computed using the AES algorithm (CBC model, 128 bit key). The hash functions were computed using the SHA-256 algorithm. We choosed the real Encron e-mail Dataset (Version 20150307, about 423 MB) to demonstrate the practical performance of our proposed scheme, which contains the data from about 150 users. We choosed about 2000 keywords whose lengths are not less than 5 characters and the total number of occurrences is higher than 20. We compared our proposed scheme to HL17, QC + 20, QC + 21, PL21, with respect to ciphertext generation, trapdoor generation, and test algorithm. Furthermore, this experiment also used random keywords. We have the smallest computation costs of the five schemes based on Figures4–6. The main reason is that our scheme does not need bilinear pairing operation, which can save a lot of computing overhead. In the ciphertexts generation algorithm, Pan and Li [41] computational overhead is about 420 times that of ours. Our trapdoor generation algorithm has a computation overhead 282 times higher than Qin et al.’s [20]. In the test algorithm, Qin et al.’s [21] computational overhead is about 25 times that of ours.Figure 4
The cost of ciphertext.Figure 5
The cost of trapdoor.Figure 6
The cost of the test.


## 6.1. Comparative Analysis of Security

A comparison of the security guarantees provided by these PAEKS schemes is shown in Table2. Reference [21] introduced the definition of fully CI-security, fullyTI-security. The mDLIN, DBDH and BDHI stand for modified Decision Linear (mDLIN) assumption, Decisional Bilinear Diffie-Hellman (DBDH) assumption and Bilinear Diffie-Hellman Inversion (BDHI) assumption respectively. The BDH and CODH stand for Bilinear DiffieHellman and Computational Oracle Diffie-Hellman. HL17 [5], QC + 20 [20], QC + 21 [21] and PL21 [41] have a common feature that they use the DR’s public key in ciphertext generation and the DR’s private key in trapdoor generation, which can naturally resist IKGA. A comparison of Table 2 shows that only our scheme has fully CI-security and fully TI-security in PAEKS. Specifically, in our scheme, the ciphertext with the same keyword is encrypted with different keys, and the trapdoor is blinded with random numbers. In their CI-security model, HL17 and PL21 still prohibited adversaries from querying cipher-keyword oracles with challenge keywords. QC + 21 and QC + 20 are fully CI-security. Trapdoors are generated by deterministic algorithms, so they are not fully TI-security. In other words, the trapdoor generation algorithm of their scheme will leak the retrieval habit. We reduce the possibility of access pattern leakage by adding a round of communication. Because the server does not know the specific index entries that meet the keyword. In addition, only our scheme also meets the result integrity verification.Table 2
Comparative security.
SchemesFully CI-securityFully TI-securityIntegrityAssumptionHL 17 [5]XXXmDLLN and DBDHQC + 20 [20]√XXBDHQC + 21 [21]√XXBDH and CODHPL21 [41]XXXBDHIOurs√√√DODH√: Schemes supporting corresponding features are supported. X: The scheme cannot support the corresponding feature.


## 6.2. Time Complexity

Table3 shows the number of operations of each algorithm. E, P, H, F denotes the operation of exponentiation, the pairing operation, hash function, pseudo-random function respectively. In the table, we disregard operations with low costs, such as normal hashing. Considering that Setup and KeyGen of different schemes have no significant difference in computational costs and the common algorithm, we only consider Encrypt/PAEKS, Trapdoor, and Test/Search algorithms. The schemes of HL17 and PL21 be slightly faster than that of QC + 20 and QC + 21, as they only calculated the hash to point operation in the keyword encryption algorithm. However, our solution is much faster than theirs. Our scheme is the fastest compared with the schemes of HL17, QC + 20, QC + 21 and PL21 in the Trapdoor algorithm, because it does not need pairing. For Test generation algorithm, our scheme requires one time inner product operation. This is almost optimal among these Test schemes.Table 3
Operations comparison of PAEKS schemes.
SchemesPAEKSTrapdoorTestHL 17 [5]3E+H3E+P+H2PQC + 20 [20]3E+P+2H2E+HH+PQC + 21 [21]3E+P+H2E+HPPL21 [41]3E+H3E+P+H2POurs3E+2HE+H2DH: denoting a hash-to-point operation. P: denoting a bilinear pairing operation. E: denoting a modular exponentiation. D: denoting a dot product.


## 6.3. Evaluation

By incorporating Relic and GMP, we are able to evaluate the effectiveness of the various schemes (HL17, QC + 20, QC + 21 and PL21). Platforms used in this experiment include Ubuntu 18.04.5 LTS with Intel (R) Xeon (R) CPU E5-2620 v4 @ 2.10 GHz and 16.00 GB of RAM. The pseudo random permutation was computed using the AES algorithm (CBC model, 128 bit key). The hash functions were computed using the SHA-256 algorithm. We choosed the real Encron e-mail Dataset (Version 20150307, about 423 MB) to demonstrate the practical performance of our proposed scheme, which contains the data from about 150 users. We choosed about 2000 keywords whose lengths are not less than 5 characters and the total number of occurrences is higher than 20. We compared our proposed scheme to HL17, QC + 20, QC + 21, PL21, with respect to ciphertext generation, trapdoor generation, and test algorithm. Furthermore, this experiment also used random keywords. We have the smallest computation costs of the five schemes based on Figures4–6. The main reason is that our scheme does not need bilinear pairing operation, which can save a lot of computing overhead. In the ciphertexts generation algorithm, Pan and Li [41] computational overhead is about 420 times that of ours. Our trapdoor generation algorithm has a computation overhead 282 times higher than Qin et al.’s [20]. In the test algorithm, Qin et al.’s [21] computational overhead is about 25 times that of ours.Figure 4
The cost of ciphertext.Figure 5
The cost of trapdoor.Figure 6
The cost of the test.


## 7. Conclusion

This paper proposes a blockchain-based public key authenticated encryption with keyword search for cloud computing scheme. The scheme can not only resist the IKGA and minimize the leakage of retrieval information, but also realize the functions of multi-keyword retrieval, result integrity verification and so on. At the same time, the security analysis and theoretical analysis of BB-PAEKS are carried out. Then, we evaluate its performance by simulation experiments. The disadvantage is that our scheme uses bloom filter, which will lead to certain false positive events. However, the error rate can be reduced as much as possible by selecting appropriate parameters. Our future work will focus on the design of lightweight multi-user public key searchable encryption schemes.



---

*Source: 2309834-2022-10-15.xml*