# Lightweight, Secure, Similar-Document Retrieval over Encrypted Data
## 4 Scheme Overview
### Private Similarity Computation and Search Queries Stage
GBF returned the worst performance, since it is modelled for computation of big set intersections and requires an oblivious transfer (OT) [43] to compute the similarity between two documents. \[R=|\text{Inter}|/|\text{Union}|, \tag{4}\]2 Performance of precision and recall. \begin{table}
\begin{tabular}{l l l} \hline \hline
**Work** & **Computation Cost** & **Communication (Bit)** \\ \hline Our work & \(h\): \(1.2\times 10^{2}\times m,pk\): \(3.2\times 10^{2}\) & \(1.2\times 10^{3}\times m\) \\ EsPRESSo & \(h\): \(2.3\times 10^{2}\times m,e\): \(3.9\times 10^{2}\times m\) & \(1.8\times 10^{2}\times m\) \\ GBF & \(h\): \(3.0\times 10^{4}\times m,pk\): \(4.4\times 10^{2}\times m^{2}\) & \(2\times 10^{4}\times m^{2}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Comparison of computational and communication costs (\(h\): time required to implement hash; \(pk\): time required to implement public and private key operations; \(e\): time required to implement exponentiations; \(m\): the number of documents. )Figure 13 shows the processing time consumed when detecting similarity between each pair of documents for both collections of size \(m\). Recall that GBF's complexity scale is \(O(m^{2})\) times, as long as it requires \((m^{2})\) complexity to compare encrypted documents. It is clear that this paper's model and the EsPRESSo protocol have linear complexity with increased document size, but the proposed model has less processing time than EsPRESSo, which can be jointly attributed to the winnowing algorithm and the inverted index. The Winnowing algorithm focuses on ensuring that only the outstanding properties are extracted from the fingerprint set, making them as few as possible, while the access time of an inverted index is very short, which is \(O(1)\). To prove the efficiency and scalability of this method for privacy-preserving DSD between big collections, the same settings as the above experiments were adopted with a set of 5000 documents randomly downloaded from the real dataset _Request For Comments_ (RFC) [40]. Figure 14 shows the processing time that this study's protocol and EsPRESSo take to compare two large sets of documents, each containing 5000 documents. It can be seen from Figure 14 that when the number of documents is small, EsPRESSo has a computational cost that is close to or slightly higher than this method; however, when the number of documents is large, the computational cost of this paper's method has a smaller growth rate and less processing time compared to EsPRESSo. This experiment therefore proves the claim that EsPRESSo is far from scalable when applied to large data [28]. Therefore, the work proposed in this study is more efficient for privacy-preserving DSD between big document collections, as well as for scalable documents. Figure 12: Performance of private and secure DSD (\(1\times m\) document). Figure 13: Performance of private and secure DSD (\(m\times m\) documents). The following experiments compare the performance of the proposed work with AEsPRESSo and GBF in terms of precision and recall, as shown in Figure 11. The precision and accuracy are formulated as in Equations (4) and (5). GBF has the best overall effectiveness because it employs the full set to represent each document; however, this results in a very expensive computational cost, as noted in previous experiments and shown in Figures 12-14. The effectiveness of this paper's model is slightly lower than GBF since it uses a Winnowing algorithm that extracts and selects the fundamental property from a fingerprint set to reduce terms that represent documents. The selection of only the most important and effective fingerprint has led to a reduction in computational complexity. The AEsPRESSo model has the least effectiveness for precision and recall due to the precision loss in the Min-Hash that is used to represent and measure the similarity between two sets. This paper concludes that the accuracy of precision is highly sensitive to the way documents are represented.