Paper 2024/1708
Subliminal Encrypted Multi-Maps and Black-Box Leakage Absorption
Abstract
We propose a dynamic, low-latency encrypted multi-map (EMM) that operates in two
modes: low-leakage mode, which reveals minimal information such as data
size, expected response length, and query arrival rate; and subliminal
mode, which reveals only the data size while hiding metadata including query
and update times, the number of operations executed, and even whether an
operation was executed at all---albeit at the cost of full correctness. We
achieve this by exploiting a tradeoff between leakage and latency, a previously
underexplored resource in EMM design. In low-leakage mode, our construction
improves upon existing work both asymptotically and empirically: it achieves
optimal server-side storage, as well as communication and computational
complexity that is independent of the maximum response length. In subliminal
mode, it is the first construction to hide metadata.
To analyze the latency and client-side storage of our construction, we utilize queuing theory and introduce a new queuing model, which may be of independent interest. To examine its metadata-hiding properties, we extend standard security definitions to account for metadata and prove a surprising result: if a scheme is subliminal in that it hides the execution of its operations, then it absorbs the leakage of any scheme that makes black-box use of it without sending additional messages. In other words, if a scheme is subliminal, then any scheme that makes black-box use of it will also be subliminal.
We implement and evaluate our construction, demonstrating that our empirical results align with our theoretical analysis and that the scheme achieves a median query latency below
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- encrypted searchstructured encryptionsearchable symmetric encryption
- Contact author(s)
-
amine bahi @ ens psl eu
seny kamara @ mongodb com
Tarik Moataz @ mongodb com
g noubir @ northeastern edu - History
- 2024-10-21: approved
- 2024-10-18: received
- See all versions
- Short URL
- https://ia.cr/2024/1708
- License
-
CC BY-NC-SA
BibTeX
@misc{cryptoeprint:2024/1708, author = {Amine Bahi and Seny Kamara and Tarik Moataz and Guevara Noubir}, title = {Subliminal Encrypted Multi-Maps and Black-Box Leakage Absorption}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1708}, year = {2024}, url = {https://eprint.iacr.org/2024/1708} }