Oblivious RAM

Suppose you store your files on an untrusted server — encrypted, so the server cannot read them. You feel safe. But every time you open a file, the server watches which encrypted block you fetch. Over time that sequence of addresses reveals your reading habits, your recent edits, even your medical history, without ever breaking the encryption itself.

This is access-pattern leakage, and it is a real attack. Researchers have shown that the sequence of memory addresses a program visits can expose the secret inputs it is processing — even when every byte stored in memory is perfectly encrypted.

Oblivious RAM (ORAM) is the solution proposed by Oded Goldreich and Rafail Ostrovsky in 1996: a layer that sits between a program and its memory and scrambles the sequence of addresses accessed, so that an observer — the server, a hardware spy, or a side-channel adversary — sees only a random-looking stream of accesses, learning nothing about which logical slot was touched or why.

The price is overhead: every real access must be disguised among fake ones. How much overhead is necessary — and sufficient — is a rich open question in cryptography.

The demo below shows a small memory bank of eight slots. Each slot holds a secret value (hidden from view). Click Read a slot to fetch one — in Naive mode the accessed slot lights up, revealing exactly which address was touched. Switch to ORAM mode and every read reshuffles all slots through dummy accesses first, so an observer watching the address bus sees the same uniform pattern regardless of which slot you actually wanted.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label class="toggle-wrap">
    <input type="checkbox" id="oramToggle">
    <span class="toggle-label">{{label_oram_mode}}</span>
  </label>
  <button id="readBtn" type="button">{{btn_read}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="mode-badge" id="modeBadge">{{badge_naive}}</div>
<div class="memory" id="memory"></div>
<div class="log-wrap">
  <div class="log-title">{{label_access_log}}</div>
  <div id="log" class="log"></div>
</div>
<div class="status" id="status"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .5rem; }
.toggle-wrap { display: flex; align-items: center; gap: .4rem; cursor: pointer; font-size: .9rem; }
.toggle-label { font-weight: 600; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.mode-badge { display: inline-block; padding: .2rem .65rem; border-radius: 20px;
              font-size: .8rem; font-weight: 700; margin-bottom: .5rem;
              background: #fde8e8; color: #c0392b; }
.mode-badge.oram { background: #e2f4e8; color: #1a7a3c; }
.memory { display: flex; gap: 6px; flex-wrap: wrap; margin-bottom: .6rem; }
.slot { width: 54px; height: 54px; display: flex; flex-direction: column;
        align-items: center; justify-content: center; border-radius: 8px;
        border: 2px solid #cdd9e3; background: #e8eef3;
        font: 700 12px ui-monospace, monospace; transition: all .25s; user-select: none; }
.slot .addr { font-size: 10px; color: #6c7a8a; font-weight: 400; margin-bottom: 2px; }
.slot .val  { font-size: 15px; color: #1d3557; }
.slot.accessed { background: #e63946; border-color: #c92f3c; }
.slot.accessed .addr, .slot.accessed .val { color: #fff; }
.slot.dummy { background: #f5c542; border-color: #d4a017; }
.slot.dummy .addr, .slot.dummy .val { color: #5a4000; }
.slot.target-oram { background: #2a9d5c; border-color: #1e7344; }
.slot.target-oram .addr, .slot.target-oram .val { color: #fff; }
.log-wrap { margin-top: .4rem; }
.log-title { font-size: .78rem; font-weight: 700; color: #6c7a8a; margin-bottom: 3px; }
.log { font: 12px ui-monospace, monospace; background: #f4f6f8; border-radius: 6px;
       padding: .4rem .6rem; min-height: 60px; max-height: 100px; overflow-y: auto;
       border: 1px solid #cdd9e3; }
.log .entry { margin: 1px 0; }
.log .entry.naive  { color: #c0392b; }
.log .entry.oram-access  { color: #1a7a3c; }
.log .entry.oram-dummy { color: #b08000; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.2em; margin-top: .3rem; }
.status.ok { color: #0a7d33; }

// Code not found

Notice that in ORAM mode the number of physical memory touches per logical read grows — that overhead is the cost of obliviousness. Reducing that overhead while keeping the access pattern truly random is the central research challenge.

Hiding which memory slot you touch is not free. How expensive must it be?

• Lower bound (Goldreich & Ostrovsky, 1996): any ORAM scheme that perfectly hides the access pattern must perform at least $\Omega(\log n)$ physical memory accesses per logical access, where $n$ is the number of memory slots. This is an information-theoretic argument: the adversary gains $\log n$ bits from the address, and the scheme must inject at least that much noise to cancel it.
• Early constructions achieved $O(\log^3 n)$ overhead — correct but far from optimal.
• Path ORAM (Stefanov et al., 2013) brought the overhead down to $O(\log^2 n)$ with a beautifully simple tree-based shuffle, and its practical constants are small enough for real cloud-storage systems.
• Optimal constructions achieve $O(\log n)$ overhead, matching the lower bound. The gap between theory and practice — implementation complexity, constant factors, server round-trips — remains an active area.
• Recursive ORAM addresses position maps (the metadata that tells you where a block lives) using another, smaller ORAM, compressing the overhead multiplicative term further.

The key insight is that ORAM overhead is unavoidable by any algorithm, not a limitation of current techniques. This connects ORAM to the broader study of oblivious computation and information-theoretic lower bounds, and to the hardness assumptions underlying cryptography.

Access-pattern leakage is a real attack in several practical settings:

• Encrypted cloud storage: a cloud provider that cannot read your files can still watch which blocks you touch. ORAM-backed storage (e.g., Obladi, ObliviStore) prevents that inference.
• Secure hardware enclaves: Intel SGX and similar trusted-execution environments protect computation from the OS, but the OS still observes page-fault addresses. Oblivious algorithms and ORAM eliminate that side channel.
• Private database queries: a database server can learn which rows a query touches even if the query is encrypted. Oblivious RAM-based databases return results without revealing the filter condition.
• Oblivious machine learning: training or running inference on a model hosted by a third party leaks which training examples are accessed. ORAM and related oblivious data structures protect the training set.
• Genomics and medical data: access patterns to a genomic database reveal which variants a clinician is testing. ORAM has been proposed as a privacy layer for sensitive health queries.

In all these cases the adversary is not breaking encryption — it is reading the metadata of which addresses appear on the bus. ORAM is the principled defense.

Encrypting data is necessary but not sufficient for privacy. The sequence of memory addresses a program visits is itself a channel — one that leaks secrets even when every stored byte is locked behind perfect cryptography.

Oblivious RAM closes that channel. The price is logarithmic overhead, a cost that Goldreich and Ostrovsky proved is unavoidable, and that modern constructions like Path ORAM have brought close to the theoretical minimum.

The next time you trust a cloud service with encrypted files, ask not just whether the encryption is strong — ask whether the server can see the rhythm of your reads. That rhythm, too, is a secret worth protecting.