Bloom filter

Correctness

Hash function

Operating system

Algorithm

Data mining

Inverted index

Encryption

Artificial intelligence

Homomorphic encryption

Set (abstract data type)

Programming language

Information retrieval

Computer science

Search engine indexing

Cloud computing

Verifiable secret sharing

Approximate string matching

Computer security

Fuzzy logic

Pattern matching

Database

IEEE Transactions on Services Computing

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.

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