Scalable Fuzzy Keyword Ranked Search Over Encrypted Data on Hybrid Clouds

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 d, the storage cost will grow exponentially or the precision of search results will greatly decrease as d 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 d 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.

Automated summary

In this article, a scalable fuzzy keyword ranked search scheme over encrypted data under hybrid clouds architecture is proposed. The similarity of keywords is measured using the edit distance, and an edit distance algorithm over encrypted data is designed to achieve fuzzy keyword search with a constant storage size and accurate results for any similarity threshold. Furthermore, a two-factor ranking function combining keyword weight with keyword morphology similarity is designed to enhance system usability. Extensive experiments are performed to demonstrate the trade-off of efficiency and security of the proposed scheme.