# How Can We Achieve Query Keyword Frequency Analysis in Privacy-Preserving Situations?
## 5 Construction
### Security Proof
Let \(\mathcal{C}\) be the challenger of the trapdoor privacy experiment before TSO in KFA-PEKS, and here construct a simulator \(\mathcal{B}\) to exploit adversary \(\mathcal{A}\) to defeat the DDH hardness problem based on \(\mathbb{Z}_{N^{2}}^{*}\). Let \((g,g^{x},g^{y},g^{xy},g^{z})\) be a set of examples of DDH hardness problems based on \(\mathbb{Z}_{N^{2}}^{*}\). Challenger \(\mathcal{C}\) first uses the generating element \(g\) to construct the public parameters of the scheme \(PP=(W,\eta,N,g)\). Then, challenger \(\mathcal{C}\) uses \(PP\) by itself to run \(Setup\), \(KeyGen_{\mathit{Ser}}\), \(KeyGen_{\mathit{DO}}\), \(KeyGen_{\mathit{DU}}\), and \(KeyGen_{\mathit{TS}}\), and obtains the secret value \(r\) shared by the KFS and the DU, the secret value \(r_{2}\) shared by the TS and the DU, and some of the MS and KFS's partial master key \((MSK_{\mathit{MS}},MSK_{\mathit{KFS}})\), the DO's public-private key pairs \((pk_{\mathit{DO}},sk_{\mathit{DO}})\), the DU's public-private key pairs \((pk_{\mathit{DU}},sk_{\mathit{DU}})\), and the TS's public-private key pairs \((pk_{\mathit{TS}},sk_{\mathit{TS}})\). Then, challenger \(\mathcal{C}\) sends \((PP,MSK_{\mathit{MS}},pk_{\mathit{DO}},pk_{\mathit{DU}},pk_{\mathit{TS}})\) to adversary \(\mathcal{A}\) and \((PP,MSK_{\mathit{KFS}},pk_{\mathit{DO}},pk_{\mathit{DU}},pk_{\mathit{TS}},sk_{ \mathit{TS}},r,r_{2})\) to simulator \(\mathcal{B}\). Adversary \(\mathcal{A}\) chooses two keyword sets \(W_{0}\) and \(W_{1}\) and corresponding trapdoor \([t]_{PK}^{b}\), where \(b\in\{0,1\}\). Next, \(\mathcal{A}\) sends \((W_{0},W_{1},[t]_{PK}^{b})\) to \(\mathcal{B}\). Finally, \(\mathcal{B}\) gives a value \(b^{{}^{\prime}}\) to guess the set of keywords \(W_{b}^{\prime}\) corresponding to the trapdoor \([t]_{PK}^{b}\), where \(b^{{}^{\prime}}\in\{0,1\}\). Throughout the process, simulator \(\mathcal{B}\) allows adversary \(\mathcal{A}\) to perform the following oracle queries with the following responses:  
* \(\mathit{Query_{\mathit{Trap}}}(\mathit{W_{b}},\mathit{pk_{\mathit{DU}}})\)**:** Input a keyword set \(W_{b}\) and the DU's public key \(pk_{\mathit{DU}}\), because simulator \(\mathcal{B}\) has the TS's private key \(sk_{\mathit{TS}}\), so it can obtain the encryption key \(PK=g^{\delta_{2}\delta_{3}}\); then, simulator \(\mathcal{B}\) runs the \(\mathit{Trapdoor}\) algorithm to generate the query trapdoor \([t]_{PK}^{b}\) corresponding to keyword set \(W_{b}\), and then, simulator \(\mathcal{B}\) sends this query trapdoor to adversary \(\mathcal{A}\). * \(\mathit{Query_{\mathit{TS}}}(\mathit{TSN})\)**:** The current timestamp \(TSN\) is input, and since the simulator \(\mathcal{B}\) has the secret value \(r\) shared by the KFS and the DU and the secret value \(r_{2}\) shared by the TS and the DU, it can obtain the processed timestamp \(g^{\cdot\cdot F(r_{2},TSN)}\) and give this value to the adversary \(\mathcal{A}\). * \(\mathbf{Query_{Test}}([T]_{pk_{DO}}[t]^{b}_{PK},\mathbf{MSK_{MS}},\mathbf{MSK_{KFS}},\mathbf{pk_{DO} },\mathbf{PK})\)**:** In this stage of interrogation, adversary \(\mathcal{A}\) has the partial master key \(MSK_{MS}\) of the MS, and simulator \(\mathcal{B}\) uses the partial master key \(MSK_{KFS}\) of the KFS to cooperate with adversary \(\mathcal{A}\) to execute the _Test_ algorithm and send the matching result to adversary \(\mathcal{A}\). For trapdoor \([t]^{b}_{PK}=(t_{DU,1},t_{DU,2})\), it satisfies: \[t_{DU,1} = \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!  
\[T_{DO,2}=g^{r_{1}}\mod N^{2}\]  
Then, simulator \(\mathcal{B}\) sends this searchable ciphertext to adversary \(\mathcal{A}\). At this point the simulator \(\mathcal{B}\) gives the guess value \(b^{{}^{\prime}}\) by a non-negligible advantage such that \(b^{{}^{\prime}}=b\). This contradicts the DDH difficulty problem based on \(\mathbb{Z}_{N^{2}}^{*}\), so the searchable ciphertext in this scheme satisfies indistinguishability.