# Lightweight, Secure, Similar-Document Retrieval over Encrypted Data
## 4 Scheme Overview
### Private Similarity Computation and Search Queries Stage
The experiments were conducted on a 2.53 GHz Intel i5 M380 CPU, Windows 7 OS 64-bit, with 3 GB RAM. The experiments were conducted using MATLAB R2008a. The Paillier cryptosystem was implemented using Java class. The inverted index was stored in a hash table to provide \(O(1)\) access time. The performance of the implementation was measured by searching the whole database through an inverted index with each potentially suspicious document to retrieve similar documents. ### Retrieval Evaluation

In this experiment, the effectiveness of the proposed scheme to retrieve similar documents from the non-secure server's encrypted database was tested. This was accomplished by using the precision evaluation metric. One hundred random, suspicious documents were selected as the query set. The comparison was assessed between this work and the resemblance \(R\) measure for computing the similarity between two documents. The \(R\) measure is defined as [41]:

\[R=|\text{Inter}|/|\text{Union}|, \tag{4}\]

where the Inter set represents the intersection set of two fingerprint sets, while the Union represents the union set. The ranking method used only employs the intersection set without using the union set to measure resemblance. The precision \(P\) of the query document \(q\) is defined as:

\[P(q)=|R\cap A|/|A|, \tag{5}\]

where \(R\) is the retrieved documents in this study, while \(A\) is the set of retrieved documents under Equation (4). Where \(Q=\{q_{1},q_{2},\ldots,q_{x}\}\) of \(x\) queries, the average precision can be

\[avg\_press=\frac{\sum_{i=1}^{x}P(q_{i})}{x} \tag{6}\]Figure 2 shows that the average precision is lower as the top-\(h\) documents increases. As expected, increasing the \(h\) value results in dissimilar documents being retrieved. ### Effectiveness

In this experiment, the goal was to use differential privacy, which works by adding or removing some noisy items into the query document without scarifying the accuracy of queries [42]. The efficacy of this work was evaluated to recover the inserted noise in the provided query. During the test, different amounts of noise were inserted into the query, ranging from 2% to 9% of the length of the query document. Noise that represents the falsified data was inserted into the query document at random locations to hide the number of fingerprints. Details on the example datasets are provided below. Figure 3 illustrates that precision decreases as the amount of the inserted noise increases. The noise value of 0.6 was adopted in our proposed model, as it does not affect the retrieval accuracy at all. ### Index Building

The construction of the secret inverted index by the data owner, \(Bob\), included generating the fingerprints and encrypting the posting vectors. In this experiment, the effect of the collection size, \(m\), and the \(k\) value for the \(k\)-gram on the secure inverted index building time and the total number of individual fingerprint terms is illustrated. Figure 4 shows that increasing \(k\) when computing the \(k\)-gram sets provokes an increase in the fingerprint terms. Similarly, increasing \(k\) requires more time to compute the fingerprint terms, as explained in Figure 5.

Figure 3: Effectiveness of the proposed scheme. Figure 2: Retrieval evaluation. ### Ranking Time

The principal purpose of the ranking technique is to speed up the process of retrieving similar documents in an orderly manner. This process sorts the similarity scores of all the encrypted storage fingerprints in descending order to obtain the sorting result. Based on the ranking result, the target comparison document set is formed from each of the encrypted stored fingerprints with the highest score extracted according to the number of retrievals. During the ranking time, the study sums up the posting vectors of the matched fingerprint terms. All vectors are of a fixed length equal to the collection size \(m\). Figure 8 shows that more matched fingerprint terms require a longer ranking time. The document collection size for this experiment was fixed at 1000.