[Resource Topic] 2024/2091: Encrypted Multi-map that Hides Query, Access, and Volume Patterns

Welcome to the resource topic for 2024/2091

Title:
Encrypted Multi-map that Hides Query, Access, and Volume Patterns

Authors: Alexandra Boldyreva, Tianxin Tang

Abstract:

We present an encrypted multi-map, a fundamental data structure underlying
searchable encryption/structured encryption. Our protocol supports updates and
is designed for applications demanding very strong data security. Not only it
hides the information about queries and data, but also the query, access, and
volume patterns. Our protocol utilizes a position-based ORAM and an encrypted
dictionary. We provide two instantiations of the protocol, along with their
operation-type-revealing variants, all using PathORAM but with different
encrypted dictionary instantiations (AVL tree or BSkiplist). Their efficiency
has been evaluated through both asymptotic and concrete complexity analysis,
outperforming prior work while achieving the same level of strong security. We
have implemented our instantiations and evaluated their performance on two
real-world email databases (Enron and Lucene). We also discuss the strengths and
limitations of our construction, including its resizability, and highlight that
optimized solutions, even with heavy network utilization, may become practical
as network speed improves.

ePrint: https://eprint.iacr.org/2024/2091

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 .