# Registered Keyword Searchable Encryption Based on SM9
## 2 Preliminaries
### Baver Triple
The challenger randomly selects_ \(b\in\{0,1\}\) _and interacts with two registration servers to obtain_ \(rsd_{w_{b}}\leftarrow\mathsf{IRSD}(\mathcal{G},sk_{RS_{0}},sk_{RS_{1}},w_{b})\)_._
* _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,A}^{\text{IND-RK-CKA}}(\lambda):=\Pr[b=b^{\prime}]-\frac{1}{2}\). If for any polynomial-time adversary \(\mathcal{A}\), its advantage \(\mathsf{Adv}_{\text{CS,A}}^{\text{IND-TD-CKA}}(\lambda)\) is negligible, we say that the scheme satisfies registered keyword indistinguishability._

## 4 Security Analysis

### Correctness

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

\[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{)}\] \[= H_{3}\bigg{(}\hat{e}\bigg{(}r(H_{2}(\mathit{rsd}_{w})P_{1}+s_{1}P _{1}),\frac{s_{1}}{s_{1}+H_{2}(\mathit{rsd}_{w^{\prime}})}P_{2}\bigg{)}\bigg{)}\] \[= H_{3}\bigg{(}\hat{e}\bigg{(}r(H_{2}(\mathit{rsd}_{w})+s_{1})P_{1},\frac{s_{1}}{s_{1}+H_{2}(\mathit{rsd}_{w^{\prime}})}P_{2}\bigg{)}\bigg{)}\] \[= H_{3}\bigg{(}\hat{e}(P_{1},P_{2})^{r(H_{2}(\mathit{rsd}_{w})+s_{1 })\frac{s_{1}}{s_{1}+H_{2}(\mathit{rsd}_{w^{\prime}})}}\bigg{)}\]

\[C_{2} = H_{3}(g^{r})=H_{3}\big{(}\hat{e}(pk_{R},P_{2})^{r}\big{)}=H_{3} \big{(}\hat{e}(s_{1}P_{1},P_{2})^{r}\big{)}=H_{3}\big{(}\hat{e}(P_{1},P_{2})^{ rs_{1}}\big{)}.\]

If \(w=w^{\prime}\), then \(\mathit{rsd}_{w}=\mathit{rsd}_{w^{\prime}}\), and therefore

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

If \(w\
eq w^{\prime}\), since \(H_{2}\) is collision-resistant, the probability of \(H_{2}(\mathit{rsd}_{w})=H_{2}(\mathit{rsd}_{w^{\prime}})\) is negligible, and therefore the probability of \(H_{3}\Big{(}\hat{e}\Big{(}C_{1},T_{\mathit{rsd}_{w^{\prime}}}\Big{)}\Big{)}=C_ {2}\) is negligible. Next, we show that the improved keyword registration algorithm can correctly compute a registered keyword. 1. \(RS_{0}\) computes \(u_{0}=s_{0,0}+H(w)_{0}\), \(e_{0}=u_{0}-a_{0}\) and \(f_{0}=v_{0}-b_{0}\), \(RS_{1}\) computes \(u_{1}=s_{0,1}+H(w)_{1}\), \(e_{1}=u_{1}-a_{1}\) and \(f_{1}=v_{1}-b_{1}\). 2. \(RS_{0}\) computes \([u\cdot v]_{0}=e\cdot b_{0}+a_{0}\cdot f+c_{0}\), \(RS_{1}\) computes \([u\cdot v]_{1}=1\cdot e\cdot f+e\cdot b_{1}+a_{1}\cdot f+c_{1}\). 3. \(RS_{0}\) and \(RS_{1}\) jointly computes \[u\cdot v. = [u\cdot v]_{0}+[u\cdot v]_{1}\] \[= e\cdot b_{0}+a_{0}\cdot f+c_{0}+1\cdot e\cdot f+e\cdot b_{1}+a_{ 1}\cdot f+c_{1}\] Figure 2:0 Figure 2:1 Figure 2:2 Figure 2:3
4. \(RS_{0}\) computes \(\theta_{0}P_{2}=\frac{v_{0}}{\mathit{i}\cdot v}P_{2}\) and \(RS_{1}\) computes \(\theta_{1}P_{2}=\frac{v_{1}}{\mathit{i}\cdot v}P_{2}\). 5. User computes Figure 2:4 Figure 2:5 Figure 2:6 Figure 2:7 Figure 2:8

As the registered keyword \(\mathit{rsd}_{w}\) above is consistent with the value generated by the original keyword registration algorithm, it is confirmed that the scheme is correct. ### 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.