# Registered Keyword Searchable Encryption Based on SM9
## 2 Preliminaries
### Baver Triple
It returns the relevant hash value \(h_{1,i}\) if it exists; if it does not and \(i\
otin\{i_{0}^{*},i_{1}^{*}\}\), then \(\mathcal{B}\) selects an unused value \(h_{j}\) from \(h_{1},\ldots h_{q_{H_{1}}}\) as the \(H_{1}\) value \(h_{1,i}=H_{1}(w_{i})=h_{j}\) of \(w_{i}\); if it does not exist and \(i=(1-b)\cdot i_{0}^{*}+b\cdot 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\). 4. When \(\mathcal{A}\) queries the \(\mathcal{H}_{2}\) value of the registered keyword \(rsd_{i}\), \(\mathcal{B}\) first checks whether there is an element containing \(rsd_{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 \(<rsd_{i},h_{2,i}>\) into the list \(L\). 5. 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}\). 6. Keyword registration query: \(\mathcal{B}\) initializes a list of registered keywords in the form of \(R=\{<w_{i},rsd_{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 \(rsd_{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},\ldots,h_{q_{H_{1}}}\}\), \(\mathcal{B}\) returns \(\frac{\pi}{\alpha+h_{1,i}}P_{2}\) as the registration key \(rsd_{i}\) of \(w_{i}\) to \(\mathcal{A}\), and stores \(<w_{i},rsd_{i}>\) into the list \(R\). 7. 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 \(rsd_{i}\). Since \(\mathcal{B}\) has the receiver's private key \(sk_{R}\), \(\mathcal{B}\) can use the private key to compute the corresponding trapdoor \(T_{rsd_{i}}\) and return it to \(\mathcal{A}\). 8. 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}\). 9. Same as in Theorem 1. When \(\mathcal{A}\) outputs its guess \(b^{\prime}\in\{0,1\}\), \(\mathcal{B}\) randomly selects an element \(<rsd_{i},h_{2,i}>\) from the list \(L_{2}\), and returns \(rsd_{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}{(q_{H_{1}}+2)^{2}}\). The following proves that the probability of \(\mathcal{A}\) querying the hash value \(H_{2}\bigg{(}\frac{\pi}{\alpha+H_{1}\left(w_{b}^{*}\right)}\bigg{)}\) in a real game is at least \(\epsilon\).