# Efficient Conjunctive Keywords Search over Encrypted E-Mail Data in Public Key Setting
## 4 Proposed Spe-Cks Scheme
### Security Proof
To respond to \(H_{1}\) queries, algorithm \(\mathbb{C}\) maintains a list of tuples \((w_{j},h_{j},\sigma_{j})\) called \(H_{1}-\)list which is initially empty. \(\mathbb{C}\) generates \(\phi=H_{3}(T^{s})=H_{3}(g^{(ts)})\) by using the keys \(pk_{S},pk_{R},sk_{S}\). When \(\mathbb{A}\) queries the random oracle \(H_{1}\) at a point \(w_{i}\in\{0,1\}^{*}\), algorithm \(\mathbb{C}\) responds as follows: \(H_{1}-\)**queries**: 1. If the query \(w_{i}\) already appears on the \(H_{1}\)-list in a tuple \((w_{i},h_{i},\sigma_{i})\), algorithm \(\mathbb{C}\) responds with \(H_{1}(w_{i}|\phi)=h_{i}\), where \(h_{i}\in\{0,1\}^{log_{2}^{2}}\). 2. Otherwise, \(\mathbb{C}\) generates a random coin \(\sigma_{i}\in[1,nq_{T}]\) so that \(Pr[1\leq\sigma_{i}\leq n]=\frac{1}{q_{T}}\). 3. If \(1\leq\sigma_{i}\leq n\), \(\mathbb{C}\) set \(h_{i}=t_{\sigma_{i}}\). Otherwise, \(\mathbb{C}\) picks a random \(a_{i}\in\{0,1\}^{log_{2}^{2}}\) and sets \(h_{i}=a_{i}\). 4. \(\mathbb{C}\) adds the tuple \((w_{i},h_{i},\sigma_{i})\) to the \(H_{1}\)-list. \(\mathbb{C}\) responds \(\mathbb{A}\) with \(H_{1}(w_{i}|\phi)=h_{i}\). The \(H_{2}-\)queries is similar to \(H_{1}-\)queries. To respond to \(H_{2}\) queries from \(\mathbb{A}\), algorithm \(\mathbb{C}\) maintains a list of tuples \((\varphi_{j},\psi_{j})\) called \(H_{2}-\)list which initially empty. When \(\mathbb{A}\) queries the random oracle \(H_{2}\) at a point \(\varphi_{i}\in G_{2}\), algorithm \(\mathbb{C}\) responds as follows: \(H_{2}-\)**queries**:  
1. If the query \(\varphi_{i}\) already appears on the \(H_{2}\)-list in a tuple \((\varphi_{i},\psi_{i})\), then algorithm \(\mathbb{C}\) responds with \(H_{2}(\varphi_{i})=\psi_{i}\), where \(\psi_{i}\in\{0,1\}^{log_{2}^{2}}\). 2. Otherwise, \(\mathbb{C}\) picks a random \(b_{i}\in\{0,1\}^{log_{2}^{2}}\) and sets \(\psi_{i}=b_{i}\). 3. \(\mathbb{C}\) adds the tuple \((\varphi_{i},\psi_{i})\) to the \(H_{2}\)-list and responds \(\mathbb{A}\) with \(H_{2}(\varphi_{i})=\psi_{i}\). **Index queries**: For any keyword set \(W_{i}=\{w_{i1},w_{i2},\ldots,w_{in}\}\) in which \(i\in[1,q_{1}]\), when \(\mathbb{A}\) asks for the secure index of \(W_{i}\), \(\mathbb{C}\) responds as follows:  
1. \(\mathbb{C}\) runs \(H_{1}-\)queries algorithm to obtain \(h_{ij}\) such that \(h_{ij}=H_{1}(w_{ij}|\phi)\) where \(j\in[1,n]\). Let \((w_{ij},h_{ij},\sigma_{ij})\) be the corresponding tuples on the \(H_{1}\)-list. If \(\sigma_{ij}\leq n\) for all \(j\in[1,n]\), then \(\mathbb{C}\) reports failure and terminates. 2. Otherwise, by using \((h_{i1},h_{i2},\ldots,h_{in})\), \(\mathbb{C}\) adopts the keyword conversion method in Section 4.1 to generate a vector \(\vec{a}\). Following the algorithm \(IndexBuild\) in Section 4.2, \(\mathbb{C}\) generates the secure index \(I_{W}\) by using \(pk_{R}\). 3. **Trapdoor queries**: When \(\mathbb{A}\) issues a query for the trapdoor corresponding to the keyword query \(Q_{i}=\{q_{i1},q_{i2},\ldots,q_{im}\}\) where \(i\in[1,q_{T}]\), algorithm \(\mathbb{C}\) responds as follows: 1. Algorithm \(\mathbb{C}\) runs \(H_{1}-\)queries algorithm to obtain \(h_{ij}\) such that \(h_{ij}=H_{1}(q_{ij}|\phi)\) where \(j\in[1,m]\). Let \((q_{ij},h_{ij},\sigma_{ij})\) be the corresponding tuples on the \(H_{1}\)-list. If \(\sigma_{ij}\leq n\) for all \(j\in[1,m]\), then \(\mathbb{C}\) reports failure and terminates. Otherwise, by using \((h_{i1},h_{i2},\ldots,h_{im})\) and \(sk_{R}\), \(\mathbb{C}\) constructs the trapdoor for query \(Q_{i}\). \(\mathbb{C}\) computes: \(l_{i}=\frac{1}{\vartheta}+\frac{\rho_{i}\sum_{p=0}^{n}s_{p}(y_{1}^{y}+h_{2}^{y} +\ldots+h_{im}^{y})}{\eta\sum_{p=0}^{n}b_{p}(h_{1}^{y}+h_{2}^{y}+\ldots+h_{im}^ {y})}\) and \(u_{i}=-\frac{\sum_{p=0}^{n}b_{p}(h_{1}^{y}+h_{2}^{y}+\ldots+h_{im}^{y})+\rho_{i }\sum_{p=0}^{n}s_{p}(h_{1}^{y}+h_{2}^{y}+\ldots+h_{im}^{y})}{\rho_{i}\eta}\), which are satisfied with the equality \(\frac{u_{i}}{u_{i}\eta x+\sum_{p=0}^{n}(s_{p}x-h_{i})(h_{1}^{y}+h_{2}^{y}+ \ldots+h_{im}^{y})}=\frac{l_{i}}{x+\rho_{i}}\).