# How Can We Achieve Query Keyword Frequency Analysis in Privacy-Preserving Situations?
## 5 Construction  
### The Concrete Construction  
For clarity and visibility, we denote the subset decision mechanism as the SDM in the description that follows. The KFA-PEKS is constructed as follows:  
* \(Setup(\kappa)\to PP\): Given the security parameter \(\kappa\), the KGC finds two large primes \(p\), \(q\) such that \(L(p)=L(q)=\kappa\), where \(L(x)\) refers to the length of the parameter \(x\), then computes \(N=pq\), \(p^{\prime}=(p-1)/2\), \(q^{\prime}=(q-1)/2\), of which \(p^{\prime}\) and \(q^{\prime}\) are two strong primes. Simultaneously, the KGC also chooses a generator of the order \((p-1)(q-1)/2\) and initializes a set of keywords \(W\), the total number of which is \(\eta\). Later the KGC sends a secret value \(r\) to the KFS and the DUs, and sends \(PP\) = (\(W\), \(\eta\), \(N\), \(g\)) to others. * \(KeyGen_{Ser}(PP)\rightarrow(MSK_{MS}\),\(MSK_{KS}\)): The KGC first executes \(KeyGen\) in DT-PKC to obtain the master key \(MSK=\lambda\), and then executes \(MkeyS\) in DT-PKC to generate two partial master keys \(MSK_{1}=\lambda_{1}\), \(MSK_{2}=\lambda_{2}\). Finally, the KGC sends \(MSK_{MS}=MSK_{1}=\lambda_{1}\) to the MS, the partial master key \(MSK_{KFS}=MSK_{2}=\lambda_{2}\) to the KFS, and keeps \(MSK=\lambda\) secret. * \(KeyGen_{DO}(PP)\rightarrow(pk_{DO}\),\(sk_{DO})\): Each DO chooses a random number \(sk_{DO}=\theta_{1}\) and calculates \(h_{DO}=g^{\theta_{1}}\). They then publish \(pk_{DO}=(N,h_{DO},g)\) as their public key, and keep \(sk_{DO}\) as their private key. * \(KeyGen_{DI}(PP)\rightarrow(pk_{DU},sk_{DIU})\): Each DU chooses a random number \(sk_{DIU}=\theta_{2}\) and calculates \(h_{DU}=g^{\theta_{2}}\). They then publish \(pk_{DIU}=(N,h_{DU},g)\) as their public key, and keep \(sk_{DIU}\) as their private key. * \(KeyGen_{TS}(PP)\rightarrow(pk_{TS},sk_{TS})\): Each TS chooses a random number \(sk_{TS}=\theta_{3}\) and calculates \(h_{TS}=g^{\theta_{3}}\). They then publish \(pk_{TS}=(N,h_{TS},g)\) as their public key, and keep \(sk_{TS}\) as their private key. * \(PEKS(W,W_{T},pk_{DO})\rightarrow[T]_{pk_{DO}}\): Firstly, DO chooses a random number \(r_{1}\), and generates \(W_{T}\) based on \(W\) such that \(W_{T}\subseteq W\) and computes the corresponding decimal number \(T\) according to its binary representation; then, encrypts \(T\) with their public key \(pk_{DO}\) to obtain the encrypted searchable ciphertext \([T]_{pk_{DO}}\) = (\(T_{DO,1},T_{DO,2}\)), which specifically is as follows: \[T_{DO,1} = g^{r_{1}\theta_{1}}(1+TN)\mod\ N^{2}\] (1) \[T_{DO,2} = g^{r_{1}}\mod\ N^{2}\] (2) Finally, the DO sends \([T]_{pk_{DO}}\) to the MS.
* \(Trapdoor(W,r,r_{2},k_{DU},pk_{TS},TSO)\rightarrow[t]_{PK}\): the DU uses their own private key \(sk_{DU}\) and TS's public key \(pk_{TS}\) to generate an encryption key \(PK=g^{\theta_{2}\theta_{3}}\). They then generate the keyword set \(W_{t}\) of interest based on \(T\) such that \(W_{t}\subseteq W\) and compute the corresponding decimal number \(t\) according to its binary representation. At the same time, the DU runs a PRF \(F\) for the specified point in order to obtain a timestamp, and shares the key \(r_{2}\) with the TS. Subsequently, the DU encrypts \(t\) with \(PK\), a secret value \(r\) (shared with the KFS) and their specified timestamp, and obtains the trapdoor \([t]_{PK}=t_{DU,1},t_{DU,2}\), which specifically is as follows: \[t_{DU,1} = g^{\theta_{2}\theta_{3}\cdot r\cdot F(r_{2},TSO)}(1+tN)\mod\ N^{2}\] (3) \[t_{DU,2} = g^{\theta_{3}}\mod\ N^{2}.\] (4) Finally, the DU sends \([t]_{PK}\) to the MS.
* step 1: After the MS receives \([T]_{pk_{DO}}\) and \([t]_{PK}\), it will execute the \(SBD\) protocol with the KFS to calculate the ciphertext of each bit of \(\
eg T\) and \(t\), i.e., \([\
eg T_{i}]_{pk_{DO}}\) and \([t_{i}]_{PK}\) for \(i\in\{0,...,\eta-1\}\).