Why every PIR scheme has to touch every record

The first thing anyone notices about private information retrieval is that it seems absurdly expensive. You want one record out of a million, and the protocol makes the server read all million. That is not an implementation defect waiting to be optimised away. It is forced.

The argument in one paragraph

Fix a single-server scheme and let $S \subseteq [n]$ be the set of indices the server reads while answering a query. Suppose there is some index $j \notin S$ . Then the server's entire view is independent of $\mathrm{DB}[j]$ , so the answer it returns cannot depend on $\mathrm{DB}[j]$ either. If the client asked for $j$ , it cannot possibly reconstruct the right value. So correctness forces $S$ to cover every index the client might have asked for — and privacy forces the distribution of $S$ to be identical for all queries. Put together: $S = [n]$ , always.

The interesting part is that this holds regardless of the cryptography. It is an information-flow argument about which memory cells were read, not about the hardness of any lattice problem.

What the server is allowed to learn

The formal privacy requirement is that for any two indices $i, i'$ , the query distributions are computationally indistinguishable:

\big\{ \mathsf{Query}(i) \big\} \;\approx_c\; \big\{ \mathsf{Query}(i') \big\}

Note what this does not say. It says nothing about the answer size, nothing about timing, and nothing about the access pattern. Those have to be argued separately, and in practice the access pattern is the one that leaks first. A scheme that is perfectly sound under the definition above can still be broken by an adversary with a cache-timing side channel, because the definition quantifies over the transcript, not over the machine.

Where the cost actually goes

Reading $n$ records is the floor, but "reading" can mean very different things:

Scheme family	Server work per query	Client state
Trivial (send everything)	$O(n)$ transfer	none
LWE-based, no preprocessing	$O(n)$ multiply-accumulate	$O(\sqrt{n})$
SimplePIR-style, with hint	$O(n)$ over small integers	$O(\sqrt{n})$ hint
Offline/online with client storage	$O(\sqrt{n})$ online	$O(\sqrt{n})$

The last row looks like it violates the bound. It does not — it moves the linear pass into an offline phase that is amortised across many queries. The database still gets touched in full; you just stop paying for it on every request.

Here is the shape of the linear pass, stripped of all the cryptography:

def answer(db, query):
    # db:    n records, each an element of Z_p
    # query: n ciphertexts, exactly one of which encrypts 1
    acc = ZERO
    for i in range(len(db)):          # <- this loop cannot be shortened
        acc = add(acc, mul(query[i], db[i]))
    return acc

Every practical speedup — SIMD packing, NTT batching, matrix–vector formulations — is a constant factor on that loop. None of them remove it.

Why this is good news

A lower bound that applies to every scheme is also a design constraint you can lean on. It tells you where to stop optimising, and it tells you that the honest comparison between two PIR schemes is never "how many records did you read" but rather:

how much work per record, measured in cycles rather than asymptotics;
how much state the client has to hold, and how it goes stale when the database updates;
how the communication scales with the record size, not just with $n$ .

Those are the three numbers I care about in every benchmark. The linear scan is a given.