# Registered Keyword Searchable Encryption Based on SM9
## 2 Preliminaries
### Baver Triple
When \(E\) occurs, the challenge ciphertext is independent of the random \(b\) selected by the challenger, i.e., the encrypted challenge keyword, so \(\Pr[b=b^{\prime}|E]=1/2\). Therefore,

\[H_{3}\Big{(}\hat{e}\Big{(}C_{1},T_{\mathit{rsd}_{w^{\prime}}} \Big{)}\Big{)} = H_{3}\bigg{(}\hat{e}\bigg{(}r(H_{2}(\mathit{rsd}_{w})P_{1}+pk_{R}), \frac{sk_{R}}{sk_{R}+H_{2}(\mathit{rsd}_{w^{\prime}})}P_{2}\bigg{)}\bigg{)}\]1 \[H_{3}\Big{(}\hat{e}\Big{(}C_{1},T_{\mathit{rsd}_{w^{\prime}}} \Big{)}\Big{)} = H_{3}\bigg{(}\hat{e}\bigg{(}r(H_{2}(\mathit{rsd}_{w})P_{1}+pk_{R}), \frac{sk_{R}}{sk_{R}+H_{2}(\mathit{rsd}_{w^{\prime}})}P_{2}\bigg{)}\bigg{)}\]2 \[H_{3}\Big{(}\hat{e}\Big{(}C_{1},T_{\mathit{rsd}_{w^{\prime}}} \Big{)}\Big{)} = H_{3}\bigg{(}\hat{e}\bigg{(}r(H_{2}(\mathit{rsd}_{w})P_{1}+pk_{R}), \frac{sk_{R}}{sk_{R}+H_{2}(\mathit{rsd}_{w^{\prime}})}P_{2}\bigg{)}\bigg{)}\]3

\[H_{3}\Big{(}\hat{e}\Big{(}C_{1},T_{\mathit{rsd}_{w^{\prime}}} \Big{)}\Big{)} = H_{3}\bigg{(}\hat{e}\bigg{(}r(H_{2}(\mathit{rsd}_{w})P_{1}+pk_{R}), \frac{sk_{R}}{sk_{R}+H_{2}(\mathit{rsd}_{w^{\prime}})}P_{2}\bigg{)}\bigg{)}\]4

According to the above inequality, \(\Pr[\
eg E]\geq 2|\Pr[b=b^{\prime}]-\frac{1}{2}|\geq 2\epsilon\) can be deduced. Since \(\mathcal{A}\) queries the hash function \(H_{3}\) no more than \(q_{H_{3}}\) times, and \(T^{*}=g^{r^{*}}=\delta(P_{1},P_{2})^{\frac{g^{r^{*}}}{\delta+h_{0}}}\), the solution \((T_{i})^{\frac{1}{r^{*}}}\) returned by \(\mathcal{B}\) to the \(q_{H_{1}}\)-BCAA problem is correct, at least with a probability of \(\frac{2\epsilon}{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\epsilon}{\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 \(e\) 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\epsilon}{\left(q_{H_{1}}+2\right)^{2}q_{H_{3}}}\). Given an instance \(\left(P_{1},P_{2},aP_{1},h_{0},\left(h_{1},\frac{a}{\alpha+h_{1}}P_{2}\right),\ldots,\left(\frac{a}{\alpha+h_{H_{1}}}P_{2}\right)\right)\) of the \(q_{H_{1}}\)-BCAA problem, where \(G_{1}\) and \(\hat{G}_{2}\) are two prime order cyclic groups with generators \(P_{1}\) and \(P_{2}\)respectively, and \(\hat{\epsilon}: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 \((pk_{RS},sk_{RS})\), and \((pk_{R},sk_{R})\). Specifically, \(\mathcal{B}\) implicitly sets \(sk_{RS}=\alpha\), and hence the corresponding public key is \(pk_{RS}=\alpha P_{1}\). \(\mathcal{B}\) sends \(\mathcal{G}\), \(pk_{RS}\), and \(pk_{R}\) to the adversary \(\mathcal{A}\). **Query 1**. : Similar to Theorem 1, \(\mathcal{A}\) can query adaptively as follows:

1. [label=0.] 2. Hash queries: \(\mathcal{B}\) creates three hash lists of the form \(L=\{<w_{i},h_{1,i}>\}\), \(L_{2}=\{<rsd_{i},h_{2,i}>\}\), and \(L_{3}=\{<T_{i},h_{2,i}>\}\) that are initialized to be empty. 3. 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}\).