# A Lightweight Authenticated Searchable Encryption without Bilinear Pairing for Cloud Computing

Authors: Haorui Du; Jianhua Chen; Ming Chen; Cong Peng; Debiao He
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Outsourcing data to cloud services is a good solution for users with limited computing resources. Privacy and confidentiality of data is jeopardized when data is transferred and shared in the cloud. The development of searchable cryptography offers the possibility to solve these problems. Symmetric searchable encryption (SSE) is popular among researchers because it is efficient and secure. SSE often requires the data sender and data receiver to use the same key to generate key ciphertext and trapdoor, which will obviously cause the problem of key management. Searchable encryption based on public key can simplify the key management problem. A public key encryption scheme with keyword search (PEKS) allows multiple senders to encrypt keywords under the receiver’s public key. It is vulnerable to keyword guessing attacks (KGA) due to the small size of the keywords. The proposal of public key authenticated encryption with keyword search (PAEKS) is mainly to resist inside keyword guessing attacks. The previous security models do not involve the indistinguishability of the same keywords (w0××=w1), which brings the user’s search pattern easy to leak. The essential reason is that the trapdoor generation algorithm is deterministic. At the same time, most of the existing schemes use bilinear pair design, which greatly reduces the efficiency of the scheme. To address these problems, the paper introduces an improved PAEKS model. We design a lightweight public key authentication encryption scheme based on the Diffie-Hellman protocol. Then, we prove the ciphertext indistinguishability security and trapdoor indistinguishability security of the scheme in the improved security model. Finally, the paper demonstrates its comparable security and computational efficiency by comparing it with previous PAEKS schemes. Meanwhile, we conduct an experimental evaluation based on the cryptographic library. Experimental results show that the computational overhead of our scheme compared with the ciphertext generation algorithm, trapdoor generation algorithm and test algorithm of other schemes Our scheme reduces 274, 158 and 60 times, respectively.


---

## Body

## 1. Introduction

It has become increasingly important and popular to use cloud storage services due to the rapid development of cloud computing. Based on the characteristics of high efficiency and low cost, cloud computing has attracted great attention from academia and industry. Users are able to upload their own data such as text, audio, and video. It can not only save their own local storage costs but also facilitate data access at any time. In addition, cloud storage services provide the ability to share data. Since cloud servers are not fully trusted, they are likely to be bribed by third parties through other means, which makes the transfer and storage of plaintext data a privacy breach. The data owner is not in direct management and control of the data. How to ensure the security and privacy of data during data sharing is the first challenge encountered in cloud server storage.Encrypting sensitive data before sending it to a cloud server is the most natural method. In the case where the ciphertext is saved directly to the cloud server, finding a specific file from among hundreds or thousands of encrypted files becomes challenging. Cloud storage is the most convenient way for users to download and decrypt all their files, and then locate the needed files or data from the plaintext obtained. Considering the high communication overhead between users and cloud storage, and the processing costs to decrypt data from user-owned devices, this solution is clearly unrealistic. It would be ideal if the cloud server would search for ciphertext data based on requirements of each user, then return the matching ciphertext data, and then the user would decrypt it. To solve the above problems, searchable encryptions (SE) are proposed.Symmetric searchable encryption (SSE) and public key searchable encryption (PEKS) are two types of searchable encryption. In 2004, Boneh et al. [1] were the first to study the search problem of data encrypted by the public key system. Any data sender (DS) can use the public key of the data receiver to encrypt keywords. The data receiver (DR) can generate a trapdoor and send it to the server through a secure channel to search the encrypted data. They also discussed the relationship between PEKS and identity based encryption (IBE) and pointed out that PEKS scheme with semantic security under adaptive keyword selection attack contains IBE scheme with IND-ID-CCA security [2].It was Byun et al. [3] who observed the keyword space was very small compared to the key space, which discovered that offline keyword attacks are possible and successfully thwarted Boneh’s scheme. The adversary could intercept the trapdoor and could perform unlimited trapdoor tests, which allowed keyword guessing attacks to succeed. This enables external attacks to be prevented from being launched by the adversary by protecting the trapdoor from being leaked, e.g. a secure method is achieved by establishing a secure communication channel between the recipient and the server, where only the server can access the trapdoor. Thus, its security can be ensured. Another solution idea is by limiting the testing capability of the adversary. That is, by specifying the PEKS of the tester. However, both methods do not work against malicious servers. How to resist malicious servers is another problem solved by PEKS.Huang and Li [4] introduced authentication techniques in PEKS, namely Public Key Authentication Encryption with Keyword Search (PAEKS) to resist malicious server attacks. In PAEKS, DS encrypted and authenticated keywords, and trapdoors can only be generated by legitimate recipients, which prevented adversaries from performing brute force tests. It was not until Qin et al. [5] that the PAEKS model was brought into question as [4] was unable to capture a real threat. In this scenario, the outsider choses multiciphertext attacks, i.e. determining if two encrypted files share some keywords. The PAEKS scheme Pan and Li [6] proposed follows scheme [5], achieving multiciphertext indistinguishability (MCI-security) and multitrapdoor indistinguishability (MTI-security) with high computational complexity. A security flaw was discovered soon after Qin et al. [7] spotted the scheme [6]. Their ciphertext indistinguishability security (CI-security) models all fail to be resistant to the fully selected keyword attack.


### 1.1. Motivation and Contributions

This study is motivated by the algorithm proposed by Qin et al. [7] and their analysis of the security system of PAEKS. In their analysis of keyword guessing attacks, [7] pointed out that most schemes often take into account the indistinguishability of ciphertext, i.e., the semantic security of the selected keywords. In other words, if the adversary does not get the trapdoor that challenges the keywords w0 and w1, it only requires the adversary to distinguish between the keyword w0 encryption or w1 encryption. In light of the following basic fact, Qin considered that a document usually contained multiple keywords, and the same keyword may appear several times.Therefore, [7] reconsidered the ciphertext indistinguishability security model of PAEKS, which is multiciphertext indistinguishability. It is worth noting that adversaries can ask for ciphertext for any keyword, including challenging keywords. This means if the model can resist an attack that involves fully selected keywords; it can protect the user’s access pattern. However, [7] only considers the security of full ciphertext, not the security of full trapdoor. Trapdoor generation algorithm is a deterministic encryption algorithm in [7]. A malicious adversary can accurately record how often a user searches for different trapdoors, thus providing insight into his search pattern. In that case, the search pattern of users must be protected. In addition, most of the existing PAEKS schemes are constructed based on bilinear mapping. The result is high computing overhead for the client side and poor practicability. We need to design a lightweight PAEKS scheme for lightweight computing devices in order to better promote the application.
(i)
Firstly, we discuss different types of adversary capabilities, analyze the security of the PAEKS scheme, and describe the security model of the hidden matching relationship(ii)
Secondly, we design a PAEKS scheme without bilinear pairing. Our scheme satisfies both trapdoor indistinguishability and ciphertext indistinguishability before the cloud server runs the test algorithm. In other words, our base scheme protects the user’s search pattern and access pattern against adversariesType-II(iii)
Finally, we provide an extended keyword approach that hides the matching relationship between keyword ciphertexts and trapdoors after the cloud service executes the test algorithm against adversaries Type-III. We analyze the security and efficiency comparison


### 1.2. Organization

In section2, contains a review of related works. Preliminary cryptographic notations and definitions are presented in section 3. We analyze previous PAEKS schemes in section 4. We present the PAEKS scheme and a searchable encryption scheme derived from it in section 5. In section 6, we present the security proof of the scheme. In section 7, we present our time consumption comparison with others. Lastly, we present our conclusions in section 8.


## 1.1. Motivation and Contributions

This study is motivated by the algorithm proposed by Qin et al. [7] and their analysis of the security system of PAEKS. In their analysis of keyword guessing attacks, [7] pointed out that most schemes often take into account the indistinguishability of ciphertext, i.e., the semantic security of the selected keywords. In other words, if the adversary does not get the trapdoor that challenges the keywords w0 and w1, it only requires the adversary to distinguish between the keyword w0 encryption or w1 encryption. In light of the following basic fact, Qin considered that a document usually contained multiple keywords, and the same keyword may appear several times.Therefore, [7] reconsidered the ciphertext indistinguishability security model of PAEKS, which is multiciphertext indistinguishability. It is worth noting that adversaries can ask for ciphertext for any keyword, including challenging keywords. This means if the model can resist an attack that involves fully selected keywords; it can protect the user’s access pattern. However, [7] only considers the security of full ciphertext, not the security of full trapdoor. Trapdoor generation algorithm is a deterministic encryption algorithm in [7]. A malicious adversary can accurately record how often a user searches for different trapdoors, thus providing insight into his search pattern. In that case, the search pattern of users must be protected. In addition, most of the existing PAEKS schemes are constructed based on bilinear mapping. The result is high computing overhead for the client side and poor practicability. We need to design a lightweight PAEKS scheme for lightweight computing devices in order to better promote the application.
(i)
Firstly, we discuss different types of adversary capabilities, analyze the security of the PAEKS scheme, and describe the security model of the hidden matching relationship(ii)
Secondly, we design a PAEKS scheme without bilinear pairing. Our scheme satisfies both trapdoor indistinguishability and ciphertext indistinguishability before the cloud server runs the test algorithm. In other words, our base scheme protects the user’s search pattern and access pattern against adversariesType-II(iii)
Finally, we provide an extended keyword approach that hides the matching relationship between keyword ciphertexts and trapdoors after the cloud service executes the test algorithm against adversaries Type-III. We analyze the security and efficiency comparison


## 1.2. Organization

In section2, contains a review of related works. Preliminary cryptographic notations and definitions are presented in section 3. We analyze previous PAEKS schemes in section 4. We present the PAEKS scheme and a searchable encryption scheme derived from it in section 5. In section 6, we present the security proof of the scheme. In section 7, we present our time consumption comparison with others. Lastly, we present our conclusions in section 8.


## 2. Related Works

The KGA is a serious concern for public key searchable encryption. It is shown that one of the main reasons the keyword will be attacked by an adversary under KGA if the keyword space is in a polynomial size. In the literature, there have been some attempts to implement IKGA security. Xu et al. [8] proposed Public Key Encryption for Fuzzy Keyword Search (PEFKS), where each keyword corresponds to an exact keyword search trapdoor and a fuzzy keyword search trapdoor. The keyword space of PEFKS was very small, but malicious parties were also unable to learn accurate keywords. Later, Chen et al. [9] pointed out that in [8] the server cannot accurately guess the keyword. As long as it knows which small set the basic keyword belongs to, it cannot protect the keyword privacy very well. [9] analyzed another main reason for keyword guessing attacks.The vulnerability is caused by the fact that anyone with knowledge of an external receiver’s public key can generate the PEKS ciphertext of any keyword. A malicious server may select a guess keyword when presented with a trapdoor, and then use it to generate ciphertext using PEKS. Then the server can guess whether the keyword hidden under the trapdoor is the right keyword until the correct keyword is found. As long as the two servers do not collide, [9] proposed a method for preventing attacks using dual-server public key encryption with keyword search. Sun et al. [10] took into account the fact that the server was malicious, and they explored whether a PEKS scheme against inside KGA can be built based on different public key cryptosystems, such as PKI based, identity-based, or certificateless cryptosystem. In order to improve the scheme’s efficiency, the researchers proposed a construction of PAEKS based on word-independent smooth projective hash functions (SPHFs) and PEKS [11–19].Combining attribute-based encryption (ABE) and searchable encryption (SE), a fine-grained search scheme is obtained. This combination leads to the development of SE schemes suitable for multiuser scenarios. The ciphertext is linked to the access policy in ciphertext-policy of ABE (CP-ABE), and the user’s key is associated with a set of attributes. Therefore, searchable scheme based on attribute encryption can resist IKGA, which mainly depends on the security of attribute encryption. Zheng et al. [20] developed the first fine-grained searchable encryption scheme by using both the variants of CP-ABE. In order to reduce the amount of calculation, efforts had been made in some schemes [21–23]. Schemes [24–28] tried to reduce the storage and calculation cost of keyword ciphertext, key and search token. In this paper, we mainly improve the computational efficiency and retrieval efficiency of key ciphertext and trapdoor in the smallest basic unit of searchable encryption structure, that is, only two parties share data. If we study the most basic units clearly, it will promote multiuser scenario.


## 3. Preliminaries

In this section, we introduce some basic concepts of cryptography, the definition of schemes, security models, threat models, and design goals.


### 3.1. Notations

The notations are described in Table1.Table 1
BRIEF SYNTHESIS OF NOTATIONS.
SymbolDescriptionG1The cyclic groupgThe generator ofG1H1,H2Hash functionPK,SKPublic and private keys of each participantsWThe keywords spaceIDwTheIDs of documents containing wapwSet of fileIDs containing the keyword wQSet ofq queryi,wi denotes the timestamp of a-query


### 3.2. Pattern Leakage

The setQ is a q-query set consisting of pairs i,w, with i representing the timestamp of a query and w representing a keyword. The access pattern [29] is as follows:
(i)
Access pattern. Documents containing a given keyword appear in the search results. The access pattern is defined asapw=IDw for quering keyword w, where IDw denotes the IDs of documents containing w(ii)
Search pattern. It shows the links between particular keywords and search queries. Its search pattern is defined asspw=ii,w∈Q for quering keyword w,.


### 3.3. 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 Figure1(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 numbersFigure 1
Inverted index.
(a)
Extract keywords from files(b)
Index matrix


### 3.4. The Adversary Attack Capability

Here we divide the adversary capabilities into 3 Types.(i)
Type-I: The adversary collects some the ciphertext and trapdoor of keywords, and they do not know the correspondence between ciphertext and plaintext(ii)
Type-II: The adversary collects all the ciphertext and part of the trapdoor of the keyword submitted by the data receiver, and only knows part of the matching relationship between the submitted trapdoor and the ciphertext. It is worth noting that the adversary does not know the matching relationship between the trapdoor being challenged and the ciphertext(iii)
Type-III: The adversary stores all the ciphertexts of keywords and all the trapdoors submitted by the data receiver, and knows the matching relationship between all the trapdoors and ciphertexts, including the trapdoors that challenge keywords


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

Computational Diffie-Hellman assumption (CDH): letG be a cyclic group, which has a prime order q, and Pi be a generator of G1. Given the tuple (Pi, aPi, bPi) E Gi, R where a, b-Z, there is no probabilistic polynomial time (PPT) algorithm to get abP, E Gj. We define the advantage.LetG is a cyclic group, which has a prime order p, and g be generator of G. We get two elements ga and gb from G. The gab needs to be calculated. CDH is hard to solve in the G


### 3.6. The Hash Diffie-Hellman Assumption (HDH)

G is a cyclic group. Its order is p. The generator is g. Given H:0,1∗⟶0,1hLen be a security cryptographic hash function. The advantage of A is negligible for a polynomial adversary A. The advantage is AdvAHDHλ=PrAg,ga,gb,R=1−PrAg,ga,gb,Hgab=1, where a,b∈Zp,R∈0,1hLen


### 3.7. The Definition of PAEKS

A PAEKS scheme includes five polynomial algorithms, which are Setup, KeyGen, PAEKS, Trapdoor, and Test. The specific construction is described as follows:(i)
pp⟵Setupλ: it is an algorithm for generating global parameters. Input a security parameter λ, and outputs a global public parameter pp(ii)
PK,SK⟵KeyGen(pp): providing participants with a public/private key pair is its responsibility
(a)
PKS,SKS⟵KeyGenpp: it is sender’s key generation algorithm. Input pp, and generates public and private key PKS,SKS(b)
PKR,SKR⟵KeyGenpp: the receiver generates keys with this algorithm. Input pp, and generates public and private key PKR,SKR(c)
PKCS,SKCS⟵KeyGenpp: this is the algorithm used by the cloud server to generate keys. Input pp, and generates public and private key PKCS,SKCS.(iii)
Cw⟵PAEKS(SKS,PKR,PKS,w): the DS performs the operation. Input SKS,PKR,PKS,w, and returns corresponding ciphertext Cw(iv)
Tw′⟵Trapdoor(SKR,PKR,PKS,PKCS,w′): The procedure is performed by DR. Input SKR,PKR,PKS,PKCS,w′, and returns corresponding trapdoor Tw′(v)
0/1⟵Test(PKR,PKS,SKCS,Cw,Tw): the cloud server manages the process. Input PKR,PKS,SKCS,Cw,Tw′. If w′∈W, outputs 1; else, outputs 0Correctness: givenCw and Tw′, and we formulate consistency as follows:Ifw=w′, PrTestSKCS,PKR,PKS,Cw,Tw′=1=1


### 3.8. System Model

The system includes the following parties: Cloud Server (CS), Data Sender (DS), and Data Receivers (DR) as depicted in Figure2.
(i)
Data Sender (DS): The DS produces his own public key and private key upon inputting the security parameter. Moreover, DS extracts keywords from files, and generates index matrix, and computes the searchable keywords ciphertexts. Finally, the DS stores ciphertexts on the CS(ii)
Data Receiver (DR): Request Users utilize targeted keywords to generate search trapdoors and send them to the CS(iii)
Cloud sever (CS): The Cloud Server has almost unlimited storage and computing power in the PAEKS system. The CS is in charge of storing searchable ciphertexts received from DS. Then, the CS addresses search queries and returns corresponding searching results ciphertexts to DRFigure 2
The system model of PAEKS.


### 3.9. Threat Model

In this paper, it supposes that DS honestly follow the PAEKS algorithm to produce searchable ciphertexts for DO. DR honestly follows the Trapdoor algorithm to produce trapdoor. The CS is supposed to be honest and curious, who will honestly perform Test algorithm, and is interested in query results and frequency information of ciphertext.


### 3.10. The Security Models of PAEKS

As part of PAEKS semantic security model, there is fully cipher-keyword indistinguishability (Fully CI-security) and fully trapdoor indistinguishability (Fully TI-security). Our fully CI-security and fully TI-security model is the same as [4, 5, 7] in settings. In addition, we propose that a PAEKS scheme for adversary Type-II, which should also meet the security of hiding its matching relationship. ie the matching relationship security model of Hidden Ciphertext and Trapdoor (HMR-security).


### 3.11. Fully CI-Security Model

(i)
Given adversaryA and the security parameter λ(ii)
Initialization. The challenger C firstly runs the algorithm Setupλ to generate the system parameter pp. C runs KeyGenpp to generate DS’s key pairs PKS,SKS, DR’s key pairs PKR,SKR and CS’s key pairs PKCS,PKCS, respectively. C gives pp, PKS,PKR and PKCS to A(iii)
Phase 1.A asks for polynomial oracle OC and OT(iv)
Challenge. After Phase 1, outputs w0∗ and w1∗. C picks a coin b∈0,1. Sends Cwb∗ to A(v)
Phase 2.A can remain to query the oracles as Phase1(vi)
Guess. Finally, A returns a bit b′∈0,1 as the guess of bA wins in the above game if he guesses b′=b. The advantage of A winning this game is defined as
(i)
(1)AdvAIND−CIλ=Prb′=b−12.Definition 1 (Fully CI-Security).
A PAEKS scheme satisfies cipher-keyword indistinguishable against chosen keywords attacks if the advantageAdvAIND−CIλ of succeeding in the above game is negligible for any polynomial A.


### 3.12. Fully TI-Security Model

(i)
Given adversaryA and security parameter λ(ii)
Initialization.C firstly performs Setupλ to generate parameter pp. Then, C runs KeyGenpp to generate DS’s key pairs PKS,SKS, data receiver’s key pairs PKR,SKR and cloud sever’s key pairs PKCS,PKCS, respectively. C gives pp and PKS,PKR and PKCS to A(iii)
Phase 1.A adaptively asks C queries on OC and OT, and gets ciphertext and trapdoor of query keywords(iv)
Challenge. After Phase 1, it outputs w0∗ and w1∗ with the restriction that w0∗ and w1∗ never be queried on oracle OC and OT by A in Phase 1. Then, C picks a coin b∈0,1 and sends the trapdoor keyword Twb∗ to A(v)
Phase 2. As Phase 1, A can continue to query the oracles(vi)
Guess. Finally, A returns a bit b′∈0,1 as the guess of b and wins the game if b′=bThe adversaryA wins in the above game if he guesses b′=b. The advantage of A winning this game is defined as
(2)AdvAIND−TIλ=Prb′=b−12.Definition 2 (Fully TI-Security).
A PAEKS scheme satisfies trapdoor indistinguishability against chosen keywords attacks if for any PPT adversaryA, the advantage AdvAIND−TIλ of succeeding in the above game is negligible.


### 3.13. HMR-Security Model

LetA be an adversary and λ be the security parameter.
(i)
Initialization.C first runs the algorithm Setupλ to generate the system parameter pp. Then, it runs KeyGenpp to generate DS’s key pairs PKS,SKS, DR’s key pairs PKR,SKR and CS’s key pairs PKCS,PKCS, respectively. C gives parameters pp, PKS,PKR and PKCS to A(ii)
Phase 1. In this approach, A asks PPT queries on the cipher-keyword, trapdoor, and test oracles, and then receives cipher and trapdoor responses to the query keywords and test results, as follows:(a)
C runs PAKESPKR,SKS,w for any keyword w, and sends Cw to A(b)
C runs TrapdoorPKS,SKR,PKCS,w′ for any keyword w′, and sends Tw′ to A(c)
For any the cipherCw and trapdoor Tw′ of keyword w and w′, C runs TestSKCS,PKR,Cw,Tw′, and if w′=w, outputs 1; else, outputs 0(iii)
Challenge. After Phase 1, it outputs two challenge keywords w0∗ and w1∗. Then, C picks a coin b∈0,1 and d∈0,1. Sends Cwb∗ and Twd∗ to A(iv)
Phase 2.A can continue to query the oracles as Phase 1. But cannot query OC and OT with w0∗ and w1∗(v)
Guess. Finally, A returns two bit b′,d′∈0,1 as the guess of b,dA wins in the above game if he guesses b′=b and d′=d. The advantage of A winning this game is defined as
(3)AdvAHMRλ=Prb′=b∧d′=d−12.Definition 3 (HMR-Security).
A PAEKS scheme satisfies matching relationship security model of Hidden Ciphertext and Trapdoor (HMR-security) if the advantageAdvAHMRλ succeeding in the above game is negligible for any polynomial A.


### 3.14. Design Goals

Our goal is to design an efficient PAEKS scheme, which can resist external keyword guessing attack and internal keyword guessing attack, and prevent the leakage of search and access pattern for adversary Type-II.


## 3.1. Notations

The notations are described in Table1.Table 1
BRIEF SYNTHESIS OF NOTATIONS.
SymbolDescriptionG1The cyclic groupgThe generator ofG1H1,H2Hash functionPK,SKPublic and private keys of each participantsWThe keywords spaceIDwTheIDs of documents containing wapwSet of fileIDs containing the keyword wQSet ofq queryi,wi denotes the timestamp of a-query


## 3.2. Pattern Leakage

The setQ is a q-query set consisting of pairs i,w, with i representing the timestamp of a query and w representing a keyword. The access pattern [29] is as follows:
(i)
Access pattern. Documents containing a given keyword appear in the search results. The access pattern is defined asapw=IDw for quering keyword w, where IDw denotes the IDs of documents containing w(ii)
Search pattern. It shows the links between particular keywords and search queries. Its search pattern is defined asspw=ii,w∈Q for quering keyword w,.


## 3.3. 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 Figure1(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 numbersFigure 1
Inverted index.
(a)
Extract keywords from files(b)
Index matrix


## 3.4. The Adversary Attack Capability

Here we divide the adversary capabilities into 3 Types.(i)
Type-I: The adversary collects some the ciphertext and trapdoor of keywords, and they do not know the correspondence between ciphertext and plaintext(ii)
Type-II: The adversary collects all the ciphertext and part of the trapdoor of the keyword submitted by the data receiver, and only knows part of the matching relationship between the submitted trapdoor and the ciphertext. It is worth noting that the adversary does not know the matching relationship between the trapdoor being challenged and the ciphertext(iii)
Type-III: The adversary stores all the ciphertexts of keywords and all the trapdoors submitted by the data receiver, and knows the matching relationship between all the trapdoors and ciphertexts, including the trapdoors that challenge keywords


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

Computational Diffie-Hellman assumption (CDH): letG be a cyclic group, which has a prime order q, and Pi be a generator of G1. Given the tuple (Pi, aPi, bPi) E Gi, R where a, b-Z, there is no probabilistic polynomial time (PPT) algorithm to get abP, E Gj. We define the advantage.LetG is a cyclic group, which has a prime order p, and g be generator of G. We get two elements ga and gb from G. The gab needs to be calculated. CDH is hard to solve in the G


## 3.6. The Hash Diffie-Hellman Assumption (HDH)

G is a cyclic group. Its order is p. The generator is g. Given H:0,1∗⟶0,1hLen be a security cryptographic hash function. The advantage of A is negligible for a polynomial adversary A. The advantage is AdvAHDHλ=PrAg,ga,gb,R=1−PrAg,ga,gb,Hgab=1, where a,b∈Zp,R∈0,1hLen


## 3.7. The Definition of PAEKS

A PAEKS scheme includes five polynomial algorithms, which are Setup, KeyGen, PAEKS, Trapdoor, and Test. The specific construction is described as follows:(i)
pp⟵Setupλ: it is an algorithm for generating global parameters. Input a security parameter λ, and outputs a global public parameter pp(ii)
PK,SK⟵KeyGen(pp): providing participants with a public/private key pair is its responsibility
(a)
PKS,SKS⟵KeyGenpp: it is sender’s key generation algorithm. Input pp, and generates public and private key PKS,SKS(b)
PKR,SKR⟵KeyGenpp: the receiver generates keys with this algorithm. Input pp, and generates public and private key PKR,SKR(c)
PKCS,SKCS⟵KeyGenpp: this is the algorithm used by the cloud server to generate keys. Input pp, and generates public and private key PKCS,SKCS.(iii)
Cw⟵PAEKS(SKS,PKR,PKS,w): the DS performs the operation. Input SKS,PKR,PKS,w, and returns corresponding ciphertext Cw(iv)
Tw′⟵Trapdoor(SKR,PKR,PKS,PKCS,w′): The procedure is performed by DR. Input SKR,PKR,PKS,PKCS,w′, and returns corresponding trapdoor Tw′(v)
0/1⟵Test(PKR,PKS,SKCS,Cw,Tw): the cloud server manages the process. Input PKR,PKS,SKCS,Cw,Tw′. If w′∈W, outputs 1; else, outputs 0Correctness: givenCw and Tw′, and we formulate consistency as follows:Ifw=w′, PrTestSKCS,PKR,PKS,Cw,Tw′=1=1


## 3.8. System Model

The system includes the following parties: Cloud Server (CS), Data Sender (DS), and Data Receivers (DR) as depicted in Figure2.
(i)
Data Sender (DS): The DS produces his own public key and private key upon inputting the security parameter. Moreover, DS extracts keywords from files, and generates index matrix, and computes the searchable keywords ciphertexts. Finally, the DS stores ciphertexts on the CS(ii)
Data Receiver (DR): Request Users utilize targeted keywords to generate search trapdoors and send them to the CS(iii)
Cloud sever (CS): The Cloud Server has almost unlimited storage and computing power in the PAEKS system. The CS is in charge of storing searchable ciphertexts received from DS. Then, the CS addresses search queries and returns corresponding searching results ciphertexts to DRFigure 2
The system model of PAEKS.


## 3.9. Threat Model

In this paper, it supposes that DS honestly follow the PAEKS algorithm to produce searchable ciphertexts for DO. DR honestly follows the Trapdoor algorithm to produce trapdoor. The CS is supposed to be honest and curious, who will honestly perform Test algorithm, and is interested in query results and frequency information of ciphertext.


## 3.10. The Security Models of PAEKS

As part of PAEKS semantic security model, there is fully cipher-keyword indistinguishability (Fully CI-security) and fully trapdoor indistinguishability (Fully TI-security). Our fully CI-security and fully TI-security model is the same as [4, 5, 7] in settings. In addition, we propose that a PAEKS scheme for adversary Type-II, which should also meet the security of hiding its matching relationship. ie the matching relationship security model of Hidden Ciphertext and Trapdoor (HMR-security).


## 3.11. Fully CI-Security Model

(i)
Given adversaryA and the security parameter λ(ii)
Initialization. The challenger C firstly runs the algorithm Setupλ to generate the system parameter pp. C runs KeyGenpp to generate DS’s key pairs PKS,SKS, DR’s key pairs PKR,SKR and CS’s key pairs PKCS,PKCS, respectively. C gives pp, PKS,PKR and PKCS to A(iii)
Phase 1.A asks for polynomial oracle OC and OT(iv)
Challenge. After Phase 1, outputs w0∗ and w1∗. C picks a coin b∈0,1. Sends Cwb∗ to A(v)
Phase 2.A can remain to query the oracles as Phase1(vi)
Guess. Finally, A returns a bit b′∈0,1 as the guess of bA wins in the above game if he guesses b′=b. The advantage of A winning this game is defined as
(i)
(1)AdvAIND−CIλ=Prb′=b−12.Definition 1 (Fully CI-Security).
A PAEKS scheme satisfies cipher-keyword indistinguishable against chosen keywords attacks if the advantageAdvAIND−CIλ of succeeding in the above game is negligible for any polynomial A.


## 3.12. Fully TI-Security Model

(i)
Given adversaryA and security parameter λ(ii)
Initialization.C firstly performs Setupλ to generate parameter pp. Then, C runs KeyGenpp to generate DS’s key pairs PKS,SKS, data receiver’s key pairs PKR,SKR and cloud sever’s key pairs PKCS,PKCS, respectively. C gives pp and PKS,PKR and PKCS to A(iii)
Phase 1.A adaptively asks C queries on OC and OT, and gets ciphertext and trapdoor of query keywords(iv)
Challenge. After Phase 1, it outputs w0∗ and w1∗ with the restriction that w0∗ and w1∗ never be queried on oracle OC and OT by A in Phase 1. Then, C picks a coin b∈0,1 and sends the trapdoor keyword Twb∗ to A(v)
Phase 2. As Phase 1, A can continue to query the oracles(vi)
Guess. Finally, A returns a bit b′∈0,1 as the guess of b and wins the game if b′=bThe adversaryA wins in the above game if he guesses b′=b. The advantage of A winning this game is defined as
(2)AdvAIND−TIλ=Prb′=b−12.Definition 2 (Fully TI-Security).
A PAEKS scheme satisfies trapdoor indistinguishability against chosen keywords attacks if for any PPT adversaryA, the advantage AdvAIND−TIλ of succeeding in the above game is negligible.


## 3.13. HMR-Security Model

LetA be an adversary and λ be the security parameter.
(i)
Initialization.C first runs the algorithm Setupλ to generate the system parameter pp. Then, it runs KeyGenpp to generate DS’s key pairs PKS,SKS, DR’s key pairs PKR,SKR and CS’s key pairs PKCS,PKCS, respectively. C gives parameters pp, PKS,PKR and PKCS to A(ii)
Phase 1. In this approach, A asks PPT queries on the cipher-keyword, trapdoor, and test oracles, and then receives cipher and trapdoor responses to the query keywords and test results, as follows:(a)
C runs PAKESPKR,SKS,w for any keyword w, and sends Cw to A(b)
C runs TrapdoorPKS,SKR,PKCS,w′ for any keyword w′, and sends Tw′ to A(c)
For any the cipherCw and trapdoor Tw′ of keyword w and w′, C runs TestSKCS,PKR,Cw,Tw′, and if w′=w, outputs 1; else, outputs 0(iii)
Challenge. After Phase 1, it outputs two challenge keywords w0∗ and w1∗. Then, C picks a coin b∈0,1 and d∈0,1. Sends Cwb∗ and Twd∗ to A(iv)
Phase 2.A can continue to query the oracles as Phase 1. But cannot query OC and OT with w0∗ and w1∗(v)
Guess. Finally, A returns two bit b′,d′∈0,1 as the guess of b,dA wins in the above game if he guesses b′=b and d′=d. The advantage of A winning this game is defined as
(3)AdvAHMRλ=Prb′=b∧d′=d−12.Definition 3 (HMR-Security).
A PAEKS scheme satisfies matching relationship security model of Hidden Ciphertext and Trapdoor (HMR-security) if the advantageAdvAHMRλ succeeding in the above game is negligible for any polynomial A.


## 3.14. Design Goals

Our goal is to design an efficient PAEKS scheme, which can resist external keyword guessing attack and internal keyword guessing attack, and prevent the leakage of search and access pattern for adversary Type-II.


## 4. Previous PAEKS Schemes

In this section, we firstly analyze the relationship between keyword ciphertext indistinguishability and access pattern and the relationship between trapdoor indistinguishability and search pattern. Secondly, it analyzes whether the previous PAEKS really meet the indistinguishability of ciphertext and trapdoors for external enemies and malicious servers. Finally, we give suggestions and methods for adversary with different abilities.


### 4.1. Why Should we Define the Indistinguishability of Cipher and Trapdoor of Keywords?

(i)
TI-Security and Search Pattern. It is well known that the disclosure of search pattern will reflect users’ search habits. If the PAEKS scheme does not meet the indistinguishability of trapdoors, trapdoors for the same keyword are the same. This allows the adversary to classify the keywords through the trapdoor, thus revealing the user’s search pattern. It can be seen that if the trapdoor does not meet the indistinguishable properties, the user’s search pattern will be divulged. The adversary can accurately guess the keywords by combining some a priori knowledge(ii)
CI-Security and Access Pattern. Access pattern disclosure will reflect the data file information matching keywords, such as the frequency of different keywords and documents. If the PAEKS scheme does not meet the indistinguishability of keyword ciphertext, the ciphertext of the same keyword is the same. Therefore, the adversary can guess the keywords through the matched file information and prior knowledgeBased on the above analysis, we believe that PAEKS should meet at least the above two points to be considered secure if we want to achieve the purpose of search and access pattern without being compromised.


### 4.2. Security Analysis of Previous PAEKS Schemes

We discuss the close relationship between indistinguishable ciphertext and indistinguishable trapdoor from the following three aspects for different types of adversaries.(i)
CI-Security and Not TI-Security. If the ciphertext of the keyword in PAEKS meets the indistinguishability, the trapdoor is discontent the indistinguishability, as shown in Figure 3(a). Three different ciphertexts of keyword w1 are represented by ellipsoids of three different colors. We can see that the ciphertext C1,C2,andC3 are indistinguishable. The trapdoor does not satisfy indistinguishability. If the adversary obtains trapdoor T1, after testing the algorithm, he can understand that C1,C2, and C3 are the ciphertext of the same keyword, which the indistinguishability of the ciphertext loses its function. The access pattern will be compromised. Therefore, this Test algorithm plays a key role in above process. It is worth noting that this also provides an idea for us to solve the problem of access pattern disclosure(ii)
Not CI-Security and TI-Security. As shown in Figure 3(b), three boxes with different colors indicate that the three trapdoors T1,T2,T3, for the keyword w1 are different. So, it meets the indistinguishability of trapdoor. C1 does not satisfy the indistinguishability of ciphertext. If the adversary obtains ciphertext C1, after testing the algorithm, he can understand that T1,T2,T3 is the trapdoor of the same keyword, which makes the user’s search pattern leak(iii)
CI-Security and TI-Security. As shown in Figure 3(c), combined with Figures 3(a) and 3(b) analysis, the adversary can also get relevant information. To be specific, if the adversary gets T1, the matching ciphertext is C1,C2,C3. Similarly, for T2,T3, the matching ciphertext is C1,C2,C3. The adversary can know that T1,T2,andT3 are trapdoors with the same keyword. The solution is the same as aboveFigure 3
Matching relationship.
(a)(b)(c)(d)Based on the study above, for adversary Type-I and Type-II, we can solve the problem of access pattern and search pattern disclosure by specifying an honest server. However, if it is the adversary Type-III, the existing schemes do not protect their privacy from the perspective of access pattern and search pattern [4–7]. In other words, none of them can resist leakage abuse attacks [30]. One possible solution is to store data distributed on servers so that statistics are not completely compromised if there is an honest server. Next, for the adversary Type-III, we will solve this problem from another angle.


## 4.1. Why Should we Define the Indistinguishability of Cipher and Trapdoor of Keywords?

(i)
TI-Security and Search Pattern. It is well known that the disclosure of search pattern will reflect users’ search habits. If the PAEKS scheme does not meet the indistinguishability of trapdoors, trapdoors for the same keyword are the same. This allows the adversary to classify the keywords through the trapdoor, thus revealing the user’s search pattern. It can be seen that if the trapdoor does not meet the indistinguishable properties, the user’s search pattern will be divulged. The adversary can accurately guess the keywords by combining some a priori knowledge(ii)
CI-Security and Access Pattern. Access pattern disclosure will reflect the data file information matching keywords, such as the frequency of different keywords and documents. If the PAEKS scheme does not meet the indistinguishability of keyword ciphertext, the ciphertext of the same keyword is the same. Therefore, the adversary can guess the keywords through the matched file information and prior knowledgeBased on the above analysis, we believe that PAEKS should meet at least the above two points to be considered secure if we want to achieve the purpose of search and access pattern without being compromised.


## 4.2. Security Analysis of Previous PAEKS Schemes

We discuss the close relationship between indistinguishable ciphertext and indistinguishable trapdoor from the following three aspects for different types of adversaries.(i)
CI-Security and Not TI-Security. If the ciphertext of the keyword in PAEKS meets the indistinguishability, the trapdoor is discontent the indistinguishability, as shown in Figure 3(a). Three different ciphertexts of keyword w1 are represented by ellipsoids of three different colors. We can see that the ciphertext C1,C2,andC3 are indistinguishable. The trapdoor does not satisfy indistinguishability. If the adversary obtains trapdoor T1, after testing the algorithm, he can understand that C1,C2, and C3 are the ciphertext of the same keyword, which the indistinguishability of the ciphertext loses its function. The access pattern will be compromised. Therefore, this Test algorithm plays a key role in above process. It is worth noting that this also provides an idea for us to solve the problem of access pattern disclosure(ii)
Not CI-Security and TI-Security. As shown in Figure 3(b), three boxes with different colors indicate that the three trapdoors T1,T2,T3, for the keyword w1 are different. So, it meets the indistinguishability of trapdoor. C1 does not satisfy the indistinguishability of ciphertext. If the adversary obtains ciphertext C1, after testing the algorithm, he can understand that T1,T2,T3 is the trapdoor of the same keyword, which makes the user’s search pattern leak(iii)
CI-Security and TI-Security. As shown in Figure 3(c), combined with Figures 3(a) and 3(b) analysis, the adversary can also get relevant information. To be specific, if the adversary gets T1, the matching ciphertext is C1,C2,C3. Similarly, for T2,T3, the matching ciphertext is C1,C2,C3. The adversary can know that T1,T2,andT3 are trapdoors with the same keyword. The solution is the same as aboveFigure 3
Matching relationship.
(a)(b)(c)(d)Based on the study above, for adversary Type-I and Type-II, we can solve the problem of access pattern and search pattern disclosure by specifying an honest server. However, if it is the adversary Type-III, the existing schemes do not protect their privacy from the perspective of access pattern and search pattern [4–7]. In other words, none of them can resist leakage abuse attacks [30]. One possible solution is to store data distributed on servers so that statistics are not completely compromised if there is an honest server. Next, for the adversary Type-III, we will solve this problem from another angle.


## 5. Construction

In this section, we first introduce a PAEKS scheme without bilinear pairs. Secondly, based on this scheme, we padding the keywords to achieve one cipher at a time from the ciphertext perspective. In addition, appropriate processing of the documents containing the key makes it possible to protect the access patterns.


### 5.1. Basic Construction

Our algorithm is consisted of five PPT algorithms, namely,Setup, KeyGen PAEKS, Trapdoor, and Test. The formal constructions are as follows:
(i)
Setupλ: G1 is cyclic groups. The order of G is prime p. Select two hash functions H1:0,1∗⟶Zp∗ and H2:G1⟶0,1∗. Choose a random generator g of G1. Output the public parameters pp=G1,p,g,H1,H2.(ii)
PK,SK⟵KeyGen(pp): It is responsible for the public/private key pair of participants(iii)
The DS chooses a random elementy∈Zp∗, and sets PKS=gymodp, SKS=y(iv)
The DR selects randomlyx∈Zp∗, and sets PKR=gxmodp, SKR=x(v)
The CS selects randomlyz∈Zp∗, and sets be PKCS=gzmodp, SKCS=z(vi)
PAEKSSKS,PKR,PKS,w: Choose a random r∈Zp∗, compute C1=gxrmodp, C2=H2gxr·gtmodp, where t=gH1wlPKSPKR, l=PKRy=gxy. The ciphertext is Cw=C1,C2.(vii)
TrapdoorSKR,PKR,PKS,PKCS,w: Compute l=PKSx=gyx, for keyword w, t=gH1wlPKSPKR. Then, choose a random k1≤k≤p−1,gcdk,p−1=1, compute u=gkmodp, T1=gkz, T2=t−x·uk−1modp−1. The trapdoor is Tw=T1,T2.(viii)
TestPKR,PKS,SKCS,Cw,Tw: Compute u′=T11/zmodp, H2PKRu′·u′T2·C1modp=?C2. If so, it outputs 1; otherwise, it outputs 0


### 5.2. Derived Construction

In basic construction, we can understand that if the PAEKS scheme itself can not hide the matching relationship between ciphertext and trapdoor for the adversary Type-III, which it always gets the relationship between ciphertext and trapdoor through Test algorithm. We consider that if we only achieve the hidden matching relationship in the simple PAEKS scheme, the solution is to fill in the keyword or attach some state information, so that the keyword can achieve the security of one time pad.To be specific, in order to prevent the malicious server from classifying ciphertext and trapdoor through the tested algorithm this leads to the disclosure of access and search pattern. We have to expand the external form of keywords to achieve that the same keyword has different ciphertext and trapdoor forms Figure3(d). Meanwhile, if we want to essentially solve the problem of search pattern and access pattern leakage, we have to operate on the original index matrix. The purpose of this operation is to achieve the uniqueness of keywords from the external form.According to the keywords of the diagram and the frequency information of the document and you can also make a choice according to your actual situation on how to construct different expressions of a keyword, here we give an example Figure1. Provide the uniqueness of keywords as follows: Solve the uniqueness of keywords as follows:
(i)
Maximum Number of Searches I. Before uploading the ciphertext, the DS stipulates that the same keyword can be searched for several times at most without disclosing the search pattern, and broadcast on the public channel. If users search more than this number of times, there is a risk of revealing the search pattern(ii)
Divided into Several Parts J. To solve the problem that different keywords return different numbers of documents, we suggest dividing the returned documents so that the number of documents returned each time is not much different. Here, the data DS needs to determine the maximum number of parts of a document and broadcast it to the Data Receiver(iii)
Keyword Form. A keyword w is set to wij, where i stands for the i-th search and j represents the j-th part of the search. For example Figure 2, we make the following settings. Note the following facts that is apw1=f1,f2,f3,f4, apw2=f1,f3,f4, apw3=f2,f4,f5, apw4=f1,f4,f5, apw5=f1,f4, let I=3,J=2. Thus, the keyword w1,w2,w3,w4,w5 extension to Table 2Table 2
Keyword Extension.
KeywordTag(timeI)Tag(partJ)w1w111w112w121w122w131w132w2w211w212w221w222w231w232w3w311w312w321w322w331w332w4w411w412w421w422w431w432w5w511w521w531Next, we apply the scheme proposed in Section VII to encrypt the filled keywords to achieve our purpose, which is to solve the problem that malicious servers can resist keyword guessing, search, and access pattern disclosure.Remark.
Once the data receiver searches for a keyword more than the predetermined number of times, it is possible to disclose the search behavior and access pattern. Another flaw is that the storage cost has doubled. Fortunately, the peace point of security and efficiency is left to the user to decide.


## 5.1. Basic Construction

Our algorithm is consisted of five PPT algorithms, namely,Setup, KeyGen PAEKS, Trapdoor, and Test. The formal constructions are as follows:
(i)
Setupλ: G1 is cyclic groups. The order of G is prime p. Select two hash functions H1:0,1∗⟶Zp∗ and H2:G1⟶0,1∗. Choose a random generator g of G1. Output the public parameters pp=G1,p,g,H1,H2.(ii)
PK,SK⟵KeyGen(pp): It is responsible for the public/private key pair of participants(iii)
The DS chooses a random elementy∈Zp∗, and sets PKS=gymodp, SKS=y(iv)
The DR selects randomlyx∈Zp∗, and sets PKR=gxmodp, SKR=x(v)
The CS selects randomlyz∈Zp∗, and sets be PKCS=gzmodp, SKCS=z(vi)
PAEKSSKS,PKR,PKS,w: Choose a random r∈Zp∗, compute C1=gxrmodp, C2=H2gxr·gtmodp, where t=gH1wlPKSPKR, l=PKRy=gxy. The ciphertext is Cw=C1,C2.(vii)
TrapdoorSKR,PKR,PKS,PKCS,w: Compute l=PKSx=gyx, for keyword w, t=gH1wlPKSPKR. Then, choose a random k1≤k≤p−1,gcdk,p−1=1, compute u=gkmodp, T1=gkz, T2=t−x·uk−1modp−1. The trapdoor is Tw=T1,T2.(viii)
TestPKR,PKS,SKCS,Cw,Tw: Compute u′=T11/zmodp, H2PKRu′·u′T2·C1modp=?C2. If so, it outputs 1; otherwise, it outputs 0


## 5.2. Derived Construction

In basic construction, we can understand that if the PAEKS scheme itself can not hide the matching relationship between ciphertext and trapdoor for the adversary Type-III, which it always gets the relationship between ciphertext and trapdoor through Test algorithm. We consider that if we only achieve the hidden matching relationship in the simple PAEKS scheme, the solution is to fill in the keyword or attach some state information, so that the keyword can achieve the security of one time pad.To be specific, in order to prevent the malicious server from classifying ciphertext and trapdoor through the tested algorithm this leads to the disclosure of access and search pattern. We have to expand the external form of keywords to achieve that the same keyword has different ciphertext and trapdoor forms Figure3(d). Meanwhile, if we want to essentially solve the problem of search pattern and access pattern leakage, we have to operate on the original index matrix. The purpose of this operation is to achieve the uniqueness of keywords from the external form.According to the keywords of the diagram and the frequency information of the document and you can also make a choice according to your actual situation on how to construct different expressions of a keyword, here we give an example Figure1. Provide the uniqueness of keywords as follows: Solve the uniqueness of keywords as follows:
(i)
Maximum Number of Searches I. Before uploading the ciphertext, the DS stipulates that the same keyword can be searched for several times at most without disclosing the search pattern, and broadcast on the public channel. If users search more than this number of times, there is a risk of revealing the search pattern(ii)
Divided into Several Parts J. To solve the problem that different keywords return different numbers of documents, we suggest dividing the returned documents so that the number of documents returned each time is not much different. Here, the data DS needs to determine the maximum number of parts of a document and broadcast it to the Data Receiver(iii)
Keyword Form. A keyword w is set to wij, where i stands for the i-th search and j represents the j-th part of the search. For example Figure 2, we make the following settings. Note the following facts that is apw1=f1,f2,f3,f4, apw2=f1,f3,f4, apw3=f2,f4,f5, apw4=f1,f4,f5, apw5=f1,f4, let I=3,J=2. Thus, the keyword w1,w2,w3,w4,w5 extension to Table 2Table 2
Keyword Extension.
KeywordTag(timeI)Tag(partJ)w1w111w112w121w122w131w132w2w211w212w221w222w231w232w3w311w312w321w322w331w332w4w411w412w421w422w431w432w5w511w521w531Next, we apply the scheme proposed in Section VII to encrypt the filled keywords to achieve our purpose, which is to solve the problem that malicious servers can resist keyword guessing, search, and access pattern disclosure.Remark.
Once the data receiver searches for a keyword more than the predetermined number of times, it is possible to disclose the search behavior and access pattern. Another flaw is that the storage cost has doubled. Fortunately, the peace point of security and efficiency is left to the user to decide.


## 6. Security Proof

In this section, we demonstrate that our basic scheme matches the design goals in the sense that it is capable of providing soundness and confidentiality. It can resist IKGA and reduce the possibility of access pattern and search pattern disclosure for adversary Type-II


### 6.1. Correctness

The ciphertext and trapdoor of keywordw and w′ are Cw=C1,C2 and Tw′, respectively. That is C1=gxrmodp, C2=H2gxr·gtmodp. let Tw′ be the trapdoor of keyword w′ generated by the receiver. u=gkmodp, T1=gkz, T2=t′−x·uk−1modp−1, where l=PKSx=gyx, t′=gH1w′lPKSPKR. It follows that
(i)
u=T11/z=gkz1/z=gk(ii)
H2PKRu·uT2·C1modp=H2gxu·gkt′−x·uk−1modp−1·gxrmodp=H2gxu·gt′−xumodp−1·gxrmodp=H2gt′·gxrmodpIfw=w′, t=t′, then H2gt′·gxrmodp=C2 with probability 1; otherwise, t≠t′,H2gt′·gxrmodp≠C2 with overwhelmig probability.


### 6.2. Confidentiality

The following theorems illustrate that our scheme is IND-CKA and IND-KGA security.(i)
Setupλ: C runs Setupλ and KeyGenpp to generate the public parameter pp and public/private key pair of participants PKS,SKS=gymodp,y of Data Sender, PKR,SKR=gxmodp,x of DR, of PKCS,SKCS=gzmodp,z of CS. Then, C sends pp,PKS,PKR,PKCS to A. Based on our assumptions, we assume that hash function H1 and H2 are secure and resistant to collisions(ii)
Phase1: A sends queries to OC and OT, and C is simulated as follows:
(a)
OC: choose a random r∈Zp∗, compute C1=gxrmodp, C2=H2gxr·gtmodp, where t=gH1wlPKSPKR, l=PKRy=gxy. The ciphertext is Cw=C1,C2.(b)
OT: compute l=PKSx=gyx, for keyword w, t=gH1wlPKSPKR. Then, choose a random k1≤k≤p−1,gcdk,p−1=1, compute u=gkmodp, T1=gkz, T2=t−x·uk−1modp−1. The trapdoor is Tw=T1,T2(iii)
Challenge: A selects w0∗,w1∗. Sends them to C. C picks a random bit b∈0,1. Encrypts wb∗ as follows:
(a)
Choose a randomr∗∈Zp∗, compute C1∗=gxr∗modp, C2=H2gxr∗·gt∗modp, where t∗=gH1wb∗lPKSPKR, l=PKRy=gxy. The ciphertext is Cwb∗∗=C1∗,C2∗(iv)
Phase2: Oracles continue to be consulted as Phase1(v)
Guess: C outputs a guess b′∈0,1. If b′=b then, C wins the game. A has the advantage that is
(4)AdvAGame0λ=AdvAKGAλ.Theorem 5.
Our scheme PAEKS implements IND-CKA security if the HDH assumption holds.Lemma 6.
The advantageAdvACKA is negligible for any polynomial adversary A.Proof.
Suppose the adversary guesses the key words in the game, and the correct event is recorded as (b′=b). We define games as follows:
Game0. It is the original IND-CKA game.Game1. Let Game1 be the same game as Game0. Assuming that Game1 is the same game as Game0, except that C chooses R∈G instead of computing t∗=gH1wb∗lPKSPKR. C sends Cwb∗∗=C1∗,C2∗=gxr∗modp,H2gxr∗·gRmodp. We have AdvAGame0−AdvAGame1<AdvAHDHλ, where AdvAHDHλ is negligible if the HDH assumption holds.Game2. Let Game2 be the same game as Game1, except that C random selects C1,C2∈G instead of Cwb∗∗=C1∗,C2∗=gxr∗modp,H2gxr∗·gRmodp. Given that r and R are random values, the Cwb∗ of Game1 and Game2 are of the same distribution as shown by C′ perspectiveWe have(5)AdvAGame2λ=AdvAGame1λ.A can only win Game2 with probability since Cwb∗ is independent of b. Thus, the advantage is
(6)AdvAGame2λ=12−12=0.Finally, according to theGame0, Game1, and Game2 we have
(7)AdvAGame2λ−AdvAKGAλ≤AdvAHDHλ,where AdvAHDHλ are negligible. Therefore, the advantage of A wins in the IND-CKA game is negligible.
(i)
Setupλ: C runs Setupλ and KeyGenpp to generate the public parameter pp and public/private key pair of participants PKS,SKS=gymodp,y of DS, PKR,SKR=gxmodp,x of DR, of PKCS,SKCS=gzmodp,z of CS. Then, C sends pp,PKS,PKR,PKCS to A. Based on what we know so far about hash functions, we assume H1 and H2 are secure and collision-resistant(ii)
Phase1: A adaptively issues queries to OC and OT, and C is simulated as follows:
(a)
OC: choose a random r∈Zp∗, compute C1=gxrmodp, C2=H2gxr·gtmodp, where t=gH1wlPKSPKR, l=PKRy=gxy. The ciphertext is Cw=C1,C2(b)
OT: compute l=PKSx=gyx, for keyword w, t=gH1wlPKSPKR. Then, choose a random k1≤k≤p−1,gcdk,p−1=1, compute u=gkmodp, T1=gkz, T2=t−x·uk−1modp−1. The trapdoor is Tw=T1,T2(iii)
Challenge: A chooses two keywords w0∗,w1∗ and sends them to C. C chooses a random bit b∈0,1, and then the trapdoor of the challenge keyword wb∗ as follows:
(a)
Computel=PKSx=gyx, for keyword wb∗, t=gH1wb∗lPKSPKR. Then, choose a random k1≤k≤p−1,gcdk,p−1=1, compute u=gkmodp, T1=gkz, T2=t−x·uk−1modp−1. The trapdoor is Twb∗=T1,T2.(iv)
Phase2: Oracles continue to be consulted as Phase1(v)
Guess: C outputs a guess b′∈0,1. If b′=b then C wins the game. A has the advantage that is
(8)AdvAGame0λ=AdvAKGAλTheorem 7.
Our PAEKS scheme implements IND-KGA security if the HDH assumption holds.Lemma 8.
The advantage ofAdvAKGA is negligible for any polynomial adversary A.Proof.
Suppose the adversary guesses the key words in the game, and the correct event is recorded as (b′=b). We define games as follows:
Game0. Game0 is the original IND-KGA.Game1. Let Game1 be the same game as Game0, except that C chooses R∈G instead of computing t∗=gH1wb∗lPKSPKR. C sends the trapdoor is Twb∗=T1,T2, where T1=gkz, T2=R−x·uk−1modp−1, k1≤k≤p−1,gcdk,p−1=1, u=gkmodpWe have(9)AdvAGame0λ−AdvAGame1λ<AdvAHDHλ,where AdvAHDHλ is negligible if the HDH assumption holds.Game2. Let Game2 be the same game as Game1, except that the C random chooses T1,T2∈G instead of Twb∗=T1,T2, where T1=gkz, T2=R−x·uk−1modp−1,k1≤k≤p−1,gcdk,p−1=1, u=gkmodp. Due to k and R are random, which Twb∗ of Game1 and Game2 are the same distribution from adversary’s view.We have(10)AdvAGame1λ=AdvAGame2λ.We know that A can only win with probabilityin Game2 because Twb∗ is independent of b. Thus, the advantage is
(11)AdvAGame2λ=12−12=0.Finally, according to theGame0, Game1, Game2 we have
(12)AdvAGame2−AdvAKGA≤AdvAHDHλ.where AdvAHDHλ are negligible. Therefore, the advantage of A wins in the IND-KGA game is negligible.
(i)
Setupλ: The challenger C runs Setupλ and KeyGenpp to generate pp and PKS,SKS=gymodp,y, PKR,SKR=gxmodp,x, and PKCS,SKCS=gzmodp,z . Then, C sends pp,PKS,PKR,PKCS to A. Based on our assumptions, we assume that hash function H1 and H2 are secure and resistant to collisions(ii)
Phase1: A adaptively sends queries to OC, OT and OTest, and C is simulated as follows:
(a)
OC: Choose a random r∈Zp∗, compute C1=gxrmodp, C2=H2gxr·gtmodp, where t=gH1wlPKSPKR, l=PKRy=gxy. The ciphertext is Cw=C1,C2.(b)
OT: Compute l=PKSx=gyx, for keyword w, t=gH1wlPKSPKR. Then, choose a random k1≤k≤p−1,gcdk,p−1=1, compute u=gkmodp, T1=gkz, T2=t−x·uk−1modp−1. The trapdoor is Tw=T1,T2.(c)
OTest: For any the cipher Cw and trapdoor Tw′ of keyword w and w′, C runs TestSKCS,PKR,Cw,Tw′, and outputs 1 if w′=w; otherwise, it outputs 0(iii)
Challenge: A selects w0∗,w1∗. Sends them to C. C selects a random bit b∈0,1, and encrypts wb∗. C picks a random bit d∈0,1, and the trapdoor of the challenge keyword wd∗ as follows:
(a)
Choose a randomr∗∈Zp∗, compute C1∗=gxr∗modp, C2=H2gxr∗·gt∗modp, where t∗=gH1wb∗lPKSPKR, l=PKRy=gxy. The ciphertext is Cwb∗∗=C1∗,C2∗.(b)
Computel=PKSx=gyx, for keyword wd∗, t=gH1wd∗lPKSPKR. Then, choose a random k1≤k≤p−1,gcdk,p−1=1, compute u=gkmodp, T1=gkz, T2=t−x·uk−1modp−1. The trapdoor is Twd∗=T1,T2.Theorem 9.
Our scheme PAEKS implements HMR-Security if the DL assumption holds.Lemma 10.
The advantageAdvAHMR is negligible for any polynomial adversary A.Proof.
We define games as follows:
Game0. The Game0 is the original version of this game.Finally,C sends Cwb∗∗ and Twd∗ to adversary.
(iv)
Phase2: Phase1 continues to be issued by A as queries to Oracles. There is only one restriction is that neither Cwb∗∗ or Twd∗ to OTest(v)
Guess. Finally, A returns b′,d′∈0,1 as the guess of b,d and wins the game if b′=b and d′=dAccording to the definition of the HMR game, the advantage of adversaryA is
(13)AdvAGame0λ=AdvAHMRλ.According to Theorem5 and Theorem 7, we know that the distribution of ciphertext and trapdoor of keywords is the same as that of random tuples from adversary view. So, A has to test algorithm to verify whether the ciphertext matches the trapdoor. Given gz and gkz, which calculating the value of k is DL problem.Finally, we have(14)AdvAGame0−AdvAHMR≤AdvADLλ,where AdvADLλ are negligible. Therefore, the advantage of A wins in the HMR game is negligible.


### 6.3. Security Analysis

(i)
Resisting attack IKGA. As far as PAEKS is concerned, only the DS has the ability to generate a legal ciphertext. The adversary executes the PAEKS algorithm, it cannot generate k. Similarly, the adversary can not generate the trapdoor of keyword. Test algorithm cannot provide any information to the adversary. Thus, our scheme can resist IKGA(ii)
Access pattern and Search pattern. For adversary Type-I, we can know that the ciphertext and trapdoor of keywords meet the indistinguishability according to Theorem 5 and Theorem 7. Therefore, the access pattern and search pattern are not compromised. However, the adversary Type-III can run the test algorithm, which will reveal some search information of the user. Then, the adversary can carry out leakage abuse attacks by combining some prior knowledge. In addition, we cannot hide the matching relationship between the ciphertexts and trapdoors from this type of powerful adversary


## 6.1. Correctness

The ciphertext and trapdoor of keywordw and w′ are Cw=C1,C2 and Tw′, respectively. That is C1=gxrmodp, C2=H2gxr·gtmodp. let Tw′ be the trapdoor of keyword w′ generated by the receiver. u=gkmodp, T1=gkz, T2=t′−x·uk−1modp−1, where l=PKSx=gyx, t′=gH1w′lPKSPKR. It follows that
(i)
u=T11/z=gkz1/z=gk(ii)
H2PKRu·uT2·C1modp=H2gxu·gkt′−x·uk−1modp−1·gxrmodp=H2gxu·gt′−xumodp−1·gxrmodp=H2gt′·gxrmodpIfw=w′, t=t′, then H2gt′·gxrmodp=C2 with probability 1; otherwise, t≠t′,H2gt′·gxrmodp≠C2 with overwhelmig probability.


## 6.2. Confidentiality

The following theorems illustrate that our scheme is IND-CKA and IND-KGA security.(i)
Setupλ: C runs Setupλ and KeyGenpp to generate the public parameter pp and public/private key pair of participants PKS,SKS=gymodp,y of Data Sender, PKR,SKR=gxmodp,x of DR, of PKCS,SKCS=gzmodp,z of CS. Then, C sends pp,PKS,PKR,PKCS to A. Based on our assumptions, we assume that hash function H1 and H2 are secure and resistant to collisions(ii)
Phase1: A sends queries to OC and OT, and C is simulated as follows:
(a)
OC: choose a random r∈Zp∗, compute C1=gxrmodp, C2=H2gxr·gtmodp, where t=gH1wlPKSPKR, l=PKRy=gxy. The ciphertext is Cw=C1,C2.(b)
OT: compute l=PKSx=gyx, for keyword w, t=gH1wlPKSPKR. Then, choose a random k1≤k≤p−1,gcdk,p−1=1, compute u=gkmodp, T1=gkz, T2=t−x·uk−1modp−1. The trapdoor is Tw=T1,T2(iii)
Challenge: A selects w0∗,w1∗. Sends them to C. C picks a random bit b∈0,1. Encrypts wb∗ as follows:
(a)
Choose a randomr∗∈Zp∗, compute C1∗=gxr∗modp, C2=H2gxr∗·gt∗modp, where t∗=gH1wb∗lPKSPKR, l=PKRy=gxy. The ciphertext is Cwb∗∗=C1∗,C2∗(iv)
Phase2: Oracles continue to be consulted as Phase1(v)
Guess: C outputs a guess b′∈0,1. If b′=b then, C wins the game. A has the advantage that is
(4)AdvAGame0λ=AdvAKGAλ.Theorem 5.
Our scheme PAEKS implements IND-CKA security if the HDH assumption holds.Lemma 6.
The advantageAdvACKA is negligible for any polynomial adversary A.Proof.
Suppose the adversary guesses the key words in the game, and the correct event is recorded as (b′=b). We define games as follows:
Game0. It is the original IND-CKA game.Game1. Let Game1 be the same game as Game0. Assuming that Game1 is the same game as Game0, except that C chooses R∈G instead of computing t∗=gH1wb∗lPKSPKR. C sends Cwb∗∗=C1∗,C2∗=gxr∗modp,H2gxr∗·gRmodp. We have AdvAGame0−AdvAGame1<AdvAHDHλ, where AdvAHDHλ is negligible if the HDH assumption holds.Game2. Let Game2 be the same game as Game1, except that C random selects C1,C2∈G instead of Cwb∗∗=C1∗,C2∗=gxr∗modp,H2gxr∗·gRmodp. Given that r and R are random values, the Cwb∗ of Game1 and Game2 are of the same distribution as shown by C′ perspectiveWe have(5)AdvAGame2λ=AdvAGame1λ.A can only win Game2 with probability since Cwb∗ is independent of b. Thus, the advantage is
(6)AdvAGame2λ=12−12=0.Finally, according to theGame0, Game1, and Game2 we have
(7)AdvAGame2λ−AdvAKGAλ≤AdvAHDHλ,where AdvAHDHλ are negligible. Therefore, the advantage of A wins in the IND-CKA game is negligible.
(i)
Setupλ: C runs Setupλ and KeyGenpp to generate the public parameter pp and public/private key pair of participants PKS,SKS=gymodp,y of DS, PKR,SKR=gxmodp,x of DR, of PKCS,SKCS=gzmodp,z of CS. Then, C sends pp,PKS,PKR,PKCS to A. Based on what we know so far about hash functions, we assume H1 and H2 are secure and collision-resistant(ii)
Phase1: A adaptively issues queries to OC and OT, and C is simulated as follows:
(a)
OC: choose a random r∈Zp∗, compute C1=gxrmodp, C2=H2gxr·gtmodp, where t=gH1wlPKSPKR, l=PKRy=gxy. The ciphertext is Cw=C1,C2(b)
OT: compute l=PKSx=gyx, for keyword w, t=gH1wlPKSPKR. Then, choose a random k1≤k≤p−1,gcdk,p−1=1, compute u=gkmodp, T1=gkz, T2=t−x·uk−1modp−1. The trapdoor is Tw=T1,T2(iii)
Challenge: A chooses two keywords w0∗,w1∗ and sends them to C. C chooses a random bit b∈0,1, and then the trapdoor of the challenge keyword wb∗ as follows:
(a)
Computel=PKSx=gyx, for keyword wb∗, t=gH1wb∗lPKSPKR. Then, choose a random k1≤k≤p−1,gcdk,p−1=1, compute u=gkmodp, T1=gkz, T2=t−x·uk−1modp−1. The trapdoor is Twb∗=T1,T2.(iv)
Phase2: Oracles continue to be consulted as Phase1(v)
Guess: C outputs a guess b′∈0,1. If b′=b then C wins the game. A has the advantage that is
(8)AdvAGame0λ=AdvAKGAλTheorem 7.
Our PAEKS scheme implements IND-KGA security if the HDH assumption holds.Lemma 8.
The advantage ofAdvAKGA is negligible for any polynomial adversary A.Proof.
Suppose the adversary guesses the key words in the game, and the correct event is recorded as (b′=b). We define games as follows:
Game0. Game0 is the original IND-KGA.Game1. Let Game1 be the same game as Game0, except that C chooses R∈G instead of computing t∗=gH1wb∗lPKSPKR. C sends the trapdoor is Twb∗=T1,T2, where T1=gkz, T2=R−x·uk−1modp−1, k1≤k≤p−1,gcdk,p−1=1, u=gkmodpWe have(9)AdvAGame0λ−AdvAGame1λ<AdvAHDHλ,where AdvAHDHλ is negligible if the HDH assumption holds.Game2. Let Game2 be the same game as Game1, except that the C random chooses T1,T2∈G instead of Twb∗=T1,T2, where T1=gkz, T2=R−x·uk−1modp−1,k1≤k≤p−1,gcdk,p−1=1, u=gkmodp. Due to k and R are random, which Twb∗ of Game1 and Game2 are the same distribution from adversary’s view.We have(10)AdvAGame1λ=AdvAGame2λ.We know that A can only win with probabilityin Game2 because Twb∗ is independent of b. Thus, the advantage is
(11)AdvAGame2λ=12−12=0.Finally, according to theGame0, Game1, Game2 we have
(12)AdvAGame2−AdvAKGA≤AdvAHDHλ.where AdvAHDHλ are negligible. Therefore, the advantage of A wins in the IND-KGA game is negligible.
(i)
Setupλ: The challenger C runs Setupλ and KeyGenpp to generate pp and PKS,SKS=gymodp,y, PKR,SKR=gxmodp,x, and PKCS,SKCS=gzmodp,z . Then, C sends pp,PKS,PKR,PKCS to A. Based on our assumptions, we assume that hash function H1 and H2 are secure and resistant to collisions(ii)
Phase1: A adaptively sends queries to OC, OT and OTest, and C is simulated as follows:
(a)
OC: Choose a random r∈Zp∗, compute C1=gxrmodp, C2=H2gxr·gtmodp, where t=gH1wlPKSPKR, l=PKRy=gxy. The ciphertext is Cw=C1,C2.(b)
OT: Compute l=PKSx=gyx, for keyword w, t=gH1wlPKSPKR. Then, choose a random k1≤k≤p−1,gcdk,p−1=1, compute u=gkmodp, T1=gkz, T2=t−x·uk−1modp−1. The trapdoor is Tw=T1,T2.(c)
OTest: For any the cipher Cw and trapdoor Tw′ of keyword w and w′, C runs TestSKCS,PKR,Cw,Tw′, and outputs 1 if w′=w; otherwise, it outputs 0(iii)
Challenge: A selects w0∗,w1∗. Sends them to C. C selects a random bit b∈0,1, and encrypts wb∗. C picks a random bit d∈0,1, and the trapdoor of the challenge keyword wd∗ as follows:
(a)
Choose a randomr∗∈Zp∗, compute C1∗=gxr∗modp, C2=H2gxr∗·gt∗modp, where t∗=gH1wb∗lPKSPKR, l=PKRy=gxy. The ciphertext is Cwb∗∗=C1∗,C2∗.(b)
Computel=PKSx=gyx, for keyword wd∗, t=gH1wd∗lPKSPKR. Then, choose a random k1≤k≤p−1,gcdk,p−1=1, compute u=gkmodp, T1=gkz, T2=t−x·uk−1modp−1. The trapdoor is Twd∗=T1,T2.Theorem 9.
Our scheme PAEKS implements HMR-Security if the DL assumption holds.Lemma 10.
The advantageAdvAHMR is negligible for any polynomial adversary A.Proof.
We define games as follows:
Game0. The Game0 is the original version of this game.Finally,C sends Cwb∗∗ and Twd∗ to adversary.
(iv)
Phase2: Phase1 continues to be issued by A as queries to Oracles. There is only one restriction is that neither Cwb∗∗ or Twd∗ to OTest(v)
Guess. Finally, A returns b′,d′∈0,1 as the guess of b,d and wins the game if b′=b and d′=dAccording to the definition of the HMR game, the advantage of adversaryA is
(13)AdvAGame0λ=AdvAHMRλ.According to Theorem5 and Theorem 7, we know that the distribution of ciphertext and trapdoor of keywords is the same as that of random tuples from adversary view. So, A has to test algorithm to verify whether the ciphertext matches the trapdoor. Given gz and gkz, which calculating the value of k is DL problem.Finally, we have(14)AdvAGame0−AdvAHMR≤AdvADLλ,where AdvADLλ are negligible. Therefore, the advantage of A wins in the HMR game is negligible.


## 6.3. Security Analysis

(i)
Resisting attack IKGA. As far as PAEKS is concerned, only the DS has the ability to generate a legal ciphertext. The adversary executes the PAEKS algorithm, it cannot generate k. Similarly, the adversary can not generate the trapdoor of keyword. Test algorithm cannot provide any information to the adversary. Thus, our scheme can resist IKGA(ii)
Access pattern and Search pattern. For adversary Type-I, we can know that the ciphertext and trapdoor of keywords meet the indistinguishability according to Theorem 5 and Theorem 7. Therefore, the access pattern and search pattern are not compromised. However, the adversary Type-III can run the test algorithm, which will reveal some search information of the user. Then, the adversary can carry out leakage abuse attacks by combining some prior knowledge. In addition, we cannot hide the matching relationship between the ciphertexts and trapdoors from this type of powerful adversary


## 7. Comparison and Analysis

We compare our scheme with the authentication based searchable schemes (HL17 [4], QC+20 [5], QC+21 [7], and PL21 [6]), 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 libraries.


### 7.1. Comparative Analysis of Security

The Table3 indicates the comparison results among the proposed PAEKS. Again, we emphasize that since the server can perform test operations, the inseparability of ciphertext and the indistinguishability of trapdoor for the same keyword have no practical significance unless the keyword is filled in like the extended version of the scheme. Therefore, we only compare the indistinguishability of external adversaries or curious servers before a retrieval token is given. We adopted the security description of [7]. In the table, we are only comparing the security of adversary Type-II. Qin et al. [7] introduced the definition of fully CI-security and fully TI-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 [4], QC+20 [5], QC+21 [7], and PL21 [6] 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. Table 3 shows that only our scheme achieves the fully CI-security and fully TI-security. Meanwhile, it can protect the user’s search pattern.Table 3
Security Comparison.
SchemesFully CI-securityFully TI-securitySearch patternAssumptionHL17 [4]×××mDLLN and DBDHQC+20[5]××BDHQC+21 [7]××BDH and CODHPL21 [6]×××BDHIOursHDH and DL√: The schemes supporting corresponding features are supported. ×: The scheme cannot support the corresponding feature.


### 7.2. Time Complexity

The Table4 shows the number of operations of each algorithm. EG is a symbol for exponentiation in group G. P is a symbol for the pairing operation. H1 is a symbol for a group element that maps any string to G. In Table 4, other schemes employ bilinear pair operation, which greatly reduces the efficiency. The computational costs of Setup and KeyGen of various schemes are both similar and have the same algorithm. Therefore, we just consider Encrypt, Trapdoor, and Test algorithms. Qin et al.’s [5, 7] schemes need to compute 3 exponentiation operations, one hash-to-point operation and one pair operation in the ciphertext phase. Their scheme needs to compute 2 power operations and one hash-to-point operation in the trapdoor phase. Huang et al.’s [4] and Pan et al.’s [6] operate the same number of times in the cipher phase and the trapdoor phase. Notice that their schemes all use bilinear bilinear operations, which leads to a large computational overhead. We can see that our scheme is the fastest in the ciphertext, trapdoor, and test phases. This is because our algorithm uses power operations which are computationally less expensive. It can be seen that our scheme is more suitable for lightweight devices.Table 4
Operations comparison of PAEKS schemes.
SchemesKeyGenPAEKSTrapdoorTestHL17 [4]2EG3EG+H13EG+P+H12PQC+20[5]2EG3EG+P+H12EG+H1PQC+21 [7]2EG3EG+P+H12EG+H1PPL21 [6]2EG3EG+H13EG+P+H1POurs3EG4EG+H14EG+H13EGH1: denoting a hash-to-point operation. P: denoting a bilinear pairing operation. EG: denoting a modular exponentiation.


### 7.3. Evaluation

We can evaluate the effectiveness of the various schemes (HL17, QC+20, QC+21, and PL21) by incorporating Relic and GMP. Platforms used in this experiment include Ubuntu 18.04.5 LTS with Intel(R) Xeon(R) CPU E5-2620 v4@2.10GHz and 16.00GB of RAM. The pseudo random permutation was computed using the AES algorithm (CBC model, 128bit key). The hash functions were computed using the SHA256 algorithm. We choose the real Encron Email Dataset (Version 20150307, about 423 MB) to demonstrate the practical performance of our proposed scheme, which contains the data from about 150 users [31]. We choose about 2000 keywords whose lengths are not less than 5 characters and the total number of occurrences is higher than 20.This paper compares the proposed scheme and the schemes in HL17, QC+20, QC+21, and PL21 in terms ofPAEKS, Trapdoor, and Test. The keywords were also chosen randomly for this experiment. As shown in Figures 4–6, we have the lowest computation cost among the five schemes for generating ciphertexts, trapdoors, and test. A key point of the high computational efficiency of our scheme is that it does not require some bilinear pairing operations, which can save a lot of computing overhead. In the ciphertexts generation algorithm, Pan and Li [6] computational overhead is about 274 times that of ours. Compared to our trapdoor generation algorithm, Qin et al.’s [5] computation overhead is about 158 times higher. It is estimated that Qin et al.’s [7] computational overhead is about 60 times ours in the test algorithm.Figure 4
Computation cost of ciphertext generation.Figure 5
Computation cost of trapdoor generation.Figure 6
Computation cost of test algorithm.To evaluate the efficiency of the PAEKS algorithm, we give the time consumption of each algorithm for testing 2000 keywords, as shown in Figure7. Communication and network effects were removed in the experimental results. Note that to generate 2000 keyword ciphertexts in our scheme, the trapdoor and test take 315.004 ms, 452.788 ms, and 204.079 ms, respectively. The time cost of generating a cipher text is 0.1575 ms. The time cost to generate a trapdoor is 0.2264 ms. The search algorithm is efficient, with an average time cost of about 0.102 ms for matching. Therefore, our scheme is more suitable for some lightweight or computationally constrained devices.Figure 7
Computation cost of PAEKS in real dataset.


## 7.1. Comparative Analysis of Security

The Table3 indicates the comparison results among the proposed PAEKS. Again, we emphasize that since the server can perform test operations, the inseparability of ciphertext and the indistinguishability of trapdoor for the same keyword have no practical significance unless the keyword is filled in like the extended version of the scheme. Therefore, we only compare the indistinguishability of external adversaries or curious servers before a retrieval token is given. We adopted the security description of [7]. In the table, we are only comparing the security of adversary Type-II. Qin et al. [7] introduced the definition of fully CI-security and fully TI-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 [4], QC+20 [5], QC+21 [7], and PL21 [6] 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. Table 3 shows that only our scheme achieves the fully CI-security and fully TI-security. Meanwhile, it can protect the user’s search pattern.Table 3
Security Comparison.
SchemesFully CI-securityFully TI-securitySearch patternAssumptionHL17 [4]×××mDLLN and DBDHQC+20[5]××BDHQC+21 [7]××BDH and CODHPL21 [6]×××BDHIOursHDH and DL√: The schemes supporting corresponding features are supported. ×: The scheme cannot support the corresponding feature.


## 7.2. Time Complexity

The Table4 shows the number of operations of each algorithm. EG is a symbol for exponentiation in group G. P is a symbol for the pairing operation. H1 is a symbol for a group element that maps any string to G. In Table 4, other schemes employ bilinear pair operation, which greatly reduces the efficiency. The computational costs of Setup and KeyGen of various schemes are both similar and have the same algorithm. Therefore, we just consider Encrypt, Trapdoor, and Test algorithms. Qin et al.’s [5, 7] schemes need to compute 3 exponentiation operations, one hash-to-point operation and one pair operation in the ciphertext phase. Their scheme needs to compute 2 power operations and one hash-to-point operation in the trapdoor phase. Huang et al.’s [4] and Pan et al.’s [6] operate the same number of times in the cipher phase and the trapdoor phase. Notice that their schemes all use bilinear bilinear operations, which leads to a large computational overhead. We can see that our scheme is the fastest in the ciphertext, trapdoor, and test phases. This is because our algorithm uses power operations which are computationally less expensive. It can be seen that our scheme is more suitable for lightweight devices.Table 4
Operations comparison of PAEKS schemes.
SchemesKeyGenPAEKSTrapdoorTestHL17 [4]2EG3EG+H13EG+P+H12PQC+20[5]2EG3EG+P+H12EG+H1PQC+21 [7]2EG3EG+P+H12EG+H1PPL21 [6]2EG3EG+H13EG+P+H1POurs3EG4EG+H14EG+H13EGH1: denoting a hash-to-point operation. P: denoting a bilinear pairing operation. EG: denoting a modular exponentiation.


## 7.3. Evaluation

We can evaluate the effectiveness of the various schemes (HL17, QC+20, QC+21, and PL21) by incorporating Relic and GMP. Platforms used in this experiment include Ubuntu 18.04.5 LTS with Intel(R) Xeon(R) CPU E5-2620 v4@2.10GHz and 16.00GB of RAM. The pseudo random permutation was computed using the AES algorithm (CBC model, 128bit key). The hash functions were computed using the SHA256 algorithm. We choose the real Encron Email Dataset (Version 20150307, about 423 MB) to demonstrate the practical performance of our proposed scheme, which contains the data from about 150 users [31]. We choose about 2000 keywords whose lengths are not less than 5 characters and the total number of occurrences is higher than 20.This paper compares the proposed scheme and the schemes in HL17, QC+20, QC+21, and PL21 in terms ofPAEKS, Trapdoor, and Test. The keywords were also chosen randomly for this experiment. As shown in Figures 4–6, we have the lowest computation cost among the five schemes for generating ciphertexts, trapdoors, and test. A key point of the high computational efficiency of our scheme is that it does not require some bilinear pairing operations, which can save a lot of computing overhead. In the ciphertexts generation algorithm, Pan and Li [6] computational overhead is about 274 times that of ours. Compared to our trapdoor generation algorithm, Qin et al.’s [5] computation overhead is about 158 times higher. It is estimated that Qin et al.’s [7] computational overhead is about 60 times ours in the test algorithm.Figure 4
Computation cost of ciphertext generation.Figure 5
Computation cost of trapdoor generation.Figure 6
Computation cost of test algorithm.To evaluate the efficiency of the PAEKS algorithm, we give the time consumption of each algorithm for testing 2000 keywords, as shown in Figure7. Communication and network effects were removed in the experimental results. Note that to generate 2000 keyword ciphertexts in our scheme, the trapdoor and test take 315.004 ms, 452.788 ms, and 204.079 ms, respectively. The time cost of generating a cipher text is 0.1575 ms. The time cost to generate a trapdoor is 0.2264 ms. The search algorithm is efficient, with an average time cost of about 0.102 ms for matching. Therefore, our scheme is more suitable for some lightweight or computationally constrained devices.Figure 7
Computation cost of PAEKS in real dataset.


## 8. Conclusion

In this paper, we have defined different types of adversary capabilities and firstly, analyze the relationship between ciphertext indistinguishability, trapdoor indistinguishability, access pattern, and search pattern. Then, we discuss the security of existing PAEKS schemes. Based on [7], we add the full TI-security model so that we can resist the leakage of search pattern. For adversary Type-II, we design a PAEKS scheme without bilinear pairs, which greatly improves efficiency compared with the previous project. Because the scheme does not use bilinear pairs as a whole, it is more suitable for edge servers and clients with limited computing power. In addition, we also put forward a solution on how to protect access pattern disclosure against adversary Type-III. Unfortunately, the memory expansion is too large. The future work is possible to construct a PAEKS scheme that can protect the search pattern and access pattern and has less memory overhead.



---

*Source: 2336685-2022-10-19.xml*