H₂O₂RAM: A High-Performance Hierarchical Doubly Oblivious RAM

The combination of Oblivious RAM (ORAM) with Trusted Execution Environments (TEE) has found numerous real-world applications due to their complementary nature. TEEs alleviate the performance bottlenecks of ORAM, such as network bandwidth and roundtrip latency, and ORAM provides general-purpose protection for TEE applications against attacks exploiting memory access patterns. The defining property of this combination, which sets it apart from traditional ORAM designs, is its ability to ensure that memory accesses, both inside and outside of TEEs, are made oblivious, thus termed doubly oblivious RAM (O₂RAM). Efforts to develop O₂RAM with enhanced performance are ongoing.
In this work, we propose H₂O₂RAM, a high-performance doubly oblivious RAM construction. The distinguishing feature of our approach, compared with the existing tree-based doubly oblivious designs, is its first adoption of the hierarchical framework that enjoys inherently better data locality and parallelization. While the latest hierarchical solution, FutORAMa, achieves concrete efficiency in the classic client-server model by leveraging a relaxed assumption of sublinear-sized client-side private memory, adapting it to our scenario poses challenges due to the conflict between this relaxed assumption and our doubly oblivious requirement. To this end, we introduce several new efficient oblivious components to build a high-performance hierarchical O₂RAM (H₂O₂RAM). We implement our design and evaluate it on various scenarios. The results indicate that H₂O₂RAM reduces execution time by up to ∼ 10³ times and saves memory usage by a factor of 5 ∼ 44 compared with state-of-the-art solutions.

© 2025 by The USENIX Association All Rights Reserved.