Registered Keyword Searchable Encryption Based on SM9

Abstract

The SM9 algorithm is an Identity-Based Encryption (IBE) algorithm independently made by China. The existing SM9 searchable encryption scheme cannot be effective against insider keyword guessing attacks and violates users’ data privacy. This article utilizes the SM9 encryption method to propose a Registered Public Keyword Searchable Encryption based on SM9 (RKSE-SM9), which uses the SM9 user keys in the registration keyword algorithm. For RKSE-SM9 to generate the keyword ciphertext or trapdoor, a secure server must first register the keyword, which effectively and reasonably protects users’ data and resists honest and curious cloud servers. From there, we also utilize Beaver’s triple to construct an improved registered keyword generation algorithm, defining and proving that the improved algorithm satisfies the concept of indistinguishability against registration keywords, achieving a higher level of privacy. In addition, compared with existing SM9 searchable encryption, our scheme proved to guarantee better security while reducing the computational efficiency by only 1%; compared with the existing registered keyword searchable encryption scheme, the overall operational efficiency increases by 63%.

1. Introduction

Local data services can no longer satisfy consumers’ and businesses’ practical demands in today’s culture of data explosion and global information connectivity, and the fast flow and dispersed storage of global data have increased the need for information sharing. Therefore, more and more users choose to place data on cloud services. Cryptography ensures that only authenticated users can encrypt and store information [1]. Before uploading an important file to the cloud, the file must be encrypted to ensure that the file will not be leaked. However, users should download all the encrypted files locally before decrypting them all to look for related data when they need to. This process consumes a lot of computation resources and communication overhead. It is unsuited for existing application scenarios. The searchable encryption technology provides the cloud server with secure retrieval of data in the ciphertext state, ensuring that only reliable users can obtain the related data, then the user can decrypt it locally to obtain the corresponding plaintext. Modern cryptography is divided into symmetric cryptography and public key cryptography [2]. Therefore, searchable encryption is also split into two forms. The most notable aspect of the public key cryptosystem, as opposed to the symmetric cryptosystem’s key management issue, is that it does not share secret keys between users. As a result, Public Key Searchable Encryption (PKSE) has a lot of users, is compatible with current application scenarios in large environments, and is more general than the symmetric searchable encryption scenario [3]. The proposed method recently includes many different cryptographic algorithms because of the launch of PEKS. It incorporates more new technologies so that the new scheme can satisfy more robust security, be compatible with more application scenarios, and meet more functions. In addition to file encryption, image encoding is also a typical encryption method [4,5].

In 2016, China State Cryptography Administration released a cryptographic standard for identity-based cryptography (IBC), which includes three primitives: identity-based signature, identity-based encryption, and identity-based encapsulation. The SM9 algorithm [6] is also an ISO standard since 2021. In the commercial cryptography system, besides SM2 elliptic curve cryptosystem, the SM9 IBC algorithm has become China’s other commercial standard for public key cryptography. The research on the SM9 algorithm is conducive to promoting the retail cryptography industry’s development, improving its technology’s innovation, and ensuring network and information security. This research combined the SM9 algorithm with searchable encryption technology to create an effective and safe public key searchable encryption algorithm, therefore extending the application of the SM9 algorithm. These are the contributions we produced:

• In the anonymous IBE, the identity information in its algorithm is replaced by keywords, and the IBE can be converted into a PEKS. We first involve a third-party server for keyword registration using SM9’s deterministic key generation algorithm and then construct a public key encryption scheme with a registered keyword search. By employing Beaver’s protocol [7] to ensure secure keyword generation, we ensured the privacy of registered keywords;
• We describe the framework of our suggested system and examine its security model in this paper. We simplify the proposed method to the q-BCAA problem and prove its security in the presence of random oracles. Our searchable encryption method is more resistant to insider keyword guessing attacks than the existing SM9 searchable encryption scheme;
• Compared with existing Registered Keyword Searchable Encryption Schemes [8], our scheme has significant advantages in both computational overhead and communication overhead, especially in terms of the PEKS Ciphertext and Testing. According to experimental data, the PEKS Ciphertext’s efficiency has grown by 84 percent, Testing’s efficiency has increased by 41.3 percent, and the overall efficiency has increased by 63 percent.

Related Works

The concept of Symmetric Searchable Encryption (SSE) was proposed by Song et al. [9] in 2000. This is the first scheme to search for encrypted data, but it uses symmetric encryption. In 2004, Boneh et al. [10] took the mail system as the background, proposed the concept of PEKS, and gave the first PEKS scheme. The security of this scheme was reduced to the difficult problem of the Bilinear Diffie–Hellman (BDH). In 2005, Abdalla et al. [11] demonstrated the PEKS game’s consistency issue and provided a general approach for converting an anonymous IBE scheme to a PEKS scheme. In 2006, Byun et al. [12] said that in our daily life, we usually use high-frequency keywords to search, which shows that there is little room for keywords, which may lead to keyword guessing attacks (KGA). In order to combat KGA, Rhee et al. [13] added two pairs of keys to their scheme and defined a new type of PEKS named Designated Public-key Encryption with Keyword Search (dPEKS). It suggested the idea of trapdoor indistinguishability, a notion that can defy offline KGA. In 2010, Tang and Chen [14] proposed a new model, namely Public Key Encryption with Registered Keyword Search (PERKS). PERKS requires the receiver to run the registered keyword algorithm to generate pre-labels. When testing the algorithm, it needs to input the generated pre-label, keyword ciphertext, and keyword trapdoor. In 2016, Chen et al. [8] added an aided server against offline keyword guessing attacks. It applied deterministic blind signatures, e.g., FDH-RSA, to generate a signature as the registered keyword. In 2017, another form of PEKS was given by Huang et al. [15]. With this approach, the sender’s private key should be included for generating the ciphertext. The sender’s authenticity may be verified by the receiver. As a result, the server is resistant to insider KGA and cannot encrypt keywords. In 2018, Sun et al. [16] combined PEKS with SSE, they adopted a signcryption algorithm when generating the searchable ciphertext, and the scheme is secured against insider KGA. In 2019, Li et al. [17] added identity authentication on the basis of dPEKS and proved it can resist insider offline KGA. In 2020, Qin et al. [18] showed that the security of Huang and Li’s [15] scheme was not ideal, and they proposed an improved PAEKS scheme that satisfies keyword privacy and trapdoors to resist chosen multi-ciphertext attacks and insider offline KGA [19]. In recent years, there have been more and more scenarios for searchable encryption, such as [20,21,22,23].

The SM9 algorithm is the only IBE standard in China, and it has also become a research hotspot in recent years. In 2020, Zhang et al. [24] proposed a fully distributed SM9 $(t,n)$ threshold private key generation mechanism to completely eliminate the single-point failure problem. In 2021, Lai et al. [25] proposed an identity-based broadcast encryption based on SM9. To alleviate SM9 key exposure issues, Sun et al. [26] and Qin et al. [27] introduced a dependable third party to take after a part of the user’s private key so that it could conduct key updates and revocations. Most recently, with the popularization of applications such as big data and cloud computing, several new cryptographic algorithms have been derived based on the national secret SM9, such as [28,29]. In 2022, Pu et al. [30] built a public-key searchable encryption method on the SM9 identity-based encryption algorithm for the first time, but it cannot resist the problem of KGA. SM9 public key searchable encryption continues to be researched, and at this point, no method that can resist KGA has been discovered. As a result, this work, for the first time, suggests a searchable encryption system with registered keywords based on SM9. Higher safety and appropriate efficiency can be achieved.

2. Preliminaries

2.1. Bilinear Maps

Definition 1 

(Bilinear Maps). $G_1$ and $G_2$ exist as two additive cyclic groups of prime order N, the generator of whom are $P_1$ and $P_2$, respectively. Have $G_T$ be a multiplicative cyclic group; there exists a homomorphic map ϕ from $G_2$ to $G_1$, such that $\varphi \left(G_2\right)=G_1$. Have an admissible bilinear map $\widehat{e}:G_1\times G_2\to G_T$, and satisfy the following conditions:

• Bilinearity: for all $P\in G_1$, $Q\in G_2$, and all $a,b\in {\mathbb{Z}}_N^{*}$, $\widehat{e}(a{P}_1,b{P}_2)=\widehat{e}{(P_1,P_2)}^{ab}$.
• Non-degeneracy: $\widehat{e}(P_1,P_2)\ne 1_{G_T}$.
• Computability: for all $P\in G_1$ and $Q\in G_2$, $\widehat{e}(P,Q)$ can be computed efficiently.

2.2. Bilinear Collision Attack Assumption

Definition 2 

(q-BCAA [31]). For a positive integer q and random $\alpha \in {\mathbb{Z}}_N^{*}$, given

$$\left(P_1,P_2,h_0,\left(h_1,\frac{\alpha }{\alpha +h_1}{P}_2\right),\dots ,\left(h_q,\frac{\alpha }{\alpha +h_q}{P}_2\right)\right)$$

where $h_i\in {\mathbb{Z}}_N^{*}(0\le i\le q)$ are randomly selected and different from each other, the Bilinear Collision Attack Assumption (q-BCAA) problem is to compute $\widehat{e}{(P_1,P_2)}^{\frac{\alpha }{\alpha +h_0}}$.

The advantage of algorithm $\mathcal{A}$ in solving the above problems is as follows:

$${\mathsf{Adv}}_{\mathcal{A}}^{q\mathrm{-BCCA}}\left(\lambda \right):=\mathrm{Pr}\left[\mathcal{A}\left(P_1,P_2,h_0,\left(h_1,\frac{\alpha }{\alpha +h_1}{P}_2\right),\dots ,\left(h_q,\frac{\alpha }{\alpha +h_q}{P}_2\right)\right)=\widehat{e}{(P_1,P_2)}^{\frac{\alpha }{\alpha +h_0}}\right].$$

If, for any polynomial–time algorithm $\mathcal{A}$, the advantage of solving the q-BCAA problem is negligible in λ, then we say that the q-BCAA problem is hard.

2.3. Beaver Triple

Definition 3 

(Beaver Triple). The Beaver triple, also known as a multiplication triple, is mainly used for multiplication calculations in secure multi-party computing protocols. Its specific algorithm is shown in Algorithm 1. In the table, for any integer x, $x_1$, and $x_2$, denote the two random shares of x, such that $x=x_1+x_2$. The operation maybe operates over some ring ${\mathbb{Z}}_N$. $c_1$ and $c_2$ are the random shares of the multiplication $a·b$. Let $P_0$ and $P_1$ denote two parties.

Algorithm 1: Beaver Triple

Input: Shares $u_i$, $v_i$, $a_i$, $b_i$, and $c_i$.

Output: Shares ${[u·v]}_i$.

1. $P_i$ computes $e_i=u_i-a_i$ and $f_i=v_i-b_i$.

2. $P_0$ and $P_1$ jointly construct e and f.

3. $P_i$ computes ${[u·v]}_i=i·e·f+e·b_i+a_i·f+c_i$.

3. The Proposed RKSE-SM9 Scheme

3.1. System Model

In this section, we introduce the system model and formal definition of RKSE-SM9.

Figure 1 displays the RKSE-SM9 scheme’s system model, which includes the following four entities:

Registration Server (RS): Input a keyword w; it generates a registered keyword $rs{d}_w$.

Sender: Input a registered keyword; it generates a keyword ciphertext $C_{rs{d}_w}$ and uploads it into a cloud server.

Receiver: Input a registered keyword; it locally generates a keyword trapdoor $T_{rs{d}_{w^{\prime }}}$ for searching.

Cloud Server (CS): Stores ciphertexts and trapdoors, runs test algorithms to search keyword ciphertexts, and returns the results to the user.

The RKSE-SM9 scheme consists of the following seven algorithms: $\mathsf{SysSetup}$, ${\mathsf{KeyGen}}_{RS}$, ${\mathsf{KeyGen}}_R$, $\mathsf{RSD}$, $\mathsf{PEKS}$, $\mathsf{Trapdoor}$, and $\mathsf{Test}$.

• $\mathsf{SysSetup}\left(\lambda \right)\to \mathcal{G}$: Input $\lambda$, which is a security parameter in the system, and output a public parameter $\mathcal{G}$.
• ${\mathsf{KeyGen}}_{RS}\left(\mathcal{G}\right)\to (p{k}_{RS},s{k}_{RS})$: Input $\mathcal{G}$, then output the registration sever’s key pair $(p{k}_{RS},s{k}_{RS})$.
• ${\mathsf{KeyGen}}_R\left(\mathcal{G}\right)\to (p{k}_R,s{k}_R)$: Input $\mathcal{G}$, then output the receiver’s key pair $(p{k}_R,s{k}_R)$.
• $\mathsf{RSD}(\mathcal{G},s{k}_{RS},w)\to rs{d}_w$: Input $\mathcal{G}$, $s{k}_{RS}$, and w, outputs the RS-derived keyword $rs{d}_w$.
• $\mathsf{PEKS}(\mathcal{G},p{k}_R,rs{d}_w)\to C_{rs{d}_w}$: Input $\mathcal{G}$, $p{k}_R$, and $rs{d}_w$, the sender outputs the PEKS ciphertext $C_{rs{d}_w}$ of w.
• $\mathsf{Trapdoor}(\mathcal{G},s{k}_R,rs{d}_{w^{\prime }})\to T_{rs{d}_{w^{\prime }}}$: Input $\mathcal{G}$, $s{k}_R$, and $rs{d}_{w^{\prime }}$, the receiver outputs the search Trapdoor $T_{rs{d}_{w^{\prime }}}$ of $w^{\prime }$.
• $\mathsf{Test}(\mathcal{G},C_{rs{d}_w},T_{rs{d}_{w^{\prime }}})\to 1/0$: Input $\mathcal{G}$, $C_{rs{d}_w}$, and $T_{rs{d}_{w^{\prime }}}$, the CS outputs 1 if $w=w^{\prime }$, otherwise outputs 0.

3.2. Construction of RKSE-SM9

As shown in

Table 1. Symbol table in the RKSE-SM9.

Notations	Description
$G_1$	a cyclic additive group of order prime number N
$P_1$	generator for the group $G_1$
$G_2$	a cyclic additive group of order prime number N
$P_2$	generator for the group $G_2$
$G_T$	a multiplicative group of order N
N	the order of group $G_1$, $G_2$, $G_T$, is a prime number greater than $2^{191}$
$\widehat{e}$	bilinear pairing $\widehat{e}:G_1\times G_2\to G_T$
$H_1$	a hash function $H_1:{\{0,1\}}^{*}\to {\mathbb{Z}}_N^{*}$
$H_2$	a hash function $H_2:G_2\to {\mathbb{Z}}_N^{*}$
$H_3$	a secure hash function $H_3:G_T\to {\{0,1\}}^n$
$(p{k}_{RS},s{k}_{RS})$	the public/private key pair of the registration server
$(p{k}_R,s{k}_R)$	the public/private key pair of the receiver
$rs{d}_w$	RS-derived keyword of w

, the elliptic curve and curve parameters used in this scheme are consistent with those used in the SM9 standard. The concrete construction of RKSE-SM9 is as follows:

• $\mathsf{SysSetup}\left(\lambda \right)\to \mathcal{G}$: Input the security parameter $\lambda$, it returns a public parameter $\mathcal{G}$=(N, $G_1$, $G_2$, $G_T$, $\widehat{e}$, $P_1$, $P_2$, $H_1$, $H_2$, $H_3$); among them, $G_1$ and $G_2$ are two cyclic additive groups of order prime N, $G_T$ is a multiplicative cyclic group of order prime N, and $P_1$ and $P_2$ are the generators of the groups $G_1$ and $G_2$, respectively. There exists a homomorphic map $\varphi$ from $G_2$ to $G_1$, such that $\varphi$. $\widehat{e}:G_1\times G_2\to G_T$ is a bilinear map, and $H_1:{\{0,1\}}^{*}\to {\mathbb{Z}}_N^{*}$, $H_2:G_2\to {\mathbb{Z}}_N^{*}$, and $H_3:G_T\to {\{0,1\}}^n$ are three hash functions.
• ${\mathsf{KeyGen}}_{RS}\left(\mathcal{G}\right)\to (p{k}_{RS},s{k}_{RS})$: Input $\mathcal{G}$, the registration server picks a random $s_0\in {\mathbb{Z}}_N^{*}$ and outputs the RS’s key pair as $(p{k}_{RS},s{k}_{RS})=(s_0{P}_1,s_0)$.
• ${\mathsf{KeyGen}}_R\left(\mathcal{G}\right)\to (p{k}_R,s{k}_R)$: Input $\mathcal{G}$, the receiver picks a random $s_1\in {\mathbb{Z}}_N^{*}$, computes $g=\widehat{e}(s_1{P}_1,P_2)$, and outputs the receiver’s key pair $(p{k}_R,s{k}_R)=(s_1{P}_1,s_1)$. It publishes $p{k}_R$ and g, and keeps $s{k}_R$ secretly.
• $\mathsf{RSD}(\mathcal{G},s{k}_{RS},w)\to rs{d}_w$: Input $\mathcal{G}$, $s{k}_{RS}$, and w, it outputs the RS-derived keyword $rs{d}_w$ of w. The RSD algorithm is shown in Figure 2.
• $\mathsf{PEKS}(\mathcal{G},p{k}_R,rs{d}_w)\to C_{rs{d}_w}$: Input $\mathcal{G}$, $p{k}_R$, and $rs{d}_w$, the sender picks a random $r\in {\mathbb{Z}}_N^{*}$, computes $C_1=r\left(H_2\left(rs{d}_w\right)P_1+p{k}_R\right)$ and $C_2=H_3\left(g^r\right)$, and finally outputs the PEKS ciphertext $C_{rs{d}_w}=(C_1,C_2)$.
• $\mathsf{Trapdoor}(\mathcal{G},s{k}_R,rs{d}_{w^{\prime }})\to T_{rs{d}_{w^{\prime }}}$: Input $\mathcal{G}$, $s{k}_R$, and $rs{d}_{w^{\prime }}$, the receiver computes $T_{rs{d}_{w^{\prime }}}=\left(\frac{s{k}_R}{s{k}_R+H_2\left(rs{d}_{w^{\prime }}\right)}\right)P_2$ and outputs the search trapdoor $T_{rs{d}_{w^{\prime }}}$.
• $\mathsf{Test}(\mathcal{G},C_{rs{d}_w},T_{rs{d}_{w^{\prime }}})\to 1/0$: Input $\mathcal{G}$, $C_{rs{d}_w}$, and $T_{rs{d}_{w^{\prime }}}$, the CS checks $H_3\left(\widehat{e}(C_1,T_{rs{d}_{w^{\prime }}})\right)$$=C_2$. If yes, it outputs 1, indicating that $w=w^{\prime }$. Otherwise, it outputs 0.

Improved registered keyword generation algorithm. In the above scheme, since the user directly sends $H_1\left(w\right)$ to the registration server when registering w, only part of the information of the keyword can be covered up, and a higher level of privacy protection for the registered keyword cannot be realized, that is, the indistinguishability of the registered keyword (see the security model 3 in Section 3.3). We further create the dual registration server to address this issue, and Beaver triple is used to safely coordinate keyword generation between the two servers. The key generation method and the keyword registration algorithm of the registration server are different in the dual registration server mode, but all other algorithms are the same as those in the preceding scheme.

• ${\mathsf{KeyGen}}_{R{S}_i}\left(\mathcal{G}\right)\to (p{k}_{R{S}_i},s{k}_{R{S}_i})(i=0,1)$: Dual server keyword registration algorithm. Input $\mathcal{G}$, the registration servers pick random $s_{0,0},s_{0,1}\in {\mathbb{Z}}_N^{*}$, and compute the public/private key pair of server as $(p{k}_{R{S}_0},s{k}_{R{S}_0})=(s_{0,0}{P}_1,s_{0,0})$ and $(p{k}_{R{S}_1},s{k}_{R{S}_1})=(s_{0,1}{P}_1,s_{0,1})$, respectively. The servers publish $p{k}_{R{S}_0}$ and $p{k}_{R{S}_1}$, and keep $s{k}_{R{S}_0}$ and $s{k}_{R{S}_1}$ secretly. Let $s_0=s_{0,0}+s_{0,1}modN$. The two servers jointly compute $p{k}_{RS}=s_0{P}_1=p{k}_{R{S}_0}+p{k}_{R{S}_1}$. Unless otherwise specified, the following operations are performed over ring ${\mathbb{Z}}_N$.
• $\mathsf{IRSD}(\mathcal{G},s{k}_{RS},w)\to rs{d}_w$: Input $\mathcal{G}$, $s{k}_{R{S}_i}$ of the $R{S}_i$, and w, the two servers jointly compute the RS-derived keyword $rs{d}_w$ for a user, so that no server knows the value the keyword w. it outputs the RS-derived keyword $rs{d}_w$ of w. The improved RSD algorithm $\mathsf{IRSD}$ is described as follows:
  • User selects a keyword w to be registered and hashes it to obtain $H_1\left(w\right)$.
  • The user sends the secret sharing $H_1\left(w\right)=H_1{\left(w\right)}_0+H_1{\left(w\right)}_1$ to $R{S}_0$ and $R{S}_1$, respectively. That is, $R{S}_0$ obtains $H_1{\left(w\right)}_0$ and $R{S}_1$ obtains $H_1\left(w\right)$;
  • The user generates two random numbers $a,b\in {\mathbb{Z}}_N^{*}$, computes $c=a·bmodN$, and sends the secret sharing $a=a_0+a_1$, $b=b_0+b_1$, and $c=c_0+c_1$ to $R{S}_0$ and $R{S}_1$, respectively. That is, $R{S}_0$ obtains shares $a_0,b_0,c_0$, and $R{S}_1$ obtains shares $a_1,b_1,c_1$;
  • The user generates a random number $v\in {\mathbb{Z}}_N^{*}$, and sends the secret sharing $v=v_0+v_1$ to $R{S}_0$ and $R{S}_1$, respectively. That is, $R{S}_0$ obtains share $v_0$, and $R{S}_1$ obtains share $v_1$;
  • $R{S}_i$ ($i=0,1$) computes $u_i=s_{0,i}+H{\left(w\right)}_i$, $e_i=u_i-a_i$ and $f_i=v_i-b_i$, respectively. Then, $R{S}_i$ broadcasts $e_i$ and $f_i$, leading to reconstruction of e and f;
  • $R{S}_i$ ($i=0,1$), respectively, computes ${[u·v]}_i=i·e·f+e·b_i+a_i·f+c_i$. That is, $R{S}_0$ computes ${[u·v]}_0=e·b_0+a_0·f+c_0$ and $R{S}_1$ computes ${[u·v]}_1=e·f+e·b_1+a_1·f+c_1$;
  • $R{S}_0$ and $R{S}_1$ broadcast ${[u·v]}_i$, leading to the reconstruction of $u·v$;
  • $R{S}_0$ and $R{S}_1$ compute ${\theta }_i=\frac{v_i}{u·v}$, respectively, then sends ${\theta }_0{P}_2$ and ${\theta }_1{P}_2$ to the user;
  • The user computes $rs{d}_w=P_2-H_1\left(w\right)·({\theta }_0{P}_2+{\theta }_1{P}_2)=\frac{s_0}{s_0+H_1\left(w\right)}{P}_2$.

3.3. Security Model

In this section, we define the security models for the RKSE-SM9 scheme in terms of the Cloud Server and the Registration Server, respectively.

Adversarial Cloud Server (CS). An internal adversary is thought to be the adversarial cloud server. Here, we describe the semantic security of this system under the assumption of internal adversaries, including Ciphertext Indistinguishability against Adaptive Chosen Keyword Attack (IND-CT-CKA) and Trapdoor Indistinguishability against Adaptive Chosen Keyword Attack (IND-TD-CKA).

Definition 4 

(IND-CT-CKA Security Model). The IND-CT-CKA security model is defined as follows:

Setup. 

The challenger generates public parameter $\mathcal{G}$, key pairs $(p{k}_{RS},s{k}_{RS})$ and $(p{k}_R,s{k}_R)$, and sends $(\mathcal{G},p{k}_{RS},p{k}_R)$ to the adversary.

Query 1. 

The adversary can adaptively query the challenger with the following queries:

• Hash query $H_i(·)$: For the value x queried by the adversary, the corresponding hash value $H_i\left(x\right)$ is returned.
• Keyword registration query $\mathsf{RSD}(·)$: The adversary sends the challenger a keyword w, and the challenger returns $rs{d}_w\leftarrow \mathsf{RSD}(\mathcal{G},s{k}_{RS},w)$ to the adversary. (We assume that the adversary must ask for the registration result of the keyword before asking for the ciphertext of the keyword. Since the PEKS is publicly computable, we omit the adversary’s query of the ciphertext of the keyword.)
• Trapdoor query $\mathsf{Trapdoor}\left(rs{d}_w\right)$: The adversary sends a keyword w to the challenger, and the challenger sends the search trapdoor $T_{rs{d}_w}\leftarrow \mathsf{Trapdoor}(\mathcal{G},s{k}_R,rs{d}_w)$ to the adversary.

Challenge. 

When the Query 1 is over, the adversary selects two never-queried keywords $w_0$, $w_1$, and sends them to the challenger. The challenger randomly selects $b\in \{0,1\}$ and runs the keyword registration algorithm to generate $rs{d}_w\leftarrow \mathsf{RSD}(\mathcal{G},s{k}_{RS},w_b)$. Finally, it sends the challenge ciphertext $C_{rs{d}_{w_b}}\leftarrow \mathsf{PEKS}(\mathcal{G},p{k}_R,rs{d}_{w_b})$ to the adversary.

Query 2. 

The adversary can continue the query the same as in Query 1 except for the two challenge keywords $w_0$ and $w_1$.

Guess. 

The adversary outputs its guess $b^{\prime }\in \{0,1\}$ and wins the game if $b=b^{\prime }$; otherwise, the adversary fails.

We refer to such an adversary $\mathcal{A}$ in the above game as an IND-CT-CKA adversary and define its advantage as ${\mathsf{Adv}}_{CS,\mathcal{A}}^{\mathrm{IND}\mathrm{-CT}\mathrm{-CKA}}\left(\lambda \right):=\mathrm{Pr}[b=b^{\prime }]-\frac{1}{2}$. If for any polynomial–time adversary $\mathcal{A}$, its advantage ${\mathsf{Adv}}_{CS,\mathcal{A}}^{\mathrm{IND}\mathrm{-CT}\mathrm{-CKA}}\left(\lambda \right)$ is negligible, we say that the scheme satisfies ciphertext indistinguishability.

Definition 5 

(IND-TD-CKA Security Model). The IND-CT-CKA security model is defined as follows:

Setup. 

Same as in Definition 4.

Query 1. 

Same as in Definition 4.

Challenge. 

When Query 1 is over, the adversary chooses two never-queried keywords, $w_0$ and $w_1$, and sends them to the challenger. The challenger randomly selects $b\in \{0,1\}$ and runs the keyword registration algorithm to generate $rs{d}_w\leftarrow \mathsf{RSD}(\mathcal{G},s{k}_{RS},w_b)$. Finally, it sends the challenge search trapdoor $T_{rs{d}_{w_b}}\leftarrow \mathsf{Trapdoor}(\mathcal{G},s{k}_R,rs{d}_{w_b})$ to the adversary.

Query 2. 

Same as in Definition 4.

Guess. 

The adversary outputs its guess $b^{\prime }\in \{0,1\}$ and wins the game if $b=b^{\prime }$; otherwise, the adversary fails.

The adversary $\mathcal{A}$’s advantage in the above game is defined as ${\mathsf{Adv}}_{CS,\mathcal{A}}^{\mathrm{IND}\mathrm{-TD}\mathrm{-CKA}}\left(\lambda \right):=\mathrm{Pr}[b=b^{\prime }]-\frac{1}{2}$. If for any polynomial–time adversary $\mathcal{A}$, its advantage ${\mathsf{Adv}}_{CS,\mathcal{A}}^{\mathrm{IND}\mathrm{-TD}\mathrm{-CKA}}\left(\lambda \right)$ is negligible, we say that the scheme satisfies trapdoor indistinguishability.

Honest but Curious Registration Server (RS). It is assured that neither the registration server nor outside attackers will learn anything about the registered keywords from the new keyword registration methodology. The following definition is for Registered Keywords Indistinguishability against Selected Keyword Attack (IND-RK-CKA). The opponent may work with one of the two keyword registration servers in the next game. We make the assumption that the adversary works with server 0 without losing generality.

Definition 6 

(IND-RK-CKA Security Model). The IND-RK-CKA game is defined as follows:

Setup. 

The challenger generates public parameter $\mathcal{G}$, key pairs $(p{k}_{R{S}_i},s{k}_{R{S}_i})$ and $(p{k}_R,s{k}_R)$, and sends ($\mathcal{G}$, $p{k}_{R{S}_0}$, $s{k}_{R{S}_0}$, $p{k}_{R{S}_1}$, $p{k}_R$, and $s{k}_R$) to the adversary.

Challenge. 

The adversary selects two challenge keywords, $w_0$ and $w_1$, and sends them to the challenger. The challenger randomly selects $b\in \{0,1\}$ and interacts with two registration servers to obtain $rs{d}_{w_b}\leftarrow \mathsf{IRSD}(\mathcal{G},s{k}_{R{S}_0},s{k}_{R{S}_1},w_b)$.

Guess. 

The adversary outputs its guess $b^{\prime }\in \{0,1\}$ and wins the game if $b=b^{\prime }$, and otherwise fails.

We refer to such an adversary $\mathcal{A}$ in the above game as an IND-RK-CKA adversary and define its advantage as ${\mathsf{Adv}}_{RS,\mathcal{A}}^{\mathrm{IND}\mathrm{-RK}\mathrm{-CKA}}\left(\lambda \right):=\mathrm{Pr}[b=b^{\prime }]-\frac{1}{2}$. If for any polynomial–time adversary $\mathcal{A}$, its advantage ${\mathsf{Adv}}_{CS,\mathcal{A}}^{\mathrm{IND}\mathrm{-TD}\mathrm{-CKA}}\left(\lambda \right)$ is negligible, we say that the scheme satisfies registered keyword indistinguishability.

4. Security Analysis

4.1. Correctness

The RKSE-SM9 scheme’s consistency is demonstrated here, and it may be inferred from the qualities of bilinear pairings.

Recall that

$$\begin{array}{ccc}\hfill H_3\left(\widehat{e}\left(C_1,T_{rs{d}_{w^{\prime }}}\right)\right)& =& H_3\left(\widehat{e}\left(r\left(H_2\left(rs{d}_w\right)P_1+p{k}_R\right),\frac{s{k}_R}{s{k}_R+H_2\left(rs{d}_{w^{\prime }}\right)}{P}_2\right)\right)\hfill \\ & =& H_3\left(\widehat{e}\left(r\left(H_2\left(rs{d}_w\right)P_1+s_1{P}_1\right),\frac{s_1}{s_1+H_2\left(rs{d}_{w^{\prime }}\right)}{P}_2\right)\right)\hfill \\ & =& H_3\left(\widehat{e}\left(r\left(H_2\left(rs{d}_w\right)+s_1\right)P_1,\frac{s_1}{s_1+H_2\left(rs{d}_{w^{\prime }}\right)}{P}_2\right)\right)\hfill \\ & =& H_3\left(\widehat{e}{\left(P_1,P_2\right)}^{r\left(H_2\left(rs{d}_w\right)+s_1\right)\frac{s_1}{s_1+H_2\left(rs{d}_{w^{\prime }}\right)}}\right)\hfill \end{array}$$

$$\begin{array}{ccc}\hfill C_2& =& \hfill H_3\left(g^r\right)=H_3\left(\widehat{e}{\left(p{k}_R,P_2\right)}^r\right)=H_3\left(\widehat{e}{\left(s_1{P}_1,P_2\right)}^r\right)=H_3\left(\widehat{e}{\left(P_1,P_2\right)}^{r{s}_1}\right).\hfill \end{array}$$

If $w=w^{\prime }$, then $rs{d}_w=rs{d}_{w^{\prime }}$, and therefore

$$H_3\left(\widehat{e}\left(C_1,T_{rs{d}_{w^{\prime }}}\right)\right)=H_3\left(\widehat{e}{\left(P_1,P_2\right)}^{r\left(H_2\left(rs{d}_w\right)+s_1\right)\frac{s_1}{s_1+H_2\left(rs{d}_{w^{\prime }}\right)}}\right)=H_3\left(\widehat{e}{\left(P_1,P_2\right)}^{r{s}_1}\right)=C_2.$$

If $w\ne w^{\prime }$, since $H_2$ is collision-resistant, the probability of $H_2\left(rs{d}_w\right)=H_2\left(rs{d}_{w^{\prime }}\right)$ is negligible, and therefore the probability of $H_3\left(\widehat{e}\left(C_1,T_{rs{d}_{w^{\prime }}}\right)\right)=C_2$ is negligible.

Next, we show that the improved keyword registration algorithm can correctly compute a registered keyword.

• $R{S}_0$ computes $u_0=s_{0,0}+H{\left(w\right)}_0$, $e_0=u_0-a_0$ and $f_0=v_0-b_0$, $R{S}_1$ computes $u_1=s_{0,1}+H{\left(w\right)}_1$, $e_1=u_1-a_1$ and $f_1=v_1-b_1$.
• $R{S}_0$ computes ${[u·v]}_0=e·b_0+a_0·f+c_0$, $R{S}_1$ computes ${[u·v]}_1=1·e·f+e·b_1+a_1·f+c_1$.
• $R{S}_0$ and $R{S}_1$ jointly computes

  $$\begin{array}{ccc}\hfill u·vs.& =& {[u·v]}_0+{[u·v]}_1\hfill \\ & =& e·b_0+a_0·f+c_0+1·e·f+e·b_1+a_1·f+c_1\hfill \\ & =& e·\left(b_0+b_1\right)+f·\left(a_0+a_1\right)+e·f+c\hfill \\ & =& e·b+f·a+e·f+a·b\hfill \\ & =& \left(e+a\right)·\left(b+f\right)\hfill \\ & =& u·v.\hfill \end{array}$$
• $R{S}_0$ computes ${\theta }_0{P}_2=\frac{v_0}{u·v}{P}_2$ and $R{S}_1$ computes ${\theta }_1{P}_2=\frac{v_1}{u·v}{P}_2$.
• User computes

  $$\begin{array}{ccc}\hfill rs{d}_w& =& P_2-H_1\left(w\right)·({\theta }_0{P}_2+{\theta }_1{P}_2)\hfill \\ & =& P_2-H_1\left(w\right)·\left(\frac{v_0}{u·v}+\frac{v_1}{u·v}\right)P_2\hfill \\ & =& P_2-H_1\left(w\right)·\frac{1}{u}{P}_2\hfill \\ & =& P_2-\frac{H_1\left(w\right)}{s_0+H_1\left(w\right)}{P}_2\hfill \\ & =& \frac{s_0}{s_0+H_1\left(w\right)}{P}_2.\hfill \end{array}$$

As the registered keyword $rs{d}_w$ above is consistent with the value generated by the original keyword registration algorithm, it is confirmed that the scheme is correct.

4.2. Security Proof

Theorem 1. 

If the q-BCAA problem is hard, then the RKSE-SM9 scheme achieves IND-CT-CKA security in the random oracle model.

Our RKSE-SM9 scheme can be reduced to the $q_{H_1}$-BCAA problem. Figure 3 depicts the process of security reduction. The simulator has two functionalities. When it communicates with the RKSE-SM9 adversary, it serves as the challenger of the RKSE-SM9 scheme. When it communicates with the $q_{H_1}$-BCAA challenger, it turns into the adversary of the $q_{H_1}$-BCAA scheme.

Proof. 

Suppose that $\mathcal{A}$ is any probabilistic polynomial–time (PPT) adversary that can successfully attack the IND-CT-CKA security with advantage $ϵ$. If $\mathcal{A}$ queries the hash random oracles $H_1$, $H_2$, and $H_3$ with times at most $q_{H_1}+2$, $q_{H_2}$, and $q_{H_3}$, then there is a PPT algorithm $\mathcal{B}$ that solves the $q_{H_1}$-BCAA problem with a probability of at least $\frac{2ϵ}{{\left(q_{H_1}+2\right)}^2{q}_{H_3}}$.

Given an instance $\left(P_1,P_2,\alpha P_1,h_0,\left(h_1,\frac{\alpha }{\alpha +h_1}{P}_2\right),\dots ,\left(\frac{\alpha }{\alpha +h_{q_{H_1}}}{P}_2\right)\right)$ of the $q_{H_1}$-BCAA problem, where $P_1$ and $P_2$ are the generators of two prime order cyclic groups $G_1$ and $G_2$, respectively, and there exists a bilinear map $\widehat{e}:G_1\times G_2\to G_T$, then algorithm $\mathcal{B}$ simulates the process of IND-CT-CKA game as follows:

Setup. 

According to the $q_{H_1}$-BCAA problem, the simulator $\mathcal{B}$ first selects three hash functions $H_1:{\{0,1\}}^{*}\to {\mathbb{Z}}_N^{*}$, $H_2:G_2\to {\mathbb{Z}}_N^{*}$, and $H_3:G_T\to {\{0,1\}}^n$, and generates public parameter $\mathcal{G}$ = (N, $G_1$, $G_2$, $G_T$, $\widehat{e}$, $P_1$, $P_2$, $H_1$, $H_2$, $H_3$). Next, $\mathcal{B}$ randomly selects $s_0\in {\mathbb{Z}}_N^{*}$, and let $(p{k}_{RS},s{k}_{RS})=(s_0{P}_1,s_0)$ be the public/private key pair of the RS. $\mathcal{B}$ implicitly chooses the receiver’s private key as $s{k}_R=\alpha$, and then sets the receiver’s public key as $p{k}_R=\alpha P_1$. Finally, $\mathcal{B}$ calculates $g=\widehat{e}(p{k}_R,P_2)$, and sends $\mathcal{G}$, $p{k}_{RS}$, and $p{k}_R$ to adversary $\mathcal{A}$.

Query 1. 

In addition to keyword registration query and keyword trapdoor query, $\mathcal{A}$ can perform queries of three hash functions. Before answering these queries, $\mathcal{B}$ randomly selects two values $i_0^{*}$ and $i_1^{*}$ from $\{1,\dots ,q_{H_1}+2\}$ as the guess results for the challenge keywords $w_0^{*}$ and $w_1^{*}$, respectively, and randomly selects $b\in \{0,1\}$ as a bit in the challenge ciphertext. $\mathcal{A}$ can adaptability query $\mathcal{B}$ as follows:

• Hash queries: $\mathcal{B}$ first creates two hash lists of the form $L=\{<w_i,h_{1,i},rs{d}_i,$$h_{2,i}>\}$ and $L^{\prime }=\{<T_i,h_{2,i}>\}$ that are initialized to be empty.
  • When $\mathcal{A}$ queries the $H_1$ value of the keyword $w_i$, $\mathcal{B}$ first checks whether there is an element by $w_i$ in the list L. It returns the relevant hash value $h_{1,i}$ if it is present; if it does not, $\mathcal{B}$ randomly selects $h_{1,i}\in {\mathbb{Z}}_N^{*}$ and returns it to $\mathcal{A}$. At the same time, because $\mathcal{B}$ knows the secret key $s_0$ of the registration server, it can calculate $rs{d}_i=\frac{s_0}{s_0+h_{1,i}}{P}_2$. If $i\notin \{i_0^{*},i_1^{*}\}$, then $\mathcal{B}$ chooses an unused value $h_j$ from $h_1,\dots h_{q_{H_1}}$ as the $H_2$ value $h_{2,i}=H_2\left(rs{d}_i\right)=h_j$ of $rs{d}_i$; if $i=(1-b)·i_0^{*}+b·i_1^{*}$, then let the $H_2$ value of $rs{d}_i$ be $h_{2,i}=h_0$; otherwise, $\mathcal{B}$ randomly selects a value $h_{2,i}\in {\mathbb{Z}}_N^{*}$ as the $H_2$ value of $rs{d}_i$. Finally, $\mathcal{B}$ stores $<w_i,h_{1,i},rs{d}_i,h_{2,i}>$ into the list L.
  • When $\mathcal{A}$ queries the ${\mathcal{H}}_2$ value of $rs{d}_i$, $\mathcal{B}$ first checks whether there is an element by $rs{d}_i$ in the list L. It returns the relevant hash value $h_{2,i}$ if it exists; if it does not, $\mathcal{B}$ randomly selects $h_{2,i}\in {\mathbb{Z}}_N^{*}$ and returns it to $\mathcal{A}$. Finally, $\mathcal{B}$ stores $<\star ,\star ,rs{d}_i,h_{2,i}>$ into the list L, the symbol “⋆” means that the value is unknown.
  • When $\mathcal{A}$ queries the $H_3$ value of the ciphertext element $T_i$, $\mathcal{B}$ first checks whether there is an element by $T_i$ in the list $L^{\prime }$. It returns the relevant hash value $h_{3,i}$; if it does not, $\mathcal{B}$ randomly selects $h_{3,i}\in {\{0,1\}}^n$ and returns it to $\mathcal{A}$. Finally, $\mathcal{B}$ stores $<T_i,h_{3,i}>$ into the list $L^{\prime }$.
• Keyword registration query: when $\mathcal{A}$ selects and sends a keyword $w_i$ to $\mathcal{B}$, $\mathcal{B}$ first checks whether there is an element $w_i$ in the list L. $\mathcal{B}$ returns the relevant registration keyword $rs{d}_i$ if it exists; otherwise, $\mathcal{B}$ creates the element $<w_i,h_{1,i},rs{d}_i,h_{2,i}>$ according to $H_1$ hash query and adds it to the list L. Finally, $\mathcal{B}$ returns the registration key $rs{d}_i$ to $\mathcal{A}$.
• Trapdoor query: when $\mathcal{A}$ queries the trapdoor of keyword $w_i$, if $i\in \{i_0^{*},i_1^{*}\}$, then $\mathcal{B}$ stops the game; otherwise, $\mathcal{B}$ queries the element containing $w_i$ in the list L, and returns the relevant hash value $h_{2,i}$. Because of the hash value $h_{2,i}\in \{h_1,\dots ,h_{q_{H_1}}\}$ of the registration key $rs{d}_i$ of $w_i$, $\mathcal{B}$ returns the corresponding element $\frac{\alpha }{\alpha +h_{2,i}}{P}_2$ as a trapdoor from the instance of the $q_{H_1}$-BCAA problem to $\mathcal{A}$.

Challenge. 

When $\mathcal{A}$ selects and sends two never-queried keywords $w_0^{*}$ and $w_1^{*}$ to $\mathcal{B}$, $\mathcal{B}$ randomly selects $r^{\prime }\in {\mathbb{Z}}_N^{*}$, computes $C_1^{*}=r^{\prime }{P}_1$ and randomly selects $C_2^{*}\in {\{0,1\}}^n$. Finally, $\mathcal{B}$ sets the challenge ciphertext $C^{*}=(C_1^{*},C_2^{*})$ of keyword $w_b$ and sends it to $\mathcal{A}$.

Query 2. 

$\mathcal{A}$ can continue the query for the keyword registration and trapdoor for any keyword with the exception of the challenge keywords $w_0^{*}$ and $w_1^{*}$.

When $\mathcal{A}$ outputs its guess $b^{\prime }\in \{0,1\}$, $\mathcal{B}$ randomly selects an element $T_i$ from the list $L^{\prime }=\{<T_i,h_{3,i}>\}$, and returns $\left(T_i\right)$ as a solution to the $q_{H_1}$-BCAA problem.

Analysis. In the challenge ciphertext, since

$$C_1^{*}=r^{\prime }{P}_1=\frac{r^{\prime }}{h_0+\alpha }(h_0+\alpha )P_1=\frac{r^{\prime }}{h_0+\alpha }(H_2\left(rs{d}_b\right)P_1+p{k}_R)$$

where $rs{d}_b$ is the registration result of the challenge keyword $w_b^{*}$, when encrypting the keyword $w_b^{*}$, $\mathcal{B}$ implicitly chooses a random number $r^{*}=\frac{r^{\prime }}{h_0+\alpha }modN$. This is consistent with the real game.

In the above game, if $\mathcal{B}$ correctly guesses the challenge keyword, $\mathcal{A}$ queries for the position of the $H_1$ value and never queries the $H_3$ value of element $T^{*}=g^{r^{*}}$ in the real game, then the simulated game above and the real game are completely equivalent. Since $\mathcal{B}$ guesses the challenge key evenly from the $q_{H_1}+2$$H_1$ hash queries of $\mathcal{A}$ and is independent of the information of the adversary, the probability of $\mathcal{B}$ correctly guessing the challenge key in $\mathcal{A}$’s query hash function is at least $\frac{1}{{\left(q_{H_1}+2\right)}^2}$. Let E denote the event “In the real game, $\mathcal{A}$ never asked for the $H_3$ value of element $T^{*}=g^{r^{*}}$. The following proves that the probability that $\mathcal{A}$ has queried the $H_3$ hash value of element $T^{*}=g^{r^{*}}$ is at least $ϵ$.

When E occurs, the challenge ciphertext is independent of the random b selected by the challenger, i.e., the encrypted challenge keyword, so $\mathrm{Pr}[b=b^{\prime }|E]=1/2$. Therefore,

$$\begin{array}{ccc}\hfill \mathrm{Pr}[b=b^{\prime }]& =& \mathrm{Pr}[b=b^{\prime }|E]\mathrm{Pr}\left[E\right]+\mathrm{Pr}[b=b^{\prime }|\neg E]\mathrm{Pr}[\neg E]\hfill \\ & \le & \mathrm{Pr}[b=b^{\prime }|E]\mathrm{Pr}\left[E\right]+\mathrm{Pr}[\neg E]\hfill \\ & =& \frac{1}{2}\mathrm{Pr}\left[E\right]+\mathrm{Pr}[\neg E]\hfill \\ & =& \frac{1}{2}+\frac{1}{2}\mathrm{Pr}[\neg E]\hfill \end{array}$$

$$\begin{array}{ccc}\hfill \mathrm{Pr}[b=b^{\prime }]& =& \mathrm{Pr}[b=b^{\prime }|E]\mathrm{Pr}\left[E\right]+\mathrm{Pr}[b=b^{\prime }|\neg E]\mathrm{Pr}[\neg E]\hfill \\ & \ge & \mathrm{Pr}[b=b^{\prime }|E]\mathrm{Pr}\left[E\right]\hfill \\ & =& \frac{1}{2}\mathrm{Pr}\left[E\right]\hfill \\ & =& \frac{1}{2}-\frac{1}{2}\mathrm{Pr}[\neg E]\hfill \end{array}$$

According to the above inequality, $\mathrm{Pr}[\neg E]\ge 2|\mathrm{Pr}[b=b^{\prime }]-\frac{1}{2}|\ge 2ϵ$ can be deduced. Since $\mathcal{A}$ queries the hash function $H_3$ no more than $q_{H_3}$ times, and $T^{*}=g^{r^{*}}=\widehat{e}{(P_1,P_2)}^{\frac{\alpha r^{\prime }}{\alpha +h_0}}$, the solution ${\left(T_i\right)}^{\frac{1}{r^{\prime }}}$ returned by $\mathcal{B}$ to the $q_{H_1}$-BCAA problem is correct, at least with a probability of $\frac{2ϵ}{q_{H_3}}$. In summary, the probability that $\mathcal{B}$ gets a correct solution to the $q_{H_1}$-BCAA problem is at least $\frac{2ϵ}{{\left(q_{H_1}+2\right)}^2{q}_{H_3}}$.

This completes the proof of Theorem 1. □

Theorem 2. 

If the q-BCAA problem is hard, then the RKSE-SM9 scheme achieves the IND-TD-CKA security in the random oracle model.

Proof. 

In the IND-TD-CKA game, suppose that $\mathcal{A}$ can successfully attack the RKSE-SM9 scheme with advantage $ϵ$ in probabilistic polynomial time. If $\mathcal{A}$ queries the hash random oracles $H_1$, $H_2$, and $H_3$ with times at most $q_{H_1}+2$, $q_{H_2}$, and $q_{H_3}$, then there is a PPT algorithm $\mathcal{B}$ solves the $q_{H_1}$-BCAA problem with a probability at least $\frac{2ϵ}{{\left(q_{H_1}+2\right)}^2{q}_{H_3}}$.

Given an instance $\left(P_1,P_2,\alpha P_1,h_0,\left(h_1,\frac{\alpha }{\alpha +h_1}{P}_2\right),\dots ,\left(\frac{\alpha }{\alpha +h_{q_{H_1}}}{P}_2\right)\right)$ of the $q_{H_1}$-BCAA problem, where $G_1$ and $G_2$ are two prime order cyclic groups with generators $P_1$ and $P_2$, respectively, and $\widehat{e}:G_1\times G_2\to G_T$ is a bilinear map, then algorithm $\mathcal{B}$ simulates the process of IND-TD-CKA game as follows:

Setup. 

Same as in Theorem 1, $\mathcal{B}$ generates system parameters $\mathcal{G}$ according to the instance of $q_{H_1}$-BCAA problem, public/private key pairs $(p{k}_{RS},s{k}_{RS})$, and $(p{k}_R,s{k}_R)$. Specifically, $\mathcal{B}$ implicitly sets $s{k}_{RS}=\alpha$, and hence the corresponding public key is $p{k}_{RS}=\alpha P_1$. $\mathcal{B}$ sends $\mathcal{G}$, $p{k}_{RS}$, and $p{k}_R$ to the adversary $\mathcal{A}$.

Query 1. 

Similar to Theorem 1, $\mathcal{A}$ can query adaptively as follows:

• Hash queries: $\mathcal{B}$ creates three hash lists of the form $L=\{<w_i,h_{1,i}>\}$, $L_2=\{<rs{d}_i,h_{2,i}>\}$, and $L_3=\{<T_i,h_{2,i}>\}$ that are initialized to be empty.
  • When $\mathcal{A}$ queries the $H_1$ value of the keyword $w_i$, $\mathcal{B}$ first checks whether there is an element by $w_i$ in the list $L_1$. It returns the relevant hash value $h_{1,i}$ if it exists; if it does not and $i\notin \{i_0^{*},i_1^{*}\}$, then $\mathcal{B}$ selects an unused value $h_j$ from $h_1,\dots h_{q_{H_1}}$ as the $H_1$ value $h_{1,i}=H_1\left(w_i\right)=h_j$ of $w_i$; if it does not exist and $i=(1-b)·i_0^{*}+b·i_1^{*}$, then let $H_1$ value of $w_i$ is $h_{1,i}=h_0$; Otherwise, $\mathcal{B}$ randomly selects a value $h_{1,i}\in {\mathbb{Z}}_N^{*}$ as the $H_1$ value of $w_i$. Finally, $\mathcal{B}$ stores $<w_i,h_{1,i}>$ into the list L.
  • When $\mathcal{A}$ queries the ${\mathcal{H}}_2$ value of the registered keyword $rs{d}_i$, $\mathcal{B}$ first checks whether there is an element containing $rs{d}_i$ in the list $L_2$. It returns the relevant hash value $h_{2,i}$ if it exists; if it does not, $\mathcal{B}$ randomly selects $h_{2,i}\in {\mathbb{Z}}_N^{*}$ and returns it to $\mathcal{A}$. Finally, $\mathcal{B}$ stores $<rs{d}_i,h_{2,i}>$ into the list L.
  • When $\mathcal{A}$ queries $H_3$ value of the ciphertext element $T_i$, $\mathcal{B}$ first checks whether there is an element by $T_i$ in the list $L_3$. It returns the relevant hash value $h_{3,i}$ if it exists; if it does not, $\mathcal{B}$ randomly selects $h_{3,i}\in {\{0,1\}}^n$ and returns it to $\mathcal{A}$. Finally, $\mathcal{B}$ stores $<T_i,h_{3,i}>$ into the list $L_3$.
• Keyword registration query: $\mathcal{B}$ initializes a list of registered keywords in the form of $R=\{<w_i,rs{d}_i>\}$. When $\mathcal{A}$ makes a registration query for the keyword $w_i$, if $i\in \{i_0^{*},i_1^{*}\}$, then $\mathcal{B}$ terminates the game. Otherwise, $\mathcal{B}$ queries list R for elements containing $w_i$ and returns the corresponding registered key $rs{d}_i$. If it does not exist, $\mathcal{B}$ queries the element containing $w_i$ in the list $L_1$, and takes out the corresponding $H_1$ value $h_{1,i}$. Since $h_{1,i}\in \{h_1,\dots ,h_{q_{H_1}}\}$, $\mathcal{B}$ returns $\frac{\alpha }{\alpha +h_{1,j}}{P}_2$ as the registration key $rs{d}_i$ of $w_i$ to $\mathcal{A}$, and stores $<w_i,rs{d}_i>$ into the list R.
• Trapdoor query: When $\mathcal{A}$ queries the trapdoor of keyword $w_i$, if $i\in \{i_0^{*},i_1^{*}\}$, then $\mathcal{B}$ stops the game; Otherwise, $\mathcal{B}$ queries the element containing $w_i$ in the list R, and takes out the corresponding registered keyword $rs{d}_i$. Since $\mathcal{B}$ has the receiver’s private key $s{k}_R$, $\mathcal{B}$ can use the private key to compute the corresponding trapdoor $T_{rs{d}_i}$ and return it to $\mathcal{A}$.

Challenge. 

When $\mathcal{A}$ selects and sends two never-queried keywords $w_0^{*}$ and $w_1^{*}$ to $\mathcal{B}$, $\mathcal{B}$ randomly selects an element $T^{*}\in G_2$ as a challenger trapdoor for the keyword $w_b^{*}$ and sends it to $\mathcal{A}$.

Query 2. 

Same as in Theorem 1.

When $\mathcal{A}$ outputs its guess $b^{\prime }\in \{0,1\}$, $\mathcal{B}$ randomly selects an element $<rs{d}_i,h_{2,i}>$ from the list $L_2$, and returns $rs{d}_i$ as a solution to the $q_{H_1}$-BCAA problem.

Analysis. In the simulated game above, if $\mathcal{B}$ correctly guesses the challenge keyword where $\mathcal{A}$ queries the hash function $H_1$, then $\mathcal{B}$ will not terminate the game. Since $\mathcal{B}$ randomly guesses the position of the challenge keyword independently of $\mathcal{A}$, the probability of guessing correctly is at least $\frac{1}{{\left(q_{H_1}+2\right)}^2}$. The following proves that the probability of $\mathcal{A}$ querying the hash value $H_2\left(\frac{\alpha }{\alpha +H_1\left(w_b^{*}\right)}\right)$ in a real game is at least $ϵ$.

Let E denote the event “$\mathcal{A}$ did not query $H_2\left(\frac{\alpha }{\alpha +H_1\left(w_0^{*}\right)}\right)$ or $H_2\left(\frac{\alpha }{\alpha +H_1\left(w_1^{*}\right)}\right)$ in the real game”. When event E occurs, the bit $b\in \{0,1\}$ chosen by the challenger is independent of $\mathcal{A}$, i.e., the probability of $b=b^{\prime }$ is $1/2$. Because

$$\begin{array}{ccc}\hfill \mathrm{Pr}[b=b^{\prime }]& =& \mathrm{Pr}[b=b^{\prime }|E]\mathrm{Pr}\left[E\right]+\mathrm{Pr}[b=b^{\prime }|\neg E]\mathrm{Pr}[\neg E]\hfill \\ & \le & \mathrm{Pr}[b=b^{\prime }|E]\mathrm{Pr}\left[E\right]+\mathrm{Pr}[\neg E]\hfill \\ & =& \frac{1}{2}\mathrm{Pr}\left[E\right]+\mathrm{Pr}[\neg E]\hfill \\ & =& \frac{1}{2}+\frac{1}{2}\mathrm{Pr}[\neg E]\hfill \end{array}$$

$$\begin{array}{ccc}\hfill \mathrm{Pr}[b=b^{\prime }]& =& \mathrm{Pr}[b=b^{\prime }|E]\mathrm{Pr}\left[E\right]+\mathrm{Pr}[b=b^{\prime }|\neg E]\mathrm{Pr}[\neg E]\hfill \\ & \ge & \mathrm{Pr}[b=b^{\prime }|E]\mathrm{Pr}\left[E\right]\hfill \\ & =& \frac{1}{2}\mathrm{Pr}\left[E\right]\hfill \\ & =& \frac{1}{2}-\frac{1}{2}\mathrm{Pr}[\neg E]\hfill \end{array}$$

so, $\mathrm{Pr}[\neg E]\ge 2|\mathrm{Pr}[b=b^{\prime }]-\frac{1}{2}|\ge 2ϵ$. Therefore, the probability that $\mathcal{A}$ queries $H_2\left(\frac{\alpha }{\alpha +H_1\left(w_b^{*}\right)}\right)$ is at least $ϵ$.

When $\mathcal{B}$ correctly guesses the challenge keyword, the game environment simulated by $\mathcal{B}$ is the same as the real game environment. Since the probability of $\mathcal{A}$ querying $H_2\left(\frac{\alpha }{\alpha +H_1\left(w_b^{*}\right)}\right)$ is at least $ϵ$, $\mathcal{B}$ obtains the group element $\frac{\alpha }{\alpha +H_1\left(w_b^{*}\right)}$ with a probability of at least $\frac{ϵ}{q_{H_2}}$. Thus, $\mathcal{B}$ can compute the correct solution $\widehat{e}\left(P_1,\frac{\alpha }{\alpha +H_1\left(w_b^{*}\right)}\right)$ of the $q_{H_1}$-BCAA problem. Furthermore, because the probability that $\mathcal{B}$ does not terminate the game is at least $\frac{1}{{\left(q_{H_1}+2\right)}^2}$, it follows that the probability that succeeds is at least $\frac{ϵ}{{\left(q_{H_1}+2\right)}^2{q}_{H_2}}$.

This completes the proof of Theorem 2. □

Theorem 3. 

In the improved registered keyword generation algorithm, if the two registration servers do not collude, the scheme in this paper satisfies the indistinguishability of the registered keywords.

Proof. 

Since the two servers are equivalent when generating the registration key, we might as well assume that the registration server $R{S}_0$ is malicious (an adversary), while the registration server $R{S}_1$ is legitimate and will not collude with the registration server $R{S}_0$. It is proved below that the registration server cannot obtain any information about the registration key.

Setup. 

The simulator runs the registration server key generation algorithm to generate the public/private key pair of $R{S}_0$ and $R{S}_1$, and sends the public keys and the private key of $R{S}_0$ to the adversary.

Challenge. 

When the simulator receives the challenge keywords $w_0$ and $w_1$ from the adversary, the challenger simulates the registration keyword generation algorithm as follows:

• The simulator randomly selects $b\in \{0,1\}$ and computes $H_1\left(w_b\right)$;
• The simulator randomly selects $H_1{\left(w_b\right)}_0\in {\mathbb{Z}}_N^{*}$, sets $H_1{\left(w_b\right)}_1=H_1\left(w_b\right)-H_1{\left(w_b\right)}_{0}modN$, and sends $H_1{\left(w_b\right)}_0$ to the adversary;
• The simulator randomly selects $a_0,b_0,c_0\in {\mathbb{Z}}_N^{*}$ and sends them to the adversary;
• The simulator randomly selects $v_0\in {\mathbb{Z}}_N^{*}$ and sends it to the adversary;
• The Simulator randomly selects $e_1,f_1\in {\mathbb{Z}}_N^{*}$ and sends them to the adversary. When it receives $e_0$ and $f_0$ from the adversary, the simulator computes $e=e_0+e_{1}modN$ and $f=f_0+f_{1}modN$;
• The simulator randomly selects ${[u·v]}_1\in {\mathbb{Z}}_N^{*}$ and sends it to the adversary;
• When it receives ${[u·v]}_0$ from the adversary, the simulator computes $u·v={[u·v]}_0+{[u·v]}_{1}modN$;
• When it receives ${\theta }_0{P}_2$ from the adversary, the simulator computes ${\theta }_1{P}_2=\frac{v_1}{u·v}{P}_2$;
• The simulator computes $rs{d}_w=P_2-H_1\left(w_b\right)({\theta }_0{P}_2+{\theta }_1{P}_2)$;

Guess. 

The adversary outputs a guessed bit $b^{\prime }\in \{0,1\}$.

Analysis. In Step 5 and Step 6 above, since

$$\left\{\begin{array}{c}{u}_1-a_1=e_{1}modN\hfill \\ v_1-b_1=f_{1}modN\hfill \\ e·f+e·b_1+a_1·f+c_1={[u·v]}_{1}modN\hfill \\ (a_0+a_1)(b_0+b_1)=c_0+c_{1}modN\hfill \end{array}\right.$$

and other parameters are known except $a_1$, $b_1$, $c_1$, and $v_1$, where $u_1=s_{0,1}+H_1{\left(w_b\right)}_1$, the above equation implicitly determines the shares $a_1$, $b_1$, $c_1$, and $v_1$ of the parameters a, b, c, and v. Therefore, the game simulated by the simulator is exactly the same as the real game.

In the simulated game, since the information sent by the simulator to the adversary is randomly selected and independent of the challenge keyword $w_b$, the probability that the adversary’s guess $b^{\prime }$ is correct is 1/2; that is, the advantage is zero.

This completes the proof of Theorem 3. □

5. Implementation and Performance

5.1. Efficiency Analysis

Up to now, no SM9-based registration keyword searchable encryption scheme has been found. For resisting insider keyword guessing attacks, we compared six studies [8,13,15,17,18,30] theoretically.

• Computation. In

  Table 2. Time consumption of basic operations (ms).

  Operations	${\mathit{T}}_{\mathbf{exp}\mathit{t}}$	${\mathit{T}}_{\mathsf{m}1}$	${\mathit{T}}_{\mathsf{m}2}$	${\mathit{T}}_{\mathbf{bp}}$	${\mathit{H}}_{{\mathit{G}}_{\mathit{T}}}$	${\mathit{T}}_{\mathit{H}}$
  Execution time	14.3	1.78	3.43	68.7	41.2	$\approx 0$

  , the time of common cryptographic operations is defined by taking the Type-F curve as an example, where $T_{\mathrm{b}\mathrm{p}}$ represents the time of bilinear pairing operation, $T_{\mathrm{e}\mathrm{x}\mathrm{p}t}$ represents the time of exponential operations over groups $G_T$, $T_{\mathrm{m}1}$ and $T_{\mathrm{m}2}$ represent the time of scalar multiplication operations of groups $G_1$ and $G_2$, respectively, and $H_{G_T}$ and $T_H$ represent the time of mapping a value to $G_T$ and ${\{0,1\}}^n$, respectively. The operation results in Table 2 are our simulations. It can be seen from Table 2 that the order of commonly used cryptographic operation time is $T_{\mathrm{b}\mathrm{p}}>H_{G_T}>T_{\exp t}>T_{\mathrm{m}2}>T_{\mathrm{m}1}>T_H$. Note that the operations $T_{\mathrm{b}\mathrm{p}}$ and $H_{G_T}$ are much larger than other operations, and the operations $T_H$ are close to 0.
  Table 3. Computational overhead.

  Schemes	PEKS Ciphertext	Trapdoor	Testing
  [8]	$T_{\mathrm{bp}}+2T_{\mathrm{m}1}+H_{G_T}$	$T_{\mathrm{m}1}$	$T_{\mathrm{bp}}+H_{G_T}$
  [13]	$T_{\mathrm{bp}}+2T_{\mathrm{m}1}+T_H$	$3T_{\mathrm{m}1}+2T_H$	$T_{\mathrm{bp}}+2T_{\mathrm{m}1}+T_H$
  [15]	$T_{\mathrm{bp}}+2T_{\mathrm{m}1}+2T_H$	$T_{\mathrm{m}1}+T_H$	$T_{\mathrm{bp}}+T_H$
  [17]	$2T_{\mathrm{bp}}+3T_{\mathrm{m}1}+2T_H$	$T_{\mathrm{bp}}+2T_{\mathrm{m}1}+2T_H$	$2T_{\mathrm{bp}}$
  [18]	$T_{\mathrm{bp}}+3T_{\mathrm{m}1}+2T_H$	$2T_{\mathrm{m}1}+T_H$	$T_{\mathrm{bp}}+T_H$
  [30]	$2T_{\mathrm{m}1}+T_{\exp t}+T_H$	$T_{\mathrm{m}2}+T_H$	$T_{\mathrm{bp}}$
  Our Scheme	$2T_{\mathrm{m}1}+T_{\exp t}+T_H$	$T_{\mathrm{m}2}+T_H$	$T_{\mathrm{bp}}+T_H$

  compares the operations required by PEKS Ciphertext, Trapdoor, and Testing of each scheme. The main comparison operations include bilinear pairing operations, exponential operations, multiplication operations, and hash operations. It can be seen from Table 3 that RKSE-SM9 is the same as that of [30], and better than others in the ciphertext algorithm. This is because other schemes have bilinear pairing operations in the PEKS Ciphertext. For Trapdoor, our scheme and that of [30] have the same operations, which are slightly slower than that of [8,15] and faster than others. For Testing, our scheme is the same as that of [15,18], closer to that of [30] and faster than the schemes of [8,13,17].
• Communication. In

  Table 4. Communication overhead.

  Schemes	Public Key Size	PEKS Ciphertext Size	Trapdoor Size
  [8]	$3|G_1|+|G_T|$	$|G_1|+|G_T|$	$|G_1|$
  [13]	$|G_1|$	$|G_1|$	$2|G_1|$
  [15]	$|G_1|$	$2|G_1|$	$|G_T|$
  [17]	∖	$2|G_1|+|G_T|$	2$|G_1|$
  [18]	$|G_1|$	$|G_1|$	$|G_1|$
  [30]	$|G_1|$	$|G_1|$	$|G_2|$
  Our Scheme	$|G_1|$	$|G_1|$	$|G_2|$

  , we use $|G_1|$, $|G_2|$, and $|G_T|$ to denote the element lengths in groups $G_1$, $G_2$, and $G_T$, respectively. The scheme of [8] requires the most expensive communication overhead when generating a public key, whereas the schemes [8,15,17] require the least amount of communication overhead when generating PEKS Ciphertext and are consistent with our scheme in terms of communication overhead, while our system and the one in [30] have comparable communication costs.

5.2. Experimental Results

Experimental simulation of the above three schemes are evaluated under the following environment: Windows 10 operating system, 1.0 GHz 4-core 64-bit Intel(R) Core(TM) i5-1035G1 CPU, 16 GB RAM, with IntelliJ IDEA 2021 as the experimental platform, using Java as the programming language, and using the JPBC package (Java pairing-based cryptography library2.0), wherein the Type-F curve in the library is used to construct an asymmetric prime order bilinear group, and the order of the curve group is 256 bits with embedding degree $k=12$.

Since the schemes [13,15,17,18] have different systems from our scheme, the scheme in this paper mainly compares it with the schemes in the studies [8,30] through experiments. SA-PEKS [8] is the first server-aided searchable encryption scheme with registered keywords, but its scheme is not based on the standard SM9. The scheme SM9-PEKS [30] is a searchable encryption scheme based on SM9, but it is not a registration keyword searchable encryption scheme, and it cannot resist KGA. First, we increase the number of keywords to experiment with each algorithm and test the execution time of the same algorithm in different schemes. Then, the running time of the original registration keyword generation algorithm proposed in this paper and the improved registration keyword algorithm is compared. During each collection of data, the results will be analyzed and summarized. All the experimental results are as follows.

Figure 4 shows the time consumed by PEKS Ciphertext in each scheme, with the number of keywords on the x-axis and time on the y-axis. The PEKS Ciphertext of our scheme is almost the same as the scheme of [30], and is better than the scheme of [8]. Specifically, when generating 1000 keyword ciphertexts, the time for our scheme is 19 s, the time for [8] is 119 s, and the scheme of [30] takes the same time as our scheme. It can be seen from Table 3 that in the PEKS Ciphertext, our scheme and [30] do not require the time-consuming operations of $T_{bp}$ and $T_{G_T}$. Thus, compared with the scheme of [8], our scheme improves the efficiency of the PEKS Ciphertext by 84%.

Figure 5 shows the running time of the Trapdoor in each scheme, where the x-axis is the number of keywords and the y-axis is the time required by the Trapdoor. From the figure, we can see that when generating 1000 keyword trapdoors, the time of our scheme as well as [30] is 3.6 s, while the time of the scheme of [8] is 2.3 s. It can be seen from Table 3 that our Trapdoor time is slower than that of [8] in theoretical analysis, as it is in the experiment.

Figure 6 displays the amount of time that Testing takes to execute in each scheme, with the time needed for Testing shown on the y-axis and the number of keywords on the x-axis. It can be seen that the efficiency of our scheme is slightly lower than the scheme of [30], but is much better than the scheme of [8]. Specifically, when running Testing 1000 times, the time of our scheme is 67 s, the time of [8] is 114.2 s, and the time of [30] is 66 s. Compared with the scheme of [8], our scheme does not require the time-consuming operations of $H_{G_T}$; our scheme improves the efficiency of the Testing by 41.3%.

Figure 7 displays the average runtime of each algorithm under different schemes, with time shown on the y-axis. In our scheme, the total time required to execute the whole process of PEKS ciphertext, Trapdoor, and Testing is 88 milliseconds, the [30] is 87 milliseconds, and the [8] is 236 milliseconds. It can be seen that the overall efficiency of our scheme is 63% higher than the scheme of [8]. Although the efficiency is reduced by 1% compared with the scheme of [30], our scheme guarantees stronger security against KGA using a few additional computing operations.

Figure 8 compares the registration keyword algorithm’s efficiency between the basic scheme and the improved scheme put forward in this work. The x-axis represents the number of keywords, while the y-axis represents time. This improved scheme includes the time the two registration servers operated together. It can be clearly seen from Figure 8 that the improved scheme is two times slower than the original scheme, but its security can satisfy the indistinguishability of the registered keywords.

To sum up, under the theoretical analysis and practical implementation, our SM9-based searchable encryption scheme considers the factors of computation overhead and communication overhead. Compared with the server-aided registration keyword searchable encryption scheme of [8], its efficiency has a significant advantage. Compared with the SM9-based searchable encryption scheme of [30], its efficiency is only reduced by 1% to ensure stronger security against keyword-guessing attacks.

6. Conclusions

Aiming at the existing SM9 public key searchable encryption scheme, it cannot resist internal KGA. A searchable encryption scheme based on SM9 with registration keywords is proposed. The identity key generation algorithm in SM9 is used to construct a registered keyword generation algorithm, and a registered keyword server is used against insider KGA. The scheme has been proven correct and secure in different security models. However, the basic scheme can only ensure that a part of the keyword information is covered and still needs to satisfy registered keywords’ privacy. To solve this issue, we add two servers, use Beaver triples to run the registration keyword algorithm interactively, and propose an improved searchable encryption scheme for registered keywords. It can cover up keyword information reasonably and efficiently, improve security, realize the privacy-preserving user data, and satisfy the indistinguishability of registered keywords. The RKSE-SM9 has much greater computing efficiency than the registered keyword searchable encryption algorithms in PEKS Ciphertext, Trapdoor, and Testing, according to theoretical analysis and simulation experiment outcomes. As a result, the suggested plan is a searchable encryption plan that ensures heavy security and fulfills effective keyword searching. Regrettably, our plan is not strong enough to withstand a server collusion attack.

Work in the future will concentrate more on scenario applications. At the moment, our search strategy only supports one term. To create a multi-keyword searchable encryption system, it may be merged with broadcast encryption in the next step. Try adding and deleting keywords; a subsequent encryption method can be built to be searchable and updateable.