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.
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 you transfer one record's worth of data, each server learns nothing, and the only cost is a trust assumption.
Library Catalog
Select a book to query privately.
Protocol Visualizer
Select a book above and click Query Privately to watch the IT-PIR protocol execute step by step.
Client generates query pair
These look like random noise to each server. Neither server can determine which bit differs — or which book you want.
Server 1 XOR computation
Server 2 XOR computation
Client reconstructs the book
What each server knew
Neither server alone saw your query. Both received cryptographically random-looking masks. The book you retrieved — — stays private as long as the two servers don't pool what they received.
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 entire price of two-server PIR: you trade the cost of downloading the whole database for the assumption that at least one server is honest.
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.