# How Can We Achieve Query Keyword Frequency Analysis in Privacy-Preserving Situations?
## 5 Construction
### Security Proof
Theorem 3.1: _Upon receipt of a time token from TS, the keyword information in trapdoor cannot be recovered by anyone except the KFS and the corresponding DUI, based on the intractability of DDH's assumption over \(Z_{N^{2}}^{*}\) (more specific information about the hardness of DDH's assumption over \(Z_{N^{2}}^{*}\) can be found in [34])._  
Proof: After reaching the timestamp \(TSO\) specified by the DU, only the KFS can obtain the keyword information in the trapdoor. Similar to the previous security requirements, trapdoor queries and ciphertext queries are not considered. The trapdoor privacy after TSO is defined by an interaction experiment **IND-sT-TP** (the indistinguishability trapdoor privacy with a specific TSO) between challenger \(\mathcal{C}\) and adversary \(\mathcal{A}\), which is expressed as follows:  
First, \(\mathcal{A}\) chooses a time point \(T^{*}\) to attack, and selects two different sets of keywords of interest, \(W_{1}\) and \(W_{2}\), which will be sent to \(\mathcal{C}\); then, \(\mathcal{C}\) randomly selects one of the two sets to generate a trapdoor which is then sent to \(\mathcal{A}\). Finally, \(\mathcal{A}\) tries to distinguish which set of keywords corresponds to the trapdoor returned by \(\mathcal{C}\). In the following, if our scheme passes the indistinguishability game of trapdoor privacy with a specific \(TSO\) (**IND-sT-TP**), then the scheme can be deemed **IND-sT-TP** secure. * **Setup:** First, \(\mathcal{A}\) chooses a point in time \(T^{{}^{\prime}}\) at which to make the attack. Then, \(\mathcal{C}\) executes algorithms \(Setup\), \(KeyGen_{Ser}\), \(KeyGen_{DU}\), \(KeyGen_{DO}\), and \(KeyGen_{TS}\) to obtain \(PP\), \((MSK_{MS},MSK_{FS})\), \((pk_{DU},sk_{DU})\), \((pk_{DO},sk_{DO})\), and \((pk_{TS},sk_{TS})\). Furthermore, it sends \((MSK_{MS},pk_{DU},pk_{DO},pk_{TS})\) to \(\mathcal{A}\). * **Phase 1:**\(\mathcal{A}\) interacts with \(\mathcal{C}\), which executes the _TimeTokenGen_ algorithm in an imitation of the TS, and sends the resulting time token to \(\mathcal{A}\). * **Challenge:**\(\mathcal{A}\) picks two different keyword sets \(W_{0}\), \(W_{1}\subseteq W\), and sends \(t_{0}\) and \(t_{1}\), representing the two sets, to \(\mathcal{C}\). Then, \(\mathcal{C}\) picks \(b\subseteq_{R}\{0,1\}\), runs \(Trapdoor(W,r,sk_{DU},pk_{TS},TSO)\rightarrow[t_{b}]_{PK}\), and sends \([t_{b}]_{PK}\) to \(\mathcal{A}\). * **Phase 2:**\(\mathcal{A}\) can continue with the first phase of queries while also executing the algorithm \(PEKS\) in an imitation of the MS interacting with the KFS. * **Guess:**\(\mathcal{A}\) starts guessing \(b\). If the given guess \(b^{{}^{\prime}}\) satisfies \(b^{{}^{\prime}}=b\), then \(\mathcal{A}\) wins this game. If \(\mathcal{A}\) can win the game described above with a non-negligible probability, then the KFA-PEKS is deemed **IND-sT-TP** secure. Suppose there exists an adversary \(\mathcal{A}\) who can win the game described above with a non-negligible probability. Let \(\mathcal{C}\) be the challenger of the trapdoor privacy experiment after \(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_{Ser}\), \(KeyGen_{DO}\), \(KeyGen_{DU}\), and \(KeyGen_{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_{MS},MSK_{KFS})\), the DO's public-private key pairs \((pk_{DO},sk_{DO})\), the DU's public-private key pairs \((pk_{DU},sk_{DU})\) and the TS's public-private key pairs \((pk_{TS},sk_{TS})\).