# How Can We Achieve Query Keyword Frequency Analysis in Privacy-Preserving Situations?
## 5 Construction
### Security Proof  
On the premise of being correct, our scheme should also satisfy the five security definitions we mentioned earlier: _keyword privacy of DUs before \(TSO\), indistinguishability of DO's searchable ciphertext, keyword privacy of DUs after \(TSO\), unlinkability of recovered keywords and DUs' identities, resistance to internal and external keyword-guessing attacks_. Below, we will prove each of these five security requirements by means of the following Theorems 1-5. **Theorem 1**: _The keyword privacy of the DU is protected until the \(TSO\) specified by the DU is reached._  
Proof. : The DU generates a trapdoor which is sent to the MS to perform a query. Then, the MS executes the _Test_ algorithm together with the KFS, and returns the test result to the DU. It is required that the test result can only be read by the DU, and the trapdoor must not reveal any information about the keywords before reaching the \(TSO\) specified by the DU. It  
Figure 2: Workflow of our system. is worth noting that in our scheme, the encryption key for the trapdoor must be generated separately by the TS or the DU, while the encryption key for the searchable ciphertext is the public key of the DO; therefore, for the same keyword, the trapdoor is uncorrelated with the searchable ciphertext, meaning that common chosen keyword attacks (CKA) can be avoided in PEKS. We use \(\mathcal{A}\) to denote the adversary in the indistinguishability game, and \(\mathcal{C}\) to denote the challenger; this game can be represented 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 (**IND-TP**), then the scheme can be deemed **IND-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_{\mathit{Ser}}\), \(KeyGen_{\mathit{DU}}\), \(KeyGen_{\mathit{DO}}\), and \(KeyGen_{\mathit{TS}}\) to obtain \(PP\), \((MSK_{\mathit{MS}}\), \(MSK_{\mathit{KFS}})\), \((pk_{\mathit{DU}},sk_{\mathit{DU}})\), \((pk_{\mathit{DO}},sk_{\mathit{DO}})\), and \((pk_{\mathit{TS}},sk_{\mathit{TS}})\). Furthermore, it sends \((MSK_{\mathit{MS}},pk_{\mathit{DU}},pk_{\mathit{DO}},pk_{\mathit{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 \(\mathit{Trapdoor}(W,r,sk_{\mathit{DU}},pk_{\mathit{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-TP** secure. Suppose there exists an adversary \(\mathcal{A}\) who can win the game described above with a non-negligible probability.