# IsoqurPEKS: An Isogeny-Based Quantum-Resistant Public-Key Encryption Scheme with Keyword Search

Authors: Qing Fan; Min Luo; Cong Peng; Lianhai Wang; Debiao He
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Since the convenience and advancement of cloud applications, many users (e.g., companies or individuals) adopt remote cloud services to reduce the local storage overload and computing consumption. However, before transferring them to the cloud server, users always encrypt outsourced data for the privacy of important data, which deprives flexible usage of these data. Public key encryption with keyword search (PEKS) undoubtedly offers a precise resolution to this issue. Unfortunately, most PEKS schemes cannot fight against quantum computing attackers, which is increasingly a research hotspot. To achieve postquantum security and privacy-preserving search function, we propose a quantum-resistant PEKS scheme named IsoqurPEKS. Our proposed instantiation satisfies basic semantic security indistinguishable against chosen keyword attack (IND-CKA), and IsoqurPEKS is proved to be secure under the security model. Furthermore, we compare IsoqurPEKS with the other eight current PEKS schemes with respect to security properties, communication, and computation costs. The comparison results indicate that the proposed scheme has the best security and performance among the nine PEKS schemes.


---

## Body

## 1. Introduction

Remote cloud services have advantages of data accessibility, data scalability, data sharing, and consistent backups of enormous data [1]. Cloud applications, such as cloud storage, cloud computing, and cloud retrieval, are becoming more prevalent for data users and enterprises. Data uploaders usually outsource their data to the cloud server, saving their local storage cost and offering easy data access. However, these remote servers are not always trusted since some malicious insiders may have full access to plaintext data. Once critical and sensitive data are exposed to hackers, significant threats to users’ property and life safety may happen. Therefore, before uploading data to the cloud server, data providers encrypt these data using encryption algorithms to provide privacy protection while depriving all search capacities of data users.Many cloud services, such as Baidu Cloud, Google Cloud, Windows Azure, and Amazon simple storage service [2] promote the development of cloud storage and searching technologies. When performing data retrieval, a straightforward approach for cloud servers is to obtain a decryption key and search required items in plaintext. However, this method breaks the initial intention of outsourced data encryption because a corrupted insider (e.g., a compromised cloud storage provider’s machine [3]) could access any unauthorized data. Another solution for data users is to download the whole database, decrypt all data locally, and retrieve interesting documents, which require a lot of memory space and computation capacity. This method does not play the role of a cloud server; instead, it puts forward high requirements for users, which are impractical in most applications [4]. To achieve data confidentiality and search function at the same time, Song et al. [5] first put forward the conception of searchable encryption.The searchable encryption mechanism enables data providers to upload encrypted data and multiple searchable keywords ciphertexts, while data users produce trapdoors of intended keywords. Utilizing the trapdoor, a cloud server could execute a search to seek matched keywords and corresponding data ciphertext. According to distinct generation types of encrypted keywords and trapdoors [6], searchable encryption is generally classified into public key encryption with keyword search (PEKS) and symmetric searchable encryption (SSE). Although SSE has efficient retrieval efficiency, which has been extensively researched [7], it still has the same key distribution problem as symmetric encryption. Then, Boneh et al. [8] introduced the first PEKS scheme, whose system architecture is shown in Figure 1. In our scheme, the data provider produces searchable ciphertext using users’ public keys, and the user generates a keyword search trapdoor by their private key. Then, the trapdoor is transmitted to the cloud server for searching matched ciphertexts, which are finally returned to the user. Furthermore, Boneh et al. have also formalized the notion of indistinguishability against chosen keyword attacks (IND-CKAs) of PEKS, which ensures the privacy of searchable ciphertext [8].Figure 1
General PEKS architecture.However, most of the current PEKS schemes are designed based on classical hard assumptions such as discrete logarithm (DL) problem and computational/decisional Diffie–Hellman (CDH/DDH) problem. Shor [9] pointed out that there is a quantum algorithm to crack the DL problem in polynomial time, which inspires scholars to explore quantum-resistant PEKS scheme construction [10]. According to the report on postquantum cryptography [11], families of postquantum primitives are designed by the lattice, multivariate polynomial, code, and isogeny. In comparison, code-based and lattice-based cryptographies suffer from large key sizes. In addition, there are no searchable encryption-compatible structures based on multivariate polynomials and hash-based cryptography as far as we know.Isogeny-based cryptography overcomes the above problem and has the potential for searchable encryption construction. Isogeny is a rational mapping from one elliptic curve to another, which is distinguished by its degree or kernel [12]. The isogeny problem is to seek a mapping path given two specified isogenous elliptic curves. Studies on isogeny-based cryptography have matured gradually, and the fastest known algorithm to find such an isogeny takes subexponential time [13]. Isogeny-basedencryption [14] gives a specific verification equation (i.e. eϕP,Q=e′P,ϕ^Qwhere ϕ is an isogeny between two elliptic curves E⟶E′ and ϕ^:E′⟶Eare mutual dual isogeny, E ⟶ GT and E′ ⟶ GT are two bilinear maps, and P/Q are separately the generators of E/E′), and the first PEKS scheme enlightens us to design an isogeny-based quantum-resistant PEKS scheme.This paper puts forward a new quantum-resistant PEKS scheme using isogeny named IsoqurPEKS. Then, we prove its IND-CKA security under the quantum random oracle (QROM) model and analyze communication cost and computation cost by comparing IsoqurPEKS with other eight PEKS schemes. Analysis results demonstrate that IsoqurPEKS has the least communication and computation overload while maintaining the property of withstanding quantum computer attacks.


### 1.1. Organizations of This Paper

Section2 introduces related works about isogeny quantum-resistant PEKS schemes. Preliminaries containing the elliptic curve and isogeny knowledge are introduced in Section 3. PEKS definitions, consistency, and security definitions of the quantum-resistant PEKS scheme are given in Section 4. We present the system model of the proposed IsoqurPEKS scheme and the threat model of each entity, and the design goals of this paper are presented in Section 5. Then, we introduce the quantum-resistant IsoqurPEKS scheme in Section 6, and we give the formal security proof of IsoqurPEKS in Section 7. Section 8 shows the property, communication cost, and time consumption comparisons with eight PEKS schemes. Eventually, we summarize this paper in Section 9.


## 1.1. Organizations of This Paper

Section2 introduces related works about isogeny quantum-resistant PEKS schemes. Preliminaries containing the elliptic curve and isogeny knowledge are introduced in Section 3. PEKS definitions, consistency, and security definitions of the quantum-resistant PEKS scheme are given in Section 4. We present the system model of the proposed IsoqurPEKS scheme and the threat model of each entity, and the design goals of this paper are presented in Section 5. Then, we introduce the quantum-resistant IsoqurPEKS scheme in Section 6, and we give the formal security proof of IsoqurPEKS in Section 7. Section 8 shows the property, communication cost, and time consumption comparisons with eight PEKS schemes. Eventually, we summarize this paper in Section 9.


## 2. Related Works

Boneh et al. [8] first put forward the notion of public key encryption with keyword search (PEKS). Following this seminal word, some further works on PEKS schemes [15–17] have been proposed in traditional public-key cryptography settings. Scholars have mainly explored two types of research orientations: diverse functionality search and security studies.Concerning functionality search, Kim et al. [18] proposed the first privacy-preserving algorithm to test whether an encrypted string includes an encrypted pattern. Meanwhile, they designed a novel wildcard search on encrypted databases, which are used to support compound queries. In terms of a multikeyword search, Wang et al. [19] proposed a secure searchable encryption scheme under the standard model supporting multikeyword retrieval. Liu et al. [20] put forward a multiuser and multikeyword search with the hiding search pattern and access pattern. Zhang et al. [21] proposed a fuzzy multikeyword search in the cloud system using Word2vec technology. Liang et al. [22] utilized advanced k-nearest neighbor (k-NN) technology to enhance search accuracy and achieve an exact multikeyword fine-grained search. Zarezadeh et al. [23] presented a multikeyword rank search scheme that enhances usability and file retrieval accuracy. Asymmetric encryption schemes supporting Boolean queries in different scenarios such as cloud applications and mobile clouds were also studied [24, 25]. However, the above schemes are built on classical intractable assumptions and cannot resist quantum computing attacks.Concerning security, scholars generally consider forward privacy and backward security of searchable encryption. Forward privacy ensures that inserting new files will not expose previous search information, and backward security means deleting files will not disclose more information in the following search process. Zhang et al. [26] and Ning et al. [27] have discussed threats brought to searchable encryption by file-injection attacks and passive attacks. Then, Bost et al. [28] used constrained pseudorandom functions and puncturable encryption and put forward forward and backward secrecy searchable encryption under the symmetric mechanism. Zeng et al. [29] introduced searchable public key encryption built on attribute-based encryption, which satisfies forward privacy. These schemes still do not take quantum-resistant attacks into account.Behnia et al. [30] proposed two lattice-based PEKS schemes with well computational efficiency and better security than the current ones. Xu et al. [10] utilized learning with error (LWE) hard problems and also proposed a lattice-based searchable encryption scheme, which satisfies postquantum security. However, lattice-based PEKS schemes have large-sized keys because they are composed of matrices. Isogeny-based cryptography has small-sized keys which have been studied deeply [12, 31–33].We put forward a PEKS scheme based on the isogeny hardness assumption to resist quantum-computing attacks. Then, we prove its security under the QROM model. Although there has been one isogeny-based PEKS scheme [34], the proposed IsoqurPEKS scheme has better efficiency. Moreover, we also evaluate this scheme by comparing it with the current eight PEKS schemes to communication cost and computation cost, indicating that our scheme has the best security and performance among these nine PEKS schemes.


## 3. Preliminaries

In this section, we introduce a basic elliptic curve and supersingular isogeny knowledge used in the scheme design. Notations used in this paper are shown in Table1.Table 1
Notation description.
NotationsDescriptionsλSecurity parameterNThe elliptic curve’s orderFqA finite field with the orderqENThe elliptic curve point group with the orderNP1,P2Two base points inEN#EThe cardinality of the elliptic curve point groupj-VariantAn index for determining elliptic curve isomorphismϕIsogenyϕ:E⟶E′ with a degree lϕ^ϕ’s dual isogeny ϕ^:E′⟶EhGeneral hash functionh:0,1∗⟶0,1lgNH′Hash-to-point functionH′:0,1∗⟶E′NGT,GT′Two multiplicative groupseBilinear mape:EN×EN⟶GTe′Bilinear mape′:E′N×E′N⟶GT′PKThe public key of the userSKThe private key of the userωProbability of one value appearing in random oracle


### 3.1. Elliptic Curve

In our scheme, we will take advantage of the following basic knowledge.Fq is a finite field with the order q. The equation y2=x3+cx+dmodq defines an elliptic curve E over Fq, where c,d∈Fq. Points on the elliptic curve E:y2=x3+cx+dmodq with the addition of the point at infinity O=0,0 constitute an additive cyclic group EN whose order is an integer N. The map e:EN×EN⟶GN is a bilinear map satisfying:(i)
Bilinearity.exP,yP=eP,Pxy for any x,y∈Zq∗(ii)
Computability.eP,Q can be easily calculated in the polynomial time for any P,Q∈EN(iii)
Nondegeneracy.eP,P≠1whereGN is a multiplicative cyclic group with the order N and P is an arbitrary generator of EN.


### 3.2. Isogeny

Isogeny is defined based on two elliptic curvesE and E′, a rational and surjective mapping ϕ:E⟶E′. It keeps the computing law of the point group, i.e., ϕP+Q=ϕP+ϕQ for any points P,Q on E. Two elliptic curves E and E′ defined over a finite field Fq are isogenous with the necessary and sufficient condition that they have the same cardinality, i.e., #E=#E′. Since isogeny could be represented by a rational polynomial, a degree, similar to polynomials, could be defined and used to differentiate various isogenies. According to Burdges et al. [14], any isogeny ϕ:E⟶E′ has one and only one corresponding dual isogeny ϕ^:E′⟶E which has a specific relationship as follows:(1)eNϕP,Q=eN′P,ϕ^Q,for any points P∈EN,Q∈E′N, where e (resp. e′) is any bilinear pairing (e.g., Weil, Tate, and Ate pairing) on E (resp. E′).Next, we consider some preliminary knowledge for difficult problems resisting quantum computers attack. We first give the following proposition.Proposition 1.
LetE be an elliptic curve determined by y2=x3+cx+d, where c,d are from the finite field Fq, and then, we give the j-variant definition as follows:(2)jE=17284c34c3+27d2,and j-variant distinguishes the isomorphism class since the necessary and sufficient condition of two isomorphic curves is that they have the same j-variant.The graph structure can embody isogeny-related hard problems. This graph structure is composed of isomorphism classes denoted by nodes and isogenies between curves denoted by edges. The isogeny graphs constructed by different degrees of isogenies are diverse, and the isogeny star is made up of various isogeny graphs while having the same nodes. Literature [31] gives detailed descriptions and visualized depictions of the isogeny star as shown in Figure 2. There are many isogeny paths from one node to another, which may consist of multiple isogenies. When the isogeny star is quite large, finding a path from the initial elliptic curve to the end elliptic curve, respectively, in different isomorphism classes will be rather difficult, which is the isogeny problem.Childs et al. [13] have pointed out that the most efficient traditional algorithm requires exponential time to seek an isogeny between two isogenous elliptic curves. However, they came up with a quantum algorithm to construct an isogeny between two given elliptic curves with the same cardinality in subexponential time. However, the running time is bounded above by exp3/2+O1lnqlnlnq under the generalized Riemann hypothesis. Most importantly, there exists no faster quantum algorithm than in the study by Childs et al. as far as we know. Assume that ϕ is an isogeny mapping from the elliptic curve E to E′, we give the following two difficult problems under quantum computers.Figure 2
Isogeny graphs and isogeny star [31].


#### 3.2.1. Supersingular Isogeny (SSI) Problem

Assume that the kernelsP+tQ specifies an isogeny ϕ:E⟶E′, where s and t are chosen randomly from ℤ/leℤ and are not divisible by l. Given the elliptic curve E′ and points ϕP,ϕQ on E′, it is difficult to find a generator T of sP+tQ. It should be specified that given a generator T=sP+tQ, it is trivial to resolve for s,t. In other words, given two elliptic curves E and E′ with the identical cardinality, it is hard to calculate an isogeny ϕ:E⟶E′ utilizing the quantum algorithm in the polynomial time.


#### 3.2.2. Extensional Computational Isogeny Problem (ECIP)

GivenP and ϕxP with x,ϕ unknown, where the point P is randomly selected on EN and x is a random number in Fq, it is difficult to calculate ϕ and x in the polynomial time for the quantum computer.


## 3.1. Elliptic Curve

In our scheme, we will take advantage of the following basic knowledge.Fq is a finite field with the order q. The equation y2=x3+cx+dmodq defines an elliptic curve E over Fq, where c,d∈Fq. Points on the elliptic curve E:y2=x3+cx+dmodq with the addition of the point at infinity O=0,0 constitute an additive cyclic group EN whose order is an integer N. The map e:EN×EN⟶GN is a bilinear map satisfying:(i)
Bilinearity.exP,yP=eP,Pxy for any x,y∈Zq∗(ii)
Computability.eP,Q can be easily calculated in the polynomial time for any P,Q∈EN(iii)
Nondegeneracy.eP,P≠1whereGN is a multiplicative cyclic group with the order N and P is an arbitrary generator of EN.


## 3.2. Isogeny

Isogeny is defined based on two elliptic curvesE and E′, a rational and surjective mapping ϕ:E⟶E′. It keeps the computing law of the point group, i.e., ϕP+Q=ϕP+ϕQ for any points P,Q on E. Two elliptic curves E and E′ defined over a finite field Fq are isogenous with the necessary and sufficient condition that they have the same cardinality, i.e., #E=#E′. Since isogeny could be represented by a rational polynomial, a degree, similar to polynomials, could be defined and used to differentiate various isogenies. According to Burdges et al. [14], any isogeny ϕ:E⟶E′ has one and only one corresponding dual isogeny ϕ^:E′⟶E which has a specific relationship as follows:(1)eNϕP,Q=eN′P,ϕ^Q,for any points P∈EN,Q∈E′N, where e (resp. e′) is any bilinear pairing (e.g., Weil, Tate, and Ate pairing) on E (resp. E′).Next, we consider some preliminary knowledge for difficult problems resisting quantum computers attack. We first give the following proposition.Proposition 1.
LetE be an elliptic curve determined by y2=x3+cx+d, where c,d are from the finite field Fq, and then, we give the j-variant definition as follows:(2)jE=17284c34c3+27d2,and j-variant distinguishes the isomorphism class since the necessary and sufficient condition of two isomorphic curves is that they have the same j-variant.The graph structure can embody isogeny-related hard problems. This graph structure is composed of isomorphism classes denoted by nodes and isogenies between curves denoted by edges. The isogeny graphs constructed by different degrees of isogenies are diverse, and the isogeny star is made up of various isogeny graphs while having the same nodes. Literature [31] gives detailed descriptions and visualized depictions of the isogeny star as shown in Figure 2. There are many isogeny paths from one node to another, which may consist of multiple isogenies. When the isogeny star is quite large, finding a path from the initial elliptic curve to the end elliptic curve, respectively, in different isomorphism classes will be rather difficult, which is the isogeny problem.Childs et al. [13] have pointed out that the most efficient traditional algorithm requires exponential time to seek an isogeny between two isogenous elliptic curves. However, they came up with a quantum algorithm to construct an isogeny between two given elliptic curves with the same cardinality in subexponential time. However, the running time is bounded above by exp3/2+O1lnqlnlnq under the generalized Riemann hypothesis. Most importantly, there exists no faster quantum algorithm than in the study by Childs et al. as far as we know. Assume that ϕ is an isogeny mapping from the elliptic curve E to E′, we give the following two difficult problems under quantum computers.Figure 2
Isogeny graphs and isogeny star [31].


### 3.2.1. Supersingular Isogeny (SSI) Problem

Assume that the kernelsP+tQ specifies an isogeny ϕ:E⟶E′, where s and t are chosen randomly from ℤ/leℤ and are not divisible by l. Given the elliptic curve E′ and points ϕP,ϕQ on E′, it is difficult to find a generator T of sP+tQ. It should be specified that given a generator T=sP+tQ, it is trivial to resolve for s,t. In other words, given two elliptic curves E and E′ with the identical cardinality, it is hard to calculate an isogeny ϕ:E⟶E′ utilizing the quantum algorithm in the polynomial time.


### 3.2.2. Extensional Computational Isogeny Problem (ECIP)

GivenP and ϕxP with x,ϕ unknown, where the point P is randomly selected on EN and x is a random number in Fq, it is difficult to calculate ϕ and x in the polynomial time for the quantum computer.


## 3.2.1. Supersingular Isogeny (SSI) Problem

Assume that the kernelsP+tQ specifies an isogeny ϕ:E⟶E′, where s and t are chosen randomly from ℤ/leℤ and are not divisible by l. Given the elliptic curve E′ and points ϕP,ϕQ on E′, it is difficult to find a generator T of sP+tQ. It should be specified that given a generator T=sP+tQ, it is trivial to resolve for s,t. In other words, given two elliptic curves E and E′ with the identical cardinality, it is hard to calculate an isogeny ϕ:E⟶E′ utilizing the quantum algorithm in the polynomial time.


## 3.2.2. Extensional Computational Isogeny Problem (ECIP)

GivenP and ϕxP with x,ϕ unknown, where the point P is randomly selected on EN and x is a random number in Fq, it is difficult to calculate ϕ and x in the polynomial time for the quantum computer.


## 4. Public Key Encryption with Keyword Search

This section introduces public key encryption with keyword search (PEKS) from three aspects: definitions, consistency, and security.


### 4.1. PEKS Definitions

A PEKS scheme consists of four algorithms, namely, setup, PEKS, trapdoor, and test. In the fist PEKS scheme, it only considers the encryption with single keyword search [8]. In practice, a file usually contains many keywords. Therefore, we use the general extended definition of PEKS, which takes a set of keywords as inputs and keeps consistency. The formal constructions are as follows:(i)
Setup1λ: the setup algorithm is performed to generate the user’s keys. With inputting the security parameter λ, this probabilistic polynomial time (PPT) algorithm returns a pair of public/private key pkPEKS,skPEKS for the user.(ii)
PKESpkPEKS,W: the PKES algorithm is performed by a data provider. Taking the public key pkPEKS and a set of keywords W as inputs, this PPT algorithm returns corresponding keywords’ searchable ciphertext CTW.(iii)
TrapdoorskPEKS,kw′: the trapdoor algorithm is executed by a search user. With the secret key skPEKS and a keyword kw′ as inputs, the trapdoor algorithm returns a trapdoor Tkw′ of kw′.(iv)
TestpkPEKS,CTW,Tkw′: the test algorithm is executed by the cloud server. With the searchable ciphertext CTW and trapdoor Tkw′ as inputs, this deterministic algorithm outputs 1 if kw′∈W; otherwise, it outputs 0.It should be noted that the trapdoor algorithm is either deterministic or probabilistic, which is determined by the specific scheme design and security requirements. We only consider the initial form, i.e., the deterministic trapdoor algorithm in this paper.


### 4.2. Consistency

For a PEKS scheme, the most essential and critical requirement is consistency [16]; that is, the returned results from the cloud server should be what the user wants to acquire. Specifically, when the cloud server gets a trapdoor Tkw′ produced by the trapdoor algorithm and ciphertext CTW generated by the PEKS algorithm, we formulate consistency as follows:(i)
TestCTW,Tkw′ always outputs 1 if kw′∈W(ii)
The probabilityPrTestCTW,Tkw′=1 is negligible if kw′∉W


### 4.3. Security Definitions of the Quantum-Resistant PEKS Scheme

The academic community usually defines the security of PEKS as the indistinguishability of keywords under chosen keyword attacks (IND-CKAs). It means that the PEKS ciphertext has the confidentiality of its contained keywords against an adversary who could not obtain the corresponding keyword search trapdoor. Specifically, IND-CKA security allows a PPT adversaryA to get a public key, query the keyword retrieval trapdoor of some desired keywords, and adaptively select two sets of keywords with the same size to challenge. A PEKS scheme is recognized to be secure if A cannot distinguish the two PEKS ciphertexts of two challenge keyword sets.


#### 4.3.1. IND-CKA Security

In the depiction of IND-CKA security, a challengerC and an adversary A will execute interactive games as follows:(i)
Setup phase: On inputting the security parameterλ, a challenger C produces public parameters PP and executes the setup algorithm. Then, they produce receivers’ public/private key pairs pkPEKS,skPEKS and send PP,pkPEKS to the adversary A.(ii)
Query phase 1:A could adaptively release the following keyword search trapdoor query of expected keyword polynomial times in this phase:Trapdoor queryQTkw: for any search trapdoor query of the keyword kw, C produces the corresponding trapdoor CTkw by executing TrapdoorskPEKS,kw and gives back CTkw to A.(iii)
Challenge phase: Having terminated query phase 1,A adaptively selects two challenge keyword sets W1∗,W2∗ with the same number of keywords, i.e., W1∗=W2∗ and transmits these two sets to C. Then, C chooses a random 0/1 bit b and calculates the challenge ciphertext CT∗=CTWc∗by performing the PEKSskPEKS,kw algorithm. Eventually, C transmits CT∗ to A.(iv)
Query phase 2:A can carry on executing the search trapdoor query of any keywords in this phase as in query phase 1, except for the keywords in challenge sets W1∗,W2∗.(v)
Guess phase: At last,A returns a guess bit b′ to challenge ciphertext CT∗.We said that the adversaryA succeeds in the above game if they successfully guess the right bit, i.e., b′=b. Assume Prb′=b denotes the probability of A successfully guessing the bit, the advantage of A winning this game is set as(3)AdvAIND−CKAλ=Prb′=b−12.Definition 1.
A PEKS scheme is recognized to be indistinguishable against chosen keywords attacks if for any PPT adversaryA, and the advantage AdvAIND−CKAλ of succeeding in the above game is nonnegligible.
We use a quantum random oracle to simulate hash functions in the formal security proof of the proposed IsoqurPEKS scheme. However, an obstacle to security proofs is how to produce random values for exponential queries, that is, how to simulate hash function under the quantum random oracle model (QROM). In the next part, we give several preliminary definitions used in the QROM.


#### 4.3.2. Specific Techniques Used in QROM

For a hash functionH:D⟶ℛ simulation, an adversary tosses a superposition φ=∑λxx and random oracle outputs ∑λxHx. If ℛ is tremendous for a quantum simulator, it is hard to give back all random responses of H through computing ∑λxHx. Zhandry [35] put forward a measure by introducing the concept of k-wise independent functions.In the following, we introduce the concept of marginal weight distribution. A weight distribution on a setD is defined by a probability distribution function D:D⟶ℝ that has ∑x∈DDx=1, where Dx≥0 for all x∈D is an assignment on D. We consider a family of functions H:D⟶ℛ for a domain D and range ℛ, denoted by ℋD,ℛ. We give the definition of marginal weight distribution DG of D on HG,ℛ where the weight of a function HG:G⟶ℛ equals to the sum of the weights of all H∈HD,ℛ that is consistent with HG on G. In other words,(4)DGHG=PrHx=HGx,∀x∈G.Definition 2.
Two weight distributionsD1 and D2 on HD,ℛ are called t-wise equivalents if for all G⊂D with size t, and the marginal weight distributions D1,G and D2,G over HG,ℛ are the same.Definition 3.
A functiong is called t-wise independent function if g is equal to a random function for all G⊂D with size t.
Next, we give the definition of semiconstant distribution, which is used to support inserting a random value into a small but essential part of oracle inputs.Definition 4.
The semiconstant distributionSCω over HD,ℛ is defined as follows:(i)
First, a random valuey is selected from ℛ.(ii)
Then, for eachx∈D,Assigny to Hx with probability ω. x is said to be a distinct input to H.Otherwise, assign a random element inℛ to Hx.


## 4.1. PEKS Definitions

A PEKS scheme consists of four algorithms, namely, setup, PEKS, trapdoor, and test. In the fist PEKS scheme, it only considers the encryption with single keyword search [8]. In practice, a file usually contains many keywords. Therefore, we use the general extended definition of PEKS, which takes a set of keywords as inputs and keeps consistency. The formal constructions are as follows:(i)
Setup1λ: the setup algorithm is performed to generate the user’s keys. With inputting the security parameter λ, this probabilistic polynomial time (PPT) algorithm returns a pair of public/private key pkPEKS,skPEKS for the user.(ii)
PKESpkPEKS,W: the PKES algorithm is performed by a data provider. Taking the public key pkPEKS and a set of keywords W as inputs, this PPT algorithm returns corresponding keywords’ searchable ciphertext CTW.(iii)
TrapdoorskPEKS,kw′: the trapdoor algorithm is executed by a search user. With the secret key skPEKS and a keyword kw′ as inputs, the trapdoor algorithm returns a trapdoor Tkw′ of kw′.(iv)
TestpkPEKS,CTW,Tkw′: the test algorithm is executed by the cloud server. With the searchable ciphertext CTW and trapdoor Tkw′ as inputs, this deterministic algorithm outputs 1 if kw′∈W; otherwise, it outputs 0.It should be noted that the trapdoor algorithm is either deterministic or probabilistic, which is determined by the specific scheme design and security requirements. We only consider the initial form, i.e., the deterministic trapdoor algorithm in this paper.


## 4.2. Consistency

For a PEKS scheme, the most essential and critical requirement is consistency [16]; that is, the returned results from the cloud server should be what the user wants to acquire. Specifically, when the cloud server gets a trapdoor Tkw′ produced by the trapdoor algorithm and ciphertext CTW generated by the PEKS algorithm, we formulate consistency as follows:(i)
TestCTW,Tkw′ always outputs 1 if kw′∈W(ii)
The probabilityPrTestCTW,Tkw′=1 is negligible if kw′∉W


## 4.3. Security Definitions of the Quantum-Resistant PEKS Scheme

The academic community usually defines the security of PEKS as the indistinguishability of keywords under chosen keyword attacks (IND-CKAs). It means that the PEKS ciphertext has the confidentiality of its contained keywords against an adversary who could not obtain the corresponding keyword search trapdoor. Specifically, IND-CKA security allows a PPT adversaryA to get a public key, query the keyword retrieval trapdoor of some desired keywords, and adaptively select two sets of keywords with the same size to challenge. A PEKS scheme is recognized to be secure if A cannot distinguish the two PEKS ciphertexts of two challenge keyword sets.


### 4.3.1. IND-CKA Security

In the depiction of IND-CKA security, a challengerC and an adversary A will execute interactive games as follows:(i)
Setup phase: On inputting the security parameterλ, a challenger C produces public parameters PP and executes the setup algorithm. Then, they produce receivers’ public/private key pairs pkPEKS,skPEKS and send PP,pkPEKS to the adversary A.(ii)
Query phase 1:A could adaptively release the following keyword search trapdoor query of expected keyword polynomial times in this phase:Trapdoor queryQTkw: for any search trapdoor query of the keyword kw, C produces the corresponding trapdoor CTkw by executing TrapdoorskPEKS,kw and gives back CTkw to A.(iii)
Challenge phase: Having terminated query phase 1,A adaptively selects two challenge keyword sets W1∗,W2∗ with the same number of keywords, i.e., W1∗=W2∗ and transmits these two sets to C. Then, C chooses a random 0/1 bit b and calculates the challenge ciphertext CT∗=CTWc∗by performing the PEKSskPEKS,kw algorithm. Eventually, C transmits CT∗ to A.(iv)
Query phase 2:A can carry on executing the search trapdoor query of any keywords in this phase as in query phase 1, except for the keywords in challenge sets W1∗,W2∗.(v)
Guess phase: At last,A returns a guess bit b′ to challenge ciphertext CT∗.We said that the adversaryA succeeds in the above game if they successfully guess the right bit, i.e., b′=b. Assume Prb′=b denotes the probability of A successfully guessing the bit, the advantage of A winning this game is set as(3)AdvAIND−CKAλ=Prb′=b−12.Definition 1.
A PEKS scheme is recognized to be indistinguishable against chosen keywords attacks if for any PPT adversaryA, and the advantage AdvAIND−CKAλ of succeeding in the above game is nonnegligible.
We use a quantum random oracle to simulate hash functions in the formal security proof of the proposed IsoqurPEKS scheme. However, an obstacle to security proofs is how to produce random values for exponential queries, that is, how to simulate hash function under the quantum random oracle model (QROM). In the next part, we give several preliminary definitions used in the QROM.


### 4.3.2. Specific Techniques Used in QROM

For a hash functionH:D⟶ℛ simulation, an adversary tosses a superposition φ=∑λxx and random oracle outputs ∑λxHx. If ℛ is tremendous for a quantum simulator, it is hard to give back all random responses of H through computing ∑λxHx. Zhandry [35] put forward a measure by introducing the concept of k-wise independent functions.In the following, we introduce the concept of marginal weight distribution. A weight distribution on a setD is defined by a probability distribution function D:D⟶ℝ that has ∑x∈DDx=1, where Dx≥0 for all x∈D is an assignment on D. We consider a family of functions H:D⟶ℛ for a domain D and range ℛ, denoted by ℋD,ℛ. We give the definition of marginal weight distribution DG of D on HG,ℛ where the weight of a function HG:G⟶ℛ equals to the sum of the weights of all H∈HD,ℛ that is consistent with HG on G. In other words,(4)DGHG=PrHx=HGx,∀x∈G.Definition 2.
Two weight distributionsD1 and D2 on HD,ℛ are called t-wise equivalents if for all G⊂D with size t, and the marginal weight distributions D1,G and D2,G over HG,ℛ are the same.Definition 3.
A functiong is called t-wise independent function if g is equal to a random function for all G⊂D with size t.
Next, we give the definition of semiconstant distribution, which is used to support inserting a random value into a small but essential part of oracle inputs.Definition 4.
The semiconstant distributionSCω over HD,ℛ is defined as follows:(i)
First, a random valuey is selected from ℛ.(ii)
Then, for eachx∈D,Assigny to Hx with probability ω. x is said to be a distinct input to H.Otherwise, assign a random element inℛ to Hx.


## 4.3.1. IND-CKA Security

In the depiction of IND-CKA security, a challengerC and an adversary A will execute interactive games as follows:(i)
Setup phase: On inputting the security parameterλ, a challenger C produces public parameters PP and executes the setup algorithm. Then, they produce receivers’ public/private key pairs pkPEKS,skPEKS and send PP,pkPEKS to the adversary A.(ii)
Query phase 1:A could adaptively release the following keyword search trapdoor query of expected keyword polynomial times in this phase:Trapdoor queryQTkw: for any search trapdoor query of the keyword kw, C produces the corresponding trapdoor CTkw by executing TrapdoorskPEKS,kw and gives back CTkw to A.(iii)
Challenge phase: Having terminated query phase 1,A adaptively selects two challenge keyword sets W1∗,W2∗ with the same number of keywords, i.e., W1∗=W2∗ and transmits these two sets to C. Then, C chooses a random 0/1 bit b and calculates the challenge ciphertext CT∗=CTWc∗by performing the PEKSskPEKS,kw algorithm. Eventually, C transmits CT∗ to A.(iv)
Query phase 2:A can carry on executing the search trapdoor query of any keywords in this phase as in query phase 1, except for the keywords in challenge sets W1∗,W2∗.(v)
Guess phase: At last,A returns a guess bit b′ to challenge ciphertext CT∗.We said that the adversaryA succeeds in the above game if they successfully guess the right bit, i.e., b′=b. Assume Prb′=b denotes the probability of A successfully guessing the bit, the advantage of A winning this game is set as(3)AdvAIND−CKAλ=Prb′=b−12.Definition 1.
A PEKS scheme is recognized to be indistinguishable against chosen keywords attacks if for any PPT adversaryA, and the advantage AdvAIND−CKAλ of succeeding in the above game is nonnegligible.
We use a quantum random oracle to simulate hash functions in the formal security proof of the proposed IsoqurPEKS scheme. However, an obstacle to security proofs is how to produce random values for exponential queries, that is, how to simulate hash function under the quantum random oracle model (QROM). In the next part, we give several preliminary definitions used in the QROM.


## 4.3.2. Specific Techniques Used in QROM

For a hash functionH:D⟶ℛ simulation, an adversary tosses a superposition φ=∑λxx and random oracle outputs ∑λxHx. If ℛ is tremendous for a quantum simulator, it is hard to give back all random responses of H through computing ∑λxHx. Zhandry [35] put forward a measure by introducing the concept of k-wise independent functions.In the following, we introduce the concept of marginal weight distribution. A weight distribution on a setD is defined by a probability distribution function D:D⟶ℝ that has ∑x∈DDx=1, where Dx≥0 for all x∈D is an assignment on D. We consider a family of functions H:D⟶ℛ for a domain D and range ℛ, denoted by ℋD,ℛ. We give the definition of marginal weight distribution DG of D on HG,ℛ where the weight of a function HG:G⟶ℛ equals to the sum of the weights of all H∈HD,ℛ that is consistent with HG on G. In other words,(4)DGHG=PrHx=HGx,∀x∈G.Definition 2.
Two weight distributionsD1 and D2 on HD,ℛ are called t-wise equivalents if for all G⊂D with size t, and the marginal weight distributions D1,G and D2,G over HG,ℛ are the same.Definition 3.
A functiong is called t-wise independent function if g is equal to a random function for all G⊂D with size t.
Next, we give the definition of semiconstant distribution, which is used to support inserting a random value into a small but essential part of oracle inputs.Definition 4.
The semiconstant distributionSCω over HD,ℛ is defined as follows:(i)
First, a random valuey is selected from ℛ.(ii)
Then, for eachx∈D,Assigny to Hx with probability ω. x is said to be a distinct input to H.Otherwise, assign a random element inℛ to Hx.


## 5. Problem Formulation

In this section, we describe the system architecture of IsoqurPEKS, the threat model of each entity, and the design goals of this paper.


### 5.1. System Model

The system includes the following parties: cloud server (CS), data providers (DPs), and request users (RUs) as depicted in Figure3. The characteristics and function of each party are depicted as follows:(i)
Data providers (DPs): Each DP produces his or her public key and private key upon inputting the security parameter. Moreover, the DP extracts keywords from files, encrypts files using symmetric encryption, and computes the searchable keyword ciphertexts associated with corresponding files. Finally, the DP stores encrypted files and searchable ciphertexts on the CS.(ii)
RUs: Request users utilize targeted keywords to generate search trapdoors and send them to the CS for information retrieval operation. Then, RUs decrypt desired files when receiving matched ciphertexts from CS.(iii)
CS: The cloud server has almost unlimited storage and computing power in the PEKS system. The CS is in charge of storing encrypted files and searchable ciphertexts received from DPs. Then, the CS addresses search queries and returns corresponding searching results ciphertexts to RUs.Figure 3
System model of the proposed IsoqurPEKS scheme.In our proposed IsoqurPEKS scheme, the data provider first extracts keywords (e.g., using such as Porter temming algorithm [36]) from documents to be uploaded. Then, they use the targeted user’s public key and a symmetric key to generate a searchable keyword ciphertext and corresponding encrypted document, which will be transferred to the cloud server (CS). When a request user (RU) searches some documents, including a specific keyword, the RU utilizes their secret key to produce a keyword search trapdoor and transfers it to the CS. Finally, the CS returns matched encrypted documents by a verifying equation through inputting a trapdoor and searchable ciphertexts.


### 5.2. Threat Model

In our scheme, we suppose that DPs honestly follow the PEKS algorithm to produce searchable ciphertexts for authorized users and transmits these ciphertexts to the CS.RUs are assumed to be semihonest adversaries. They honestly execute the scheme when conducting a search query while may attempt to know some sensitive information associated with ciphertexts and queries, respectively, produced by other DPs and RUs.The CS is supposed to be honest but curious which will honestly perform the test algorithm and has an interest in obtaining desired information of other parties through either intermediate values or computation results.


### 5.3. Design Goals

Our goal is to propose an isogeny-based quantum-resistant PEKS scheme equipped with functions and security requirements.(i)
Data privacy: nobody could get information about searchable ciphertexts uploaded and encrypted by DPs. In other words, the searchable ciphertext remains confidential.(ii)
Access pattern hiding: Retrieval results of a query such as encrypted files matching the user’s query are concealed from the CS.(iii)
Quantum attack resilience: There does not exist a polynomial-time quantum algorithm that could acquire RUs’ private information such as private secrets and uploaded plaintexts by DPs.


## 5.1. System Model

The system includes the following parties: cloud server (CS), data providers (DPs), and request users (RUs) as depicted in Figure3. The characteristics and function of each party are depicted as follows:(i)
Data providers (DPs): Each DP produces his or her public key and private key upon inputting the security parameter. Moreover, the DP extracts keywords from files, encrypts files using symmetric encryption, and computes the searchable keyword ciphertexts associated with corresponding files. Finally, the DP stores encrypted files and searchable ciphertexts on the CS.(ii)
RUs: Request users utilize targeted keywords to generate search trapdoors and send them to the CS for information retrieval operation. Then, RUs decrypt desired files when receiving matched ciphertexts from CS.(iii)
CS: The cloud server has almost unlimited storage and computing power in the PEKS system. The CS is in charge of storing encrypted files and searchable ciphertexts received from DPs. Then, the CS addresses search queries and returns corresponding searching results ciphertexts to RUs.Figure 3
System model of the proposed IsoqurPEKS scheme.In our proposed IsoqurPEKS scheme, the data provider first extracts keywords (e.g., using such as Porter temming algorithm [36]) from documents to be uploaded. Then, they use the targeted user’s public key and a symmetric key to generate a searchable keyword ciphertext and corresponding encrypted document, which will be transferred to the cloud server (CS). When a request user (RU) searches some documents, including a specific keyword, the RU utilizes their secret key to produce a keyword search trapdoor and transfers it to the CS. Finally, the CS returns matched encrypted documents by a verifying equation through inputting a trapdoor and searchable ciphertexts.


## 5.2. Threat Model

In our scheme, we suppose that DPs honestly follow the PEKS algorithm to produce searchable ciphertexts for authorized users and transmits these ciphertexts to the CS.RUs are assumed to be semihonest adversaries. They honestly execute the scheme when conducting a search query while may attempt to know some sensitive information associated with ciphertexts and queries, respectively, produced by other DPs and RUs.The CS is supposed to be honest but curious which will honestly perform the test algorithm and has an interest in obtaining desired information of other parties through either intermediate values or computation results.


## 5.3. Design Goals

Our goal is to propose an isogeny-based quantum-resistant PEKS scheme equipped with functions and security requirements.(i)
Data privacy: nobody could get information about searchable ciphertexts uploaded and encrypted by DPs. In other words, the searchable ciphertext remains confidential.(ii)
Access pattern hiding: Retrieval results of a query such as encrypted files matching the user’s query are concealed from the CS.(iii)
Quantum attack resilience: There does not exist a polynomial-time quantum algorithm that could acquire RUs’ private information such as private secrets and uploaded plaintexts by DPs.


## 6. Proposed IsoqurPEKS

Our proposed scheme consists of four algorithms: setup, PEKS, trapdoor, and test. The setup algorithm is executed by a user and generates the user’s public and private key pair using an isogeny and a random number by inputting a security parameter. ThePEKS algorithm is performed by data providers and used to produce the searchable ciphertext against quantum computer attacks. To obtain some files containing specific keywords from the cloud server, a user utilizes their secret to perform the trapdoor algorithm to output a searchable trapdoor. Finally, the cloud server inputs the trapdoor, the user’s public key, and searchable ciphertext and then returns correct ciphertexts to the user by the test algorithm(i)
Setupλ: the setup algorithm is executed by a user to produce a pair of private key and public key.First, the user selects an elliptic curveE with an order N where P1,P2 are two base points on the additive cyclic group EN.Then, they randomly chooseα∈ℤN∗ and generate an l-isogeny ϕ:E⟶E′ with its dual l-isogeny ϕ^:E′⟶E and two bilinear mappings e,e′, respectively, on EN,E′N.They also produce two secure cryptographic hash functionsH′:0,1∗⟶E′N and h:0,1∗⟶0,1lgN.Finally, they computeϕαP1,ϕαP2 and set PK=PK1:=ϕαP1,PK2:=ϕαP2,P1,P2,e,e′,H′,h,SK=α,ϕ,ϕ^.(ii)
PEKSPK,W: when a data provider transmits encrypted files to the cloud server for secure storage and retrieval, they extract keywords W=kw1,…,kwn from the file to upload and perform the following steps:For eachkwi∈A, the DP randomly selects r,s∈ℤN∗ and uses the random numbers and the authorized user’s public key to compute searchable ciphertexts C0=rP1+sP2, ti=e′PK1,rH′kwi⋅e′PK2,sH′kwi, Ci=hti.Then, they initialize a history-independent arrayℒ to store ciphertexts Ci,i∈1,…,n.Finally, this algorithm outputs PEKS ciphertextsAE=C0,ℒ and sends them together with the corresponding encrypted file to the cloud server.(iii)
TrapdoorSK,kw: if a user desires to request files including the keyword kw′, they utilize their private key α,ϕ^ to compute a trapdoor Tkw′=ϕ^αH′kw′ and transfer the trapdoor Tkw′ to the cloud server.(iv)
TestPK,AE,Tkw′: given public key PK, a PEKS ciphertext AE=C0,ℒ, and a trapdoor Tkw′, the cloud server performs steps as follows:It initializes an empty setS and verifies whether heC0,Tkw′∈ℒ.IfheC0,Tkw′∈ℒ, the CS adds the corresponding encrypted file to S; otherwise, it searches the next ciphertext.Finally, the CS returnsS to the user.What should be specified is that our main work focuses on security against quantum attacks, and we suppose keywords are uncertain and unlimited. Thus, we do not take into account the keyword guessing attack.


### 6.1. Consistency

According to the introduction in Section B, we analyze the correctness of isoqurPEKS. GivenTkw′ produced by the trapdoor algorithm and C0,ℒ produced by the PEKS algorithm, we have(5)eC0,Tkw′=erP1+sP2,ϕ^αH′kw′,=e′ϕrP1+sP2,αH′kw′,=e′ϕrP1,αH′kw′⋅e′ϕsP2,αH′kw′,=e′PK1,rH′kw′⋅e′PK2,sH′kw′.On the other hand,Ci=he′PK1,rH′kwi⋅e′PK2,sH′kwi. Thus, the equation heC0,Tkw′∈ℒ if there exists a Ct,t∈1,2,…,n which satisfies kwt=kw′.


## 6.1. Consistency

According to the introduction in Section B, we analyze the correctness of isoqurPEKS. GivenTkw′ produced by the trapdoor algorithm and C0,ℒ produced by the PEKS algorithm, we have(5)eC0,Tkw′=erP1+sP2,ϕ^αH′kw′,=e′ϕrP1+sP2,αH′kw′,=e′ϕrP1,αH′kw′⋅e′ϕsP2,αH′kw′,=e′PK1,rH′kw′⋅e′PK2,sH′kw′.On the other hand,Ci=he′PK1,rH′kwi⋅e′PK2,sH′kwi. Thus, the equation heC0,Tkw′∈ℒ if there exists a Ct,t∈1,2,…,n which satisfies kwt=kw′.


## 7. Security Proof

In this section, we will prove IND-CKA security of the IsoqurPEKS instantiation under the QROM, and the proof method of which has been used in lecture [37].Theorem 1.
For the advantageAdvSSIℛ of the computational isogeny problem and the advantage AdvIsoqurPEKSIND−CKAA of A breaking IsoqurPEKS’s security, we have the following equation under the quantum random oracle model:(6)AdvIsoqurPEKSIND−CKAA≤AdvSSIR1/234qh+14+2qh1/2,where qh is the maximum of hash function queries.Proof.
GameG0: this game is executed by the adversary A who tries to break the real scheme as 1 and the challenger C. Specifically, C responds the trapdoor query according to the trapdoor algorithm:(i)
Trapdoor queryQTkw′: Given a query keyword kw′, C computes Tkw′←TrapdoorSK,kw′ and gives back Tkw′ to A.
Assume that the adversaryA’s advantage in this game is AdvA,G0=∈ and the challenger C knows related secret values. We have the advantage of A breaking IND-CKA in G0 is the same as that in the real word:(7)AdvA,G0=AdvA,Real.
GameG1: The game G1 is identical to G0 except for the challenge ciphertext CT∗ generation in the challenge phase. What should be specified is that the public keys are changed into ϕ^xQ1,ϕ^xQ2,Q1,Q2 and that private keys are x,ϕ^,ϕ, where x∈Fq, Q1,Q2∈E′N are two points and ϕ^:E′N⟶EN is an isogeny. These settings correspond to PK and SK of the proposed scheme in Section 6. Therefore, the challenge ciphertext is accordingly transformed into C0∗=rϕ^xQ1+sϕ^xQ2, ti∗=he′Q1,rH′kwie′Q2,sH′kwi,Ci∗=hti∗, where r,s are two random numbers in Fq, H′:0,1∗⟶E′N is a hash function, and h:0,1∗⟶0,1lgN is a general hash function. This transformation does not change the searchable ciphertext computing rule, and no more information has been leaked; thus, we have(8)AdvA,G1=AdvA,G0.
GameG2: In this game, we introduce the rule of aborting. Let ω be selected from (0, 1), and W is a subset of D where kw˜ is randomly chosen from D and placed in W with an independent probability ω. W0∗,W1∗ are two challenge keyword sets chosen by A. G2 aborts if two challenge keyword sets W0∗,W1∗⊊⊊, A queries H′kw where kw∈W, and we have(9)AdvA,G2≥ω1−ωqH′AdvA,G2,≥ωAdvA,G2−ω2qH′.
Before continuing to the next simulation, we give the following lemmas [35] to depict QROM.Lemma 1.
LetA be an adversary with the capacity of quantum computing and makes q queries to an random oracle H:D⟶ℛ. We depict H using some weight distribution D; that is, for each z, the probability value PrH←DH=z is a linear combination of PrH←DHri=di,i∈1,…,2s for all possible ri and di.Lemma 2.
Suppose there is a2qi-wise independent function. In that case, it can be successfully simulated by a quantum algorithm ℛ when any quantum adversary A makes qi queries to random oracles ℬi, which could have the same output values while making no queries.According to the above lemmas, we can see that quantum random oracles are simulated by a quantum algorithmℛ in the polynomial time. This technique can simulate hash function queries and responses of the H′-query and h-query in the IsoqurPEKS’s security proof.In addition, how to insert some randomly selected values to the intended quantum oracle queries is another problem of security proofs under QROM. Then, we have Lemma3 as follows.Lemma 3.
The The distribution of outputs of a quantum algorithm makingqHqueries to an oracle drawn from the semi-constant distribution ω is at most a distance3/8qH4ω2away from the case when the oracle is drawn from the uniform distribution.We assume that if an adversaryA queries the inserted value of corresponding oracle outputs, then the simulation is successful with the probability ϵ. Furthermore, the probability of successful simulations is ∈ω−3/8qH4ω2 if A utilizes one of the values with the probability ω, where the choice of ω could decide the success probability. We employ this solution to insert a hard-to-be-resolved SSI problem into a hash function h output in the IsoqurPEKS’s security proof.GameG3: This game introduces a quantum random oracle. In other words, the computing method of the hash function H′⋅ is changed. η is set as H′kw∗ for all kw∗∈W, and hash outputs are randomly selected for other queries. In this case, H′ is distributed according to SCω. According to Lemma 3, the distance of output distribution in G3 is 3/8qh+14ω2 from that in G2. Therefore, we have(10)AdvA,G2−AdvA,G3≥3/8qh+14ω2.GameG4: In game G4, the rule of producing challenge ciphertexts is changed and Ci∗,i=1,…,n are randomly selected instead of computing by hCi∗. The final challenge ciphertext is independent of the challenge keyword sets. Therefore, we have(11)AdvA,G4=0.We construct an algorithmℛ of the isogeny problem with the advantage AdvWCSSIℛ. We suppose that ℛ has quantum access to random oracles H′^:W⟶E′N,H′′^:W⟶0,1 and h^:GT⟶Fq∗ where the probability of H′′^ outputting 1 is ω. Let W be the set of kw∗ such that H′kw∗=1. We can infer that the above conditions are equivalent to G4. According to Lemma 2, ℛ can simulate H′^,H′′^ and h^ by separately using a qH′+1-wise and a qh+1-wise independent functions without oracle queries. ℒ is an initially empty list held by ℛ.(i)
Setting of public parameters. Assume that an adversaryA transmits two challenge sets W0∗=w0,1∗,w0,2∗,…,w0,n∗ and W1∗=w1,1∗,w1,2∗,…,w1,n∗ to the challenger C, where n is a positive integer. Then, given P,ϕx−1P and Q1,Q2,ϕ^xQ1,ϕ^xQ2, C sets pk=ϕ^xQ1,ϕ^xQ2,Q1,Q2 and sk are correspondingly x,ϕ^,ϕ, where the isogeny ϕ is mapping from the elliptic curve E to the elliptic curve E′, ϕ^ is its dual isogeny, P,ϕ^xQ1,ϕ^xQ2 are points on E, and Q1,Q2,ϕx−1P are points on E′. ℛ receives the hard problem instance ϕ^xQ1,ϕ^xQ2,Q1,Q2. Then, ℛ transfers the public parameter E,E′ and PK=ϕ^xQ1,ϕ^xQ2,Q1,Q2 to A.(ii)
Challenge ciphertext simulation.ℛ chooses random r∗,s∗ and computes C0∗=r∗ϕ^xQ1+s∗ϕ^xQ2,η as the challenge ciphertext.(iii)
H′-query. Upon receiving kw, ℛ sets the outputs of H′ as follows:(12)H′kw=ζ,ifH′^kw=1,H′^kw,otherwise.(iv)
h-query. Upon receiving Ci, ℛ simulates h by setting hCi=h^Ci.(v)
Query simulation.Hash queryQH′kw: It uniformly selects a random αi and computes αiϕx−1P1. Then, C reserves kw,α,αiϕx−1P1 in the H′-list, and the αiϕx−1P1 is transferred to A.Trapdoor queryQTkw′: Given a query keyword kw, C retrieves kw′ in the H′-list and uses α in the H′-list to compute αiP1 if kw′ is in the H′-list; otherwise, it uniformly chooses an α and computes αP1. Finally, C returns αiP1 to A.


### 7.1. Success Probability Analysis

IfA performs queries contained in W to H′, A could distinguish the simulation environment from the real environment. Nevertheless, these events will not appear due to the game hopping in G2. Then, A succeeds in the game with the advantage AdvA,G5. Hence, we have(13)AdvA,G4−AdvA,G3≤AdvSSIℛ.Then, by combining advantages, we have(14)AdvIsqurPEKSA≤1ωAdvSSIR+ω38qH′+14+qH′.Because right side of the equation is minimized whenω=AdvSSIℛ/3/8qH′+14+qH′, we have(15)AdvIsoqurPEKSIND−CKAA≤AdvSSIR1/234qH′+14+2qH′1/2.


## 7.1. Success Probability Analysis

IfA performs queries contained in W to H′, A could distinguish the simulation environment from the real environment. Nevertheless, these events will not appear due to the game hopping in G2. Then, A succeeds in the game with the advantage AdvA,G5. Hence, we have(13)AdvA,G4−AdvA,G3≤AdvSSIℛ.Then, by combining advantages, we have(14)AdvIsqurPEKSA≤1ωAdvSSIR+ω38qH′+14+qH′.Because right side of the equation is minimized whenω=AdvSSIℛ/3/8qH′+14+qH′, we have(15)AdvIsoqurPEKSIND−CKAA≤AdvSSIR1/234qH′+14+2qH′1/2.


## 8. Comparison and Analysis

To the best of our knowledge, there is no isogeny-based quantum-resistant PEKS scheme currently. There are many public encryption schemes with keyword search [38–45], while they cannot withstand quantum attacks since these schemes are based on classical DL assumption, DBDH assumption, or CBDH assumption. In this section, we first compare IsoqurPEKS with existing PEKS schemes regarding security properties. Then, we compare IsoqurPEKS with the other eight PEKS schemes from aspects of computation and communication costs.Table2 indicates the comparison results among the proposed IsoqurPEKS scheme and its counterpart PEKS schemes concerning security properties. The proposed IsoqurPEKS scheme is based on isogeny hard assumption, which has been proved in Section 7 under the quantum random oracle model. Thus, our scheme can resist quantum attacks. Moreover, our construction does not require a trusted authority to generate secret keys, which some PEKS schemes require it.Table 2
Comparison of security properties with other PEKS schemes.
SchemesQRNTASecurityXLZCT20 [38]××SMWXLYY20 [39]×✓ROMZQDT21 [40]×✓ROMZLW19 [41]×✓ROMNT21 [42]×✓ROMMHFF20 [43]××SMSBSL21 [44]××ROMWDC20 [45]××SMIsoqurPEKS✓✓QROMQR: quantum resistance, NTA: no trusted model, ✓: the scheme supports corresponding features,×: the scheme fails in supporting the corresponding feature, SM: standard model, ROM: random oracle model, QROM: quantum random oracle model.Subsequently, we analyze the computational complexity with respect to searchable ciphertext generation, trapdoor generation, and testing. We only consider the time-consuming operations, e.g., hash-to-pointTH, bilinear pairing operation TBP, general multiplication over point TGM, modular exponentiation operation TEX, and isogeny operation TIso. According to [46], we get the running time of different operations implemented on a Raspbian GNU/Linux 8 system with ARMv7 Processor rev 4 1.2 GHz. Because the isogeny operation happens in the trapdoor generation process, which is performed by the cloud server, we use the isogeny (i.e., group action) computing time as described in [47]. Above all, we have TH=47.312ms,TBP=30.829ms,TGM=0.098ms,TEX=20.352ms,TIso=40.8ms. Table 3 shows the different operation comparisons of nine PEKS schemes. In the PEKS phase, the data provider generates one searchable ciphertext for each keyword by computing C0=rP1+sP2,ti=e′PK1,rH′kwi⋅e′PK2,sH′kwi which requires two bilinear pairing operations and two scalar multiplication operations. In the trapdoor generation phase, the user computes Tkw′=ϕ^αH′kw′, which requires one scalar multiplication operation and one isogeny operation. When the server searches matched ciphertexts, it computes eC0,Tkw′ and heC0,Tkw′ which requires one bilinear pairing operation and one general hash function operation. The comparison results in Figure 4 indicate that IsoqurPEKS consumes the least time in ciphertext generation, trapdoor generation, and testing processes among these nine PEKS schemes.Table 3
Operations comparison of PEKS schemes.
SchemesCiphertext generationTrapdoor generationTestingXLZCT20 [38]4TEX52TEX+5TGM49TEXWXLYY20 [39]4TEX1TEX2TEXZQDT21 [40]TBP+2TEX+THTBP+TEX+THTBP+TEX+THZLW19 [41]7TEX6TEX6TBPNT21 [42]2TBP+5TGM+Th2TBP+5TGM+Th2TBP+2TEX+2TGMMHFF20 [43]3TBP+13TEXTEX+4Th4TBP+4TEXSBSL21 [44]TBP+3TH+3TGM2TH+2TGMTBP+4THWDC20 [45]4TEXTBP+2TEX2TBPIsoqurPEKS2TBP+2TGMTGM+TIsoTBPTH: running time of a hash-to-point operation, TBP: running time of a bilinear pairing operation, TGM: running time of a general multiplication over point, TEX: running time of a modular exponentiation operation, TIso: running time of an isogeny operation.Figure 4
Running time comparison.In addition, we also perform a comparison with respect to the communication complexity of single document/keyword encryption and search. Since the elliptic curve point group is defined over a finite fieldFq, we set p as a 512-bit element. For pairing-based schemes, the pairing operation is e:G1×G1⟶GT where points in G1 and GT are 1024-bit elements. The general hash function is SHA256 in implementation. Thus, the output of h is a 256-bit string. The comparison results are depicted in detail in Table 4. For the searchable ciphertext and trapdoor production of a single keyword in IsoqurPEKS, it outputs one point C0, one hash value hti, and one point ϕ^αH′kw′. Thus, the communication cost of the proposed scheme is 160 bytes and 128 bytes, respectively, which requires the least communication width for keywords trapdoor search and giving back matched ciphertexts.Table 4
Communication costs comparison of PEKS schemes (bytes).
SchemesCiphertextTrapdoorXLZCT20 [38]5G1+GT=7685G1=640WXLYY20 [39]GT=128G1=128ZQDT21 [40]q+G1=192G1=128ZLW19 [41]q+5G1=704G1=128NT21 [42]2G1+GT=384G1+GT=256MHFF20 [43]q+4G1+2GT=832q+G1=192SBSL21 [44]q+G1=704G1=128WDC20 [45]2G1=256GT=128IsoqurPEKSh+G1=160GT=128G1: the byte size of a point in G1. GT: the byte size of a point in GT. q: the byte size of an element in q. h: the output byte length of the general hash function h⋅.


## 9. Conclusion

This paper introduces a new method for the quantum-resistant public encryption scheme with keyword search construction and establishes the hard assumption of elliptic curve isogeny computation. Our proposed scheme, IsoqurPEKS, could fight against attacks of quantum adversaries and is provably secure under the quantum random oracle model. We give formal security proof of IsoqurPEKS and analyze its security properties by comparing it with the other eight PEKS schemes. As far as we know, IsoqurPEKS is not only the first isogeny-based quantum-resistant PEKS scheme but also the most efficient scheme in terms of computation and communication costs compared with the listed current eight PEKS schemes. Since IsoqurPEKS is designed under the assumption that keywords cannot be enumerated, our subsequent work is putting forward an isogeny-based and quantum-resistant PEKS scheme against keyword guessing attack under the assumption that keywords could be listed in the polynomial time.



---

*Source: 8453228-2022-11-01.xml*