# How Can We Achieve Query Keyword Frequency Analysis in Privacy-Preserving Situations?
## 5 Construction
### Security Proof
Then, challenger \(\mathcal{C}\) sends \((PP,MSK_{MS},pk_{DO},pk_{DU},pk_{TS})\) to adversary \(\mathcal{A}\) and \((PP,MSK_{KFS},pk_{DO},pk_{DU},pk_{TS},sk_{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 keywordscorresponding 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:  
* \(\mathbf{Query_{Trap}(W_{b},pk_{DU}):}\) Input a keyword set \(W_{b}\) and DU's public key \(pk_{DU}\), because simulator \(\mathcal{B}\) has the TS's private key \(sk_{TS}\), so it can obtain the encryption key \(PK=g^{\theta_{2}\theta_{3}}\); then simulator \(\mathcal{B}\) runs _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}\). * \(\mathbf{Query_{TS}(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^{r.F(r_{2},TSN)}\) and give this value to the adversary \(\mathcal{A}\). * \(\mathbf{Query_{Test}([T]_{pk_{DO}},[t]_{PK}^{b},MSK_{MS},MSK_{KFS},pk_{DO},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]_{PK}^{b}=(t_{DU,1},t_{DU,2})\), it satisfies: \[t_{DU,1} =g^{\theta_{2}\theta_{3}\cdot r\cdot F(r_{2},TSO)}(1+t_{b}N)\mod N^{2},\] \[t_{DU,2} =g^{\theta_{2}\theta_{3}}\mod N^{2}\] At this point the simulator \(\mathcal{B}\) gives the guessed value \(b^{{}^{\prime}}\) by a non-negligible advantage such that \(b^{{}^{\prime}}\ =\ b\). This contradicts the DDH difficulty problem based on \(\mathbb{Z}_{N2}^{*}\), so the query trapdoor satisfies indistinguishability in this scheme until it reaches the \(TSO\) specified by the DU. The KFS is unable to locate the relevant DU through the keyword being recovered. Proof. : In Theorem 3, we prove that after reaching the time point \(TSO\), specified by the DU, only the KFS can open the keyword information in the corresponding trapdoor, for the purpose of performing keyword frequency analysis. In order to ensure the privacy of DUs while performing keyword frequency analysis, our solution needs to prevent the KFS from finding the corresponding DUs through the recovered keywords. In the specific structure of our scheme, the MS is responsible for providing file storage services to the DO, and for responding to query requests initiated by the DU at the same time. When performing keyword frequency analysis, the MS sends the query trapdoor of the DU to the KFS, and then the KFS uses the time token of the TS to recover the queried keywords of the DUs. During the entire process, the KFS does not interact with the DUs. On the premise that the MS does not collude with the KFS, the KFS can only recover the query keywords, but cannot link them to the corresponding DUs through the recovery results. In this way, the security required by the scheme is achieved. Internal or external attackers cannot obtain any information about users' keywords from encrypted searchable ciphertext or query trapdoors. Proof. : In the specific structure of the scheme, the result of the joint MS and KFS calculation is a secret value which is encrypted with the DU's public key. Therefore, only the DU can know the query result.