# Lightweight and Privacy-Preserving Multi-Keyword Search over Outsourced Data
## 5 Analysis and Comparison
### Theoretical Analysis  
As shown in Table 3, the performance of the proposed basic and extended PRMS schemes are theoretically compared with related ones [9; 12; 13; 42] in three phases, namely, ciphertext index generation, trapdoor generation and search process. Note that among these schemes, [PERSON] et al. 's scheme [13] was designed in the public key setting. Let \(\mu\) denote the number of documents. It can be seen that in the system setup phase, only the keyword search scheme proposed in the public key setting has to perform resource-intensive operations--that is, in [PERSON] et al. 's scheme [13], one exponentiation operation in bilinear group should be taken in this phase, where the exponentiation operation takes much more computing time than that of addition and multiplication. In the process of the ciphertext index generation for a document, both proposed PRMS schemes only require the data owner to take modular multiplication and addition opera \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Scheme**} & **Setup** & **Index** & **Trapdoor** & **Search** & \multirow{2}{*}{**Setting**} \\  & **—** & **Generation** & **Generation** & **Process** & \\ \hline [PERSON] et al.’s scheme [12] & — & \(O(\mu n^{2})\) & \(O(n^{2})\) & \(O(\mu n)\) & Private key \\ \hline [PERSON] et al.’s scheme [9] & — & \(O(ab\mu n^{2})\) & \(O(n^{2})\) & \(O(\mu\log n)\) & Private key \\ \hline [PERSON] et al.’s scheme [42] & — & \(O(\mu n^{3})\) & \(O(n^{2})\) & \(O(\beta\mu\log n)\) & Private key \\ \hline [PERSON] et al.’s scheme [13] & \(1 Exp\) & \(O(\mu n)\) & \(O(n)\) & \(O(\mu n^{2})\) & Public key \\ \hline Basic PRMS scheme (Section 3 and [15]) & — & \(O(\mu n)\) & \(O(n)\) & \(O(\mu n)\) & Private key \\ \hline Extended PRMS scheme (Section 4) & — & \(O(\mu n2n)\) & \(O(n)\) & \(O(\mu n)\) & Private key \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Theoretical comparison. tions. Thus, the time complexity of this phase in the proposed PRMS schemes are \(O(\mu n)\) and \(O(\mu zn)\), respectively, which depend on the length \(n\) of index vector and the number \(\mu\) of documents. Since each document would be attached with \(z\) types of keywords, the time complexity of the extended PRMS scheme also relies on \(z\). In [PERSON] et al. 's scheme [PERSON] et al. (2018), the generation of ciphertext index involves two matrix multiplications between the split index vectors and the transposed matrices of \((n+2)\times(n+2)\), which means the time complexity is \(O(\mu n^{2})\). In [PERSON] et al. 's scheme [PERSON] et al. (2018), the time cost of ciphertext index generation includes building a tree-based index group, constructing indexes for documents, and encrypting all nodes in the index tree. There are total \(O(\alpha\mu b)\) nodes in the index tree, where \(\alpha\) is a decimal and \(b\) represents the number of invertible matrices for each group. The encryption for each node needs to perform two multiplication operations of \(n\times n\) matrix. Thus, the time complexity of this phase [PERSON] et al. (2018) is \(O(\alpha\mu bn^{2})\). In [PERSON] et al. 's scheme [PERSON] et al. (2018), the data owner needs to construct a \(KBB\) index tree with \(O(n)\) nodes before performing encryption, where the encryption requires the multiplications of \(n\times n\) matrices. Hence, the total time complexity is \(O(\mu n^{3})\). In [PERSON] et al. 's scheme [PERSON] et al. (2018), each keyword in the index vector for each document should be separately encrypted, which requires two exponentiations and one bilinear pairing operation. Thus, their scheme has the time complexity of \(O(\mu n)\). For the trapdoor generation, the proposed PRMS schemes only involve modular multiplication and addition operations. Thus, the time complexity of both proposed PRMS schemes is \(O(n)\). In [PERSON] et al. 's scheme [PERSON] et al. (2018), the trapdoor generation includes the query vector splitting and encryption, where the encryption is realized by matrix multiplications of \((n+2)\times(n+2)\) inverse matrices.