Enabling Efficient Verifiable Fuzzy Keyword Search Over Encrypted Data in Cloud Computing

Searchable encryption can support data user to selectively retrieve the cipher documents over encrypted cloud data by keyword-based search. Most of the existing searchable encryption schemes only focus on the exact keyword search. When data user makes spelling errors, these schemes fail to return the result of interest. In searchable encryption, the cloud server might return the invalid result to data user for saving the computation cost or other reasons. Therefore, these exact keyword search schemes find little practical significance in real-world applications. In order to address these issues, we propose a novel verifiable fuzzy keyword search scheme over encrypted cloud data. For the purpose of introducing this scheme, we first propose a verifiable exact keyword search scheme and then extend this scheme to the fuzzy keyword search scheme. In the fuzzy keyword search scheme, we employ the linked list as our secure index to achieve the efficient storage. We construct a linked list with three nodes for each exact keyword and generate a fuzzy keyword set for it. To reduce the computation cost and the storage space, we generate one index vector for each fuzzy keyword set, rather than each fuzzy keyword. To resist malicious behaviors of the cloud server, we generate an authentication label for each fuzzy keyword to verify the authenticity of the returned ciphertexts. Through security analysis and experiment evaluation, we show that our proposed schemes are secure and efficient.