Low-Cost Hiding of the Query Pattern

Florian Kerschbaum

Towards efficient search over encrypted data, various searchable encryption schemes have been proposed in the literature. While these schemes are effective in preserving the privacy of the underlying data against a snapshot attacker, they, however, leak some information during search operations due to access and query pattern leakage. Consequently, this potential privacy concern introduces general attacks by an adversary that controls the cloud service provider and hence can observe these patterns. Using some prior knowledge about data or query distribution the adversary can run simple frequency analysis attacks. While there are known, lightweight countermeasures to hide the access pattern by padding the ciphertexts, the same is not true for the query pattern or the combination of query and access pattern. Oblivious RAM can hide these patterns, but requires a superlinear cost in the size of the database and hence will become slower as data grows.
In this paper we present a method to hide the query pattern of searchable encryption schemes by introducing fake queries. We initiate an analytical study to achieve a stronger notion of security where each keyword has the same query frequency as at least d - 1 others. Our method only introduces a constant overhead per query on Zipf distributed data.