Welcome to the resource topic for 2019/1132
Title:
Lower Bounds for Encrypted Multi-Maps and Searchable Encryption in the Leakage Cell Probe Model
Authors: Sarvar Patel, Giuseppe Persiano, Kevin Yeo
Abstract:Encrypted multi-maps (EMMs) enable clients to outsource the storage of a multi-map to a potentially untrusted server while maintaining the ability to perform operations in a privacy-preserving manner. EMMs are an important primitive as they are an integral building block for many practical applications such as searchable encryption and encrypted databases. In this work, we formally examine the tradeoffs between privacy and efficiency for EMMs. Currently, all known dynamic EMMs with constant overhead reveal if two operations are performed on the same key or not that we denote as the \mathit{global\ key\text{-}equality\ pattern}. In our main result, we present strong evidence that the leakage of the global key-equality pattern is inherent for any dynamic EMM construction with O(1) efficiency. In particular, we consider the slightly smaller leakage of \mathit{decoupled\ key\text{-}equality\ pattern} where leakage of key-equality between update and query operations is decoupled and the adversary only learns whether two operations of the \mathit{same\ type} are performed on the same key or not. We show that any EMM with at most decoupled key-equality pattern leakage incurs \Omega(\log n) overhead in the \mathit{leakage\ cell\ probe\ model}. This is tight as there exist ORAM-based constructions of EMMs with logarithmic slowdown that leak no more than the decoupled key-equality pattern (and actually, much less). Furthermore, we present stronger lower bounds that encrypted multi-maps leaking at most the decoupled key-equality pattern but are able to perform one of either the update or query operations in the plaintext still require \Omega(\log n) overhead. Finally, we extend our lower bounds to show that dynamic, \mathit{response\text{-}hiding} searchable encryption schemes must also incur \Omega(\log n) overhead even when one of either the document updates or searches may be performed in the plaintext.
ePrint: https://eprint.iacr.org/2019/1132
Talk: https://www.youtube.com/watch?v=DL30LsMQc6I
Slides: https://iacr.org/submit/files/slides/2020/crypto/crypto2020/232/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .