A Privacy-preserving Fuzzy Search Scheme Supporting Logic Query over Encrypted Cloud Data

Fuzzy keyword search is a necessary and important feature of information retrieval in modern cloud storage services since users with insufficient knowledge may input typos or keywords with inconsistent formats. However, most of the existing fuzzy search schemes adopt bloom filter and locality sensitive hashing which cannot resist Sparse Non-negative Matrix Factorization based attack (SNMF attack). To this end, we propose a new secure multi-keyword fuzzy search scheme for encrypted cloud data, our scheme leverages random redundancy method to handle the deterministic of bloom filter to resist SNMF attack. Besides the privacy, our scheme uses tree-based index construction to improve search efficiency and allows users to conduct complicated fuzzy search with logic operations “AND”, “OR” and “NOT”, which can meet more flexible and fine-grained query demands. The theoretical analysis and experiments on real-world data show the security and high performance of our scheme.