In Encrypted Cloud Data:an Efficient Fuzzy Searchable Encryption Scheme Based On Bed-tree

Searchable encryption is a cryptographic primitive that supports users to search for data by keywords on ciphertext,which can effectively solve the problem that cannot be directly queried on ciphertext data retrieved by traditional encryption schemes.In cryptographic datasets in the cloud,when users make a mistake in inputting the query keywords for their own reasons,the searchable encryption that only supports exact query will lead to search results that are far from users’ expectations,or even have no search results.With the support of fuzzy keyword query,the cloud server will search for files as similar as possible to them based on the query keyword,thus effectively avoiding the above problem.Search accuracy and search efficiency are two important indicators of the effectiveness and practicality of searchable encryption schemes.Now few existing schemes can support efficient search with high accuracy,which will be investigated in this thesis.Based on the premise that cloud servers are “honest but not trustworthy”,we propose a searchable encryption scheme for fuzzy queries based on an improved Bed-tree structure by taking into account the impact of index construction methods and search algorithms on search efficiency,The main work is as follows:(1)A keyword fingerprint generation algorithm based on Hybrid-gram and Simhash is designed,which can extract more keyword features,retain the similarity between keywords as much as possible.This algorithm makes the Hamming distance between keyword-transformed fingerprints smaller,thus can achieve fuzzy search more accurately.Compared with searchable schemes that use wildcards or grams to construct fuzzy sets,our algorithm does not need to construct fuzzy sets for each keyword,therefore greatly reduces the storage cost and computation cost of cloud servers and it is suitable for massive data scenarios with cloud storage.(2)The K-means++ clustering algorithm with contour coefficients is introduced to improve the Bed-tree structure and construct an index structure KMT that supports efficient search process.The K-means++ clustering algorithm solves the K-value and outlier problems and makes the clustering algorithm more suitable for the KMT structure.Based on this clustering algorithm,similar keyword Simhash fingerprints in the KMT index are clustered into the same cluster,and the range of fingerprint sets similar to the query vector can be quickly narrowed down based on the Euclidean distance between the query vector and the cluster centroid during the search process,thus improving the search efficiency.(3)Efficient searchable encryption scheme supporting fuzzy queries are designed and its security is proved.In the scheme,a depth-first fuzzy keyword matching strategy is used to eliminate sub-fingerprint nodes while searching,which makes it possible to achieve fuzzy search more accurately without traversing the whole index tree and reduces the search time greatly.To make the search results more user-friendly,the scheme performs fine-grained twofactor ranking of the search results based on two factors,Hamming distance and relevance score,to improve the user search to improve the user search experience.The experimental results show that this scheme achieves fuzzy keyword search under encrypted cloud data while ensuring data privacy,which improves the search efficiency and saving time and space costs greatly,thus verifying the effectiveness and practicality of the scheme.