VRFMS: Verifiable Ranked Fuzzy Multi-keyword Search over Encrypted Data

Searchable encryption(SE) allows users to efficiently retrieve data over encrypted cloud data, but most existing SE schemes only support exact keyword search, resulting in false results due to minor typos or format inconsistencies of queried keywords. The fuzzy keyword search can avoid this limitation, but still incurs low search accuracy and efficiency. Besides, most of fuzzy keyword search schemes do not consider malicious cloud servers which may execute a fraction of search operations or forge some results due to various interest incentives such as saving computation or storage resources. To solve these problems, we propose an efficient and Verifiable Ranked Fuzzy Multi-keyword Search scheme, called VRFMS. VRFMS uses locality-sensitive hashing and bloom filter to implement fuzzy keyword search, and employs Term Frequency-Inverse Document Frequency(TF-IDF) to sort the relevant results. Aiming to further improve the search accuracy, we design an improved bi-gram keyword transformation method. Furthermore, the homomorphic MAC technique and a random challenge technique are utilized to verify the correctness and completeness of returned results, respectively. Formal security analysis and empirical experiments demonstrate that VRFMS is secure and efficient in practical applications, respectively.