# How Can We Achieve Query Keyword Frequency Analysis in Privacy-Preserving Situations?
## 3 Preliminaries
### Dt-Pkc
#### 3.4.1 Basic Structure  
Our scheme takes a similar introduction to DT-PKC as that of [22]. Among them, since this paper needs to use the joint decryption of dual servers, the \(PSDec1\) algorithm and \(PSDec2\) algorithm in [23] are retained and rewritten as \(PMDec1\) algorithm and \(PMDec2\) algorithm in this paper. Furthermore, this paper does not involve the joint decryption between users, so the PWDec1 and PWDec2 algorithms are omitted. It is important to emphasize that this change will not affect the content that follows. The DT-PKC infrastructure consists of eight algorithms: \(KeyGen\), \(Enc\), \(Udec\), \(MDec\), \(MkeyS\), \(PMDec1\), \(PMDec2\), and \(CR\). The definition of DT-PKC accepted in [23], with slight modifications, is as follows:  
* _KeyGen_: Given the security parameter \(\kappa\), 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}=\frac{(p-1)}{2}\), \(q^{\prime}=\frac{(q-1)}{2}\), of which \(p^{\prime}\) and \(q^{\prime}\) are two strong primes. Simultaneously, KGC also chooses a generator of the order \(\frac{(p-1)(q-1)}{2}\), and chooses a random number \(\theta\) such that \(\theta\in[1,\frac{N}{4}]\). Finally, KGC obtains the public key \(pk_{i}=(N,g,h_{i}=g^{\theta})\) and the private key \(sk_{i}=\theta\) for user \(i\), and computes the master key \(MSK=\lambda=\frac{lcm(p-1,\ q-1)}{2}\), where \(lcm(a,b)\) refers to finding the least common multiple of \(a\) and \(b\).
* \(Encryption\) (\(Enc\)): Enter the plaintext \(m\) and the public key \(pk_{i}\) and choose a random number \(r\) (\(r\in[1,\frac{N}{4}]\)) to generate the ciphertext \([m]_{pk_{i}}=\{C_{i,1},C_{i,2}\}\), where \(C_{i,1}=g^{r\theta}(1+mN)\mod\ N^{2}\); \(T_{i,2}=g^{r}\mod\ N^{2}\).
* _Decryption With User's Private Key (UDec)_: Enter the ciphertext \([m]_{pk_{i}}\) and the private key \(sk_{i}\) to generate the corresponding plaintext \(m\) as follows: \[m^{{}^{\prime}}=\frac{C_{i,1}}{C_{i,2}}\mod\ N^{2},\] \[m=\frac{m^{{}^{\prime}}-1}{N}.\]
* _Decryption With Master Key (MDec)_: Enter the ciphertext \([m]_{pk_{i}}\) and the master key \(MSK\) to generate the corresponding plaintext \(m\) by first calculating: \[C_{i,1}^{A}\mod\ N^{2}=g^{\lambda_{i}\cdot\theta_{r}}(1+mN\lambda)\mod\ N^{2}=(1+mN\lambda).\] Then, since \(gcd(\lambda,N)=1\), we are able to obtain \(m\) by the following expression: \[m^{{}^{\prime}}=C_{i,1}^{\lambda}\mod\ N^{2},\] \[m=\frac{m^{{}^{\prime}}-1}{N}\cdot\lambda^{-1}\mod\ N.\]
* _Master Key Splitting (MkeyS)_: Enter the master key \(MSK\) to generate two partial master keys \(MSK=\lambda_{1}\) and \(MSK=\lambda_{2}\) such that \(\lambda_{1}+\lambda_{2}\equiv 0\mod\ \lambda\) and \(\lambda_{1}+\lambda_{2}\equiv 1\mod\ N^{2}\).
* _Partial Decryption With Partial Master Key Step One (PMDec1)_: Enter the ciphertext \([m]_{pk_{i}}\) and the partial master key \(MSK_{1}\) to generate the partial ciphertext \(CT_{i}^{1}\) as follows: \[CT_{i}^{1}=(C_{i,1})^{\lambda_{1}}=g^{r\theta\lambda_{1}}(1+mN\lambda_{1})\mod \ N^{2}.\]
* _Partial Decryption With Partial Master Key Step Two (PMDec2)_: Enter the partial ciphertext \(CT_{i}^{1}\), the ciphertext \([m]_{pk_{i}}\) and the partial master key \(MSK_{2}\) to generate the corresponding plaintext \(m\) by first calculating: \[CT_{i}^{2}=(C_{i,1})^{\lambda_{2}}=g^{r\theta\lambda_{2}}(1+mN\lambda_{2})\mod \ N^{2}.\] Then, we can obtain the plaintext \(m\) by computing: \[CT=CT_{i}^{1}\cdot CT_{i}^{2},\] \[m=\frac{CT_{i}-1}{N},\]
* _Ciphertext Refresh (CR)_: Enter the ciphertext \([m]_{pk_{i}}\) and a random number \(r^{{}^{\prime}}\in\mathbb{Z}_{N}\) to generate another ciphertext \([m]^{{}^{\prime}}_{pk_{i}}=\{C^{{}^{\prime}}_{i,1},C^{{}^{\prime}}_{i,2}\}\), where \[C^{{}^{\prime}}_{i,1}=T_{i,1}\cdot h^{{}^{\prime}}_{i}\ ;\ C^{{}^{\prime}}_{i,2}=C_{i,2}\cdot g^{{}^{\prime}}.\]