Efficient Strong Privacy-Preserving Conjunctive Keyword Search Over Encrypted Cloud Data
Searchable symmetric encryption (SSE) supports keyword search over outsourced symmetrically encrypted data. Dynamic searchable symmetric encryption (DSSE), a variant of SSE, further enables data updating. Most prior DSSE works primarily focus on single keyword search, and some have later expanded to support conjunctive keyword search. These works on conjunctive DSSE primarily consider forward and backward privacy. Ideally, the server should only learn the result sets related to all the keywords in the conjunction. However, existing schemes suffer from keyword pair result pattern (KPRP) leakage, making the server reveal the partial result sets containing two of the query keywords. We propose the first DSSE scheme to address the above concerns that achieves strong privacy-preserving conjunctive keyword search. Specifically, our scheme can maintain forward and backward privacy and eliminate KPRP leakage, offering a higher level of security for DSSE. The search complexity is proportional to the number of documents stored in the database in several existing schemes. However, the complexity of our scheme scales with the update frequency of the least frequent keyword in the conjunction, which is much smaller than the size of the entire database. Besides, we devise a least frequent keyword acquisition protocol to reduce the frequent interactions between the data owner and search users. Finally, we analyze the security of our scheme and evaluate its performance theoretically and experimentally. The results show that our scheme has strong privacy preservation and efficiency.
READ FULL TEXT