BOMAP: A Round-Efficient Construction of Oblivious Maps
Ruixuan Wang, Siyi Lv, Xiang Li, Haoshuai Gong, Zheli Liu, Tong Li, Liang Guo · IEEE Transactions on Dependable and Secure Computing · 2025
Oblivious map is a cryptographic data structure for programs whose data access patterns exhibit some degree of predictability, which plays a pivot role in constructing high-security searchable encryption schemes that protect both search and access patterns. Typically, oblivious map schemes adopt the combination of an index tree and Oblivious RAM (ORAM) in their construction. However, the round complexity of access operations in these schemes is inherently linked to the height of the index tree, which is logarithmically proportional to the total number of blocks, denoted as$N$. This results in a traditional requirement of$O(\log N)$rounds of interaction per access, which is a significant inefficiency that hampers the practical applicability of oblivious maps. To this end, we design a new fixed-height index tree structure and employ it to construct a new oblivious map scheme, called BOMAP. This scheme features a small number of interaction rounds and does not require the client to store state information beyond the cache. Additionally, BOMAP achieves obliviousness with reduced padding in each access operation. We analyze the theoretical communication size for BOMAP and conclude that BOMAP has obvious advantages when an adaptive height is selected based on$N$(e.g., a 4-level index tree when$N=2^{24}$). Experimental results further demonstrate that the fewer interaction rounds and less padding strategy make BOMAP more efficient than previous oblivious map schemes.