H2O2RAM: A High-Performance Hierarchical Doubly Oblivious RAM

H2O2RAM: A High-Performance Hierarchical Doubly Oblivious RAM

Speakers: Leqian Zheng

Conference: USENIX Security

YouTube: https://www.youtube.com/watch?v=cMgwXVNM9IA

Overview

In the realm of modern computing, particularly within cloud environments leveraging Trusted Execution Environments (TEEs), the confidentiality of data is paramount. However, traditional security measures often fall short in protecting against a subtle yet potent class of attacks: those that infer sensitive information by observing a program's access patterns. While encryption secures data at rest and in transit, the sequence and location of memory accesses during computation can still leak critical insights, such as inferring a secret value by observing which accounts are accessed in a transaction. This talk introduces Oblivious RAM (ORAM) as a fundamental primitive designed to mitigate such leakage, ensuring that memory access patterns provide no meaningful information beyond the total length of the input data.

The presentation by Leqian Zheng (who also introduced himself as Lucian Jen during the talk) at USENIX Security focuses on addressing the notorious performance overheads associated with existing ORAM designs, especially when integrated with TEEs. While TEEs offer attractive features like confidentiality, integrity, and isolation, most do not inherently obscure access patterns. ORAM is thus crucial for comprehensive privacy in these settings. The core challenge lies in the significant performance penalty ORAM imposes, transforming operations that typically take nanoseconds into milliseconds or even hours. H2O2RAM, a High-Performance Hierarchical Doubly Oblivious RAM, is presented as a solution that drastically improves ORAM efficiency by leveraging hierarchical data structures, optimizing oblivious hash schemes, and exploiting data locality and parallelization opportunities inherent in its design.

The significance of H2O2RAM lies in its ability to make ORAM practical for real-world confidential computing applications. By achieving substantial speedups—up to 1,000 times faster than prior state-of-the-art designs—H2O2RAM removes a major barrier to widespread adoption of access-pattern-oblivious computation. This work not only contributes advanced theoretical insights into ORAM construction but also provides concrete, implementable optimizations that enable robust privacy guarantees without crippling performance, thereby enhancing the security posture of sensitive applications running in untrusted cloud environments.

Background

▶ Watch: Introduction to ORAM and access pattern leakage (0:00)

The problem of access pattern leakage stems from the observation that even if data is encrypted, the timing, frequency, and sequence of memory requests can reveal information about the underlying secret data. For example, in a database query, observing which records are accessed might reveal sensitive attributes about the query itself, even if the records' content remains encrypted. This side channel is particularly insidious in confidential computing paradigms, where applications execute within Trusted Execution Environments (TEEs) like Intel SGX or AMD SEV. While TEEs provide strong guarantees for code and data integrity and confidentiality within the enclave, they typically do not obscure the memory access patterns observed by the untrusted host operating system or hypervisor.

Oblivious RAM (ORAM) was conceived to address this fundamental vulnerability. An ORAM scheme transforms a sequence of logical memory accesses into a seemingly random sequence of physical memory accesses, ensuring that an adversary observing the physical accesses cannot infer any information about the logical access pattern. Early ORAM designs typically followed either a tree-based or hierarchical approach. Tree-based ORAMs often scatter data across memory nodes and buckets, leading to poor data locality. Hierarchical ORAMs, in contrast, tend to store data blocks in more contiguous memory regions across different levels, which intuitively suggests better performance due to improved cache utilization.

Despite decades of research, ORAM's practical deployment has been severely hampered by its substantial performance overheads. The speaker highlights this stark reality: a final operation on a standard memory system that takes nanoseconds might require tens of milliseconds when performed obliviously with ORAM. Similarly, a sub-second shortest path algorithm could balloon into several hours of execution time with existing ORAM implementations. This drastic slowdown makes many ORAM-protected applications computationally infeasible for real-world use. The primary reasons for these overheads include:

1. High Computational Complexity: Many ORAM operations, especially for ensuring obliviousness, involve complex cryptographic primitives or extensive data shuffling.
2. Poor Data Locality: Tree-based ORAMs, in particular, often involve accessing data scattered across memory, leading to frequent cache misses and increased memory latency.
3. Limited Parallelization: Recursive operations, common in many ORAM constructions, make effective parallelization challenging, limiting the ability to leverage modern multi-core processors.
4. Rebuild Costs: To maintain obliviousness and prevent adversaries from building a history of access patterns, ORAMs periodically "rebuild" their internal state, which is a time-dominant and computationally expensive process.

The motivation behind H2O2RAM is to overcome these persistent performance barriers, making ORAM a viable technology for protecting access patterns in confidential computing. The key insight driving H2O2RAM is that if a hierarchical ORAM can achieve comparable asymptotic capacity to tree-based designs, it should inherently perform better in practice due to superior data locality and greater potential for parallelization in its rebuild process. While tree-based ORAMs require recursive, hard-to-parallelize operations, hierarchical ORAM's rebuilds often consist of several rounds of oblivious sorts that are more amenable to parallel execution. This foundational belief underpins the design of H2O2RAM, which aims to optimize the core components of hierarchical ORAMs: the underlying oblivious hash tables.

Key Findings

▶ Watch: H2O2RAM's key insight: Hierarchical ORAM benefits (3:00)

The central finding of this research is that a hierarchical ORAM (HRAM) architecture, when meticulously optimized, can achieve significantly higher performance than existing tree-based ORAM designs, especially in the context of confidential computing. The H2O2RAM design capitalizes on several key insights and contributions:

1. Superior Data Locality in Hierarchical Designs: The authors observe that hierarchical ORAMs naturally store data blocks in more contiguous memory regions across their levels, unlike tree-based ORAMs where data is scattered. This inherent data locality translates directly to better cache performance and reduced memory access latency.
2. Enhanced Parallelization for Rebuilds: The time-dominant rebuild process in hierarchical ORAMs primarily consists of several rounds of oblivious sorts. These operations are far easier to parallelize compared to the recursive operations typical of tree-based ORAMs, leading to substantial speedups.
3. Novel Optimized Oblivious Hash Schemes: The core technical challenge in HRAMs is optimizing the performance of their underlying hash tables. H2O2RAM introduces three novel and fully optimized oblivious hash schemes, each designed to offer different advantages across varying input sizes and operational requirements:

• Oblivious Bucket Hash (OBH): Optimized for distributing data blocks into buckets with uniform capacity, ensuring obliviousness through padding and full bucket scans. A key finding is the necessity of numerical search to determine the optimal number of buckets (N) for peak performance, as a general setting (N=M) is suboptimal.
• Oblivious Cuckoo Hash (OCH): Addresses the limitations of traditional cuckoo hashing with large "stashes" for overflow. The research leverages theoretical results to show that reducing the number of candidate entries (K) to at most six significantly decreases the overhead of stash lookups (from hundreds/thousands to just six comparisons).
• Hybrid Hash Scheme (HHS): Designed for scenarios where inputs can be randomly shuffled. It combines non-oblivious distribution to main hash tables with oblivious routing of a small, secret portion to a secondary hash table, further optimizing for performance.

1. Novel Oblivious Pattern Matching Algorithm: As a core building block for oblivious cuckoo hash construction, H2O2RAM introduces a new oblivious pattern matching algorithm that is empirically shown to be constant times faster than previous approaches. This algorithm is also noted to be of independent interest for other oblivious computation tasks.
2. Adaptive Hash Scheme Selection: The research highlights that no single hash scheme is universally optimal. Different schemes excel within specific ranges of input sizes (e.g., linear scan for <1,000 blocks, bucket hash for middle levels). H2O2RAM employs a dynamic, context-aware selection of appropriate hash tables, which, while not changing the asymptotic complexity, significantly improves practical performance.
3. Asymptotic Efficiency and Practical Speedup: The design achieves an asymptotic complexity of O(log² N), which is on par with state-of-the-art tree-based ORAMs. Crucially, in practical benchmarks, H2O2RAM demonstrates an astounding 1,000x speedup compared to previous state-of-the-art ORAM designs like GraphORAM and Anamnesiac ORAM. This validates the premise that optimized hierarchical designs can indeed outperform their tree-based counterparts in practice.

These findings collectively demonstrate that high-performance, access-pattern-oblivious memory is achievable, thereby making ORAM a more practical and deployable solution for securing sensitive computations in untrusted environments.

Technical Deep Dive

▶ Watch: H2O2RAM design: Optimizing host tables with hash schemes (4:00)

H2O2RAM's high performance stems from its hierarchical design and the meticulous optimization of its core components: oblivious hash tables. The system is built around multiple levels of these hash tables, each chosen and configured for optimal performance under specific conditions. The overall asymptotic complexity of H2O2RAM is O(log² N), matching the best known theoretical bounds for ORAMs, but its practical performance gains are derived from constant factor optimizations.

The talk details three primary optimized oblivious hash schemes that serve as the building blocks for H2O2RAM:

1. Oblivious Bucket Hash (OBH)

• Mechanism: In this scheme, a pseudo-random function (PRF) is used to distribute each data block into one of N buckets. Each bucket is designed to have a uniform capacity. To ensure obliviousness, each bucket is padded with dummy elements to reach its full capacity, regardless of the actual number of real data items it contains. This padding ensures that an observer cannot distinguish between a real data item and a dummy one, nor can they infer the true occupancy of a bucket.
• Obliviousness: During a lookup operation, the entire target bucket must be scanned linearly. This hides the actual location of the accessed item within the bucket and the total number of real items present.
• Optimization Challenge: A fundamental trade-off exists between the number of buckets (N) and the cost per lookup. Increasing N reduces the capacity of individual buckets, thereby lowering the linear scan cost per lookup. However, a larger N also leads to a larger overall hash table size, which in turn increases the cost of the periodic rebuild process.
• Solution: The authors developed a numerical analysis approach, specifically a ternary search, to determine the optimal N that minimizes the overall complexity. This deviates from a commonly adopted setting where N is simply equal to M (the total number of data blocks), which the experiments showed to be suboptimal. This precise tuning of N is critical for achieving peak performance. The bucket capacity must be set to a lower bound that guarantees a negligible probability of overflow, ensuring all data blocks can be safely distributed.

1. Oblivious Cuckoo Hash (OCH)

• Mechanism: Standard cuckoo hashing assigns each data block to one of K candidate table entries (typically K=2). If both candidate locations are occupied, the block is "kicked" to one of its alternative locations, potentially triggering a chain reaction. In previous hierarchical ORAM designs, data blocks that could not be placed after a certain number of kicks were shunted into a separate stash of size O(log N).
• Problem with Stashes: While theoretically O(log N), the concrete values for stash sizes in prior work could be hundreds or even thousands of entries. Crucially, to maintain obliviousness, each lookup operation in these schemes required scanning the entire stash in addition to the K candidate entries. This linear scan of a potentially large stash introduced significant performance overhead.
• Optimization: The H2O2RAM design seeks to eliminate or drastically reduce the need for this cumbersome stash while retaining a negligible overflow probability. Leveraging theoretical results from a work by Kevin Y in Crypto '23, the authors' numerical analysis demonstrates that setting K to at most six candidate entries is sufficient. This reduction from potentially thousands of stash comparisons to a maximum of six (oblivious) comparisons represents a massive performance improvement.
• Novel Building Block: A key contribution here is the development of a novel oblivious by pattern matching algorithm. This algorithm serves as the core building block for the OCH construction and is stated to be constant times faster than previous approaches. It is also highlighted as being of independent interest for other oblivious computation tasks. The previous cuckoo hash construction was typically specified for "stash cuckoo hash," which was not suitable for a "stashless" or significantly reduced-stash cuckoo hash table.

1. Hybrid Hash Scheme (HHS)

• Mechanism: This scheme is designed for situations where the input data can be assumed to be randomly shuffled (which can be achieved in O(N) time using previous work). Under this assumption, data blocks can be initially distributed or assigned to buckets in a non-oblivious way to a set of main hash tables, similar to standard plaintext hashing. To maintain overall obliviousness for the entire system, only a small, secret portion of each large main hash bucket is then obliviously routed to a secondary, smaller hash table.
• Optimization Targets: Three main parameters are optimized in this scheme:
• Number of Main Hash Tables: Similar to the bucket hash, the optimal number of main hash tables needs careful tuning.
• Sampling Parameters: Determining how many data blocks from each main hash bucket should be obliviously and securely routed to the secondary hash table. This is improved through numerical analysis.
• Underlying Hash Schemes: For both the main and secondary hash tables, which can be quite large, linear scanning is prohibitive. Therefore, the authors recursively adopt other optimized oblivious hash schemes (like OBH or OCH) for these components, effectively creating a multi-layered oblivious hash structure.

Adaptive Scheme Selection: A critical meta-observation made by the researchers is that "no single hash scheme is universally optimal." Each scheme exhibits superior performance within a specific range of input sizes. For instance, a simple linear scan method, despite its high asymptotic lookup cost, performs exceptionally well for small inputs (e.g., no more than 1,000 data blocks in their experiments). The bucket hash table, on the other hand, is suited for middle-level operations in their hierarchical design. This insight leads to an adaptive strategy where H2O2RAM dynamically selects the most appropriate oblivious hash scheme based on the current input size and operational context. This intelligent selection, while not altering the asymptotic complexity, contributes substantially to the observed practical performance improvements.

By carefully integrating these optimized hash schemes within a hierarchical framework and employing adaptive selection, H2O2RAM achieves its remarkable performance, making ORAM a practical reality for demanding confidential computing applications.

Demo / Proof of Concept

▶ Watch: Hybrid approach: Selecting optimal hash schemes based on input (10:00)

While the talk does not describe a live demonstration of H2O2RAM in action, it presents a thorough experimental evaluation and benchmark analysis validating its performance claims. The speaker emphasizes that these experiments rigorously quantify the benefits of the proposed optimizations and the overall H2O2RAM architecture.

The key aspects of the experimental evaluation include:

1. Optimal Parameter Validation: The necessity of tuning parameters, such as the number of buckets (N) in the oblivious bucket hash table, was empirically validated. The experiments showed that the optimal N, determined through numerical analysis, yielded an overall running time several times faster than a generally adopted, non-optimized setting (e.g., N=M). This directly validates the theoretical insights regarding the trade-offs in hash table design.
2. Scalability with Input and Block Sizes: H2O2RAM's performance was evaluated across different input data sizes and data block sizes. The observed growth trends in performance were found to be aggressive, consistent with the O(log² N) asymptotic analysis, confirming the theoretical efficiency of the design.
3. Comparative Benchmarks: The most compelling result from the benchmark evaluations is that H2O2RAM achieved approximately a 1,000x speedup compared to prior state-of-the-art ORAM designs.

• For GraphORAM, the results were directly taken from their published paper.
• For Anamnesiac ORAM (Anamnesiac), the authors undertook a complete reimplementation. This reimplementation itself integrated new algorithmic optimizations and was hosted in a brand new GitHub repository, outperforming the legacy implementation from the original Anamnesiac paper. The fact that H2O2RAM still significantly outperformed this optimized baseline underscores its efficiency.

The presentation provides a link to their open-source repositories and a paper for more detailed evaluations, indicating that the work is publicly available for scrutiny and further development. These comprehensive benchmarks serve as the practical proof of concept, demonstrating H2O2RAM's ability to deliver high-performance oblivious memory access in real-world scenarios.

Defensive Implications

▶ Watch: H2O2RAM's O(log^2 N) asymptotic complexity and performance (11:00)

H2O2RAM significantly strengthens the defensive posture of applications operating in confidential computing environments by making Oblivious RAM (ORAM) a truly practical and deployable technology. Prior to H2O2RAM, the prohibitive performance overheads of ORAM meant that many applications either had to forgo access pattern privacy entirely or accept crippling performance degradation. This presented a significant dilemma for defenders: compromise on a crucial privacy guarantee or render the application unusable.

With H2O2RAM's 1,000x speedup, defenders can now realistically integrate ORAM into their systems without the crippling performance penalties that plagued previous designs. This has several profound implications:

1. Enhanced Privacy in TEEs: It enables a more complete privacy story for applications running in Trusted Execution Environments (TEEs) like Intel SGX or AMD SEV. While TEEs protect the confidentiality and integrity of data inside the enclave, they do not inherently hide memory access patterns from the untrusted host. H2O2RAM provides the missing piece, allowing TEE-protected applications to achieve end-to-end data privacy, including the crucial aspect of access pattern obliviousness, against powerful adversaries (e.g., cloud providers, hypervisors) who can observe memory bus traffic.
2. Broader Applicability of ORAM: The dramatically improved performance opens the door for ORAM to be applied to a much wider range of real-world applications that were previously considered too performance-sensitive. This includes secure databases, privacy-preserving machine learning, encrypted search, and other data-intensive computations where access patterns could leak sensitive information.
3. Reduced Risk of Side-Channel Attacks: By obscuring access patterns, H2O2RAM effectively neutralizes a potent class of side-channel attacks that exploit memory access behavior. This mitigates risks associated with inferring sensitive data (e.g., secret keys, search queries, financial transactions) from observable memory operations.
4. Practical Deployment in Cloud: For organizations deploying sensitive workloads in public cloud environments, H2O2RAM offers a robust mechanism to enhance trust and compliance. It allows them to leverage the scalability and cost-effectiveness of cloud infrastructure while maintaining strong privacy guarantees against potential adversaries, including the cloud provider itself.
5. Foundation for Future Research: H2O2RAM's optimizations and novel algorithmic components, such as the oblivious pattern matching algorithm, provide a strong foundation for future research and development in secure computation. It demonstrates that significant practical gains in ORAM performance are still achievable, encouraging further innovation in this critical area.

In essence, H2O2RAM empowers defenders to implement a more comprehensive and practical approach to data privacy, moving beyond mere data encryption to truly conceal the very act of accessing information.

Key Takeaways

• Access Pattern Leakage is a Critical Threat: Even in confidential computing environments with TEEs, observing memory access patterns can infer sensitive information, necessitating Oblivious RAM (ORAM).
• Hierarchical ORAMs Offer Performance Advantages: H2O2RAM leverages the inherent data locality and parallelization potential of hierarchical ORAM designs over traditional tree-based methods.
• Optimized Oblivious Hash Schemes are Key: The core of H2O2RAM's performance lies in three meticulously optimized hash schemes: Oblivious Bucket Hash, Oblivious Cuckoo Hash, and a Hybrid Hash Scheme, each tailored for different scenarios.
• Parameter Tuning is Essential: Numerical analysis, like ternary search, is crucial for finding optimal parameters (e.g., number of buckets) for oblivious hash tables, leading to significant performance gains.
• Novel Algorithms Improve Efficiency: H2O2RAM introduces a new, constant-factor faster oblivious pattern matching algorithm, which is a key building block for its Cuckoo Hash and potentially useful independently.
• Achieves 1,000x Speedup: H2O2RAM achieves an impressive 1,000-fold speedup compared to prior state-of-the-art ORAM implementations, making oblivious computation practical for real-world applications with an O(log² N) asymptotic complexity.

About the Speaker(s)

Leqian Zheng is the speaker for this presentation. During his introduction, he also referred to himself as Lucian Jen and stated that the work on high-performance Oblivious RAM is a collaborative effort. The details shared within the transcript indicate that his research focuses on advancing the practicality of secure computation techniques, particularly in the domain of confidential computing and Trusted Execution Environments, by addressing fundamental performance bottlenecks in cryptographic primitives like Oblivious RAM. His work involves both theoretical analysis and practical optimization of complex data structures and algorithms.