# Registered Keyword Searchable Encryption Based on SM9
## 2 Preliminaries
### Baver Triple
\(\hat{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}(\mathcal{G})\to(pk_{RS},sk_{RS})\): Input \(\mathcal{G}\), the registration server picks a random \(s_{0}\in\mathbb{Z}_{N}^{*}\) and outputs the RS's key pair as \((pk_{RS},sk_{RS})=(s_{0}P_{1},s_{0})\). * \(\mathsf{KeyGen}_{R}(\mathcal{G})\to(pk_{R},sk_{R})\): Input \(\mathcal{G}\), the receiver picks a random \(s_{1}\in\mathbb{Z}_{N}^{*}\), computes \(g=\hat{e}(s_{1}P_{1},P_{2})\), and outputs the receiver's key pair \((pk_{R},sk_{R})=(s_{1}P_{1},s_{1})\). It publishes \(pk_{R}\) and \(g\), and keeps \(sk_{R}\) secretly. * \(\mathsf{RSD}(\mathcal{G},sk_{RS},w)\to rsd_{w}\): Input \(\mathcal{G}\), \(sk_{RS}\), and \(w\), it outputs the RS-derived keyword \(rsd_{w}\) of \(w\). The RSD algorithm is shown in Figure 2.
* \(\mathsf{PEKS}(\mathcal{G},pk_{R},rsd_{w})\to C_{rsd_{w}}\): Input \(\mathcal{G}\), \(pk_{R}\), and \(rsd_{w}\), the sender picks a random \(r\in\mathbb{Z}_{N}^{*}\), computes \(C_{1}=r(H_{2}(rsd_{w})P_{1}+pk_{R})\) and \(C_{2}=H_{3}(g^{r})\), and finally outputs the PEKS ciphertext \(C_{rsd_{w}}=(C_{1},C_{2})\). * \(\mathsf{Trapdoor}(\mathcal{G},sk_{R},rsd_{w^{\prime}})\to T_{rsd_{w^{\prime}}}\): Input \(\mathcal{G}\), \(sk_{R}\), and \(rsd_{w^{\prime}}\), the receiver computes \(T_{rsd_{w^{\prime}}}=\left(\frac{sk_{R}}{sk_{R}+H_{2}(rsd_{w^{\prime}})}\right) P_{2}\) and outputs the search trapdoor \(T_{rsd_{w^{\prime}}}\). * \(\mathsf{Test}(\mathcal{G},C_{rsd_{w^{\prime}}},T_{rsd_{w^{\prime}}})\to 1/0\): Input \(\mathcal{G}\), \(C_{rsd_{w^{\prime}}}\), and \(T_{rsd_{w^{\prime}}}\), the CS checks \(H_{3}(\hat{e}(C_{1},T_{rsd_{w^{\prime}}}))\)\(=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}(w)\) 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}_{RS_{i}}(\mathcal{G})\to(pk_{RS_{i^{\prime}}},sk_{RS_{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 \((pk_{RS_{0}},sk_{RS_{0}})=(s_{0,0}P_{1},s_{0,0})\) and \((pk_{RS_{1}},sk_{RS_{1}})=(s_{0,1}P_{1},s_{0,1})\), respectively. The servers publish \(pk_{RS_{0}}\) and \(pk_{RS_{1}}\), and keep \(sk_{RS_{0}}\) and \(sk_{RS_{1}}\) secretly. Let \(s_{0}=s_{0,0}+s_{0,1}\bmod N\). The two servers jointly compute \(pk_{RS}=s_{0}P_{1}=pk_{RS_{0}}+pk_{RS_{1}}\). Unless otherwise specified, the following operations are performed over ring \(\mathbb{Z}_{N}\). * \(\mathsf{IRSD}(\mathcal{G},sk_{RS},w)\to rsd_{w}\): Input \(\mathcal{G}\), \(sk_{RS_{i}}\) of the \(RS_{i}\), and \(w\), the two servers jointly compute the RS-derived keyword \(rsd_{w}\) for a user, so that no server knows the value the keyword \(w\). it outputs the RS-derived keyword \(rsd_{w}\) of \(w\). The improved RSD algorithm \(\mathsf{IRSD}\) is described as follows: 1. User selects a keyword \(w\) to be registered and hashes it to obtain \(H_{1}(w)\). 2. The user sends the secret sharing \(H_{1}(w)=H_{1}(w)_{0}+H_{1}(w)_{1}\) to \(RS_{0}\) and \(RS_{1}\), respectively.