# MinHash-Based Fuzzy Keyword Search of Encrypted Data across Multiple Cloud Servers
## 4 Security and Performance Analysis
### Performance Analysis  
We performed some experiment to test the performance of the proposed scheme on some actual datasets that we obtained from http://www/cs/cmu.edu/~enron/. The experiment environment is as follows: the operating system is 64-bit Windows 7, the CPU is an Inter(R) Core(TM) i5 (2.8 HGHz) with 4 GB of memory. We used the Java class library of PDFBox to extract the content of the PDF documents. The collection of keywords is formed after extracting the keywords of the document title and filtering out some stop words. In the experiment, Hmac-SHA1 was used as the one-way hash function with 160-bit outputs. The advantages of our proposed scheme are apparent after comparing it to the wildcard and the Gram scheme.  
Figure 4 shows the comparison result on the spatial overhead, showing that with the same set of keywords, the space cost of the fingerprint is much smaller than the ciphertext fuzzy set constructed by the traditional methods. The advantage on space overhead only becomes more obvious as the size of the dataset increases.  
The time consumed for constructing the keyword fuzzy set in the MinHash fingerprint is close to the Gram method with d = 2 with the time overhead remaining at a relatively low level as shown in Figure 5.  
Figure 4: Spatial overhead of constructing the fuzzy set.  
Figure 5: Time consumption for the construction of the finger/cipher-text fuzzy set.  
The index construction time in Figure 6 shows that when the editing distance increases, the size of the fuzzy set increases sharply, so does the index construction time in the conventional method. When the edit distance remains the same, the fuzzy set generated by the wildcard is relatively large, so is the index construction time. Thus, the index construction time is greatly affected by the fuzzy set in the traditional method. However, the proposed scheme uses keyword fingerprints to construct a fingerprint index tree, which will not be affected by the size of the fuzzy collections. In the index construction phase, the proposed scheme calculates the key fingerprints and relevance scores, which incurs very little time overhead while reducing the storage space and optimizing the sorting results.  
Figure 7 shows multi-server search efficiency, which compares the single-server model with the multi-server model where the number of servers is 1, 10, 50 and 100, respectively. As can be seen in the figure, when the number of ciphertext files remains the same, the more the number of servers participating in the search, the higher the search efficiency. Especially, as the number of files increases, the improvement on search efficiency becomes more significant. The retrieval time does not always decrease with the increase in the number of servers, however, since the server S needs to sort out the retrieval results transmitted from the servers S\({}_{1}\), S\({}_{2}\),..., S\({}_{N}\) before deriving the final retrieval results. The experiment also indicates that when the number of servers is not particularly large, search for ciphertext files in the multi-server model will result in significant improvement on efficiency as the number of servers participating in the search increases. This is especially the case with a large number of documents.  
Figure 6: Time consumption for index construction.  
Figure 7: Efficiency of retrieval with different number of servers.  
Experiment was also performed to analyze different file segmentation storage methods, i.e., random segmentation and average segmentation, under single server model and multiple server model. In the experiment, each file has 40 keywords and the keyword trapdoor that the user utilizes for retrieval contains 10 keywords. Figure 8a-c show the results with \(10,50\) and \(100\) servers, respectively. Moreover, the number of files that are retrieved in parallel (not exceeding the trapdoor of the number of servers) may be stored randomly on the servers (MSRD) or equally divided among the servers (MSUD). Figure 8 shows the average value of 10 experiments.