Privacy-Preserving Bloom Filter-Based Keyword Search Over Large Encrypted Cloud Data
Yanrong Liang, Jianfeng Ma, Yinbin Miao, Da Kuang, Xiangdong Meng, Robert H. Deng
Abstract
To achieve the search over encrypted data in cloud server, Searchable Encryption (SE) has attracted extensive attention from both academic and industrial fields. The existing Bloom filter-based SE schemes can achieve similarity search, but will generally incur high false positive rates, and even leak the privacy of values in Bloom filters (BF). To solve the above problems, we first propose a basic <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</u> rivacy-preserving <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</u> loom filter-based <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</u> eyword <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</u> earch scheme using the Circular Shift and Coalesce-Bloom Filter (CSC-BF) and Symmetric-key Hidden Vector Encryption (SHVE) technology (namely PBKS), which can achieve effective search while protecting the values in BFs. Then, we design a new index structure T-CSCBF utilizing the <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</u> win Bloom Filter (TBF) technology. Based on this, we propose an improved scheme PBKS+, which assigns a unique inclusion identifier to each position in each BF with privacy protection. Formal security analysis proves that our schemes are secure against Indistinguishability under Selective Chosen-Plaintext Attack (IND-SCPA), and extensive experiments using real-world datasets demonstrate that our schemes are feasible in practice.