# How Can We Achieve Query Keyword Frequency Analysis in Privacy-Preserving Situations?
## 3 Preliminaries
### Subset Decision Mechanism (SDM)  
Given a universal set \(W\), and two subsets and \(W_{T}\) and \(W_{t}\), and these sets being represented in decimal integers and binary representations, the role of the SDM [22] is to perform some calculations on these decimal integers and binary representations to determine whether \(W_{t}\subseteq W_{T}\). In this paper, the SDM is used as an important component of the matching process. In the next description, we let \(W\) denote the set of all keywords whose binary and decimal forms are denoted as \((1,...,1)\) and \(SUM\), and \(W_{T}\) denote the set of keywords corresponding to the document uploaded by the data owner (DO), which is represented in binary and decimal form as \((T_{\eta-1},...,T_{0})\) and \(T\), respectively. Furthermore, \begin{table}
\begin{tabular}{c c} \hline \hline
**Notations** & **Descriptions** \\ \hline \(W\) & The universal keyword set \\ \hline \(D\) & A document \\ \hline \(DS\) & All documents stored on the server \\ \hline \(DS[\omega]\) & All documents that contain the keyword \(\omega\) \\ \hline \(SQ\) & Keywords included in a query \\ \hline \(W_{id}\) & All keywords contained in document with identifier \(id\) \\ \hline \(W_{c}\) & The keyword set represented by \(c\) \\ \hline \(\omega\) & A keyword \\ \hline \((c_{\eta-1},...,c_{0})\) & The unsigned binary representation of a positive decimal \(c\) \\ \hline \(c_{\eta-1}\) & The highest bit \\ \hline \(c_{0}\) & The least bit \\ \hline \(\eta\) & The bit length of \(c\), the number of keywords in \(W\) \\ \hline \(\
eg c\) & The complement of \(c\) \\ \hline \multicolumn{3}{c}{A positive decimal integer is used as the plaintext representation of} \\ \(T\) & searchable ciphertext, and its binary representation can represent the \\ \multicolumn{3}{c}{relationship between the set \(W_{T}\) and the universal set \(W\)} \\ \hline \multirow{3}{*}{\(t\)} & A positive decimal integer is used as the plaintext representation of \\  & searchable ciphertext, and its binary representation can represent the \\ \multicolumn{3}{c}{relationship between the set \(W_{t}\) and the universal set \(W\)} \\ \hline \(sk_{i}\) & Secret key of participant \(i\) \\ \hline \(pk_{i}\) & Public key of participant \(i\) \\ \hline \(MSK_{i}\) & Partial master key of participant \(i\) \\ \hline \(TSO\) & Timestamp specified by DUs \\ \hline \(TSN\) & Timestamp generated periodically by the time server \\ \hline \([\cdot\cdot]_{pk}\) & The encryption of \(\cdot\) under the public key \(pk\) \\ \hline \(SUM\) & The decimal integer \(2^{\eta}-1\) \\ \hline \(L(\cdot)\) & The bit length of \(\cdot\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary of notations. we let \(W_{t}\) denote the set of keywords corresponding to the data user's (DU's) query request in binary and decimal form as \((t_{\eta-1},...,t_{0})\) and \(t\), respectively. The key for the SDM to determine \(W_{t}\subseteq W_{T}\) is to ensure that there is no \(i\) that satisfies \(t_{i}=1\) and \(T_{i}=0\). In the SDM, the inputs are a universal keyword set \(W=\{\omega_{\eta-1},...,\omega_{0}\}\) with two subsets WT and Wt such that \(W_{T},W_{t}\subseteq W\). The outputs are a result value \(\mathcal{R}\), which represents whether \(W_{t}\subseteq W_{T}\). The specific process can be described as follows. We first compute the complement \((-T_{\eta-1},...,-T_{0})\) of the binary of \(T\) and the corresponding integer \(\
eg T\). Then, perform a bitwise addition of \(\
eg T_{i}\) and \(t_{i}\) to obtain \(\mathcal{C}_{i}\). Finally, if there is no \(\mathcal{C}_{i}=2\), then, \(W_{t}\subseteq W_{T}\); otherwise, \(W_{t}\
subseteq W_{T}\). The working mechanism of the SDM is described formally in Algorithm 1. ```
0: A universal set \(W=\{\omega_{\eta-1},...,\omega_{0}\}\), two subsets \(W_{t},W_{T}\subseteq W\). 0: Whether \(W_{t}\subseteq W_{T}\). 1: Compute the binary representations \((T_{\eta-1},...,T_{0})\), \((t_{\eta-1},...,t_{0})\) of \(W_{T},W_{t}\).