A Practical Query Correlation Obfuscator Applied in Conjunctive Searchable Encryption

A widely existing leakage in searchable encryption (SE) schemes: query correlation is mentioned by Grubbs et al., and subsequently, Oya et al. exploit this leakage to construct a query recovery attack against single keyword query schemes, proving the threat of this leakage to the security of searchable encryption schemes. We have noticed that there is currently no work on hiding query correlation in conjunctive keyword searchable encryption (CSE) schemes which is widely used. In this work, we successfully capture this leakage in CSE and construct a query proxy QCX that smooths query correlation by inserting fake queries into real queries sequence. Experiments indicate that QCX substantially diminishes the accuracy of the leaked query correlation pattern and frequency leakage, significantly reducing the success rate of query correlation attacks.