# Lightweight, Secure, Similar-Document Retrieval over Encrypted Data
## 3 Document Fingerprinting  
In the detection of totally and partially similar or copied texts, fingerprinting can be effectively manipulated through the use of hash codes. Primarily, the text is split into a set of \(k\)-grams in order to obtain the fingerprint. This \(k\)-gram set is then hashed and compressed in the process of selecting a subset of these codes to form a fingerprint. The principal challenge posed by this technique is the selection of the most appropriate and smallest hash value from which to constitute the fingerprint. Thus, choosing the most appropriate technique has a great effect on reducing the size of the fingerprint set and facilitates the secure search query document. This can considerably reduce the encrypted comparison operations to retrieve similar documents, which plays an effective role in facilitating scalable documents comparing and reducing client response times. The present study has selected the Winnowing algorithm [12], which nominates the most effective and smallest hash value from \(k\)-gram window slides. Particular boundaries exist for detecting similarities among duplicated and original texts when employing such hashed fingerprints. In the subsequent section, a concise explanation of the function of this algorithm is given. Given the string \(St\) as a sequence of \(n\) characters, the \(k\)-gram is a substring of length \(k\). For example, the 4 grams of the string \(St\) = 'to be or not to be' is ['tobe', 'obeo', 'beor', 'eorn', 'omo', 'nott', 'otto', 'ttob', 'tobe'] of length \(n-k+1\). Hashing the \(k\)-gram set is achieved by [PERSON]'s algorithm [34]. This algorithm allows the hash of the \(i+1\)st \(k\)-gram to be computed efficiently from the \(i\)th \(k\)-gram. Suppose that the first \(k\)-gram is a set of \(t_{1},\ldots,t_{k}\) numbers in the based \(b\). Then, we can hash these numbers as:  
\[F_{1}=(t_{1}\times b^{k-1}+t_{2}\times b^{k-2}+\cdots+t_{k-1}\times b+t_{k}) \mod M, \tag{1}\]  
where \(M\) is a constant defined by the user. The second \(k\)-gram of \(t_{2},\ldots,t_{k+1}\) numbers is computed efficiently as follows:  
\[F_{2}=(((F_{1}-t_{1}\times b^{k})+t_{k+1})\times b)\mod M. \tag{2}\]Generally, the \(i\)th \(k\)-gram is computed as:  
\[F_{i}=(\left(((F_{i-1}-t_{1}\times b^{k})+t_{k+i-1})\times b\right)\mod M,\forall i =2\ldots n. \tag{3}\]  
Now the Winnowing algorithm selects the fingerprint among the \(F_{1},\ldots,F_{n-k+1}\) hash codes. Given any two documents, this algorithm guarantees finding substring matches between the documents which satisfy the following criteria:  
1. The length of the matched strings is not less than the guarantee threshold, \(T\). 2. The length of the matched substrings does not exceed the noise threshold, \(k\). Note that both \(T>k\) and \(k\) are user-defined values. Choosing a large value of \(k\) prevents coincidental matching between two documents, however, it does limit the sensitivity to reordered document contents, since it cannot detect the relocation of any substring of a length less than \(k\). Therefore, it is necessary to choose a minimum value of \(k\) such that coincidental matches will be negligible. The algorithm defines a window size as: \(w=T-k+1\). Each position in the sequence \(1\leq i\leq(n-k+1)-w+1\) defines a window of hashes \(F_{i},\ldots,F_{i+w-1}\). In each window, the minimum hash value is selected. Should there be more than one hash with the minimum value in the same window, only the rightmost occurrence must be selected. The same hash value among successive windows will not be inserted in the fingerprint. All selected hashes are considered to be the fingerprint of document. Consequently, it plays an essential role to select the much fewer numbers of actual hash values, incurring a low computational overhead. For example, suppose we have the following hash codes: 77 72 42 17 98 50 17 98 88 67 39 77 72 42 17 98, and suppose that the window size is w = 4.