Paper 2024/556

Menhir: An Oblivious Database with Protection against Access and Volume Pattern Leakage

Leonie Reichert, Technical University of Darmstadt
Gowri R Chandran, Technical University of Darmstadt
Phillipp Schoppmann, Google (United States)
Thomas Schneider, Technical University of Darmstadt
Björn Scheuermann, Technical University of Darmstadt

Analyzing user data while protecting the privacy of individuals remains a big challenge. Trusted execution environments (TEEs) are a possible solution as they protect processes and Virtual Machines (VMs) against malicious hosts. However, TEEs can leak access patterns to code and to the data being processed. Furthermore, when data is stored in a TEE database, the data volume required to answer a query is another unwanted side channel that contains sensitive information. Both types of information leaks, access patterns and volume patterns, allow for database reconstruction attacks. In this paper, we present Menhir, an oblivious TEE database that hides access patterns with ORAM guarantees and volume patterns through differential privacy. The database allows range and point queries with SQL-like WHERE-clauses. It builds on the state-of-the-art oblivious AVL tree construction Oblix (S&P'18), which by itself does not protect against volume leakage. We show how volume leakage can be exploited in range queries and improve the construction to mitigate this type of attack. We prove the correctness and obliviousness of Menhir. Our evaluation shows that our approach is feasible and scales well with the number of rows and columns in the database.

Available format(s)
Publication info
Published elsewhere. ASIA CCS 2024
https: //
PrivacyTEE DatabaseOblivious Data StructuresAccess Pattern LeakageVolume Pattern Leakage
Contact author(s)
leonie reichert @ tu-darmstadt de
chandran @ encrypto cs tu-darmstadt de
schoppmann @ google com
schneider @ encrypto cs tu-darmstadt de
scheuermann @ tu-darmstadt de
2024-05-22: revised
2024-04-10: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Leonie Reichert and Gowri R Chandran and Phillipp Schoppmann and Thomas Schneider and Björn Scheuermann},
      title = {Menhir: An Oblivious Database with Protection against Access and Volume Pattern Leakage},
      howpublished = {Cryptology ePrint Archive, Paper 2024/556},
      year = {2024},
      doi = {https: //},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.