# An Efficient Searchable Public-Key Authenticated Encryption for Cloud-Assisted Medical Internet of Things

Authors: Tianyu Chi; Baodong Qin; Dong Zheng
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

In recent years, it has become popular to upload patients’ medical data to a third-party cloud server (TCS) for storage through medical Internet of things. It can reduce the local maintenance burden of the medical data and importantly improve accuracy in the medical treatment. As remote TCS cannot be fully trusted, medical data should be encrypted before uploading, to protect patients’ privacy. However, encryption makes search capabilities difficult for patients and doctors. To address this issue, Huang et al. recently put forward the notion of Public-key Authenticated Encryption with Keyword Search (PAEKS) against inside keyword guessing attacks. However, the existing PAEKS schemes rely on time-consuming computation of parings. Moreover, some PAEKS schemes still have security issues in a multiuser setting. In this paper, we propose a new and efficient PAEKS scheme, which uses the idea of Diffie-Hellman key agreement to generate a shared secret key between each sender and receiver. The shared key will be used to encrypt keywords by the sender and to generate search trapdoors by the receiver. We prove that our scheme is semantically secure against inside keyword guessing attacks in a multiuser setting, under the oracle Diffie-Hellman assumption. Experimental results demonstrate that our PAEKS scheme is more efficient than that of previous ones, especially in terms of keyword searching time.


---

## Body

## 1. Introduction

In today’s society, almost all medical service providers will use some form of electronic medical record system [1]. Specifically, medical Internet of things (MIoT) has become a new technology to gather data from patients by small wearable devices or implantable sensors. With the increasing number of medical data, the burden of hospital storage equipment is heavy, and it needs a professional person to maintain. If the hardware storage device is damaged and data is lost due to other force majeure factors, it will lead to very serious consequences. The most important way to solve this problem is to upload the data to the third-party cloud server (TCS). However, after the data is uploaded to the TCS, the patient’s privacy will not be guaranteed. Once the cloud server managers or external malicious attackers steal the data, it will cause data leakage and other problems [2].In order to solve the problem of data security, the best way is to encrypt the data and then upload the result to TCS. But when medical service providers want to retrieve the electronic medical records of patients, it becomes more difficult. First, doctors need to download all encrypted data to a local server and then decrypt it locally. After that, they can search for the desired results in the plaintext medical data. However, this process is very cumbersome and impractical for most applications. Due to the powerful cloud computing, medical institutions hope that the cloud server can complete the retrieval function instead of doing it themselves. But if the key is sent to the cloud server, the patient’s private data still has the risk of exposure.To address the above security issues, the conception of (symmetric-key) searchable encryption (SE) was proposed by Song et al. [3]. It is a powerful technology that allows the cloud server to search on encrypted data using some search trapdoors generated by the local data users. In 2004, Boneh et al. [4] proposed a public-key version of SE, namely, Public-key Encryption with Keyword Search (PEKS). This scheme embeds keywords in public-key encryption and is very suitable for scenarios of a multiuser data sharing setting, e.g., medical data sharing. There are three parties in the PEKS scheme: cloud server, data sender, and data receiver. The sender (e.g., patient) has a lot of privacy files Fi and wants to share them with the receiver (e.g., doctor). First, the sender extracts the keyword wi from each file Fi, encrypts the keyword with the PEKS scheme, and then encrypts each file with other encryption schemes (not necessarily the same as the PEKS scheme). Let the keyword cipher text be Cwi. The sender uploads all cipher texts to the TCS. In order to search whether there is a document containing the keyword w in the encrypted document, the receiver generates a search trapdoor Tw of the keyword w and sends the trapdoor to the cloud server. After the server receives Tw, it checks whether each keyword cipher text matches with the search trapdoor. If so, it indicates that the corresponding encrypted document must contain the desired keyword. After that, the results are returned to the receiver, and the receiver can get the required plaintext data by decrypting the encrypted documents.As mentioned in Figure1, we will apply searchable encryption to telemedicine services, where the patient is the sender and the medical service provider is the receiver. Each patient can encrypt and upload their own electronic medical record to the cloud server. When the patient wants to see a doctor remotely, the doctor can retrieve the medical data information related to some disease on the third-party cloud server according to the keyword information of the patient. In this process, doctors will only get data related to a certain disease and will not expose other information (such as name) of patients.Figure 1
Telemedicine service based on searchable encryption.However, PEKS inherently has a disadvantage to resist against keyword guessing attacks (KGA). Ideally, a keyword space can be considered infinite. In practice, however, this is not the case. In real life, users often use a limited number of keywords because of their living habits, which leads to the transformation of the original polynomial space into an affixed and low-entropy space. In this case, the adversary can guess the keywords contained in the searching trapdoor as follows: First, the adversary guesses all the keyword spaces of the user and then generates keyword cipher text one by one. The adversary checks the trapdoor requested by the user one by one with keyword cipher texts generated by itself. If there is coincidentally the same situation, the adversary can obtain the keyword information retrieved by the user, thus exposing the privacy of the user. This kind of attack can be easily mounted by the cloud server, as the cloud server has users’ searching trapdoors. Such attack is often called inside keyword guessing attacks (IKGA).To resist against KGA is very challenging. Recently, many methods [5–11] were proposed to prevent KGA on PEKS schemes; however, most of them were later proven insecure [12–15]. In 2017, Huang and Li [16] proposed a new primitive, namely, Public-key Authenticated Encryption with Keyword Search (PAEKS), to solve the problem of inside KGA. In PAEKS, the data sender not only encrypts a keyword but also authenticates it, so that a search trapdoor can only match with the corresponding data sender. PAEKS is also applicable to cloud-assisted MIoT, as in general, the doctor just searches on a designated patient’s medical data. However, the proposed concrete PAEKS scheme still has some security issues [17–19]. In particular, Noroozi and Eslami [18] pointed out that it cannot handle multiuser settings and provided an improvement security model for PAEKS in a multiuser setting.


### 1.1. Our Contribution

In this paper, we research on new and efficient construction of PAEKS schemes in a multiuser setting for cloud-assisted MIoT. Our main contributions are as follows:(i)
We observe that in PAEKS, both the data sender and data receiver hold a pair of public/secret keys. If they can compute a shared key without any interaction, then the shared key can be viewed as a secret key of a symmetric searchable encryption scheme. Inspired by this, we propose an efficient PAEKS scheme, which involves the (noninteractive) Diffie-Hellman key exchange scheme to compute the shared key and Song et al.’s SSE scheme to encrypt keywords. It removes the usage of time-consuming operation of pairing in previous PAEKS schemes(ii)
We show that our scheme is semantically secure against IKGA in a multiuser setting under the oracle Diffie-Hellman assumption [20]. Specially, it satisfies both cipher text indistinguishability and trapdoor indistinguishability(iii)
We compare our scheme with some related PAEKS scheme in terms of security and computation efficiency and also do some experiments to demonstrate the efficiency of our schemes for protecting the privacy of cloud-assisted MIoT data. Experiment results show that our scheme is more efficient than that of previous ones, especially in terms of keyword searching time


### 1.2. Paper Organization

In the next section, we will briefly introduce some cryptographic primitives. Our main construction of the PAEKS scheme and its security proof are given in Section3. In Section 4, we compare the efficiency of our scheme with that of other related PAEKS schemes. Finally, we summarize the paper in Section 5.


## 1.1. Our Contribution

In this paper, we research on new and efficient construction of PAEKS schemes in a multiuser setting for cloud-assisted MIoT. Our main contributions are as follows:(i)
We observe that in PAEKS, both the data sender and data receiver hold a pair of public/secret keys. If they can compute a shared key without any interaction, then the shared key can be viewed as a secret key of a symmetric searchable encryption scheme. Inspired by this, we propose an efficient PAEKS scheme, which involves the (noninteractive) Diffie-Hellman key exchange scheme to compute the shared key and Song et al.’s SSE scheme to encrypt keywords. It removes the usage of time-consuming operation of pairing in previous PAEKS schemes(ii)
We show that our scheme is semantically secure against IKGA in a multiuser setting under the oracle Diffie-Hellman assumption [20]. Specially, it satisfies both cipher text indistinguishability and trapdoor indistinguishability(iii)
We compare our scheme with some related PAEKS scheme in terms of security and computation efficiency and also do some experiments to demonstrate the efficiency of our schemes for protecting the privacy of cloud-assisted MIoT data. Experiment results show that our scheme is more efficient than that of previous ones, especially in terms of keyword searching time


## 1.2. Paper Organization

In the next section, we will briefly introduce some cryptographic primitives. Our main construction of the PAEKS scheme and its security proof are given in Section3. In Section 4, we compare the efficiency of our scheme with that of other related PAEKS schemes. Finally, we summarize the paper in Section 5.


## 2. Preliminaries

In this section, we recall some basic conceptions of cryptographic primitives that will be used in this paper, including cyclic group, hardness assumption, pseudorandom functions, syntax of PAEKS, and its security model.


### 2.1. Cyclic Group

LetG be a group with order p. We say that G is a cyclic group, if the group G can be generated by a single element g∈G. That is, every element h∈G has the form h=gx for some exponent x∈ℤp. We call g to be a generator of the group. In our scheme, we use a cyclic group with a prime order; i.e., p is a prime. In this case, any group element except the identity will be a generator.


### 2.2. Oracle Diffie-Hellman (ODH) Problem [20]

LetG be a cyclic group with prime order p and a generator g. Let H be a hash function from G to some n-bit length space 0,1n. The ODH problem states that given a tuple g,gx,gy,T and an oracle Ogx·, to decide whether T is Hgxy or a random string from 0,1n, here, x and y are randomly chosen from ℤp, and the oracle returns Hhx for each h∈G. Let A be any probabilistic polynomial time (PPT) algorithm. We say that A breaks the ODH problem over group G and H with advantage at most ϵodh, if
(1)PrAOgx·g,gx,gy,Hgxy=1−PrAOgx·g,gx,gy,T=1<ϵodh.Definition 1 (ODH assumption).
We say that the ODH assumption holds over groupG and H, if for any PPT algorithm A, its advantage ϵodh in solving the ODH problem is negligible in κ (the bit length of p).


### 2.3. Pseudorandom Functions (PRFs)

A pseudorandom function is a family of functions such that for a random choice from the family, its input/output behavior is computationally indistinguishable from that of a random function. A formal definition of PRFs is given below.Definition 2 (PRFs).
Letf:K×X⟶Y be a family of functions indexed with key space K from X to Y. We say that f is an ϵf−securePRFs if
(1)
Given a keyk∈K and an input x∈X, there is an efficient algorithm to compute the output y=fkx(2)
For any PPT algorithmA that makes at most polynomial number of oracle queries, the following advantage is at most ϵf: where F=f:X⟶Y and the oracles are given an input x∈X and output the corresponding image of the function.
(2)PrAOgx·=1:k⟵K−PrAOgx·=1:f⟵F≤ϵf,The above definition indicates that, given any polynomial number of valid input/output pairsxi,fkxi, no PPT adversary can predicate fkx for a new and distinct input x. Specifically, fkx is computationally indistinguishable from a random y∈Y.


### 2.4. PAEKS and Security Model

The notion of Public-key Authenticated Encryption with Keyword Search (PAEKS) was first proposed in [16] to protect the privacy of a keyword against inside keyword guessing attacks. It involves the public/secret key pair into the cipher text to prevent keyword guessing attacks by the insider server. We first recall its definition.Definition 3 (syntax of PAEKS).
A PAEKS scheme consists of the following six PPT algorithms:(i)
Setup (λ). This is the global parameter generation algorithm. It takes the security parameter λ as input and outputs global system parameter Param(ii)
KeyGenS(Param). This is the sender’s key generation algorithm. It takes the global system parameter Param as input and outputs a public/secret key pair pkS,skS(iii)
KeyGenR(Param). This is the receiver’s key generation algorithm. It takes the global system parameter Param as input and outputs a public/secret key pair pkR,skR(iv)
PAEKSskS,pkR,w. This is the keyword encryption algorithm performed by the sender. It takes the sender’s secret key skS, the receiver’s public key pkR, and a keyword w as input and outputs a PAEKS cipher text C of the keyword w(v)
TrapdoorskR,pkS,w. This is the trapdoor generation algorithm performed by the receiver. It takes the receiver’s secret key skR, the sender’s public key pkS, and a keyword w as input and outputs a trapdoor Tw(vi)
TestTw,C,pkS,pkR. This is the test algorithm performed by the cloud server. It takes a trapdoor Tw, a PAEKS cipher text C, the sender’s public key pkS, and the receiver’s public key pkR as input and outputs 1 if C and Tw contain the same keyword and 0 otherwiseNext, we recall the improved security model for PAEKS in a multiuser setting by Noroozi and Eslami [18]. It includes trapdoor indistinguishability (TI) and cipher text indistinguishability (CI). Both of them are described through games played between an adversary A and the challenger C.Definition 4 (TI security game).
The TI security game is described as follows:(i)
Initialization. Given a security parameter λ, the challenger generates the global system parameter. Then, the challenger generates the receiver’s public/secret keys pkR,skR and the sender’s public/secret keys pkS,skS. It executes the adversary A on input Param,pkS,pkR(ii)
Phase 1. The adversary A is permitted to adaptively query the following two oracles polynomial times:(a)
Cipher Text OracleOCw,pk. Given a keyword w and a public key pk, the challenger computes the cipher text C by running the algorithm PAEKS skS,pk,w and returns the cipher text to A(b)
Trapdoor OracleOTw,pk. Given a keyword w and a public key pk, the challenger computes the trapdoor Tw by running the algorithm trapdoor skR,pk,w and returns the trapdoor to A(iii)
Challenge. When phase 1 ends, the adversary A outputs two challenge keywords w0∗ and w1∗, which have not been queried to the oracles OC·,pkR and OT·,pkS before. Now, the challenger chooses a random bit b∈0,1, computes the Twb∗⟵trapdoorskR,pkS,wb∗, and returns it to the adversary A(iv)
Phase 2. In this phase, the adversary A can continue to access the oracles, with the restriction that neither w0∗ nor w1∗ could be queried to the oracles OC·,pkR and OT·,pkS(v)
Guessing. Finally, the adversary A outputs a bit b′ as the guess of b. If b′=b, we say that A wins the game
We defineA’s advantage in breaking the TI security of PAEKS as
(3)AdvATIλ=Prb′=b−12.Definition 5 (CI security game).
Similarly, the CI security game can be described as follows:(i)
Initialization. Given a security parameter λ, the challenger generates the global system parameter Param. Then, the challenger generates the receiver’s public/secret keys pkR,skR and the sender’s public/secret keys pkS,skS. It executes the adversary A on input Param,pkS,pkR(ii)
Phase 1. The adversary A is allowed to adaptively query the following two oracles polynomial times:(a)
Cipher Text OracleOCw,pk. Given a keyword w and a public key pk, the challenger computes the cipher text C by running the algorithm PAEKSskS,pkR,w and returns the cipher text to A(b)
Trapdoor OracleOTw,pk. Given a keyword w and a public key pk, the challenger computes the trapdoor Tw by running the algorithm trapdoor skR,pkS,w and returns the trapdoor to A(iii)
Challenge. When phase 1 ends, the adversary A outputs two challenge keywords w0∗ and w1∗, which have not been queried to the oracles OC·,pkR and OT·,pkS before. Now, the challenger chooses a random bit b∈0,1, computes the Cwb∗⟵PAEKSskS,pkR,wb∗, and returns it to the adversary A(iv)
Phase 2. In this phase, the adversary A can continue to access the oracles, with the restriction that neither w0∗ nor w1∗ could be queried to the oracles OC·,pkR and OT·,pkS(v)
Guessing. Finally, the adversary A outputs a bit b′ as the guess of b. If b′=b, we say that A wins the game
We defineA’s advantage in breaking the CI security of PAEKS as
(4)AdvACIλ=Prb′=b−12.If for any PPT adversaryA, both AdvATIλ and AdvACIλ are negligible in the security parameter λ; we say that the PAEKS is semantically secure against inside keyword guessing attacks.


## 2.1. Cyclic Group

LetG be a group with order p. We say that G is a cyclic group, if the group G can be generated by a single element g∈G. That is, every element h∈G has the form h=gx for some exponent x∈ℤp. We call g to be a generator of the group. In our scheme, we use a cyclic group with a prime order; i.e., p is a prime. In this case, any group element except the identity will be a generator.


## 2.2. Oracle Diffie-Hellman (ODH) Problem [20]

LetG be a cyclic group with prime order p and a generator g. Let H be a hash function from G to some n-bit length space 0,1n. The ODH problem states that given a tuple g,gx,gy,T and an oracle Ogx·, to decide whether T is Hgxy or a random string from 0,1n, here, x and y are randomly chosen from ℤp, and the oracle returns Hhx for each h∈G. Let A be any probabilistic polynomial time (PPT) algorithm. We say that A breaks the ODH problem over group G and H with advantage at most ϵodh, if
(1)PrAOgx·g,gx,gy,Hgxy=1−PrAOgx·g,gx,gy,T=1<ϵodh.Definition 1 (ODH assumption).
We say that the ODH assumption holds over groupG and H, if for any PPT algorithm A, its advantage ϵodh in solving the ODH problem is negligible in κ (the bit length of p).


## 2.3. Pseudorandom Functions (PRFs)

A pseudorandom function is a family of functions such that for a random choice from the family, its input/output behavior is computationally indistinguishable from that of a random function. A formal definition of PRFs is given below.Definition 2 (PRFs).
Letf:K×X⟶Y be a family of functions indexed with key space K from X to Y. We say that f is an ϵf−securePRFs if
(1)
Given a keyk∈K and an input x∈X, there is an efficient algorithm to compute the output y=fkx(2)
For any PPT algorithmA that makes at most polynomial number of oracle queries, the following advantage is at most ϵf: where F=f:X⟶Y and the oracles are given an input x∈X and output the corresponding image of the function.
(2)PrAOgx·=1:k⟵K−PrAOgx·=1:f⟵F≤ϵf,The above definition indicates that, given any polynomial number of valid input/output pairsxi,fkxi, no PPT adversary can predicate fkx for a new and distinct input x. Specifically, fkx is computationally indistinguishable from a random y∈Y.


## 2.4. PAEKS and Security Model

The notion of Public-key Authenticated Encryption with Keyword Search (PAEKS) was first proposed in [16] to protect the privacy of a keyword against inside keyword guessing attacks. It involves the public/secret key pair into the cipher text to prevent keyword guessing attacks by the insider server. We first recall its definition.Definition 3 (syntax of PAEKS).
A PAEKS scheme consists of the following six PPT algorithms:(i)
Setup (λ). This is the global parameter generation algorithm. It takes the security parameter λ as input and outputs global system parameter Param(ii)
KeyGenS(Param). This is the sender’s key generation algorithm. It takes the global system parameter Param as input and outputs a public/secret key pair pkS,skS(iii)
KeyGenR(Param). This is the receiver’s key generation algorithm. It takes the global system parameter Param as input and outputs a public/secret key pair pkR,skR(iv)
PAEKSskS,pkR,w. This is the keyword encryption algorithm performed by the sender. It takes the sender’s secret key skS, the receiver’s public key pkR, and a keyword w as input and outputs a PAEKS cipher text C of the keyword w(v)
TrapdoorskR,pkS,w. This is the trapdoor generation algorithm performed by the receiver. It takes the receiver’s secret key skR, the sender’s public key pkS, and a keyword w as input and outputs a trapdoor Tw(vi)
TestTw,C,pkS,pkR. This is the test algorithm performed by the cloud server. It takes a trapdoor Tw, a PAEKS cipher text C, the sender’s public key pkS, and the receiver’s public key pkR as input and outputs 1 if C and Tw contain the same keyword and 0 otherwiseNext, we recall the improved security model for PAEKS in a multiuser setting by Noroozi and Eslami [18]. It includes trapdoor indistinguishability (TI) and cipher text indistinguishability (CI). Both of them are described through games played between an adversary A and the challenger C.Definition 4 (TI security game).
The TI security game is described as follows:(i)
Initialization. Given a security parameter λ, the challenger generates the global system parameter. Then, the challenger generates the receiver’s public/secret keys pkR,skR and the sender’s public/secret keys pkS,skS. It executes the adversary A on input Param,pkS,pkR(ii)
Phase 1. The adversary A is permitted to adaptively query the following two oracles polynomial times:(a)
Cipher Text OracleOCw,pk. Given a keyword w and a public key pk, the challenger computes the cipher text C by running the algorithm PAEKS skS,pk,w and returns the cipher text to A(b)
Trapdoor OracleOTw,pk. Given a keyword w and a public key pk, the challenger computes the trapdoor Tw by running the algorithm trapdoor skR,pk,w and returns the trapdoor to A(iii)
Challenge. When phase 1 ends, the adversary A outputs two challenge keywords w0∗ and w1∗, which have not been queried to the oracles OC·,pkR and OT·,pkS before. Now, the challenger chooses a random bit b∈0,1, computes the Twb∗⟵trapdoorskR,pkS,wb∗, and returns it to the adversary A(iv)
Phase 2. In this phase, the adversary A can continue to access the oracles, with the restriction that neither w0∗ nor w1∗ could be queried to the oracles OC·,pkR and OT·,pkS(v)
Guessing. Finally, the adversary A outputs a bit b′ as the guess of b. If b′=b, we say that A wins the game
We defineA’s advantage in breaking the TI security of PAEKS as
(3)AdvATIλ=Prb′=b−12.Definition 5 (CI security game).
Similarly, the CI security game can be described as follows:(i)
Initialization. Given a security parameter λ, the challenger generates the global system parameter Param. Then, the challenger generates the receiver’s public/secret keys pkR,skR and the sender’s public/secret keys pkS,skS. It executes the adversary A on input Param,pkS,pkR(ii)
Phase 1. The adversary A is allowed to adaptively query the following two oracles polynomial times:(a)
Cipher Text OracleOCw,pk. Given a keyword w and a public key pk, the challenger computes the cipher text C by running the algorithm PAEKSskS,pkR,w and returns the cipher text to A(b)
Trapdoor OracleOTw,pk. Given a keyword w and a public key pk, the challenger computes the trapdoor Tw by running the algorithm trapdoor skR,pkS,w and returns the trapdoor to A(iii)
Challenge. When phase 1 ends, the adversary A outputs two challenge keywords w0∗ and w1∗, which have not been queried to the oracles OC·,pkR and OT·,pkS before. Now, the challenger chooses a random bit b∈0,1, computes the Cwb∗⟵PAEKSskS,pkR,wb∗, and returns it to the adversary A(iv)
Phase 2. In this phase, the adversary A can continue to access the oracles, with the restriction that neither w0∗ nor w1∗ could be queried to the oracles OC·,pkR and OT·,pkS(v)
Guessing. Finally, the adversary A outputs a bit b′ as the guess of b. If b′=b, we say that A wins the game
We defineA’s advantage in breaking the CI security of PAEKS as
(4)AdvACIλ=Prb′=b−12.If for any PPT adversaryA, both AdvATIλ and AdvACIλ are negligible in the security parameter λ; we say that the PAEKS is semantically secure against inside keyword guessing attacks.


## 3. Our PAEKS Scheme

In this section, we introduce a PAEKS scheme for an electronic medical record system. The system framework is given in Figure2.Figure 2
Our PAEKS system framework.


### 3.1. The Construction

Our PAEKS scheme is described as follows:(i)
Setupλ. Select a cyclic group G with prime order p and a random generator g of G. Select three pseudorandom functions: E:K′×W⟶0,1n, f:K′′×0,1n⟶K, and F:K′×0,1m−n⟶0,1m, where K′, K′′, and K are the key spaces of the three PRFs, respectively, and W is the keyword space. Let H be a hash function, defined as H:G⟶K′×K′′. Finally, return Param=G,g,p,E,f,F(ii)
KeyGenS(Param). Randomly select x⟵Zp, and set pkS≔gx and skS≔x. Return skS and pkS(iii)
KeyGenR(Param). Randomly select y⟵Zp, and set pkR≔gy and skS≔y. Return skR and pkR(iv)
PAEKSskS,pkR,w. To encrypt a keyword w∈W, do the following:(a)
Compute the keysk′k′′=HpkRskS=Hgxy(b)
ComputeX=Ek′w and k=fk′′X(c)
Select a random stringS∈0,1n−m and set U=SFkS(d)
SetC=X⊕U(e)
Finally, returnC(v)
TrapdoorskR,pkS,w. Compute k′k′′=HpkRskS=Hgxy,X=Ek′w and k=fk′′X. Return the trapdoor Tw=Xk′′(vi)
TestTw,C. Compute U=C⊕X and parse it as ST. If T=FkS holds, return 1; otherwise, return 0


#### 3.1.1. Correctness

Let the receiver’s key pair bepkR,skR=gx,x and the sender’s key pair be pkS,skS=gy,y. Then, the key k′‖k′′=Hgxy can be generated by each other. Let C be a cipher text of keyword w generated by the sender and Tw be the corresponding search trapdoor generated by the receiver. According to the keyword encryption algorithm, there must exist two strings X and U and a random string S∈0,1n−m such that C=X⊕U, X=Ek′w, and U=S‖FkS, where k=fk′′X. For a right trapdoor of keyword w, it should be in the form Tw=X‖k, where X=Ek′w and k=fk′′X. So, X⊕C=U. Let S be the first n−m bits of U and T be the last m bits. Clearly, T=FkS will hold. Thus, for the same keyword, the cipher text will match with the corresponding trapdoor.Fixing a cipher textC′ of a distinct keyword w′≠w, we have C′=X′⊕U′, for some X′=Ek′w′. Since E is a pseudorandom function, then X=Ek′w is a random string over 0,1n with probability at least 1−ϵE. In this case, X⊕C′ will be a random string. Since F is also a pseudorandom function, for a random string S′‖T′, the equation FkS′=T′ holds with probability at most ϵE+1/2n. Thus, the cipher text C′ matches with the search trapdoor with a negligible probability. So our PAEKS scheme satisfies the correctness.


### 3.2. Security Proof

In this section, we prove that our PAEKS scheme satisfies both trapdoor indistinguishability and cipher text indistinguishability. Its trapdoor indistinguishability follows from the theorem below.Theorem 6.
If the oracle Diffie-Hellman assumption holds andE is a pseudorandom function, then our PAEKS scheme achieves trapdoor indistinguishability. Specifically, for any PPT adversary A, we have
(5)AdvATIλ≤ϵodh+ϵE,where ϵodh and ϵE are the advantages to break the ODH assumption and the pseudorandomness of the PRF E.Proof.
LetA be any PPT adversary that aims to break the security of trapdoor indistinguishability of our PAEKS scheme. We prove Theorem 6 by a sequence of games. Let Suci denote the event that A succeeds (i.e., b′=b) in the i-th game.
Game 0. This is the original trapdoor in a distinguishability game as defined in Definition 4. In this game, the challenger generates two public/secret key pairs pkS,skS and pkR,skR for the sender and the receiver, respectively, and gives the public keys to A. In addition, the adversary can adaptively issue queries to the trapdoor oracle OT·,· and cipher text oracle OC·,· with any keyword w∈W and public key pk. But, for the two challenge keywords w0∗ and w1∗, the adversary cannot submit them to the oracles OT·,pkS and OC·,pkR. Let Twb∗ denote the challenge trapdoor of wb∗, where b⟵0,1. Let b′ denote the guess of b by A. So, A’s advantage in this game is
(6)AdvATIλ=PrSuc0−12,
Game 1. This game is the same as the previous game with the exception of k′‖k′′ being sampled from K′×K′′ uniformly at random. Recall that in the previous game, the challenger computes k′‖k′′ by HpkSskR (namely, HpkRskS) according to the keyword encryption algorithm (namely, trapdoor generation algorithm). We now prove that
(7)PrSuc1−PrSuc0≤ϵodh,
Given an instance of the oracle Diffie-Hellman problemg,gx,gy,K, where K=Hgxy or K is a random string from K′×K′′, we construct an algorithm B to solve it using A as a subroutine. B sets pkS≔gx and pkR≔gy and gives them to A. The corresponding secret keys are implicitly set to be x and y, respectively. In addition, B chooses the other system parameters, including E,f,F, by itself. Parse K as k′‖k′′. When A issues queries to the oracles OT·,pk and OC·,pk with pk∉pkS,pkR, B involves the oracle Ogypk or Ogxpk to obtain the shared key k′‖k′′. When A issues queries to the oracles OT·,pkS and OC·,pkR, B uses k′‖k′′ to generate cipher texts and trapdoors. For example, for a keyword w, B computes the cipher text C as follows:
(1)
ComputeX=Ek′w and k=fk′′X(2)
Select a random stringS∈0,1n−m and set U=SFkS(3)
SetC=X⊕U
Given two challenge keywordsw0∗ and w1∗, B computes the challenge trapdoor Twb∗ as follows:
(1)
Choose a random bitb∈0,1(2)
ComputeX∗=Ek′wb∗ and k∗=fk′′X∗(3)
SetTwb∗=X∗k∗
Finally,A outputs a bit b′ as a guess of b. If b′=b, B outputs 1; otherwise, B outputs 0.
Clearly, ifK=Hgxy, the above game is identical to Game 0. Otherwise, it is identical to Game 1. So,
(8)PrBgx,gy,Hgxy=1:x,y⟵ℤp=PrSuc0,PrBgx,gy,K=1:x,y←ℤp,K⟵K′×K′′=PrSuc1.
This proves the result of Equation (7).
Game 2. This game is identical to the previous game with the exception of X∗ being sampled randomly from 0,1n. Assuming that E is a pseudorandom function, we have
(9)PrSuc2−PrSuc1≤ϵE.
We now prove Equation (9). Given a challenge pseudorandom function E, we construct an algorithm B to break its pseudorandomness using A as a subroutine. B chooses the system parameter, the sender and receiver’s public/secret key pairs, as in the previous game, with the exception of E being provided by its own challenger. Specifically, the random string k′′∈K′′ is chosen by B itself, but k′ is implicitly defined by the secret key of the challenge pseudorandom function E. Next, we show how B answers A’s queries of cipher texts and trapdoors with w,pkR or w,pkS, respectively. For a keyword w, B computes its cipher text as follows:
(1)
Query the challenger ofE with w to obtain the result X=Ek′w(2)
Computek=fk′′X(3)
Select a random stringS∈S and compute U=SFkS(4)
SetC=X⊕U
B computes its trapdoor as follows:
(1)
Submitw to its own challenger to obtain the result X=Ek′w(2)
Computek=fk′′X(3)
SetTw=Xk
WhenA submits two challenge keywords w0∗ and w1∗, B picks a random bit b and sends wb∗ to the oracle of PRF E for challenging. The PRF challenger will return the challenge PRF value X∗ to B, which may be Ek′wb∗ or a random value. B then computes k∗=fk′′X∗ and returns Twb∗=X∗‖k∗ to the adversary. Finally, A outputs a guess bit b′. If b′=b, B outputs 1; otherwise, it outputs 0.
From the above analysis, it is clear that ifX∗=Ek′wb∗, B actually simulates an environment of Game 1 for the adversary A. If X∗ is random, the simulated environment is identical to Game 2. Thus, if A’s success probability between Game 1 and Game 2 has difference PrSuc2−PrSuc1, then B can distinguish X∗=Ek′wb∗ from a random one with the same advantage. This computes the proof of Equation (9).
Note that in Game 2, the challenge trapdoor is independent of the two challenge keywords. So, the adversary has no success advantage in this game, i.e.,(10)PrSuc2=12.
Taking Equations (6) to (10) together, it follows that
(11)AdvATIλ≤ϵodh+ϵE.
This completes the proof of Theorem6.The cipher text indistinguishability of our PAEKS scheme follows from the theorem below.Theorem 7.
If the oracle Diffie-Hellman assumption holds andf,F are pseudorandom functions, then our PAEKS scheme achieves cipher text indistinguishability. Specifically, for any PPT adversary A, we have
(12)AdvACIλ≤ϵodh+ϵf+ϵF,where ϵodh, ϵf, and ϵF are the advantages to break the ODH assumption and the pseudorandomness of the PRFs f and F, respectively.Proof.
Similar to the proof of Theorem6, we prove the above theorem also via a sequence of games. In each game, A is a PPT adversary, aiming to break the cipher text indistinguishability of our PAEKS scheme. b is the challenge random bit, selected by the challenger, and b′ is A’s guess bit. We denote the event that b′=b in each game as Suci.
Game 0. This is the original cipher text indistinguishability game as defined in Definition 5. So,
(13)AdvACIλ=PrSuc0−12.
Game 1. This game is the same as Game 0, except that the value k′‖k′′ is chosen randomly from K′×K′′. Under the ODH assumption, these two games are computationally indistinguishable, i.e.,
(14)PrSuc1−PrSuc0≤ϵodh.
The proof of the above equation is similar to that of Equation (7); we omit it here.
Game 2. This game is identical to Game 1, except the following modification to the challenge cipher text. Suppose that wb∗ is the challenge keyword and X∗=Ek′wb∗ is the corresponding internal value of the cipher text. In this game, k∗ is selected randomly from K, instead of being computed via k∗=fk′′X∗. Note that, for normal keyword cipher text, k is still computed from fk′′X. Under the assumption that f is a pseudorandom function, these two games are computationally indistinguishable. Specially, we have
(15)PrSuc2−PrSuc1≤ϵf.
The proof of the above equation is similar to that of Equation (9); we omit it here.
Game 3. In this game, we replace the challenge value U∗=S∗Fk∗S∗ with a random string U∗⟵0,1n. Recall that, in this game, k∗ is sampled uniformly from K. By the pseudorandomness of PRF F, S∗‖Fk∗S∗ is computationally indistinguishable from a random n-bit string. Similarly, we can prove that
(16)PrSuc3−PrSuc2≤ϵF.
In Game 3,U∗ is random and is independent of the challenge keywords. So, the adversary has no advantage in this game, i.e.,
(17)PrSuc3=12.
Taking Equations (13) to (17) together, we complete the proof of Theorem 7.From Theorems6 and 7, we conclude that our PAEKS scheme is semantically secure against inside keyword guessing attack assuming that the ODH problem is hard and E,f,F are PRFs.


## 3.1. The Construction

Our PAEKS scheme is described as follows:(i)
Setupλ. Select a cyclic group G with prime order p and a random generator g of G. Select three pseudorandom functions: E:K′×W⟶0,1n, f:K′′×0,1n⟶K, and F:K′×0,1m−n⟶0,1m, where K′, K′′, and K are the key spaces of the three PRFs, respectively, and W is the keyword space. Let H be a hash function, defined as H:G⟶K′×K′′. Finally, return Param=G,g,p,E,f,F(ii)
KeyGenS(Param). Randomly select x⟵Zp, and set pkS≔gx and skS≔x. Return skS and pkS(iii)
KeyGenR(Param). Randomly select y⟵Zp, and set pkR≔gy and skS≔y. Return skR and pkR(iv)
PAEKSskS,pkR,w. To encrypt a keyword w∈W, do the following:(a)
Compute the keysk′k′′=HpkRskS=Hgxy(b)
ComputeX=Ek′w and k=fk′′X(c)
Select a random stringS∈0,1n−m and set U=SFkS(d)
SetC=X⊕U(e)
Finally, returnC(v)
TrapdoorskR,pkS,w. Compute k′k′′=HpkRskS=Hgxy,X=Ek′w and k=fk′′X. Return the trapdoor Tw=Xk′′(vi)
TestTw,C. Compute U=C⊕X and parse it as ST. If T=FkS holds, return 1; otherwise, return 0


### 3.1.1. Correctness

Let the receiver’s key pair bepkR,skR=gx,x and the sender’s key pair be pkS,skS=gy,y. Then, the key k′‖k′′=Hgxy can be generated by each other. Let C be a cipher text of keyword w generated by the sender and Tw be the corresponding search trapdoor generated by the receiver. According to the keyword encryption algorithm, there must exist two strings X and U and a random string S∈0,1n−m such that C=X⊕U, X=Ek′w, and U=S‖FkS, where k=fk′′X. For a right trapdoor of keyword w, it should be in the form Tw=X‖k, where X=Ek′w and k=fk′′X. So, X⊕C=U. Let S be the first n−m bits of U and T be the last m bits. Clearly, T=FkS will hold. Thus, for the same keyword, the cipher text will match with the corresponding trapdoor.Fixing a cipher textC′ of a distinct keyword w′≠w, we have C′=X′⊕U′, for some X′=Ek′w′. Since E is a pseudorandom function, then X=Ek′w is a random string over 0,1n with probability at least 1−ϵE. In this case, X⊕C′ will be a random string. Since F is also a pseudorandom function, for a random string S′‖T′, the equation FkS′=T′ holds with probability at most ϵE+1/2n. Thus, the cipher text C′ matches with the search trapdoor with a negligible probability. So our PAEKS scheme satisfies the correctness.


## 3.1.1. Correctness

Let the receiver’s key pair bepkR,skR=gx,x and the sender’s key pair be pkS,skS=gy,y. Then, the key k′‖k′′=Hgxy can be generated by each other. Let C be a cipher text of keyword w generated by the sender and Tw be the corresponding search trapdoor generated by the receiver. According to the keyword encryption algorithm, there must exist two strings X and U and a random string S∈0,1n−m such that C=X⊕U, X=Ek′w, and U=S‖FkS, where k=fk′′X. For a right trapdoor of keyword w, it should be in the form Tw=X‖k, where X=Ek′w and k=fk′′X. So, X⊕C=U. Let S be the first n−m bits of U and T be the last m bits. Clearly, T=FkS will hold. Thus, for the same keyword, the cipher text will match with the corresponding trapdoor.Fixing a cipher textC′ of a distinct keyword w′≠w, we have C′=X′⊕U′, for some X′=Ek′w′. Since E is a pseudorandom function, then X=Ek′w is a random string over 0,1n with probability at least 1−ϵE. In this case, X⊕C′ will be a random string. Since F is also a pseudorandom function, for a random string S′‖T′, the equation FkS′=T′ holds with probability at most ϵE+1/2n. Thus, the cipher text C′ matches with the search trapdoor with a negligible probability. So our PAEKS scheme satisfies the correctness.


## 3.2. Security Proof

In this section, we prove that our PAEKS scheme satisfies both trapdoor indistinguishability and cipher text indistinguishability. Its trapdoor indistinguishability follows from the theorem below.Theorem 6.
If the oracle Diffie-Hellman assumption holds andE is a pseudorandom function, then our PAEKS scheme achieves trapdoor indistinguishability. Specifically, for any PPT adversary A, we have
(5)AdvATIλ≤ϵodh+ϵE,where ϵodh and ϵE are the advantages to break the ODH assumption and the pseudorandomness of the PRF E.Proof.
LetA be any PPT adversary that aims to break the security of trapdoor indistinguishability of our PAEKS scheme. We prove Theorem 6 by a sequence of games. Let Suci denote the event that A succeeds (i.e., b′=b) in the i-th game.
Game 0. This is the original trapdoor in a distinguishability game as defined in Definition 4. In this game, the challenger generates two public/secret key pairs pkS,skS and pkR,skR for the sender and the receiver, respectively, and gives the public keys to A. In addition, the adversary can adaptively issue queries to the trapdoor oracle OT·,· and cipher text oracle OC·,· with any keyword w∈W and public key pk. But, for the two challenge keywords w0∗ and w1∗, the adversary cannot submit them to the oracles OT·,pkS and OC·,pkR. Let Twb∗ denote the challenge trapdoor of wb∗, where b⟵0,1. Let b′ denote the guess of b by A. So, A’s advantage in this game is
(6)AdvATIλ=PrSuc0−12,
Game 1. This game is the same as the previous game with the exception of k′‖k′′ being sampled from K′×K′′ uniformly at random. Recall that in the previous game, the challenger computes k′‖k′′ by HpkSskR (namely, HpkRskS) according to the keyword encryption algorithm (namely, trapdoor generation algorithm). We now prove that
(7)PrSuc1−PrSuc0≤ϵodh,
Given an instance of the oracle Diffie-Hellman problemg,gx,gy,K, where K=Hgxy or K is a random string from K′×K′′, we construct an algorithm B to solve it using A as a subroutine. B sets pkS≔gx and pkR≔gy and gives them to A. The corresponding secret keys are implicitly set to be x and y, respectively. In addition, B chooses the other system parameters, including E,f,F, by itself. Parse K as k′‖k′′. When A issues queries to the oracles OT·,pk and OC·,pk with pk∉pkS,pkR, B involves the oracle Ogypk or Ogxpk to obtain the shared key k′‖k′′. When A issues queries to the oracles OT·,pkS and OC·,pkR, B uses k′‖k′′ to generate cipher texts and trapdoors. For example, for a keyword w, B computes the cipher text C as follows:
(1)
ComputeX=Ek′w and k=fk′′X(2)
Select a random stringS∈0,1n−m and set U=SFkS(3)
SetC=X⊕U
Given two challenge keywordsw0∗ and w1∗, B computes the challenge trapdoor Twb∗ as follows:
(1)
Choose a random bitb∈0,1(2)
ComputeX∗=Ek′wb∗ and k∗=fk′′X∗(3)
SetTwb∗=X∗k∗
Finally,A outputs a bit b′ as a guess of b. If b′=b, B outputs 1; otherwise, B outputs 0.
Clearly, ifK=Hgxy, the above game is identical to Game 0. Otherwise, it is identical to Game 1. So,
(8)PrBgx,gy,Hgxy=1:x,y⟵ℤp=PrSuc0,PrBgx,gy,K=1:x,y←ℤp,K⟵K′×K′′=PrSuc1.
This proves the result of Equation (7).
Game 2. This game is identical to the previous game with the exception of X∗ being sampled randomly from 0,1n. Assuming that E is a pseudorandom function, we have
(9)PrSuc2−PrSuc1≤ϵE.
We now prove Equation (9). Given a challenge pseudorandom function E, we construct an algorithm B to break its pseudorandomness using A as a subroutine. B chooses the system parameter, the sender and receiver’s public/secret key pairs, as in the previous game, with the exception of E being provided by its own challenger. Specifically, the random string k′′∈K′′ is chosen by B itself, but k′ is implicitly defined by the secret key of the challenge pseudorandom function E. Next, we show how B answers A’s queries of cipher texts and trapdoors with w,pkR or w,pkS, respectively. For a keyword w, B computes its cipher text as follows:
(1)
Query the challenger ofE with w to obtain the result X=Ek′w(2)
Computek=fk′′X(3)
Select a random stringS∈S and compute U=SFkS(4)
SetC=X⊕U
B computes its trapdoor as follows:
(1)
Submitw to its own challenger to obtain the result X=Ek′w(2)
Computek=fk′′X(3)
SetTw=Xk
WhenA submits two challenge keywords w0∗ and w1∗, B picks a random bit b and sends wb∗ to the oracle of PRF E for challenging. The PRF challenger will return the challenge PRF value X∗ to B, which may be Ek′wb∗ or a random value. B then computes k∗=fk′′X∗ and returns Twb∗=X∗‖k∗ to the adversary. Finally, A outputs a guess bit b′. If b′=b, B outputs 1; otherwise, it outputs 0.
From the above analysis, it is clear that ifX∗=Ek′wb∗, B actually simulates an environment of Game 1 for the adversary A. If X∗ is random, the simulated environment is identical to Game 2. Thus, if A’s success probability between Game 1 and Game 2 has difference PrSuc2−PrSuc1, then B can distinguish X∗=Ek′wb∗ from a random one with the same advantage. This computes the proof of Equation (9).
Note that in Game 2, the challenge trapdoor is independent of the two challenge keywords. So, the adversary has no success advantage in this game, i.e.,(10)PrSuc2=12.
Taking Equations (6) to (10) together, it follows that
(11)AdvATIλ≤ϵodh+ϵE.
This completes the proof of Theorem6.The cipher text indistinguishability of our PAEKS scheme follows from the theorem below.Theorem 7.
If the oracle Diffie-Hellman assumption holds andf,F are pseudorandom functions, then our PAEKS scheme achieves cipher text indistinguishability. Specifically, for any PPT adversary A, we have
(12)AdvACIλ≤ϵodh+ϵf+ϵF,where ϵodh, ϵf, and ϵF are the advantages to break the ODH assumption and the pseudorandomness of the PRFs f and F, respectively.Proof.
Similar to the proof of Theorem6, we prove the above theorem also via a sequence of games. In each game, A is a PPT adversary, aiming to break the cipher text indistinguishability of our PAEKS scheme. b is the challenge random bit, selected by the challenger, and b′ is A’s guess bit. We denote the event that b′=b in each game as Suci.
Game 0. This is the original cipher text indistinguishability game as defined in Definition 5. So,
(13)AdvACIλ=PrSuc0−12.
Game 1. This game is the same as Game 0, except that the value k′‖k′′ is chosen randomly from K′×K′′. Under the ODH assumption, these two games are computationally indistinguishable, i.e.,
(14)PrSuc1−PrSuc0≤ϵodh.
The proof of the above equation is similar to that of Equation (7); we omit it here.
Game 2. This game is identical to Game 1, except the following modification to the challenge cipher text. Suppose that wb∗ is the challenge keyword and X∗=Ek′wb∗ is the corresponding internal value of the cipher text. In this game, k∗ is selected randomly from K, instead of being computed via k∗=fk′′X∗. Note that, for normal keyword cipher text, k is still computed from fk′′X. Under the assumption that f is a pseudorandom function, these two games are computationally indistinguishable. Specially, we have
(15)PrSuc2−PrSuc1≤ϵf.
The proof of the above equation is similar to that of Equation (9); we omit it here.
Game 3. In this game, we replace the challenge value U∗=S∗Fk∗S∗ with a random string U∗⟵0,1n. Recall that, in this game, k∗ is sampled uniformly from K. By the pseudorandomness of PRF F, S∗‖Fk∗S∗ is computationally indistinguishable from a random n-bit string. Similarly, we can prove that
(16)PrSuc3−PrSuc2≤ϵF.
In Game 3,U∗ is random and is independent of the challenge keywords. So, the adversary has no advantage in this game, i.e.,
(17)PrSuc3=12.
Taking Equations (13) to (17) together, we complete the proof of Theorem 7.From Theorems6 and 7, we conclude that our PAEKS scheme is semantically secure against inside keyword guessing attack assuming that the ODH problem is hard and E,f,F are PRFs.


## 4. Experiments and Efficiency Comparison

In this section, we analyze the efficiency of our PAEKS scheme and compare it with some other related schemes, including Boneh et al.’s PEKS scheme [4] and PAEKS schemes of [16, 18, 19]. Except our scheme, all the others are designed in bilinear groups. That is, besides group G, there are another group GT and a bilinear map e defined from G×G to GT.Table1 demonstrates the theoretical result of efficiency comparison in terms of keyword encryption, trapdoor generation, testing, and two security properties. In the table, we use symbols “E” and “P” to denote the evaluation of a modular exponentiation and a bilinear pairing, respectively. “H1” denotes a special hash function that maps an arbitrary string to a group element, while “H2” denotes a traditional hash function, e.g., MD5. We denote the pseudorandom function as “F.”Table 1
Efficiency comparison.
SchemesEncryptionTrapdoorTestIKGAMultiuserBoneh et al. [4]3E+H1+H2+PE+H1PNoYesHuang and Li [16]3E+H1E+H1+P2PYesNoNoroozi and Eslami [18]3E+H1E+H1+P2PYesYesQin et al. [19]3E+H1+H2+P2E+H1PYesUnknownOursE+H2+3FE+H2+2FFYesYesFigure3 shows the length of each parameter in different PEKS/PAEKS schemes. With the exception of Boneh et al.’s scheme, the other three schemes involve the sender’s public key and secret key in the keyword encryption algorithm and trapdoor generation algorithm, respectively. It can be seen from the figure that our scheme has shorter trapdoor and cipher text than other schemes. For the other parameters, our scheme still has comparable length with other schemes.Figure 3
Comparison of parameter sizes.Among these operations, the computation of the pairing is usually the most time-consuming. According to the construction ofH1 in [21], its computation is usually inefficient with the comparison of the traditional hash function. In a random oracle model, it is easy to construct a PRF from an efficient hash function. From these observations, we can see that our keyword testing algorithm should be much faster than that of the other three schemes. For encryption and the trapdoor generation, the advantage of our scheme is not obvious among them. In terms of security, Boneh et al.’s scheme cannot resist against IKGA. The scheme of [16] can prevent IKGA, but it is not secure in a multiuser setting. The scheme of [19] did not show its security in a multiuser setting.To evaluate the efficiency of these schemes in practice, we use a laptop with 1.7 GHz Intel i3 CPU, 2 GB memory, and a Windows 7 operating system to implement them. We use the jPBC library and choose a type A pairing, which makes use of the curvey2=x3+x over the field Fq for prime q≡3mod4. We run each algorithm with different times and record their time in seconds. The results are shown in Figures 4, 5, and 6, respectively. As the computations of Noroozi and Eslami and Huang and Li, they possess the same experimental results. Experiment results show that our encryption algorithm and trapdoor generation algorithm are slightly faster than those of the other schemes. But our keyword testing algorithm is significantly faster than that of the other schemes.Figure 4
Running time of the encryption algorithm.Figure 5
Running time of the trapdoor algorithm.Figure 6
Running time of the test algorithm.


## 5. Conclusion

In this paper, we proposed a new public-key authenticated encryption scheme with keyword search. Our scheme uses the idea of the Diffie-Hellman key exchange protocol to generate a shared secret key between the sender and the receiver. The shared key can be viewed as the secret key of a symmetric-key searchable encryption scheme to encrypt keywords by the sender or to generate search trapdoors by the receiver. Under the ODH assumption, our PAEKS scheme can achieve both trapdoor indistinguishability and cipher text indistinguishability, and hence, it can resist inside keyword guessing attacks. The scheme is also efficient. Specifically, its keyword searching algorithm is very fast in the sense that it requires only one computation of PRF, while the previous schemes require at least one expensive pairing operation.



---

*Source: 8816172-2020-07-14.xml*