Secure Multi-keyword Fuzzy Search Supporting Logic Query over Encrypted Cloud Data

Compared with exact search, fuzzy search will meet more practical requirements in searchable encryption since it can handle spelling errors or search the keywords with similar spelling. 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). In this paper, 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. The scheme 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.