Paper 2025/1621

Page-efficient Encrypted Multi-Maps: New Techniques for Optimal Search Bandwidth

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 $\tilde{\mathcal{O}}(\log N/p)$ page-efficiency and $\mathcal{O}(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 $\tilde{\mathcal{O}}(\log N/p)$ page-efficiency and $\mathcal{O}(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 $\mathcal{O}(p)$ and $\tilde{\mathcal{O}}(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.