International Association
for Cryptologic Research

A leakage suppressor is a compiler that transforms a structured encryption (STE) scheme into a new scheme with an improved leakage profile. General-purpose suppressors for the query equality (qeq) pattern---which reveals if and when two queries are the same---were given for both static (Kamara et. al, \emph{Crypto '18}) and dynamic (George et. al, \emph{Eurocrypt '19}) encrypted structures. While the schemes that result from these suppressors are asymptotically efficient, they are not practical due to large constants in their query complexity. In this work, we propose a new query equality suppressor for dictionary encryption schemes that results in practical qeq-hiding encrypted dictionaries at the cost of revealing the distribution of the queries. The resulting constructions are \emph{distribution-aware}, in the sense that they make use of the query distribution, and \emph{distribution-leaking} in the sense that they also reveal it. We show how to instantiate and optimize our suppressor for query distributions that are Zipf-distributed, resulting in a scheme with $O(1)$ online query complexity at the cost of a rebuild with $O(m \log^2 m/\log\log m)$ complexity, where $m$ is the size of the input dictionary.