# Registered Keyword Searchable Encryption Based on SM9
## 2 Preliminaries
### Baver Triple
Finally, \(\mathcal{B}\) stores \(<\star,\star,rsd_{i},h_{2,i}>\) into the list \(L\), the symbol \"\(\star\)\" 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}\). 2. 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 \(rsd_{i}\) if it exists; otherwise, \(\mathcal{B}\) creates the element \(<w_{i},h_{1,i},rsd_{i},h_{2,i}>\) according to \(H_{1}\) hash query and adds it to the list \(L\). Finally, \(\mathcal{B}\) returns the registration key \(rsd_{i}\) to \(\mathcal{A}\). 3. 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},\ldots,h_{q_{H_{1}}}\}\) of the registration key \(rsd_{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}\). 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 \((T_{i})\) as a solution to the \(q_{H_{1}}\)-BCAA problem. **Analysis. ** In the challenge ciphertext, since

\[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{)}\]0

where \(rsd_{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}\bmod N\). 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 \(\epsilon\).