Scalable Fuzzy Keyword Ranked Search Over Encrypted Data on Hybrid Clouds
Hua Zhang, Shaohua Zhao, Ziqing Guo, Qiaoyan Wen, Wenmin Li, Fei Gao
Abstract
Searchable encryption (SE) is a powerful technology that enables keyword-based search over encrypted data becomes possible. However, most SE schemes focus on exact keyword search which can not tolerate misspellings and typos. Existing fuzzy keyword search schemes only support fuzzy search within a limited similarity threshold <inline-formula><tex-math notation="LaTeX">$d$</tex-math></inline-formula> , the storage cost will grow exponentially or the precision of search results will greatly decrease as <inline-formula><tex-math notation="LaTeX">$d$</tex-math></inline-formula> increases. Moreover, the current fuzzy keyword ranked search schemes consider only the keyword weight, and disregard the influence of keyword morphology similarity on the ranking. In this article, we propose a scalable fuzzy keyword ranked search scheme over encrypted data under hybrid clouds architecture. We use the edit distance to measure the similarity of keywords and design an edit distance algorithm over encrypted data, in which our scheme achieves fuzzy keyword search for any similarity threshold <inline-formula><tex-math notation="LaTeX">$d$</tex-math></inline-formula> with a constant storage size and accurate search results. Furthermore, we design a two-factor ranking function combining keyword weight with keyword morphology similarity, which is utilized to rank the search results and enhance system usability. Extensive experiments are performed to demonstrate the trade-off of efficiency and security of the proposed scheme.