# Registered Keyword Searchable Encryption Based on SM9
## 2 Preliminaries
### Baver Triple
: Suppose that \(\mathcal{A}\) is any probabilistic polynomial-time (PPT) adversary that can successfully attack the IND-CT-CKA security with advantage \(\epsilon\). 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}\) that solves the \(q_{H_{1}}\)-BCAA problem with a probability of at least \(\frac{2\epsilon}{\left(q_{H_{1}}+2\right)^{2}q_{H_{3}}}\). Given an instance \(\left(P_{1},P_{2},\alpha P_{1},h_{0},\left(h_{1},\frac{\alpha}{a+h_{1}}P_{2} \right),\ldots,\left(\frac{\alpha}{a+h_{H_{1}}}P_{2}\right)\right)\) of the \(q_{H_{1}}\)-BCAA problem, where \(P_{1}\) and \(P_{2}\) are the generators of two prime order cyclic groups \(G_{1}\) and \(G_{2}\), respectively, and there exists a bilinear map \(\hat{\epsilon}:G_{1}\times G_{2}\to G_{T}\), then algorithm \(\mathcal{B}\) simulates the process of IND-CT-CKA game as follows:

Figure 2:9 Security reduction. Setup.According to the \(q_{H_{1}}\)-BCAA problem, the simulator \(\mathcal{B}\) first selects three hash functions \(H_{1}:\{0,1\}^{*}\rightarrow\mathbb{Z}_{N}^{*}\), \(H_{2}:G_{2}\rightarrow\mathbb{Z}_{N}^{*}\), and \(H_{3}:G_{T}\rightarrow\{0,1\}^{n}\), and generates public parameter \(\mathcal{G}=(N\), \(G_{1}\), \(G_{2}\), \(G_{T}\), \(\hat{e}\), \(P_{1}\), \(P_{2}\), \(H_{1}\), \(H_{2}\), \(H_{3})\). Next, \(\mathcal{B}\) randomly selects \(s_{0}\in\mathbb{Z}_{N}^{*}\), and let \((pk_{KS},sk_{RS})=(s_{0}P_{1},s_{0})\) be the public/private key pair of the RS. \(\mathcal{B}\) implicitly chooses the receiver's private key as \(sk_{R}=\alpha\), and then sets the receiver's public key as \(pk_{R}=\alpha P_{1}\). Finally, \(\mathcal{B}\) calculates \(g=\hat{e}(pk_{R},P_{2})\), and sends \(\mathcal{G}\), \(pk_{RS}\), and \(pk_{R}\) to adversary \(\mathcal{A}\). 1. In addition to keyword registration query and keyword trapdoor query, \(\mathcal{A}\) can perform queries of three hash functions. Before answering these queries, \(\mathcal{B}\) randomly selects two values \(i_{0}^{*}\) and \(i_{1}^{*}\) from \(\{1,\ldots,q_{H_{1}}+2\}\) as the guess results for the challenge keywords \(w_{0}^{*}\) and \(w_{1}^{*}\), respectively, and randomly selects \(b\in\{0,1\}\) as a bit in the challenge ciphertext. \(\mathcal{A}\) can adaptability query \(\mathcal{B}\) as follows: 1. Hash queries: \(\mathcal{B}\) first creates two hash lists of the form \(L=\{<w_{i},h_{1,i},rsd_{i},\)\(h_{2,i}>\}\) and \(L^{\prime}=\{<T_{i},h_{2,i}>\}\) that are initialized to be empty. * 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\). It returns the relevant hash value \(h_{1,i}\) if it is present; if it does not, \(\mathcal{B}\) randomly selects \(h_{1,i}\in\mathbb{Z}_{N}^{*}\) and returns it to \(\mathcal{A}\). At the same time, because \(\mathcal{B}\) knows the secret key \(s_{0}\) of the registration server, it can calculate \(rsd_{i}=\frac{s_{0}}{s_{0}+h_{1,i}}P_{2}\). If \(i\
otin\{i_{0}^{*},i_{1}^{*}\}\), then \(\mathcal{B}\) chooses an unused value \(h_{j}\) from \(h_{1},\ldots h_{q_{H_{1}}}\) as the \(H_{2}\) value \(h_{2,i}=H_{2}(rsd_{i})=h_{j}\) of \(rsd_{i}\); if \(i=(1-b)\cdot i_{0}^{*}+b\cdot i_{1}^{*}\), then let the \(H_{2}\) value of \(rsd_{i}\) be \(h_{2,i}=h_{0}\); otherwise, \(\mathcal{B}\) randomly selects a value \(h_{2,i}\in\mathbb{Z}_{N}^{*}\) as the \(H_{2}\) value of \(rsd_{i}\). Finally, \(\mathcal{B}\) stores \(<w_{i},h_{1,i},rsd_{i},h_{2,i}>\) into the list \(L\). * When \(\mathcal{A}\) queries the \(\mathcal{H}_{2}\) value of \(rsd_{i}\), \(\mathcal{B}\) first checks whether there is an element by \(rsd_{i}\) in the list \(L\). 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}\).