Welcome to the resource topic for 2024/1708
Title:
Subliminal Encrypted Multi-Maps and Black-Box Leakage Absorption
Authors: Amine Bahi, Seny Kamara, Tarik Moataz, Guevara Noubir
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 10 milliseconds, making it practical for some applications.
ePrint: https://eprint.iacr.org/2024/1708
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 .