# Lightweight and Privacy-Preserving Multi-Keyword Search over Outsourced Data
## 5 Analysis and Comparison
### Performance Evaluation  
We conducted experimental evaluation of the proposed PRMS constructions and compared with [PERSON] et al.'s scheme [PERSON] et al. (2018). The experiments were implemented using JAVA programming language on a platform with Windows 10 operating system, Intel(R) Core(TM) i5-7500 CPU 3.71 GHz and 8 GB memory. In experiments, all procedures were compared--that is, ciphertext index construction, search trapdoor generation and cloud search. Note that the encryption on documents of the proposed PRMS constructions are only determined by the employed symmetric encryption scheme. Thus, the performance of document encryption was not considered in experiments. The chosen parameters satisfy \(n\leq 2^{32}\), \(\mid\gamma\mid=\mid\gamma_{\ell}\mid=\mid\delta\mid=\lambda_{1}=200\), \(\mid p\mid=\lambda_{2}=512\), \(\mid m_{i}\mid=\lambda_{3}=128\), and \(\mid t_{i}\mid=\lambda_{4}=128\).  
As shown in Figure 6, the size of index vector varies from 10 to 100 to evaluate the performance of generating ciphertext index. It can be seen that the time costs of the proposed basic PRMS construction are less than 1 ms for all cases in processing one document, while the costs of [PERSON] et al.'s scheme [12] rapidly increase as the number of keywords increases.  
For processing a document with multiple types of keywords with the proposed extended PRMS scheme, different number of keyword types were considered, that is, \(z=5,10,\cdots,30\). The performance of the extended PRMS construction for processing one document is shown in Figure 7. It can be seen from Figures 6 and 7 that the cost of processing a document with the extended PRMS construction is roughly \(z\) times of that with the basic PRMS construction.  
For the query generation and search phases, both the basic and extended PRMS constructions enjoy the same performance. As shown in Figure 8, the time costs of all these schemes are linear with the number of keywords in the query. Note that [PERSON] et al.'s scheme [12] needs to perform matrix multiplications in generating search trapdoor. Thus, the proposed PRMS constructions are more efficient than their scheme [12] in all cases.  
Figure 8: Time cost on search trapdoor generation.  
Figure 6: Time cost on ciphertext index generation.  
Figure 7: Time cost on ciphertext index generation for multiple types of keywords by the extended PRMS scheme.  
For the search by the cloud server, the proposed PRMS constructions do not involve complicated computation operations. In the experiments, the cloud server was considered to search over \(\mu=200\) outsourced documents. The performance is shown in Figure 9 for the proposed PRMS constructions and [PERSON] et al.'s scheme Cao et al. (2018). It can be seen that the performance of keyword search with all these schemes enjoy roughly linear relation with the number of keywords in the query for all cases. Furthermore, the performance of [PERSON] et al.'s scheme Cao et al. (2018) would decrease greatly when the number of keywords in the query vector increases. Thus, the search procedure of the proposed PRMS schemes are more efficient than that in [PERSON] et al.'s scheme Cao et al. (2018).