# Efficient Conjunctive Keywords Search over Encrypted E-Mail Data in Public Key Setting
## 4 Proposed Spe-Cks Scheme
### Construction  
Based on the method described in Section 4.1, the index vector \(\vec{a}\) and the query vector \(\vec{x}\) are obtained by converting \(W\) and \(Q\), respectively. Then, through encrypting \(\vec{a}\) and \(\vec{x}\) under two cyclic groups over a prime order, the encrypted index for \(W\) and the trapdoor for \(Q\) are built. By utilizing the bilinear pairing technique, the test algorithm tests whether \(Q\) is a subset of \(W\). The concrete construction of SPE-CKS scheme is given as follows. * \(KeyGen_{R}(1^{n})\): Given a security parameter \(1^{n}\), the algorithm generates three cyclic groups \(G\), \(G_{1}\), \(G_{2}\) of prime order \(q\) and an admissible bilinear pairing \(\hat{e}:G_{1}\times G_{1}\to G_{2}\) and picks a random generator \(g_{0}\) of \(G\), a random generator \(g\) of \(G_{1}\) and two hash functions \(H_{1}:\{0,1\}^{*}\to Z_{q}^{*}\) and \(H_{2}:G_{2}\to\{0,1\}^{log_{2}^{q}}\). \(\hat{e},H_{1},H_{2}\) and \(g\) are open to the public. Choosing \(n+3\) random numbers \(\alpha_{0},\alpha_{1},\ldots,\alpha_{n},\beta,t\in Z_{q}^{*}\), it outputs the public key \(pk_{R}=\{X_{0}=g^{\alpha_{0}},X_{1}=g^{\alpha_{1}},\ldots,X_{n}=g^{\alpha_{n} },Y=g^{\beta},\mu=\hat{e}(g,g),g_{0},T=g_{0}^{t}\}\) and the secret key \(sk_{R}=\{\alpha_{0},\alpha_{1},\ldots,\alpha_{n},\beta,t\}\). * \(KeyGen_{S}(1^{n},pk_{R})\): Given a security parameter \(1^{n}\), the algorithm generates a hash function \(H_{3}:G\to\{0,1\}^{*}\). Randomly choosing a number \(s\in Z_{q}^{*}\), it outputs \(pk_{S}=\{S=g_{0}^{s},H_{3}\}\) and \(sk_{S}=\{s\}\). * \(IndexBuild(pk_{R},\ pk_{S},\ sk_{S},\ W)\): The algorithm first computes \(\phi=H_{3}(T^{s})=H_{3}(g^{(ts)})\). Then, given a keyword set \(W=\{w_{1},w_{2},\ldots,w_{n}\}\), the algorithm constructs a \(n\)-degree polynomial \(f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots+a_{1}x+a_{0}=(x-H_{1}(w_{1}|\phi))(x-H_ {1}(w_{2}|\phi))\ldots(x-H_{1}(w_{n}|\phi))\) by using the keyword conversion method mentioned in Section 4.1, where \(H_{1}(w_{1}|\phi),H_{1}(w_{2}|\phi),\ldots,H_{1}(w_{n}|\phi)\) are \(n\) roots of the equation \(f(x)=0\). Given a random numbers \(r\) and the coefficient of \(f(x)\) that is \(a_{n},a_{n-1},\ldots,a_{0}\), it computes \(C_{i}=X_{i}^{r}\times g^{ra_{i}}=g^{r(a_{i}+a_{i})}\) for each \(i\in[0,n]\) by using \(pk_{R}\). Let \(C_{W}=Y^{r}=g^{r\beta}\) and \(D_{W}=H_{2}(\mu^{r})\), the index of the keyword set \(W\) is: \(I_{W}=(C_{0},C_{1},\ldots,C_{n},C_{W},D_{W})\). * \(Trapdoor(pk_{R},\ pk_{S},\ sk_{R},\ Q)\): The algorithm computes \(\phi=H_{3}(S^{t})=H_{3}(g^{(ts)})\). Given a keyword set \(Q=\{q_{1},q_{2},\ldots,q_{m}\}\), it selects a random number \(u\in Z_{q}\) and computes \(T_{i}=g^{\frac{H_{1}(q_{1}|\phi|^{j}+H_{1}(q_{2}|\phi|^{j}+\ldots+H_{1}(q_{m }|\phi)^{j}}{u^{\beta}+\sum_{j=0}^{n}\alpha_{j}(H_{1}(q_{1}|\phi)^{j}+H_{1}(q_{ 2}|\phi)^{j}+\ldots+H_{1}(q_{m}|\phi)^{j})}}\) for each \(i\in[0,n]\) by using \(sk_{R}\). Let \(T=g^{\frac{u}{u\beta+\sum_{j=0}^{n}\alpha_{j}(H_{1}(q_{1}|\phi)^{j}+H_{1}(q_{ 2}|\phi)^{j}+\ldots+H_{1}(q_{m}|\phi)^{j})}}\), the trapdoor for the keyword query \(Q\) is \(T_{Q}=(T_{0},T_{1}\ldots,T_{n},T)\). * \(Test(pk_{R},\ pk_{S},\ T_{Q},\ I_{W})\): Given a trapdoor \(T_{Q}=(T_{0},T_{1},\ldots,T_{n},T)\) and a secure index \(I_{W}=(C_{0},C_{1},\ldots,C_{n},C_{W},D_{W})\), the algorithm computes \(\theta_{1}=\prod_{i=0}^{n}\hat{e}(C_{i},T_{i})\), \(\theta_{2}=\hat{e}(C_{W},T)\) and tests if \(H_{2}(\theta_{1}\times\theta_{2})=D_{W}\). If so, outputs 1; otherwise, outputs 0.