# Lightweight and Privacy-Preserving Multi-Keyword Search over Outsourced Data
## 5 Analysis and Comparison  
### Security Analysis  
**Theorem 3**: _If the symmetric encryption algorithm chosen by data owner is secure, then the proposed basic and extended PRMS schemes guarantee the privacy of outsourced documents against the server._  
Proof.: As shown in the proposed PRMS schemes of Section 3 and Section 4, the outsourced documents are encrypted with some symmetric encryption algorithm. Thus, if such symmetric encryption algorithm is secure, then the encrypted documents would not leak the contents of these documents.  
**Theorem 4**: _The proposed basic and extended PRMS schemes guarantee the privacy of keywords for outsourced documents against the server._  
Proof.: In the index generation phase of the basic PRMS scheme, each element \(I_{i}\) in the index vector \(\vec{I}\) is randomized using one-time random value \(m_{i}\). Thus, if all these elements \(m_{i}\) (\(1\leq i\leq n+2\)) are uniformly distributed and independently chosen from \(Z_{\lambda_{3}}\), then all encrypted indexes \(\hat{I}_{i}\) (\(1\leq i\leq n+2\)) would have the same distribution, which means \(\Pr[\hat{I}_{i_{1}}]=\Pr[\hat{I}_{i_{2}}]\) for different \(i_{1}\) and \(i_{2}\). Therefore, the cloud server cannot deduce the content of index vector. For the index generation phase of the extended PRMS scheme, the elements in each index vector \(\bar{I}_{\ell}\) are processed in the similar way. Thus, the encrypted index vectors would not leak the private information of outsourced documents.  
The proposed basic and extended PRMS schemes guarantee the privacy of trapdoors against the server.  
In the trapdoor generation phase of the basic PRMS scheme, each element \(Q_{i}\) in the query vector \(\bar{Q}\) is randomized using one-time random value \(t_{i}\). Furthermore, for the whole query vector \(\bar{Q}\), \(\delta\) is also randomly chosen. Thus, if all these elements \(t_{i}\) (\(1\leq i\leq n+2\)) and \(\delta\) are uniformly distributed and independently chosen from \(Z_{\lambda_{3}}\) and \(Z_{\lambda_{1}}\), respectively, then all encrypted trapdoor entries \(\hat{Q}_{i}\) (\(1\leq i\leq n+2\)) would have the same distribution, which means \(\Pr[\hat{Q}_{i_{1}}]=\Pr[\hat{Q}_{i_{2}}]\) for different \(i_{1}\) and \(i_{2}\). Therefore, the cloud server cannot deduce the content of query vector. For the trapdoor generation phase of the extended PRMS scheme, the elements in the query vector \(\bar{Q}\) with regard to each keyword dictionary \(D_{\ell}\) are processed in the similar way. Thus, the encrypted search trapdoor vectors would not leak the private information of trapdoor and outsourced documents.  
The proposed basic and extended PRMS schemes offer unlinkability of trapdoors against the server.  
As analyzed in the proof of Theorem 4.1, if all elements \(t_{i}\) (\(1\leq i\leq n+2\)) and \(\delta\) are uniformly distributed and independently chosen from \(Z_{\lambda_{3}}\) and \(Z_{\lambda_{1}}\), respectively, then all entries \(\hat{Q}_{i}\) (\(1\leq i\leq n+2\)) in the encrypted trapdoor would have the same distribution, which means \(\Pr[\hat{Q}_{i_{1}}]=\Pr[\hat{Q}_{i_{2}}]\) for different \(i_{1}\) and \(i_{2}\). Hence, the cloud server would not be able to determine whether two search trapdoors are generated for the same query. Furthermore, for the trapdoor generation phase of the extended PRMS scheme, the elements in the query vector \(\bar{Q}\) with regard to each keyword dictionary \(D_{\ell}\) are processed in the similar way. Thus, the encrypted search trapdoor vectors enjoys unlinkability.