Oblivious RAM

Preserve logical memory reads and writes while making observed physical access traces indistinguishable for equally long request sequences.

Version

v1 · 2026-10-03 · History

Domain-specific #

13478

Aliases

ORAM, Oblivious random-access memory, Oblivious memory simulation

Core Idea

An oblivious RAM (ORAM) lets a computation read and write logical memory while hiding which locations it selected from someone who watches physical storage accesses. It places a protocol between logical requests and observable memory. The protocol has to return the right data and make the physical address traces of any two equally long request sequences indistinguishable under its stated security model.[^{ref-dcfa6cc57c26][}ref-8922698bc2e3]

Encrypting stored blocks is not enough by itself: even when block contents are secret, repeatedly visiting a visible address can reveal a pattern. ORAM addresses that pattern channel. Its formal guarantee does not automatically hide request count, timing, data contents or every other side channel; the observer and compared sequences must be specified.[^ref-8922698bc2e3]

Scope of Application

In remote storage, a trusted client can use Path ORAM so an untrusted server sees tree-path accesses rather than a direct series of requested block addresses. In secure hardware, ZeroTrace uses oblivious memory primitives with Intel SGX to reduce leakage from memory access behavior outside the protected computation. Both preserve a logical block interface while mediating what the outside observer sees.[^{ref-8922698bc2e3][}ref-bb380d4e771e]

Clarity

ORAM separates logical addresses—the blocks the program wants—from physical addresses—the locations an observer sees. A correct encrypted database with visibly direct lookups is not an ORAM. A protocol that always makes the same accesses but returns wrong values is not one either. The property is the conjunction of correct memory behavior and hidden access choice.[^{ref-dcfa6cc57c26][}ref-8922698bc2e3]

Manages Complexity

Many designs can serve the same purpose. Scanning every location on every request can hide the chosen address but is costly. Path ORAM uses remapping and path transfers to reduce cost under particular storage assumptions. Evaluating a design therefore involves separate questions about trace privacy, correctness, bandwidth, client state and what the actual observer can measure.[^{ref-dcfa6cc57c26][}ref-8922698bc2e3]

Abstract Reasoning

Take two possible logical request sequences of the same length and ask whether their observable physical traces can be told apart. Then ask whether each execution returns and updates the right values. If either test fails, the claimed ORAM guarantee fails. Even if both pass, inspect whether timing or other observations lie outside the proof's stated scope.[^{ref-dcfa6cc57c26][}ref-8922698bc2e3]

Knowledge Transfer

The same ORAM relation applies to remote servers, secure processors and other memory settings when logical reads/writes, an external trace observer and the same correctness and indistinguishability tests are present. A broader idea of making observables insensitive to hidden choices can be useful elsewhere, but the name ORAM should not be exported to non-memory examples merely by analogy.[^{ref-8922698bc2e3][}ref-bb380d4e771e]

[^ref-dcfa6cc57c26]: Oded Goldreich and Rafail Ostrovsky, “Software Protection and Simulation on Oblivious RAMs”, Journal of the ACM 43, no. 3 (1996): 431–473, especially §1.2 and Definition 2.3.2.1. [^ref-8922698bc2e3]: Emil Stefanov et al., “Path ORAM: An Extremely Simple Oblivious RAM Protocol”, arXiv:1202.5150v3 (2014), especially §§1–3 and Definition 1. [^ref-bb380d4e771e]: Sajin Sasy, Sergey Gorbunov and Christopher W. Fletcher, “ZeroTrace: Oblivious Memory Primitives from Intel SGX”, NDSS (2018), abstract, §I-B and §III-C.

Neighborhood in Abstraction Space

Oblivious RAM sits in a moderately populated region (59^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Program Execution & Runtime Concepts (27 abstractions)

Nearest neighbors

• Hierarchical Storage Management — 0.86
• Cache-Only Memory Architecture — 0.86
• Buffer Overflow — 0.85
• Fragmentation (computing) — 0.85
• Rematerialization — 0.84

Computed from structural-signature embeddings · 2026-10-08