Private Information Retrieval

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.

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">{{hint}}</p>
<div class="db-row" id="db-display"></div>
<div class="picker">
  <label>{{target_label}} <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">{{proto_sub_a}}</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">{{proto_sub_b}}</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">{{btn_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; }

// Code not found

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.

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)$ total communication; later work (Beimel et al., Woodruff–Yekhanin) pushed this to $n^{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.

"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.

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.