Structured Encryption and Dynamic Leakage Suppression
Structured encryption (STE) schemes encrypt data structures in such a way that they can be privately queried. Special cases of STE 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 the leakage of STE schemes. A notable example is the query equality suppression framework (Kamara et al. CRYPTO’18) which transforms dynamic STE schemes that leak the query equality into new schemes that do not. Unfortunately, this framework can only produce static schemes and it was left as an open problem to design a solution that could yield dynamic constructions.In this work, we propose a dynamic query equality suppression framework that transforms volume-hiding semi-dynamic or mutable STE schemes that leak the query equality into new fully-dynamic constructions that do not. We then use our framework to design three new fully-dynamic STE schemes that are “almost” and fully zero-leakage which, under natural assumptions on the data and query distributions, are asymptotically more efficient than using black-box ORAM simulation. These are the first constructions of their kind. This is joint work with Seny Kamara (Brown University) and Tarik Moataz (Aroki Systems).
Marilyn George is a PhD candidate at Brown University, where she is advised by Prof. Seny Kamara. Her primary interests are in applied cryptography, with an emphasis on structured encryption. She is also interested in algorithmic game theory and privacy-conscious system design. Before starting her PhD, she obtained her Masters from the Indian Institute of Science, and was a Research Fellow at Microsoft Research India, working on analytics over encrypted data.