# Lightweight and Privacy-Preserving Multi-Keyword Search over Outsourced Data
## 3 Basic PRMS Construction  
This section introduces a basic PRMS scheme based on the inner product similarity computing technology [41], where the procedures are summarized in Figure 2. The frequently used notations are summarized in Table 2.  
Figure 2: The procedures of basic PRMS scheme. * **System setup**: With input security parameters \(\lambda_{1},\lambda_{2},\lambda_{3},\lambda_{4}\), the data owner constructs a dictionary \(D\), which contains \(n\) keywords. The data owner randomly picks a large prime \(p\) such that \(|p|=\lambda_{2}\), an element \(s\in_{R}Z_{p}^{*}\), and a cryptographic one-way hash function \(H:\{0,1\}^{*}\rightarrow\{0,1\}^{\lambda_{1}}\). Thus, the system public parameters are \(para=(\lambda_{1},\lambda_{2},\lambda_{3},\lambda_{4},p,n,H)\). The data owner keeps \(D\) and \(s\) secret. * **Index generation**: For each document \(F\), the data owner encrypts it as ciphertext document \(\overline{F}\) using some secure symmetric encryption algorithm, randomly picks a unique file name \(N\), and calculates the length \(d\) of document \(F\). The data owner computes \(\gamma=H(N,d)\) and constructs the index vector \(\overline{I}\) such that if the document \(F\) contains the \(i\)th keyword in the dictionary \(D\), then \(I_{i}=1\), otherwise \(I_{i}=0\). The data owner further sets \(I_{n+1}=I_{n+2}=0\), chooses \(n+2\) random number \(m_{i}\) such that \(|\ m_{i}|=\lambda_{3}\) for \(1\leq i\leq n+2\), and encrypts each \(I_{i}\) as follows: \[\hat{I}_{i}=s\cdot(I_{i}\cdot\gamma+m_{i})\mod p\] (1) Then for document \(F\), the data owner outsources the ciphertext index vector \(\hat{I}=(\hat{I}_{1},\hat{I}_{2},\cdots,\hat{I}_{n+2})\) and the processed file \(\hat{F}=(\overline{F},\gamma)\) to the cloud server, and keeps \((N,d)\) at local. * **Trapdoor generation**: Data user picks a large random number \(\delta\) such that \(|\ \delta\ |=\lambda_{1}\), and computes \(s^{-1}\mod p\). From the query keyword set \(W\), data user constructs query vector \(\vec{Q}\), where \(Q_{i}=1\) if the query keyword set \(W\) contains the \(i\)-th keyword in the dictionary \(D\), otherwise \(Q_{i}=0\). The data user then sets \(Q_{n+1}=Q_{n+2}=0\), and randomly chooses \(n+2\) numbers \(t_{i}\) such that \(|\ t_{i}\ |=\lambda_{4}\) for \(1\leq i\leq n+2\). The data user constructs the search trapdoor \(\hat{Q}=(\hat{Q}_{1},\hat{Q}_{2},\cdots,\hat{Q}_{n+2})\), where \[\hat{Q}_{i}=s^{-1}\cdot(Q_{i}\cdot\delta+t_{i})\mod p\] (2) \begin{table}
\begin{tabular}{c c} \hline
**Notations** & **Descriptions** \\ \hline \(\lambda_{i}\ (i=1,2,3,4)\) & Security parameters \\ \hline \(s\) & Secret key of data owner \\ \hline \(p\) & Large prime \\ \hline \(H\) & One-way hash function \\ \hline \(N\) & The filename of document \(F\) \\ \hline \(d\) & The size of document \(F\) \\ \hline \(F\) & Document \\ \hline \(\overline{F}\) & Encrypted document \\ \hline \(D\) & Keyword dictionary \\ \hline \(n\) & Number of keywords in \(D\) \\ \hline \(\mathbf{D}\) & Dictionary set \(\mathbf{D}=\{D_{1},D_{2},\cdots,D_{z}\}\) \\ \hline \(W\) & A set of search keywords \\ \hline \(\overline{I}\) & A plaintext index vector \(\overline{I}=(I_{1},I_{2},\cdots)\) \\ \hline \(\overline{I}\) & A ciphertext index vector \(\overline{I}=(I_{1},I_{2},\cdots)\) \\ \hline \(\vec{Q}\) & Query vector \(\vec{Q}=(\hat{Q}_{1},\hat{Q}_{2},\cdots)\) constructed from \(W\) \\ \hline \(\vec{Q}\) & Search trapdoor in ciphertext format \\ \hline \(\gamma\) & The hash value with regard to document \(F\) \\ \hline \(m_{i},t_{i}\) & Random numbers for \(1\leq i\leq n+2\) \\ \hline \(\delta\) & Random number \\ \hline \(\tau\) & Search threshold \\ \hline \end{tabular}
\end{table} 
Table 2: Notations. The data user sets the search threshold, \(\tau\), and submits the search trapdoor \(\hat{Q}\) and \((\tau,\delta)\) to the cloud server. * **Search**: Once received, the encrypted search trapdoor \(\hat{Q}\), the cloud server computes the similarity score \(\mathsf{Score}(\vec{I},\vec{Q})\) with each \(\hat{I}\) of outsourced documents as follows.