International Association
for Cryptologic Research

Oblivious map (OMAP) is an important component in encrypted databases, utilized to safeguard against the server inferring sensitive information about client's encrypted key-value stores based on \emph{access patterns}. Despite its widespread usage and importance, existing OMAP solutions face practical challenges, including the need for a large number of interaction rounds between the client and server, as well as the substantial communication bandwidth requirements. For example, the state-of-the-art protocol named OMIX++ in VLDB 2024 still requires $O(\log{n})$ interaction rounds and $O(\log^2{n})$ communication bandwidth per access, where $n$ denote the total number of key-value pairs stored.

In this work, we introduce more practical and efficient OMAP constructions. Consistent with all prior OMAPs, our proposed constructions also adapt only the \emph{tree-based Oblivious RAM} (ORAM) to achieve OMAP for enhanced practicality. In terms of complexity, our approach needs only $O(\log{n}/\log{\log{n}})$ interaction rounds and $O(\log^2{n}/\log{\log{n}})$ communication bandwidth per data access, achieving the lowest communication volume to the best our of knowledge. This improvement results from our two main contributions. First, unlike prior works that rely solely on search trees, we design a novel framework for OMAP that combines hash table with search trees. Second, we propose a more efficient tree-based ORAM named DAORAM, which is of significant independent interest. This newly developed ORAM noticeably accelerates our constructions. We implement both our proposed constructions and prior methods to experimentally demonstrate that our constructions substantially outperform prior methods in terms of efficiency.