SimplePIR, and what a preprocessed hint really costs

SimplePIR reports numbers that sound too good for single-server PIR: throughput within a small factor of a plain memory scan. The trick is a client-side hint computed once, before any query exists. The question I keep coming back to is who pays for that hint, and when it stops being a good trade.

The construction, compressed

Arrange the database as a square matrix $\mathbf{D} \in \mathbb{Z}_p^{\sqrt{n} \times \sqrt{n}}$. The server publishes, once:

where $\mathbf{A}$ is derived from a public seed. A query for cell $(r, c)$ is an LWE encryption of the indicator vector $\mathbf{u}_c$, and the server replies with $\mathbf{D} \cdot \mathbf{q}$. The client subtracts the relevant row of $\mathbf{H}$ to cancel the LWE mask and reads off row $r$.

The server-side work is one matrix–vector product over 32-bit integers. That is why it is fast: no NTTs, no modular reduction chains, just multiply-accumulate that the memory subsystem can keep fed.

The part that is easy to skip

The hint $\mathbf{H}$ has $\sqrt{n} \cdot k$ entries and the client has to store all of it. With $k = 1024$ and 32-bit entries:

For a browser client, 64 MB of state per database is already at the edge of reasonable. And the hint is not a one-time cost in the way the paper's framing suggests, because:

1. It is per-database. Query three different datasets, hold three hints.
2. It goes stale on update. Any write to $\mathbf{D}$ invalidates the rows of $\mathbf{H}$ that depend on it. For an append-mostly dataset you can patch incrementally; for a mutable one you are re-downloading.
3. It has to be downloaded before the first query, which means the latency of query number one is dominated by a transfer that is orders of magnitude larger than the query itself.

Where the break-even sits

Let $h$ be the hint size, $c$ the per-query communication, and $m$ the number of queries a client makes before the hint goes stale. Amortised communication per query is

With $h \approx 64\ \mathrm{MB}$ and $c \approx 250\ \mathrm{KB}$, the hint stops dominating only once $m \gtrsim 256$. That is a lot of queries against an unchanging database. It is a good fit for something like a certificate transparency lookup or a blocklist check, where clients are long-lived and the data moves slowly. It is a bad fit for anything resembling a search box.

// The measurement that actually matters, and that throughput plots hide
fn amortised_bytes_per_query(hint_bytes: f64, query_bytes: f64, queries: u32) -> f64 {
    hint_bytes / queries as f64 + query_bytes
}

What I would want reported

Every PIR paper reports throughput in GB/s of database scanned. Almost none report the number above. If you are evaluating a scheme for deployment, ask for:

• hint size as a function of $n$, with the concrete parameter set, not the asymptotic;
• the update story — full recompute, incremental patch, or none;
• amortised per-query bytes at $m = 1, 10, 100$.

Throughput tells you what the server can do. Those three tell you what the client has to accept.