Welcome to the resource topic for 2025/1621
Title:
Page-efficient Encrypted Multi-Maps: New Techniques for Optimal Search Bandwidth
Authors: Francesca Falzon, Zichen Gui, Michael Reichle
Abstract:Encrypted multi-maps (EMMs) allow a client to outsource a multi-map to an untrusted server and then later retrieve the values corresponding to a queried label. They are a core building block for various applications such as encrypted cloud storage and searchable encryption. One important metric of EMMs is memory-efficiency: most schemes incur many random memory accesses per search query, leading to larger overhead compared to plaintext queries. Memory-efficient EMMs reduce random accesses but, in most known solutions, this comes at the cost of higher query bandwidth.
This work focuses on EMMs run on SSDs and we construct two page-efficient schemes—one static and one dynamic—both with optimal search bandwidth. Our static scheme achieves \bigOtilde{\log N/p} page-efficiency and \bigo(1) client storage, where N denotes the size of the EMM and p the SSD’s page size. Our dynamic scheme achieves forward and backward privacy with \bigOtilde{\log N/p} page-efficiency and \bigo(M) client storage, where M denotes the number of labels. Among schemes with optimal server storage, these are the first to combine optimal bandwidth with good page-efficiency, saving up to \bigo(p) and \bigOtilde{p\log\log (N/p)} bandwidth over the state-of-the-art static and dynamic schemes, respectively. Our implementation on real-world data shows strong practical performance.
ePrint: https://eprint.iacr.org/2025/1621
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 .