A Privacy-Preserving Fuzzy Keyword Search Scheme over Encrypted Cloud Data

Fuzzy keyword search is an important and necessary functionality for information retrieval in modern cloud storage services, since cloud users may submit queries with typos errors or have deficient knowledge about the underlying keywords of cloud data sets. However, for the purpose of privacy preservation, data is usually encrypted before outsourcing to the cloud, which greatly compromises the data utilization flexibility and efficiency. In this paper, we propose F2SE as a novel fuzzy keyword search scheme over encrypted cloud data. Using keyword fingerprint extraction and secure kNN encryption, F2SE can achieve a top-k ranked fuzzy keyword search according to the keyword similarity. Meanwhile, F2SE can return keywords containing special sub strings customized by cloud users with deficient background knowledge, which can be used for exploratory search or uncertain search. Thorough security analysis shows F2SE is KPA-secure while extensive experiments over real data sets demonstrate that F2SE has a low memory overhead and practical searching time cost.