Never Decrypted: Reading the Row Without Revealing Which Row

1. The library that watches what you read#

You look up a drug interaction, a phone number that just called you, a landmark in a photo. Transport encryption hides that lookup from everyone on the wire -- your ISP, the coffee-shop Wi-Fi, a national firewall -- but not from the party that matters: the server decrypts your query and sees exactly which row you asked for. In 2007 a peer-reviewed paper concluded that fixing this was hopeless on real hardware ^[1]; by 2024 the same idea ran silently on the phone in your pocket ^[2]. The gap between those poles is this article.

The problem sounds simple until you try to state it precisely: can you read one row of a database without the owner learning which row? Every tool you already trust misses the target. TLS encrypts the channel, so the eavesdropper sees ciphertext -- but the server terminates that channel, decrypts your request, and reads the index in the clear. The threat model has quietly inverted. The adversary is not on the network. The adversary is the party holding the data.

flowchart LR
C["Client: read row i"] -->|"query under TLS"| N["Network path"]
N -->|"ciphertext only"| S["Server holds all n rows"]
S -->|"TLS terminates here"| D["Server decrypts the query"]
D --> K["Server now knows i"]
E["Eavesdropper, ISP, Wi-Fi"] -.->|"sees nothing useful"| N

So how could anyone possibly hide the index from the server? There is exactly one obviously private answer, and it is a joke: have the server ship you the entire database, and read the row you want on your own machine. The server treats every client identically, so it learns nothing about $i$. It also just moved $n$ records to answer a one-record question.

That baseline gives us the measuring stick for the rest of the article: a two-axis ledger. The first axis is communication -- how many bits cross the wire per query. The second is server computation -- how many bits of the database the server must touch to answer one query. Downloading everything costs $n$ on both. Every generation of PIR is a different, quantified answer to one question: how far below $n$ can you push each axis, and what do you pay -- client storage, an extra hardness assumption, a preprocessing phase, a non-collusion requirement, or plain money?

The server is the adversary. Encryption in transit protects your data from everyone except the one party that decrypts and answers your query -- and that party sees exactly which row you read. PIR moves the guarantee from the wire to the query itself, and the honest bar it must beat is the ridiculous one: just download the whole database.

This is Part 4 of Never Decrypted, a series on computation that uses, transmits, and reasons about data without ever decrypting it. The single-server story here rests on homomorphic encryption, built in the companion post on fully homomorphic encryption; the private set lookups PIR resembles but does not solve live in the earlier post on OPRFs and private set intersection. If downloading everything is the only thing that obviously works, how could anyone ever do better -- and why did it take until the 2020s to ship?

2. 1995: the problem gets a name and a wall#

The field begins with a single paper. In 1995, Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan defined private information retrieval, gave it the two-axis framing we just built, and in the same stroke proved that the honest bar cannot be beaten by one server alone ^[3]. Their model is deliberately austere: the database is a string of $n$ bits, the client wants bit $D[i]$, and "privacy" means the server's view is independent of $i$. No cryptography, no assumptions -- just information.

Under that model they proved a wall: with a single server and perfect privacy, the client must download everything.

"To completely guarantee the privacy of the user, the whole database should be downloaded; namely $n$ bits should be communicated." -- Chor, Goldreich, Kushilevitz, and Sudan, 1995

The argument is a counting argument, and it rewards being felt in the gut rather than taken on faith -- as long as you run it in the right order. Start from what unconditional privacy forces: the whole transcript the server sees must be identical no matter which index the client wanted. If it shifted with $i$ even slightly, a server that studied the transcript could shift its guess, and privacy would not be perfect.

So the primitive is query-independence -- any transcript that can occur when the client wants row $i$ can also occur when it wants any other row $j$. The more familiar statement, that the answer carries no information about $i$, is a downstream consequence, not the starting point. "Possible" here means possible with positive probability over the client's own private coins -- the secret decoding randomness the server never sees. The client reconstructs its bit from the transcript using those coins, so one fixed transcript together with fixed coins yields exactly one output bit. Making that caveat explicit is what turns the intuition into a proof ^[3].

Now count the transcripts. Fix the wanted index $i$ and suppose fewer than $2^n$ transcripts are possible for it. There are $2^n$ possible databases, so two of them, $x$ and $y$, must produce the very same transcript $C$ -- identical query and, crucially, identical server answer. By query-independence, that transcript is also reachable when the client instead wanted some index $j$ where the databases disagree, $x_j \neq y_j$.

But faced with $C$ and its private coins, the client emits a single fixed bit. Correctness demands that bit equal $x_j$ when the database is $x$ and $y_j$ when it is $y$ -- and those differ. Contradiction. So at least $2^n$ transcripts must be possible, and merely naming one takes $n$ bits. The download bar is not lazy engineering; for one server with perfect privacy it is provably the only solution ^{[3, 4]}. It is a theorem.

That distinction is the hinge of everything that follows, because the 1995 impossibility only bites under two conditions held at once: one server and unconditional privacy. Drop either and the wall has a door.

Relax "one server" -- put the database on two or more replicas that do not talk to each other -- and you keep perfect privacy while paying far less than $n$ in communication. That is the multi-server, information-theoretic line, where the next section builds a scheme by hand. Relax "unconditional" -- allow a computational hardness assumption -- and a single server can be private after all, the line that eventually ships. The impossibility did not close the field. It drew the two roads out of it. Cite the founding result carefully: the conference version is Chor, Goldreich, Kushilevitz, and Sudan at FOCS 1995, and the journal version is JACM 45(6), 1998. They are the same work; do not date the idea to 1998 or the journal to 1995 ^[3].

One server cannot beat the download bar without giving up perfect privacy. So what exactly breaks the impossibility when you add a second server -- and what new, fragile thing do you have to trust in exchange?

3. Two servers, one XOR, and privacy from nowhere#

Here is the escape, and it is not the one you would guess. Do not encrypt anything. Instead, replicate the database onto two servers that never communicate, and split your question into two halves that each look like noise. The 1995 impossibility assumed one server; give the client two, and perfect privacy costs far less than a full download ^[3]. The tool is XOR and nothing else.

Work over bits. The database is $n$ bits, held identically by Server 1 and Server 2, and you want bit $D[i]$. The client picks a uniformly random mask -- an $n$-bit string where each position is an independent coin flip -- and calls it $q_1$. It builds $q_2$ by copying $q_1$ and flipping the one bit at position $i$, then sends $q_1$ to Server 1 and $q_2$ to Server 2.

Each server computes the parity of the database bits its mask selects -- the XOR of $D[j]$ over every $j$ where the mask is 1 -- and returns that single bit. The client XORs the two replies.

Watch what cancels. The two masks agree everywhere except position $i$, so in the XOR of the two parities every database bit is counted twice and vanishes -- except $D[i]$, which was selected by exactly one of the masks. The client is left holding $D[i]$ and nothing else.

sequenceDiagram
participant C as Client
participant S1 as Server1
participant S2 as Server2
Note over C: Pick random mask q1, build q2 as q1 with bit i flipped
C->>S1: Send mask q1
C->>S2: Send mask q2
S1-->>C: Parity of selected bits, a1
S2-->>C: Parity of selected bits, a2
Note over C: XOR a1 with a2, all bits but i cancel, recover D of i

Now the privacy claim, which is where the magic actually lives. Server 1 sees $q_1$, a uniformly random string -- every mask is equally likely, so it reveals nothing about $i$. Server 2 sees $q_2$, which is also uniformly random, because flipping a fixed position of a uniform string leaves it uniform. Each server, alone, learns nothing about your index in the strongest possible sense: not "cannot compute it efficiently," but "the string it received is statistically independent of $i$." No assumption, no cipher, no key.

// Two-server information-theoretic PIR: the whole idea on one screen.
// The n-bit DB is held by BOTH servers, which must NOT talk to each other.
const DB = [1, 0, 1, 1, 0, 0, 1, 0]; // n = 8 bits
const i = 5;                          // the row we want -- kept secret

// Client: pick a uniformly random mask, then flip only position i for q2.
const rnd = () => DB.map(() => Math.round(Math.random()));
const q1 = rnd();
const q2 = q1.map((b, j) => (j === i ? b ^ 1 : b));

// Each server returns the XOR (parity) of the DB bits its mask selects.
const answer = (q) => q.reduce((acc, b, j) => acc ^ (b & DB[j]), 0);
const a1 = answer(q1), a2 = answer(q2);

// Client XORs the two replies. Every bit but i cancels.
console.log("recovered D[i] =", a1 ^ a2, "  actual =", DB[i]);
console.log("server 1 saw:", q1.join(""));
console.log("server 2 saw:", q2.join(""), "-- both look like pure noise");

Run it and change $i$: the recovered bit always matches, and each server's view is an unbiased coin-flip string that betrays nothing. This is the first genuine shift in understanding the article offers. The way past the impossibility was never encryption. It was replication plus XOR -- an idea from coding theory, not cryptography. That is not a coincidence. A PIR scheme is essentially a locally decodable code: any single database symbol can be recovered by reading only a few positions of an encoding. Yekhanin's survey makes the correspondence precise, and progress on one side has repeatedly moved the other ^[5].

Now the ledger, and the catch. The by-hand scheme names an arbitrary subset of all $n$ positions, so each query is itself $n$ bits long -- "each server sent only a single bit, but the messages sent by the user ... are $n$ bits long," as CGKS note ^[3]. Privacy came for free, but on the communication axis this buys nothing over downloading. The genuine sublinear win comes from shrinking the query description, and it is worth seeing rather than taking on faith.

Reshape the $n$ bits into a $\sqrt{n} \times \sqrt{n}$ grid. Instead of a subset of everything, the client sends each server a random subset of the $\sqrt{n}$ columns -- a subset to Server 1, and to Server 2 the same subset with the target's column toggled in or out. Each server returns one parity per row: a $\sqrt{n}$-bit vector whose entry for row $r$ is the XOR of the grid entries in row $r$ over just the columns it was handed.

XOR the two vectors and every column cancels except the target's, which survives in full; the entry in the target row is your bit. That is $\sqrt{n}$ up and $\sqrt{n}$ back per server -- $O(\sqrt{n})$ communication, genuinely below $n$ ^[3].

The same crank turns further. Recurse on that $\sqrt{n}$-bit answer, or reshape into a three-dimensional cube of side $n^{1/3}$ and query a sub-cube, and communication falls to $O(n^{1/3})$. The cube naively needs eight servers, one per corner, but a radius-1 covering code collapses them to two: every one of the eight corners lies within one bit-flip of either 000 or 111 -- 000 covers $\{000, 001, 010, 100\}$ and 111 covers $\{111, 110, 101, 011\}$ -- so two servers cover the whole cube and still reach $O(n^{1/3})$ (CGKS Table I) ^[3].

Server computation, though, does not improve -- each parity still sweeps a constant fraction of the database, so every server does $\Theta(n)$ work per query. And all of it rests on one load-bearing assumption that XOR cannot defend.

The two-server escape is real, it is unconditional, and it is brittle: it demands at least two replicas that you trust never to whisper. The founding $O(n^{1/3})$ barrier was not even the end of the information-theoretic story. Dvir and Gopi shattered the two-decade-old $O(n^{1/3})$ two-server bound in 2015-16, reaching subpolynomial $n^{o(1)}$ communication -- proof that the information-theoretic line still has room to move ^[6]. But most real deployments have exactly one server and no willing, non-colluding twin. Can a single server give you privacy, with no replica to trust?

4. One server, an encrypted question, and the wrong race#

In 1997 Eyal Kushilevitz and Rafail Ostrovsky answered that question with a paper whose title is a thesis: "Replication Is Not Needed." A single server can be private after all -- if you stop demanding unconditional privacy and let the server compute on an encrypted query instead ^[7]. This is the birth of computational single-server PIR, and it is also, though nobody would notice for a decade, the birth of a strategic mistake.

The mechanism is the one the whole modern field still runs on. Lay the $n$-bit database out as a $\sqrt{n} \times \sqrt{n}$ matrix. To fetch the entry in column $c$, the client sends an encrypted selection vector: $\sqrt{n}$ ciphertexts that decrypt to 0 everywhere except a single encrypted 1 in position $c$.

The server, using only the public key, folds each row of the matrix against that encrypted vector and produces one output ciphertext per row -- each an encryption of that row's entry in column $c$. The client decrypts only the row it wanted. The server never learned $c$, because it only ever touched ciphertext ^[7].

flowchart TD
Q["Client encrypts a selection vector, a single 1 at column c hidden among 0s"] --> SV["Server holds the database as a matrix"]
SV --> F["For each row, fold the row against the encrypted vector using the public key"]
F --> R["Server returns one ciphertext per row, each encrypting that row entry in column c"]
R --> D["Client decrypts only the wanted row and reads the record"]

That $\sqrt{n}$-up, $\sqrt{n}$-back fold is only Kushilevitz-Ostrovsky's base case. Its answer is itself a bundle of $\sqrt{n}$ ciphertexts, of which the client wants exactly one -- so apply PIR again to that bundle, recursing $L = \lceil 1/\epsilon \rceil - 1$ levels (equivalently, viewing the database as an $(L+1)$-dimensional hypercube and folding one axis per level). That drives the $O(\sqrt{n})$ base case down to the $O(n^{\epsilon})$ the ledger records, for any constant $\epsilon > 0$ ^[7].

That single-axis victory lit up a decade of relentless progress. Christian Cachin, Silvio Micali, and Markus Stadler drove communication to polylogarithmic in 1999, CMS rested on the $\Phi$-hiding assumption, a number-theoretic conjecture about the hidden prime factors of Euler's totient. We only name it; the number theory is not the point of this article ^{[8, 9]}. and by 2005 Craig Gentry and Zulfikar Ramzan reached constant communication rate, the response barely larger than the record itself ^[10]. On the communication axis, PIR looked finished. On paper, the problem was solved.

Then someone finally timed the other axis. In 2007 Radu Sion and Bogdan Carbunar measured single-server computational PIR on real hardware and published a verdict that stopped the field cold.

Deploying non-trivial single-server PIR on real hardware "would have been orders of magnitude less time-efficient than trivially transferring the entire database." -- Sion and Carbunar, 2007

Read that against the thesis. The whole point of PIR is to beat the trivial download. Sion and Carbunar showed that every clever single-server scheme, timed end to end, lost to the very baseline it was built to beat -- because the server still ground through $\Theta(n)$ expensive modular-exponentiation operations per query, and moving a few kilobytes over a fast network is cheaper than a server doing a billion big-integer multiplies ^[1]. The community had spent ten years shrinking the wrong number.

Worse, the computational wall was already a theorem. In work that culminated in the 2004 Journal of Cryptology, Amos Beimel, Yuval Ishai, and Tal Malkin proved that without preprocessing, any PIR server must do $\Omega(n)$ work -- it cannot answer a query while ignoring part of its database, or the ignored part could not have influenced the answer ^[11]. Sion and Carbunar had measured, on silicon, a floor that theory guaranteed.

gantt
title PIR milestones on two axes, 1995 to 2026
dateFormat YYYY
axisFormat %Y
section Communication axis
CGKS two-server IT-PIR :milestone, 1995, 0d
Kushilevitz-Ostrovsky single-server CPIR :milestone, 1997, 0d
CMS polylog communication :1999, 2001
Gentry-Ramzan constant rate :milestone, 2005, 0d
section Computation axis
Sion-Carbunar impractical verdict :milestone, 2007, 0d
XPIR lattice revival :milestone, 2016, 0d
SimplePIR near memory bandwidth :milestone, 2023, 0d
section Deployment
Apple ships keyword PIR :2024, 2026

Two honest caveats keep this from being a hit piece. First, the verdict was contested: in 2011 Femi Olumofin and Ian Goldberg re-measured with better implementations and argued that multi-server and even some single-server PIR already beat trivial download for realistic parameters ^[12]. Second, the theory cuts the other way too: Beimel, Ishai, Kushilevitz, and Malkin proved that any nontrivial single-server PIR implies one-way functions exist ^[13].

So a computational assumption is unavoidable for one server -- but it is a claim about the necessity of some assumption, not about fully homomorphic encryption specifically. Homomorphic encryption is the efficient road, never a logical requirement.

Here is the running ledger so far, one row per generation:

If $\Omega(n)$ server work is a theorem, single-server PIR seems condemned to lose the clock forever. There turn out to be exactly two honest ways out -- and confusing them is the most common mistake in the whole subject.

5. Two escapes from the computation trap#

A theorem that says $\Omega(n)$ server work is unavoidable without preprocessing is not a dead end. It is a signpost with two arrows, because there are exactly two things you can change: keep the linear work but make each unit almost free, or break the "without preprocessing" clause and buy sublinear online time with an offline phase. The modern era of PIR is the parallel pursuit of both, and telling them apart is the single most important distinction in the subject.

flowchart TD
W["Omega(n) server work without preprocessing, a theorem"] --> A["Escape 4a: keep it linear, make each unit cheap"]
W --> B["Escape 4b: change the model with preprocessing and client state"]
A --> A1["XPIR, SealPIR, Spiral, SimplePIR, DoublePIR, FrodoPIR touch every bit at memory bandwidth"]
B --> B1["CGK, CHK, Piano, DEPIR buy genuinely sublinear online server time"]

Escape 4a: linear is fine if each unit is cheap. Stop fighting the wall. If the server must touch every bit, make touching a bit cost almost nothing. In 2016 Carlos Aguilar-Melchor and colleagues built XPIR by throwing out slow modular exponentiation and replacing it with fast lattice arithmetic -- Ring-LWE homomorphic encryption, whose per-operation cost is a small-integer multiply, not a big-integer power.

Their paper says it plainly: "the conclusion of Sion and Carbunar is not valid anymore: cPIR is of practical value" ^[14]. The wrong-axis decade ended not by beating the $\Omega(n)$ floor but by making the floor cheap to stand on.

The line then sprinted. SealPIR (2018) compressed the client's query so a single ciphertext expands, server-side, into the full selection vector -- roughly a 274-times smaller query -- and added probabilistic batch codes to amortize many queries at once ^[15]. Spiral (2022) composed two lattice schemes to push the response rate toward 0.81, so the answer is barely larger than the record ^[16].

Then, in 2023, SimplePIR and DoublePIR shrank the server's online job to essentially one cheap matrix-vector product over a small modulus -- a single product in SimplePIR, plus a second, much smaller one in DoublePIR. They hit roughly 10 and 7.4 gigabytes per second per core, within a small factor of raw memory bandwidth ^[17].

SimplePIR's matrix-vector product is worth seeing in full, because it shows at once why the linear work is cheap and how the client scrubs off the encryption noise with no server-side decryption at all. Store the database as a $\sqrt{N} \times \sqrt{N}$ matrix $D$ over a small plaintext modulus $p$, and fix a public matrix $A$ that everyone derives from a short seed. Pick a ciphertext modulus $q$ and a scale $\Delta = \lfloor q/p \rfloor$. The scheme is four short steps:

• Setup, once. The server publishes a hint equal to the product $D\,A$. It depends only on the database and the public $A$, never on a query, so it is computed a single time and reused by every client forever after.
• Query row $(i_{\mathrm{row}}, i_{\mathrm{col}})$. The client samples a secret vector $s$ and a tiny error $e$, and sends one vector $\mathrm{qu} = A\,s + e + \Delta\,u_{\mathrm{col}}$, where $u_{\mathrm{col}}$ is the indicator with a single 1 in the target column. That $\mathrm{qu}$ is an ordinary LWE ciphertext -- uniform-looking -- so the server learns nothing about the column.
• Answer. The server returns $\mathrm{ans} = D\,\mathrm{qu}$. This one matrix-vector product is the entire online cost: about $2N$ small-integer operations, roughly one multiply and one add per database byte.
• Recover. The client subtracts the hint mask and rounds: it computes $\mathrm{ans}[i_{\mathrm{row}}] - \mathrm{hint}[i_{\mathrm{row}}]\cdot s$ and rounds to the nearest multiple of $\Delta$.

Why does that land on the wanted entry? Expand the answer and the structure falls out: $\mathrm{ans} = D\,\mathrm{qu} = (D A)\,s + D\,e + \Delta\,(D\,u_{\mathrm{col}})$, and the first term is exactly $\mathrm{hint}\cdot s$. The client downloaded $\mathrm{hint} = D A$ and knows its own secret $s$, so it recomputes that masking term and subtracts it away.

The vector $D\,u_{\mathrm{col}}$ is just the target column of the database, so what remains at row $i_{\mathrm{row}}$ is $\Delta$ times the wanted entry plus the small residual $D\,e$; rounding to the nearest multiple of $\Delta$ erases the residual and returns the entry. The hint cancels the mask; the rounding cancels the noise; and the server, having only ever multiplied by a ciphertext, never learns which entry you read ^[17].

// Toy SimplePIR: the server's entire online job is ONE matrix-vector product,
// and a precomputed hint lets the client cancel the LWE mask.
const p = 16, q = 1 << 20, DELTA = q / p;   // plaintext modulus, ciphertext modulus, scale
const sqrtN = 4, n = 8;                       // DB is sqrtN x sqrtN; lattice dimension n
const mod = (x) => ((x % q) + q) % q;
const randInt = (hi) => Math.floor(Math.random() * hi);

// Database: a sqrtN x sqrtN matrix of plaintext values in [0, p).
const D = Array.from({length: sqrtN}, () => Array.from({length: sqrtN}, () => randInt(p)));
// Public matrix A (sqrtN x n), uniform mod q -- in practice derived from a short seed.
const A = Array.from({length: sqrtN}, () => Array.from({length: n}, () => randInt(q)));

// Setup, once and query-independent: hint = D * A  (a sqrtN x n matrix).
const hint = D.map((row) => Array.from({length: n},
(_, k) => mod(row.reduce((acc, d, c) => acc + d * A[c][k], 0))));

// Client wants entry (iRow, iCol); iCol is hidden in the query, iRow never leaves the client.
const iRow = 2, iCol = 3;
const s = Array.from({length: n}, () => randInt(q));           // secret vector
const e = Array.from({length: sqrtN}, () => randInt(3) - 1);   // small error in {-1,0,1}
// qu = A*s + e + DELTA * u_col  -- an LWE encryption of the column indicator.
const qu = A.map((Arow, c) =>
mod(Arow.reduce((acc, a, k) => acc + a * s[k], 0) + e[c] + (c === iCol ? DELTA : 0)));

// Answer: ans = D * qu -- one matrix-vector product, the whole online server cost.
const ans = D.map((row) => mod(row.reduce((acc, d, c) => acc + d * qu[c], 0)));

// Recover: subtract the hint mask, then round off the small noise.
const mask = mod(hint[iRow].reduce((acc, h, k) => acc + h * s[k], 0));
const recovered = Math.round(mod(ans[iRow] - mask) / DELTA) % p;

console.log("recovered =", recovered, "  actual D[iRow][iCol] =", D[iRow][iCol]);
console.log("the server only ever saw qu, an LWE ciphertext -- never iRow or iCol");

But the authors are scrupulous about what they did not do.

The SimplePIR server "must touch every bit of the database to answer even a single client query." -- Henzinger, Hong, Corrigan-Gibbs, Meiklejohn, and Vaikuntanathan, 2023

FrodoPIR (2023) added the piece deployment needs: a client-independent offline phase, so the server precomputes one batch of state that every client reuses, and then named the honest price. Its measured cost is under one second per query, a response blow-up under 3.6 times, and about $1 for 100,000 queries ^[18]. That is the first time in this article we can write PIR's cost as a number you could put in a budget.

"Linear" was never the enemy. Slow linear was. Once each unit of the unavoidable $\Theta(n)$ work costs about one 32-bit multiply-add at memory bandwidth, the server's full sweep of the database finishes in the time it takes to stream that database through the CPU. The right question flips from "how few bits can I send?" to "how cheap can I make each unit of work I already cannot avoid?"

Escape 4b: change the model. The other door accepts a one-time cost to break the no-preprocessing clause, and buys something 4a can never have: genuinely sublinear online server time.

Henry Corrigan-Gibbs and Dmitry Kogan opened this model for PIR in 2020, showing an offline phase could buy sublinear online time ^[19]. In 2022, Corrigan-Gibbs, Alexandra Henzinger, and Kogan achieved sublinear amortized time on a single server, holding about $\sqrt{n}$ of client state, and proved a matching lower bound that says roughly that much state is necessary ^[20].

Piano (2024) then stripped the assumptions to the floor: sublinear online time from one-way functions only -- pseudorandom functions, no homomorphic encryption -- in about 150 lines of code ^{[21, 22]}. And the asymptotic endpoint arrived in Lin, Mook, and Wichs's 2023 STOC Best Paper.

So the disambiguation, stated once and enforced for the rest of the article: 4a is fast-but-linear (touches every bit, stateless, simple), and 4b is sublinear-but-stateful-or-preprocessing-heavy (touches few bits, but holds $\sqrt{n}$ client state or huge public tables). They are not competitors racing to one finish line. They are different trades. Two escapes, two price tags -- so which one actually ships to a billion phones, and why that one?

6. The 2026 toolbox, laid side by side#

By 2026 there is no "best PIR." There are five living families, each parked at a different point on the same trade-off surface, and the honest way to present them is a single table that scores every one on the two-axis ledger plus the things the ledger hides: client storage, the hardness assumption, and the preprocessing model.

Family 1A, fast-linear single-server PIR, is the deployed line: SimplePIR and DoublePIR, Spiral, SealPIR, FrodoPIR, and two schemes newer than the breakthrough itself. YPIR (2024) removes the client hint entirely with "silent" preprocessing, reaching up to 83% of memory bandwidth with no offline communication ^[24]. Respire (2024) targets small records, retrieving one 256-byte record from a million-record database in about 6.1 KB of online communication ^[25].

Family 1B, sublinear-online preprocessing PIR, is CHK and Piano ^{[20, 21]}. Family 1C is DEPIR and its practicalization race ^[23]. Family 1D is the multi-server information-theoretic line ^{[3, 6]}. And Family 1E, keyword PIR, is an orthogonal layer that rides on top of any of the others.

Read the table as a map of trades, not a leaderboard. Family 1A wins wall-clock throughput and statelessness while conceding $\Theta(n)$ work per query. Within 1A, the axis being optimized is not the compute -- it is the offline hint. Trace the hint shrinking across 1A: SimplePIR needs a 121 MB per-client hint, DoublePIR cuts it to 16 MB, FrodoPIR makes the offline state client-independent so every client reuses it, and YPIR removes the client hint altogether with silent preprocessing ^{[17, 18, 24]}. Family 1B wins sublinear online server time from the minimal assumption, paying $\sqrt{n}$ client storage and statefulness. Family 1C wins the asymptotic ideal -- stateless clients, $\mathrm{polylog}$ server time -- at the price of enormous public tables that are only now becoming tractable. DEPIR's preprocessing is huge but shrinking fast: Okada, Player, Pohmann, and Weinert reported orders-of-magnitude optimizations and a first implementation in 2024 ^[27], and a 2026 preprint pushed the server state for an $N=2^{23}$ database from a prior 733 TB down to 171 GB, at about 21 ms amortized per query in a batch ^[28].

The toolbox is real, fast, and honestly priced. So where, concretely, does it run for a billion people -- and what does that deployment quietly trade away?

7. PIR on a billion phones, and its honest bill#

The thesis is now a shipping product. By 2024 Apple runs keyword PIR at consumer scale in two features, both on the homomorphic-encryption-based linear line -- family 1A -- and both wrapped in an Oblivious HTTP relay that hides the client's IP address from the answering server.

Enhanced Visual Search, in Photos, is the mass-scale one: it is on by default. When your phone wants to name a landmark in a photo, it computes an embedding of the image region, encrypts it under BFV, and runs a private nearest-neighbor search plus PIR against a global index Apple holds.

In Apple's own words, the system uses "homomorphic encryption (HE) along with technologies like private information retrieval (PIR) and private nearest neighbor search (PNNS)" and runs at "post-quantum 128-bit security" ^[2]; Apple's privacy note says it "privately matches places in your photos to a global index Apple maintains on our servers ... using homomorphic encryption" ^[29]. That Enhanced Visual Search ships on by default in iOS 18 and macOS 15 was surfaced less by Apple's launch messaging than by developers -- Jeff Johnson prominent among them -- who found the toggle already enabled and asked whether users had meaningfully consented ^{[30, 31]}.

Live Caller ID Lookup is the opt-in, provider-dependent one: when enabled, it fetches caller-identification and spam information for an incoming number. Apple states it plainly: "Live Caller ID Lookup relies on Private Information Retrieval (PIR)," the implementation "relies on homomorphic encryption," it "implements the Brakerski-Fan-Vercauteren (BFV) HE scheme," and BFV is "quantum resistant" ^[32]. Unusually, the backend is open: Apple publishes a reference server and the swift-homomorphic-encryption library, so the deployed stack is not a black box ^[33].

flowchart LR
D["Device computes an embedding or a phone number"] --> E["Encrypt under BFV, client keeps the key"]
E --> O["Oblivious HTTP relay hides the client IP"]
O --> S["Server runs keyword PIR on ciphertext, never decrypts"]
S --> A["Encrypted answer travels back"]
A --> R["Device decrypts locally and reads the result"]

Both features rest on BFV, a Ring-LWE scheme whose internals belong to the FHE post, not here; enough that BFV lets the server fold an encrypted query against its index without a key, and that its lattice hardness is plausibly post-quantum ^[34]. What matters for our ledger is which escape Apple chose, and it chose 4a: the server does full linear work per query, fast.

Why 4a and not the asymptotically superior sublinear lines? A labeled inference, not an Apple claim: a default-on, high-churn feature spread across a billion heterogeneous devices cannot ask each one to hold and periodically refresh $\sqrt{n}$ bytes of client state, which is exactly what the sublinear 1B and 1C lines require. The stateless, linear-but-fast 1A line is the only family whose operational shape fits a mass-consumer deployment, so that is the one that ships ^{[17, 21]}. The answer is not that 4a is faster in the abstract -- it is that statelessness beats asymptotics when your client population is a billion phones that churn constantly. It ships, and it works. But every choice on that stack traded something away. How does an engineer who is not Apple actually pick?

8. The decision fan: no single winner#

Put the families on trade-off axes instead of a leaderboard, and the shape of the choice becomes clear. Three questions route you to a family, and each answer pairs a strength with the limitation it leaves standing.

The first axis is how many servers you trust. Two or more replicas that will not collude buy unconditional privacy with no hardness assumption -- the information-theoretic multi-server line ^[3] -- but you must operate non-colluding infrastructure, which most single-vendor deployments cannot. One server needs a computational assumption instead of a replica.

The second axis is how much state the client can carry. Fast-linear 1A is stateless and simple, paying $\Theta(n)$ server work per query ^[17]. Sublinear 1B (CHK, Piano) cuts online work to $\tilde{O}(\sqrt{n})$ but demands roughly $\sqrt{n}$ bytes of per-client state and a client long-lived enough to amortize its offline phase ^{[20, 21]}. Doubly-efficient 1C keeps clients stateless and server time $\mathrm{polylog}$, but relocates the cost to enormous public tables ^[23].

The third axis is which assumption you will accept. Spiral and DEPIR want lattice homomorphic encryption; Piano wants only a pseudorandom function, the weakest cryptography that can do the job ^{[16, 23, 21]}. Weaker assumptions are safer and often faster per operation, but so far buy sublinearity only in the stateful model.

flowchart TD
Q1{"Two or more non-colluding servers?"} -->|"yes, unconditional privacy"| MS["1D multi-server IT-PIR"]
Q1 -->|"no, single server"| Q2{"Clients can hold sqrt n state?"}
Q2 -->|"no, stateless and high churn"| FL["1A fast-linear plus a keyword layer"]
Q2 -->|"yes, few long-lived clients"| SUB["1B Piano or CHK, sublinear online"]
Q2 -->|"want the asymptotic ideal, huge tables acceptable"| DE["1C DEPIR"]

Every option on this fan shares one silence. Each is only a privacy mechanism: it hides which row you read. None promises the row you got back is the right row, or that the database is hidden from you. What can no PIR promise -- and which gaps are engineering debt versus provable, permanent walls?

9. Four walls, and the row you cannot trust#

Now that PIR demonstrably works, it is worth seeing exactly how far it cannot go -- because several of the ceilings are theorems, not engineering backlog. Four walls, then a fifth thing PIR was never built to do.

Wall one: one server plus unconditional privacy equals download everything. This is the 1995 impossibility, and it is permanent. No cleverness beats it, because it is an information-theoretic counting bound: the baseline is not the worst case, it is the optimal case for that threat model ^[3].

Wall two: no preprocessing means $\Omega(n)$ server work. Sublinear server time is impossible in the no-preprocessing model, full stop ^[11]. This is the abstract statement of SimplePIR's practical confession that the server "must touch every bit of the database to answer even a single client query" ^[17]. You can move the cost with preprocessing, but you cannot make it vanish.

Wall three: some assumption is unavoidable for one server. Any nontrivial single-server PIR implies one-way functions exist ^[13]. So single-server privacy can never be unconditional -- but note precisely what that says. A one-way function is necessary; fully homomorphic encryption is not. HE is the efficient road, and Piano proves a pseudorandom function suffices for the sublinear line ^[13].

Wall four: the multi-server line is bounded by coding theory. Because a PIR scheme is essentially a locally decodable code, the best achievable multi-server communication is pinned to open questions about those codes -- which is why the two-server frontier is measured in the same breath as LDC lower bounds ^[5].

Then the ceiling that surprises people most, and the one the series turns on: basic PIR hides your index from the server, but it does nothing to hide the rest of the database from you.

Basic PIR gives only the server-side half of that guarantee. ※ SPIR is the symmetric version -- privacy for both parties at once -- which is why it coincides with oblivious transfer, a strictly stronger and more expensive primitive than plain PIR ^[35]. A curious client running ordinary PIR can fish: nothing in the protocol stops it from asking for records it has no right to, because the whole design goal was to protect the client's query, not the server's data. If you need to protect the data from the client too, you do not want PIR, you want SPIR or oblivious transfer.

That third correction is not a settled theorem like the first four. It is a live gap -- the seam where privacy stops and integrity was never promised. It, and the size of DEPIR's tables, are where the frontier actually is.

10. The unfinished map#

The mechanism is proven and shipping, which is exactly when the interesting problems start. Here is where a reader could actually push.

Shrink DEPIR's tables. Doubly-efficient PIR reaches the asymptotic ideal but pays with $O(N^{1+\epsilon})$ preprocessed state, and driving that toward $O(N)$ while keeping $\mathrm{polylog}$ online time is the central open engineering problem of the line ^[23]. The trajectory is steep and public: concrete optimizations and a first implementation in 2024 ^[27], open prototypes exploring algebraic-HE variants ^{[36, 37]}, and a 2026 preprint cutting server state from hundreds of terabytes to hundreds of gigabytes for a fixed database size ^[28].

Make sublinear single-server PIR stateless. The 1B line buys sublinear online time only by holding about $\sqrt{n}$ of per-client state, and CHK proved a matching lower bound suggesting that much state may be inherent to the client-hint model ^[20]. Whether a stateless client can get sublinear online time on a single server, outside the huge-table DEPIR regime, is open.

Close the integrity seam. This is the one that matters most for the series.

The rest of the frontier is a good to-do list:

• Keyword PIR at web scale -- private safe-browsing blocklists, Certificate Transparency lookups -- pushes throughput and record-size limits that Respire and YPIR are actively chasing ^{[25, 24]}.
• Updatable and streaming databases strain the preprocessing lines, whose hints assume a database that does not change under them.
• Batching and multi-query lower bounds ask how much cheaper $k$ queries can be than $k$ times one, the question SealPIR's probabilistic batch codes opened ^[15].
• Metadata leakage beyond the index -- when and from where you queried -- is only partly handled by Apple's Oblivious HTTP and differential-privacy scaffolding ^[2].
• The multi-server communication frontier reopened by Dvir and Gopi is still moving ^[6].

The row-hiding mechanism is settled. The guarantees around it -- small preprocessing, verifiable answers, metadata hygiene -- are the next decade, and the next post. Before then, one practical question remains: given all this, how do you actually choose, this week?

11. Choosing, and when not to use PIR at all#

Here is a procedure you can act on this week. Start by trying not to use PIR, because the trivial baseline is genuinely optimal below a break-even size, and then route by the constraints that actually bind.

The budgeting rule for the deployed line is simple because the work is linear: a fast-linear server sweeps its whole database once per query, so at roughly 10 GB/s per core a $d$-gigabyte database costs about $d/10$ core-seconds of compute per query, plus a response several times larger than the record ^{[17, 18]}. Wrap the whole thing in Oblivious HTTP so the index is not the only thing you hide.

// Should you use PIR, or just download the database?
// PIR server work is LINEAR: it streams the whole DB past the CPU once.
const dbSizeGB = 8;           // database size in gigabytes
const downlinkGbps = 0.1;     // client download speed, gigaBITS per second
const pirThroughputGBs = 10;  // SimplePIR-class server, gigaBYTES/s/core
const pirCores = 8;

// Time to just download the entire database (the trivial baseline).
const downloadSec = (dbSizeGB * 8) / downlinkGbps;
// Time for one PIR query: the server sweeps the DB once at its throughput.
const pirSec = dbSizeGB / (pirThroughputGBs * pirCores);

console.log("download everything:", downloadSec.toFixed(1), "s per query");
console.log("PIR linear scan:    ", pirSec.toFixed(3), "s per query");
console.log(pirSec < downloadSec
? "PIR wins on wall-clock -- but you still pay server compute + response blow-up"
: "below break-even: just download it, simpler and leak-free");

Rules of thumb are cheap. Here are the questions people actually ask.

12. Frequently asked questions#

13. Reading the row, and trusting it#

Return to the three lookups from the opening: the drug interaction, the number that just called, the landmark in the photo. You can now explain, mechanism by mechanism, how each stays private. The query leaves your device as an encrypted selection vector or an encrypted embedding; the server folds its database against that ciphertext without a key; an Oblivious HTTP relay strips your IP on the way; the answer comes back sealed, and only your device opens it. The server answered a question about a row it never identified.

Thirty years turned an impossibility into a product. PIR lets a client fetch record $i$ while the server provably never learns $i$ -- won first on the communication axis (two-server XOR, then single-server homomorphic encryption, then polylogarithmic and constant-rate), then on the computation axis (fast-linear throughput and sublinear-preprocessing), and finally shipped to a billion phones. The baseline it beat was never lazy engineering: downloading everything is provably optimal for one server with perfect privacy, and PIR beats it at a cost you can name in dollars and gigabytes, but never zero.

The honest bill stays attached: linear server compute at cents per thousand queries, and a response several times larger than the record ^[18]. That is the real price of running keyword PIR by default in a billion camera rolls ^[2] -- and of the fact that a server sweeping every bit at memory bandwidth still never learns which bit you wanted.

Two threads run out of this post into the rest of Never Decrypted. The BFV and Ring-LWE machinery that lets the server compute on your encrypted query is built from first principles in the fully homomorphic encryption post; the private set operations PIR resembles but does not perform live in the OPRF and private set intersection post. And one honest sentence stays open, the same seam the FHE post left: PIR bought you privacy, not correctness ^[3].

You can read the row without revealing which row. Whether you can trust the row you got back is the next story.