Towards Practical Oblivious Map

Xinle Cao, Weiqi Feng, Jian Liu, Jinjin Zhou, Wenjing Fang, Lei Wang, Quanqing Xu, Chuanhui Yang and Kui Ren.

(Abstract) 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 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$ denotes 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 constructions also adapt only the tree-based Oblivious RAM (ORAM) and oblivious data structures (ODS) to achieve OMAP for enhanced practicality. In complexity, our approach needs $O(\log{n}/\log{\log{n}}) +O(\log{\lambda})$ interaction rounds and $O(\log^2{n}/\log{\log{n}}) + O(\log{\lambda}\log{n})$ communication bandwidth per data access where $\lambda$ is the security parameter. This new complexity 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 as it supports obliviously accessing hash tables much more efficiently. We implement both our proposed constructions and prior methods to experimentally demonstrate that our constructions substantially outperform prior methods in terms of efficiency.

The full version of the paper is posted here.

ORAM Methods

• Insecure Freecursive (ASPLOS 2015), which is implemented here. The reset_method needs to be set to "hard".
• Secure Freecursive with probabilistic resets (TCC 2017), which is implemented here. The reset_method needs to be set to "prob".
• The proposed DAORAM with deterministic resets, which is implemented here.

OMAP Methods

• OMAP based on AVL (CCS 2014), which is implemented here. The distinguishable_search needs to be set to False.
• OMAP based on optimized AVL (VLDB 2024), which is implemented here. The distinguishable_search needs to be set to True.
• OMAP based on the B+ tree (VLDB 2020), which is implemented here.
• The proposed OMAP framework is implemented here. It can be instantiated with any ORAM class contained in this repo combined with any OMAP class in this repo.

The open-sourced repositories we used as reference for the OMAP based on AVL tree and OMAP based on B+ tree are here: AVL B+ tree.

Project Structure

• The demo folder consists of demonstrations of how to use socket to set up ORAM/OMAP server and client.
• The dependency folder consists of some dependencies used including the socket, cryptography, etc.
• The omaps folder consists of all the OMAP constructions considered.
• The orams folder consists of all the ORAM constructions considered.
• The tests folder consists of test cases for validating correctness of our implementations.

How to run this code

You need to first install the package listed in requirements.txt. If you want to run the schemes with "local server", sample usages can be found in tests/test_orams.py or tests/test_omaps.py. If you wish to set up a remote server, you should first run demo/server.py on the server and then run demo/oram_client.py or demo/oram_client.py on your client device.