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.

Structured encryption (STE) schemes encrypt data structures in such a way that they can be privately queried. Special cases ofSTE include searchable symmetric encryption (SSE) and graph encryption. Like all sub-linear encrypted search solutions, STE leaks information about queries against persistent adversaries. To address this, a line of work on leakage suppression was recently initiated that focuses on techniques to mitigate or completely remove the leakage of STE schemes (Kamara et al. CRYPTO’18 and Kamara and Moataz, Eurocrypt ’19). A notable example is the cache-based compiler which, when combined with the rebuild compiler, transforms any dynamic STE scheme that leaks the query equality into a new scheme that does not. Unfortunately, this compiler can only produce static schemes and it was left as an open problem to design a compiler that could yield dynamic constructions. In this work, we propose a dynamic variant of the cache-based compiler. Our compiler can transform any volume-hiding semi-dynamic or mutable STE scheme that leaks the query equality pattern into into a new fully-dynamic construction that does not. Using this compiler, we design three new fully-dynamic STE schemes that are “almost” and fully zero-leakage which, under natural assumptions about the data and query distributions, are asymptotically more efficient than using black-box ORAM simulation. These are the first constructions of their kind.