Oblivious Network RAM

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

TL;DR

This paper introduces Oblivious Network RAM (O-NRAM), a new model of computation that achieves significantly lower overhead than standard Oblivious RAM (ORAM). By assuming that memory is partitioned into banks where internal offsets are hidden from adversaries, the authors demonstrate that high degrees of parallelism can be leveraged to achieve $O(1)$ bandwidth blowup—effectively bypassing the well-known logarithmic lower bounds of traditional ORAM.

What Problem Does This Paper Address?

Standard ORAM is a cryptographic primitive that allows a CPU to access untrusted memory without revealing its access patterns. However, it suffers from a fundamental "tax": a theoretical lower bound of $\Omega(\log N)$ bandwidth blowup (where $N$ is the memory size). As modern ORAM constructions approach this limit, researchers are looking for ways to further reduce overhead for practical applications like secure processors and distributed storage.

The authors identify a gap: traditional ORAM assumes an adversary sees the exact address of every memory request. In many realistic scenarios—such as a CPU communicating with multiple "active" memory banks (DIMMs with built-in decryption) or a client using multiple distributed storage servers—the adversary might see which bank is being accessed but not the specific offset within that bank. This paper explores how to exploit this "free obliviousness" within banks to make the overall system faster.

Methods

The authors propose the Oblivious Network RAM (O-NRAM) model, where memory is distributed across $M$ banks. The adversary observes the sequence of bank identifiers but not the internal addresses.

Key techniques include:

  • Sequential-to-Sequential Compiler: They adapt the partition-based ORAM idea. Each bank implements a deamortized Cuckoo hash table to ensure $O(1)$ worst-case access time. They use a recursive position map (similar to Path ORAM) to track where data blocks reside across banks.
  • Parallelism as an Obfuscator: A core contribution is the "Parallel-to-Sequential" compiler. If a program is "sufficiently parallel" (generating large batches of requests), the CPU can group these requests, assign them to banks pseudorandomly, and pad the accesses to each bank to a worst-case maximum. This makes the bank-access pattern independent of the actual data requested.
  • Parallel-to-Parallel Compiler: To simulate a Parallel RAM (PRAM) on a Network PRAM, they utilize sophisticated parallel algorithms:
  • Parallel Static Hashing: To suppress duplicate requests within a batch.
  • Colored Compaction: To efficiently route requests to their respective bank "buckets" in $O(\log^* P)$ time.

Datasets

Not discussed in the paper. As a theoretical work focused on algorithmic complexity and cryptographic proofs, the paper does not use empirical datasets or benchmarks. It relies on asymptotic analysis and the Chernoff bound to prove security and performance guarantees.

Key Insights and Ideas

  • "Free Obliviousness" within Banks: The most powerful insight is that if you can hide the local address, the global problem of hiding access patterns becomes much easier. This shifts the bottleneck from hiding the exact address to merely hiding the distribution of requests across banks.
  • Parallelism Facilitates Obliviousness: Usually, parallelism is seen as a way to increase speed. Here, it is used as a cryptographic tool. Because instructions in a parallel batch can be executed in any order, the system can "shuffle" and "pad" them to create a deterministic, data-independent access pattern to the memory banks.
  • The Log-Star Revolution: For general parallel programs, the authors achieve a blowup of $O(\log^* N)$—the "iterated logarithm," which is practically a constant for any imaginable value of $N$. This is a massive improvement over the $\text{poly-log } N$ overhead found in standard Oblivious PRAM (OPRAM).

Key Results

The paper provides a systematic study of the "cost of obliviousness" in the NRAM model:

  • Sequential Programs: For large memory words ($W = \Omega(\log^2 N)$), O-NRAM achieves $O(1)$ bandwidth blowup. For smaller words, it achieves $O(\log N)$ blowup, which is still an improvement over the $O(\log^2 N)$ found in many standard ORAMs.
  • Highly Parallel Programs: Programs with parallelism $P = \omega(M \log N)$ can be simulated with $O(1)$ blowup in both runtime and bandwidth.
  • General Parallel Programs: A P-parallel PRAM can be simulated on an O-NPRAM with $O(\log^* P)$ parallel runtime blowup and optimal total work.

Limitations and Future Work

  • Hardware Requirements: The model assumes "active memory" or trusted logic on memory banks/storage nodes. This requires a departure from traditional "passive" memory architectures, though the authors argue this is becoming more realistic with technologies like Intel SGX and trusted DIMMs.
  • Word Size Dependency: The $O(1)$ bandwidth result for sequential programs relies on non-uniform or large memory word sizes. For very small word sizes, the overhead remains logarithmic.
  • Adaptive Adversaries: The proofs for some parallel constructions assume the input $x$ is fixed before emulation begins (non-adaptive). Extending these results to fully adaptive adversaries in all settings remains a technical challenge.
  • Practical Implementation: While the asymptotic results are impressive, the "concrete" constants involved in deamortized Cuckoo hashing and colored compaction can be high. Future work could focus on simplifying these algorithms for real-world systems.

Summary updated

Abstract

Oblivious RAM (ORAM) is a cryptographic primitive that allows a trusted CPU to securely access untrusted memory, such that the access patterns reveal nothing about sensitive data. ORAM is known to have broad applications in secure processor design and secure multi-party computation for big data. Unfortunately, due to a logarithmic lower bound by Goldreich and Ostrovsky (Journal of the ACM, '96), ORAM is bound to incur a moderate cost in practice. In particular, with the latest developments in ORAM constructions, we are quickly approaching this limit, and the room for performance improvement is small. In this paper, we consider new models of computation in which the cost of obliviousness can be fundamentally reduced in comparison with the standard ORAM model. We propose the Oblivious Network RAM model of computation, where a CPU communicates with multiple memory banks, such that the adversary observes only which bank the CPU is communicating with, but not the address oset within each memory bank. In other words, obliviousness within each bank comes for free either because the architecture prevents a malicious party from observing the address accessed within a bank, or because another solution is used to obfuscate memory accesses within each bank and hence we only need to obfuscate communication patterns between the CPU and the memory banks. We present new constructions for obliviously simulating general or parallel programs in the Network RAM model. We describe applications of our new model in secure processor design and in distributed storage applications with a network adversary.
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