Introduction

Imagine a medical database that lists every known genetic risk factor. You want to look up one variant — the one that matches your own DNA. But if you send your query to the server, the server now knows which variant you are worried about. That is a serious privacy leak, even if the database itself is fully public.

Private Information Retrieval (PIR) solves exactly this: you want to download record i from a database of n records, and the server must learn nothing — not even a probability distribution over which record you cared about.

The trivial solution is obvious: download the entire database, then pick record i locally. That guarantees perfect privacy but costs you n bits of bandwidth no matter how large the database is. The deep question is: can you do better?

The surprising answer, proved by Chor, Goldreich, Kushilevitz, and Sudan in 1995, is yes — but only if you use more than one non-colluding server, or if you accept a computational assumption (the server can't break a hard cryptographic problem). Single-server PIR with information-theoretic privacy requires downloading everything; multi-server or computationally-secure PIR can do exponentially better.

This is one of the cleanest examples of how cryptography redraws the boundary between what is and isn't possible — not by computing faster, but by being cleverer about what information leaks.

Try the XOR Trick

The demo below shows the classic 2-server XOR-based PIR scheme from Chor et al. (1995). A database of 8 bits is split across two servers. You pick which bit you want; the protocol constructs two random-looking queries so that each server individually sees a uniformly random subset of positions — learning nothing about your target.

<p class="hint">A public database of 8 bits (D[0]…D[7]). Pick which bit you want to retrieve <b>privately</b>. The XOR-PIR scheme sends two random-looking queries — neither server learns your target index. Only combining their XOR responses reveals your bit.</p>
<div class="db-row" id="db-display"></div>
<div class="picker">
  <label>Target index <b id="idx-label">0</b>:</label>
  <input type="range" id="idx-slider" min="0" max="7" value="0">
</div>
<div class="protocol-grid" id="protocol-grid">
  <div class="proto-col">
    <div class="proto-title">Server A query</div>
    <div id="qa-bits" class="bit-row"></div>
    <div class="proto-sub">random subset S</div>
  </div>
  <div class="proto-col">
    <div class="proto-title">Server B query</div>
    <div id="qb-bits" class="bit-row"></div>
    <div class="proto-sub">S ⊕ {target}</div>
  </div>
</div>
<div class="responses" id="responses">
  <div class="resp-box">Server A replies: <b id="ra">–</b></div>
  <div class="resp-box">Server B replies: <b id="rb">–</b></div>
</div>
<div class="result-row">
  <button id="btn-query" type="button">Send Private Query</button>
  <div id="result" class="result-msg"></div>
</div>
<div class="privacy-note" id="privacy-note"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.db-row { display: flex; gap: 5px; margin-bottom: .7rem; }
.db-bit { width: 36px; height: 36px; display: flex; align-items: center; justify-content: center;
          font: 700 15px ui-monospace, monospace; border-radius: 6px;
          background: #dce8f4; border: 1px solid #aac4de; color: #1d3557; }
.db-bit.target { background: #1d3557; color: #fff; border-color: #1d3557; }
.db-label { font-size: .7rem; color: #888; text-align: center; margin-top: 2px; }
.picker { display: flex; align-items: center; gap: .7rem; margin-bottom: .8rem; }
.picker label { font-size: .9rem; }
#idx-slider { width: 160px; }
.protocol-grid { display: flex; gap: 16px; margin-bottom: .7rem; }
.proto-col { flex: 1; background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 8px; padding: .5rem .6rem; }
.proto-title { font-size: .8rem; font-weight: 700; color: #1d3557; margin-bottom: .4rem; }
.proto-sub { font-size: .72rem; color: #777; margin-top: .3rem; }
.bit-row { display: flex; flex-wrap: wrap; gap: 4px; }
.q-bit { width: 28px; height: 28px; display: flex; align-items: center; justify-content: center;
         font: 700 12px ui-monospace, monospace; border-radius: 5px;
         background: #c9d8e8; border: 1px solid #aab8c8; color: #1d3557; }
.q-bit.hi { background: #e63946; border-color: #c92f3c; color: #fff; }
.q-bit.target-hi { background: #2a9d8f; border-color: #1f7a6e; color: #fff; }
.responses { display: flex; gap: 10px; margin-bottom: .7rem; }
.resp-box { flex: 1; background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 8px;
            padding: .45rem .6rem; font-size: .88rem; text-align: center; }
.resp-box b { color: #1d3557; }
.result-row { display: flex; align-items: center; gap: 1rem; margin-bottom: .6rem; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
.result-msg { font-size: 1rem; font-weight: 700; }
.result-msg.ok { color: #0a7d33; }
.privacy-note { font-size: .8rem; color: #555; background: #f9fafb;
                border: 1px solid #dde3ea; border-radius: 6px; padding: .4rem .6rem; line-height: 1.5; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// 2-server XOR-based Private Information Retrieval (Chor et al. 1995).
// Database: n=8 bits.  Client wants D[i].
// Protocol:
//   1. Client picks a random subset S ⊆ {0..n-1}.
//   2. Query to server A = S.
//   3. Query to server B = S △ {i}  (symmetric difference, i.e. XOR the i-th bit).
//   4. Server A replies XOR of D[j] for j in S.
//   5. Server B replies XOR of D[j] for j in (S △ {i}).
//   6. Client computes rA ⊕ rB = D[i].  (The XORs cancel everywhere except position i.)
// Privacy: each server sees a uniformly random subset (S and S△{i} are both uniform if S is uniform), so neither server learns i.
const N = 8;
// Fixed public database — all values visible to the user.
const DB = [1, 0, 1, 1, 0, 0, 1, 0];

function renderDB(target) {
  const row = document.getElementById('db-display');
  row.innerHTML = '';
  DB.forEach((bit, idx) => {
    const wrap = document.createElement('div');
    wrap.style.textAlign = 'center';
    const cell = document.createElement('div');
    cell.className = 'db-bit' + (idx === target ? ' target' : '');
    cell.textContent = bit;
    const lbl = document.createElement('div');
    lbl.className = 'db-label';
    lbl.textContent = '[' + idx + ']';
    wrap.appendChild(cell);
    wrap.appendChild(lbl);
    row.appendChild(wrap);
  });
}

function renderQueryBits(containerId, setS, targetIdx, isB) {
  const row = document.getElementById(containerId);
  row.innerHTML = '';
  for (let j = 0; j < N; j++) {
    const inS = setS.has(j);
    const cell = document.createElement('div');
    // For server B, highlight the flipped target bit distinctly
    if (isB && j === targetIdx) {
      cell.className = 'q-bit target-hi';
    } else if (inS) {
      cell.className = 'q-bit hi';
    } else {
      cell.className = 'q-bit';
    }
    cell.textContent = inS ? '1' : '0';
    row.appendChild(cell);
  }
}

function xorSubset(subset) {
  let acc = 0;
  subset.forEach(j => { acc ^= DB[j]; });
  return acc;
}

function runQuery() {
  const i = parseInt(document.getElementById('idx-slider').value, 10);

  // Step 1: random subset S
  const S = new Set();
  for (let j = 0; j < N; j++) {
    if (Math.random() < 0.5) S.add(j);
  }

  // Step 2+3: queries
  const SB = new Set(S);
  if (SB.has(i)) SB.delete(i); else SB.add(i);

  renderQueryBits('qa-bits', S, i, false);
  renderQueryBits('qb-bits', SB, i, true);

  // Step 4+5: server responses
  const rA = xorSubset(S);
  const rB = xorSubset(SB);
  document.getElementById('ra').textContent = rA;
  document.getElementById('rb').textContent = rB;

  // Step 6: recover
  const recovered = rA ^ rB;
  const correct = DB[i];
  const match = recovered === correct;

  const resultEl = document.getElementById('result');
  resultEl.textContent = 'rA ⊕ rB = ' + rA + ' ⊕ ' + rB + ' = ' + recovered + (match ? ' ✓' : ' ✗');
  resultEl.className = 'result-msg ' + (match ? 'ok' : 'bad');

  // Explain privacy
  const sSize = S.size;
  const sbSize = SB.size;
  document.getElementById('privacy-note').textContent =
    fmt('Server A received a subset of size %sSize%; server B received a subset of size %sbSize%. Without colluding, neither can distinguish which index you wanted from any other. The expected query size per server is n/2 = 4 indices.', { sSize: sSize, sbSize: sbSize });

  console.log(fmt('PIR run: target=%i% DB[i]=%correct% S=%v% SB=%v2% rA=%rA% rB=%rB% recovered=%recovered% match=%match%', { i: i, correct: correct, v: [...S].join(','), v2: [...SB].join(','), rA: rA, rB: rB, recovered: recovered, match: match }));
}

const slider = document.getElementById('idx-slider');
slider.addEventListener('input', () => {
  document.getElementById('idx-label').textContent = slider.value;
  renderDB(parseInt(slider.value, 10));
  document.getElementById('qa-bits').innerHTML = '';
  document.getElementById('qb-bits').innerHTML = '';
  document.getElementById('ra').textContent = '–';
  document.getElementById('rb').textContent = '–';
  document.getElementById('result').textContent = '';
  document.getElementById('privacy-note').textContent = '';
});

document.getElementById('btn-query').addEventListener('click', runQuery);

// Initial render
renderDB(0);
Result
Console

Notice what each server receives: a random subset of indices. Neither server can tell which bit you care about. Only by combining both responses with XOR do you recover your bit. This is information-theoretic privacy — it holds even against a computationally unbounded server — and the query cost is just n/2 bits per server instead of the naive n bits.

The catch is the two-server assumption: if the two servers collude and compare notes, the privacy evaporates. Avoiding that limitation requires heavier cryptography (lattice-based or homomorphic schemes) but then you can achieve privacy with a single server.

The Real Complexity

PIR sits at a rare intersection of information theory and cryptography.

  • Information-theoretic lower bound. Chor et al. (1995) proved that a single server cannot answer a PIR query with fewer than n bits of communication while preserving perfect privacy. The intuition: if one bit of the database were missing from your query, the server could answer differently for databases that differ only on that bit — leaking which bit you didn't care about, and by symmetry which one you did.
  • Multi-server schemes beat the lower bound. With two non-colluding servers the XOR trick achieves O(n)O(n) total communication; later work (Beimel et al., Woodruff–Yekhanin) pushed this to n1/kn^{1/k} for k servers, and eventually polylogarithmic total communication.
  • Computational PIR with one server. If factoring large integers is hard (or if Learning With Errors is hard — see lattice problems), a single server can answer a PIR query with polylog(n) bits. The server could theoretically break the privacy, but only if it solves a problem we believe requires exponential time.
  • Connection to other hard problems. Efficient single-server PIR implies one-way functions exist, which is one of the foundational assumptions of modern cryptography. Proving PIR impossible without one-way functions would be a major breakthrough.

The status: multi-server information-theoretic PIR is fully solved with polylogarithmic communication; single-server computational PIR is an active research area with practical constructions under lattice assumptions but still expensive for large databases.

Where It Matters

"Fetch a record without revealing which one" sounds abstract, but it maps directly onto a long list of real problems:

  • Private contact tracing: during COVID-19, researchers proposed PIR-based protocols so a user could check whether they had been near an infected person without revealing their own contact list to the health authority.
  • Private DNS: every time your browser resolves a domain name, a DNS server learns which site you are visiting. PIR-based DNS (e.g., Oblivious DNS over HTTPS, RFC 9230) hides the query from the resolver.
  • Confidential stock-price lookups and patent searches: financial and legal queries are commercially sensitive; PIR lets a client search without advertising its interests.
  • Censorship-resistant content delivery: a reader can fetch a blocked article from a distributed database without revealing to any single node which article was requested.
  • Anonymous messaging: systems like Signal's sealed-sender rely on ideas close to PIR so that the server cannot build a social graph from metadata alone.

PIR is also a theoretical building block: it implies oblivious RAM (ORAM) — a way to access any data structure privately — which in turn underpins secure computation and trusted-execution enclaves.

Conclusion

Private Information Retrieval teaches a subtle lesson: the content of a public database is not the only thing that needs protecting — the question you ask can be just as sensitive.

The story has a neat arc. Perfect single-server privacy costs everything (you must download the whole database). Add a second server that doesn't collude, and suddenly the XOR trick slashes the cost. Assume a hard cryptographic problem, and a single server suffices at polylogarithmic cost. Every relaxation of the model unlocks a new protocol.

In that sense PIR is a microcosm of cryptography itself: security is not a binary property but a precise trade-off between what the adversary is allowed to do, what computational assumptions hold, and how much overhead you are willing to pay. The invisible query — the one that reveals nothing while learning everything — is one of the most elegant objects the field has produced.

For deeper context on the hardness assumptions behind computational PIR, see factoring and lattice problems.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/private-information-retrieval/Content licensed under CC BY-NC 4.0.