Introduction

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.

Try It

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.

<!-- ORAM demo: naive vs oblivious memory access -->
<div class="controls">
  <label class="toggle-wrap">
    <input type="checkbox" id="oramToggle">
    <span class="toggle-label">ORAM mode</span>
  </label>
  <button id="readBtn" type="button">Read a slot</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>
<div class="mode-badge" id="modeBadge">NAIVE — leaks address</div>
<div class="memory" id="memory"></div>
<div class="log-wrap">
  <div class="log-title">Access log (observer's view)</div>
  <div id="log" class="log"></div>
</div>
<div class="status" id="status"></div>

/* Styles for the ORAM demo */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ORAM demo: compare naive vs oblivious memory reads

const N = 8; // number of memory slots
// secret logical values (hidden from observer)
const SECRET = ['A1','B7','C3','D9','E2','F5','G8','H4'];

let oramMode = false;
let accessCount = 0;

// Fisher-Yates shuffle
function shuffle(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

// permutation[phys] = logical index stored at physical slot phys
let permutation = Array.from({ length: N }, (_, i) => i);

function renderSlots(highlighted) {
  // render all physical slots; only show addresses, never values
  const mem = document.getElementById('memory');
  mem.innerHTML = '';
  for (let phys = 0; phys < N; phys++) {
    const logical = permutation[phys];
    const d = document.createElement('div');
    d.className = 'slot';
    if (highlighted) {
      if (highlighted.type === 'naive' && phys === highlighted.phys) d.className += ' accessed';
      if (highlighted.type === 'oram' && phys === highlighted.real) d.className += ' target-oram';
      if (highlighted.type === 'oram' && highlighted.dummies && highlighted.dummies.includes(phys)) d.className += ' dummy';
    }
    d.innerHTML = `<span class="addr">${'S%i%'.replace('%i%', phys)}</span><span class="val">?</span>`;
    mem.appendChild(d);
  }
}

function appendLog(text, cls) {
  const log = document.getElementById('log');
  const e = document.createElement('div');
  e.className = 'entry ' + cls;
  e.textContent = text;
  log.appendChild(e);
  log.scrollTop = log.scrollHeight;
}

function setStatus(text, cls) {
  const s = document.getElementById('status');
  s.textContent = text;
  s.className = 'status ' + (cls || '');
}

function naiveRead() {
  // Naive read: directly access the target physical slot — address is visible
  const target = Math.floor(Math.random() * N);
  accessCount++;
  renderSlots({ type: 'naive', phys: target });
  const val = SECRET[permutation[target]];
  appendLog(i18nFmt('READ phys[%addr%] → value *** (address EXPOSED)', { addr: target, val: val }), 'naive');
  setStatus(i18nFmt('Read physical slot %addr% — observer sees exactly which slot was touched.', { addr: target }), '');
}

function oramRead() {
  // ORAM read: reshuffle all slots, touch all physical addresses
  const logicalTarget = Math.floor(Math.random() * N);
  // assign a new random physical location to every logical slot
  const newPerm = shuffle(Array.from({ length: N }, (_, i) => i));
  const dummyPhys = [];
  for (let phys = 0; phys < N; phys++) {
    if (newPerm[phys] !== logicalTarget) dummyPhys.push(phys);
  }
  const realPhys = newPerm.indexOf(logicalTarget);
  // touch every physical slot (dummy + real) so observer cannot distinguish
  for (let phys = 0; phys < N; phys++) {
    if (phys !== realPhys) {
      appendLog(i18nFmt('TOUCH phys[%addr%] (dummy)', { addr: phys }), 'oram-dummy');
    }
  }
  permutation = newPerm;
  accessCount++;
  renderSlots({ type: 'oram', real: realPhys, dummies: dummyPhys });
  const val = SECRET[logicalTarget];
  appendLog(i18nFmt('READ phys[%addr%] ← logical[%logical%] → value *** (hidden in uniform noise)', { addr: realPhys, logical: logicalTarget, val: val }), 'oram-access');
  setStatus(i18nFmt('Read logical slot %logical% now at phys[%addr%] — observer sees uniform noise.', { logical: logicalTarget, addr: realPhys }), 'ok');
}

document.getElementById('oramToggle').addEventListener('change', function() {
  oramMode = this.checked;
  const badge = document.getElementById('modeBadge');
  if (oramMode) { badge.textContent = 'ORAM — address hidden'; badge.className = 'mode-badge oram'; }
  else          { badge.textContent = 'NAIVE — leaks address'; badge.className = 'mode-badge'; }
  renderSlots(null);
  setStatus('');
});

document.getElementById('readBtn').addEventListener('click', function() {
  if (oramMode) oramRead(); else naiveRead();
});

document.getElementById('resetBtn').addEventListener('click', function() {
  permutation = Array.from({ length: N }, (_, i) => i);
  accessCount = 0;
  document.getElementById('log').innerHTML = '';
  renderSlots(null);
  setStatus('');
});

renderSlots(null);
Result
Console

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.

The Real Complexity

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 Ω(log⁡n)\Omega(\log n) physical memory accesses per logical access, where nn is the number of memory slots. This is an information-theoretic argument: the adversary gains log⁡n\log n bits from the address, and the scheme must inject at least that much noise to cancel it.
  • Early constructions achieved O(log⁡3n)O(\log^3 n) overhead — correct but far from optimal.
  • Path ORAM (Stefanov et al., 2013) brought the overhead down to O(log⁡2n)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)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/oblivious-ram/Content licensed under CC BY-NC 4.0.