Oblivious Network RAM

Dana Dachman-Soled, Chang Liu, Charalampos Papamanthou, Elaine Shi, Uzi Vishkin

Abstract

Traditional Oblivious RAM (ORAM) constructions are constrained by a fundamental theoretical lower bound of $\Omega(\log N)$ bandwidth blowup. This paper introduces Oblivious Network RAM (O-NRAM), a novel computational model that leverages memory partitioning and parallelism to bypass these limits. By assuming that memory is distributed across multiple banks where internal offsets remain hidden from adversaries, O-NRAM achieves $O(1)$ bandwidth blowup in several key settings, effectively reducing the cryptographic "tax" on secure memory access to a near-constant overhead.

Introduction

In the realm of secure computation, Oblivious RAM (ORAM) serves as a critical primitive, allowing a processor to access untrusted memory without leaking information through its access patterns. Despite decades of optimization, standard ORAM remains bottlenecked by the Goldreich-Ostrovsky lower bound, which dictates that any ORAM must incur at least a logarithmic overhead in bandwidth relative to the memory size $N$. As modern systems move toward distributed architectures and secure enclaves (like Intel SGX), there is an urgent need for more efficient obliviousness.

This work identifies a significant opportunity in the way memory is physically organized. In many realistic scenarios—such as a CPU communicating with multiple "active" memory banks or a client utilizing distributed storage—an adversary might observe which bank is being accessed but cannot see the specific offset within that bank. The authors formalize this as the Oblivious Network RAM (O-NRAM) model, exploring how this "free obliviousness" within banks can be exploited to achieve unprecedented performance gains.

The O-NRAM Model

The O-NRAM model assumes memory is partitioned into $M$ distinct banks. The adversary is modeled as a network observer who can see the sequence of bank identifiers for every request but lacks visibility into the internal addressing of each bank. This shift in the threat model changes the core challenge: instead of hiding the exact address of every request, the system must now only hide the distribution of requests across the $M$ banks.

Algorithmic Compilers

The authors propose three primary compilers to translate standard RAM programs into the O-NRAM model:

1. Sequential-to-Sequential Compiler

This compiler adapts partition-based ORAM techniques. Each bank implements a deamortized Cuckoo hash table, ensuring that every access takes $O(1)$ time in the worst case. To manage the location of data blocks across banks, the system employs a recursive position map, similar to the structure used in Path ORAM. For large memory words ($W = \Omega(\log^2 N)$), this approach yields a constant $O(1)$ bandwidth blowup.

2. Parallel-to-Sequential Compiler

A key innovation of this work is using parallelism as a cryptographic tool rather than just a performance enhancer. If a program generates large batches of requests (parallelism $P = \omega(M \log N)$), the CPU can group these requests and assign them to banks pseudorandomly. By padding the accesses to each bank to a deterministic worst-case maximum, the bank-access pattern becomes entirely independent of the underlying data, resulting in $O(1)$ blowup.

3. Parallel-to-Parallel Compiler

To simulate a Parallel RAM (PRAM) on a Network PRAM, the authors utilize advanced parallel algorithms, including Parallel Static Hashing to suppress duplicate requests and Colored Compaction. The latter allows the system to route requests to their respective bank "buckets" in $O(\log^* P)$ time, where $\log^*$ is the iterated logarithm—a value that is practically constant for all realistic values of $P$.

Key Results and Performance

The performance of O-NRAM represents a significant leap over traditional ORAM. As shown in the table below, O-NRAM consistently outperforms the best-known ORAM constructions across various word sizes and parallelism levels.

Comparison of RAM to O-NRAM blowup against best known ORAM constructions across different computational settings.

For general parallel programs, the $O(\log^* N)$ blowup is a massive improvement over the $\text{poly-log } N$ overhead typically found in standard Oblivious PRAM (OPRAM). In the most favorable settings—highly parallel programs or those with large word sizes—the overhead is reduced to a true constant $O(1)$.

Discussion and Future Work

While O-NRAM offers a theoretical breakthrough, its practical adoption depends on the evolution of hardware. The model requires "active memory" or trusted logic at the bank level, a departure from traditional passive DIMMs. However, the rise of Trusted Execution Environments (TEEs) and smart storage controllers suggests that such architectures are becoming increasingly feasible.

Future research may focus on reducing the concrete constants associated with deamortized Cuckoo hashing and colored compaction, which remain high despite their optimal asymptotic complexity. Additionally, extending the proofs to handle fully adaptive adversaries in all parallel settings remains an open technical challenge. Nonetheless, O-NRAM provides a powerful roadmap for building the next generation of high-performance, privacy-preserving storage systems.

Summary updated

BibTeX
@article{dachmansoled2015oblivious,
  author = {Dana Dachman-Soled and Chang Liu and Charalampos Papamanthou and Elaine Shi and Uzi Vishkin},
  title = {{Oblivious Network RAM}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2015},
  url = {https://openreview.net/forum?id=HEW5Cs31OY},
}
Figure