You are looking at a specific version 20191002:082355 of this paper. See the latest version.

Paper 2019/1132

Leakage Cell Probe Model: Lower Bounds for Key-Equality Mitigation in Encrypted Multi-Maps

Sarvar Patel and Giuseppe Persiano and 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 is, they leak 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
lower boundsencrypted searchencrypted multi-mapsleakage
Contact author(s)
kwlyeo @ google com
History
2020-10-12: last of 2 revisions
2019-10-02: received
See all versions
Short URL
https://ia.cr/2019/1132
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.