Patron Shield
2-Server IT-PIR · Chor et al. 1995
Retrieve one book from a catalog by sending each of two servers a random XOR mask that differ in exactly one bit, then XOR the replies to rebuild the record neither server could identify.
Private Information
Retrieval
Every time you search a library catalog, the server learns what you looked for. Your reading interests — medical diagnoses, political views, personal struggles — are logged and potentially exposed.
Private Information Retrieval solves this. You retrieve exactly what you want from a database — and the server learns nothing about which item you chose. It still learns that you queried, and when; PIR hides the index, not the visit.
This demo implements the 1995 Chor et al. two-server IT-PIR protocol. The privacy guarantee is information-theoretic — not computational. No assumptions about server computing power are required. It is provably private, on one condition: the two servers must not collude. Run a query below, then trigger the collusion attack to see exactly why.
Why two servers?
Hiding which record you want looks impossible with one server. The only information-theoretic way to keep a single server from learning your query is to download the entire database every time. PIR's trick is to split the work across two servers — so instead of downloading all N records you send two masks and receive two record-sized XOR responses, neither server learns which record you asked for, and the cost is a trust assumption.
Library Catalog
Select a book to query privately.
Protocol Visualizer
Teaching simulation. Both "servers", the full catalog, your selection and every response run inside this one browser tab — there is no network, no trust boundary, and the whole database is already on your machine, so no privacy service is actually being performed. A real deployment needs independently operated replicas, separate query delivery paths, and a client you trust: the JavaScript that reads your click already knows the index before PIR begins.
Select a book above and click Query Privately to watch the IT-PIR protocol execute step by step.
Client generates query pair
Each mask on its own is uniformly random over all values of a 8-bit query, so neither server can determine which bit differs — or which book you want. Only a party holding both can see it.
Server 1 XOR computation
Server 2 XOR computation
Client reconstructs the book
What each server knew
Neither server alone saw your query. Each mask is uniformly random from the server that received it — not merely random-looking. That is the difference between this guarantee and a computational one: there is no distribution to distinguish and no work an unbounded server could do to narrow the index down. The book you retrieved — — stays private as long as the two servers don't pool what they received.
Scoped precisely: from its own mask, either server learns zero information about which record you requested. It does not hide that a query happened, who asked, when, how often, or the response size — those are transport and identity problems this protocol does not address.
The two masks are not independent — by construction S′ = S ⊕ {i}, so they differ in exactly one bit: yours. Any party holding both masks recovers your query with a single XOR. That is the price of two-server PIR: you trade the cost of downloading the whole database for the assumption that no single party ever sees both masks.
Note what that assumption does not buy. Privacy and correctness rest on different requirements, and "at least one server is honest" runs them together: index privacy survives as long as no one party holds both masks — one dishonest server learns nothing on its own, however it behaves. But correctness needs both servers to compute honestly. A single malicious server can return arbitrary bytes, and r₁ ⊕ r₂ is then a corrupted record with nothing in this protocol to flag it. Detecting that takes an added integrity mechanism — an authenticated database snapshot, commitments, or verifiable computation — which IT-PIR does not supply.
One bit survives: position . Colluding servers learn instantly that you asked for . Privacy is gone. This is why the threat model requires the servers to be operated by independent, non-colluding parties.
Naive vs. Private Query
GET /catalog/search?q=[select a book above]
The server receives your exact search term and logs it. Your reading interests are permanently recorded.
How PIR scales — the √N trick
The query above carries one bit per record. Here is how it stays small as the catalog grows.
This demo sends an N-bit mask — one bit per record. Fine for 8 books; a million-record catalog would mean a million-bit query.
Instead, arrange the catalog as a √N × √N grid. To fetch the record at (row r, column c), send each server a √N-bit column mask — the two masks differing in only column c. Each server returns one parity per row (√N values); XOR the two replies to rebuild the entire target column, then read row r.
Same information-theoretic privacy, same non-collusion assumption — but the query shrinks from N to √N. The servers see only a random column subset, so c stays hidden, and r is never transmitted. That sublinear cost is why two-server PIR is a landmark result, not just a privacy trick.
Implementation note: this demo packs each query mask into a single 32-bit integer, so its live 1-D protocol is capped at DB_SIZE ≤ 32 records (the catalog here is 8). That ceiling is a JavaScript-number convenience, not a property of PIR — the O(n)-communication scaling lesson above is illustrated with the √N slider rather than by actually growing the live database. A production implementation would use a bit-vector or the √N matrix layout to reach realistic catalog sizes.
These three figures count query bits only — what the client sends. Each server still returns a record-sized response, so the total bytes on the wire are the two queries plus two responses; in the matrix scheme each server returns one parity per row, so the responses grow with √N as well. PIR shrinks the query, not the reply.