Private information retrieval (PIR) lets a client fetch record $x$ from a server's database without the server learning $x$. Its basic obstacle is the linear scan. If the server skips any record, it learns the client did not want that record, so standard PIR costs the server work proportional to the database size $N$ on every query. Preprocessing PIR avoids this. The client first streams the database once and stores short "hints," which are XOR sums of pseudorandom subsets of records. Later it answers each query by asking the server to XOR a slightly altered subset and cancelling the result against the matching hint. This brings server work down to about $\sqrt{N}$.
The fastest designs of this kind assume an honest server. Plinko uses an invertible pseudorandom function (a keyed function whose outputs can be traced back to every input that produced them) to find the right hint in near-constant time and to apply database updates in worst-case near-constant time. It explicitly leaves malicious servers open. The main malicious threat is a selective failure attack: the server corrupts a record during the offline stream, waits, and watches whether the client later fails. The failure reveals which hint was used, and the hint is correlated with the query.
This proposal borrows a measurement idea from particle physics. At electron-positron colliders running just above pair-production threshold, particles come in correlated pairs. Experimenters fully reconstruct one partner, the "tag," and use it to infer the other. Comparing double-tag and single-tag yields cancels an unknown normalization (J. Alexander et al.; Improved measurements of D→Kℓν). We apply the same structure to PIR. Each record is covered by two independently keyed hints, and every query reconstructs the target twice. A per-record authenticator lets the client keep whichever reconstruction verifies, so its visible behaviour is the same unless both hints are contaminated. The ratio of "both verified" to "one verified" outcomes also gives a free estimate of how much of the database the server has corrupted.
Core Claim
Take a preprocessing PIR scheme with invertible-PRF hint lookup and give each index two hints drawn from two independent keys. Suppose the server has corrupted $k$ records before the queries begin. A query's outcome then depends on the queried index only when both of its hints contain a corrupted record. In the standard one-record-per-chunk hint structure of Piano, a hint containing $x$ includes a given record from another chunk with probability $1/\sqrt{N}$. This gives
$$ \Pr[\text{query-dependent failure}] \;\le\; \Big(\tfrac{k}{\sqrt{N}}\Big)^{2} \;=\; \frac{k^{2}}{N}, $$
where the square comes from the independence of the two keys. With a single hint the same quantity is $k/\sqrt{N}$.
Corruption of the online answers leaks nothing. Each submitted set looks uniformly random to the server, so whatever it corrupts is independent of $x$; it can deny service but cannot learn from it. The scheme keeps Plinko's near-constant lookup and update costs at a constant-factor storage overhead (two tables), which is consistent with the storage–time lower bound $r \cdot t = \Omega(N)$ of Limits of Preprocessing for Single-Server PIR.
The guarantee is statistical. Leakage is bounded by $k^2/N$ per query, not eliminated. That weakness is stated up front, and the experiments are designed to decide whether the trade is worth making against the main alternative, described next.
Relation to Prior Work
Three works motivate the design and one constrains it.
Piano supplies the hint structure: $\sqrt{N}$ chunks, PRF-seeded sets with one element per chunk, and punctured-and-plugged queries. We keep that structure but add a second independent covering.
Plinko supplies the selective-evaluation mechanism. Its invertible PRF, built from a pseudorandom multinomial sampler, finds the hints containing $x$ in near-constant time and pinpoints the hints touched by an update. We run two instances and inherit its update path unchanged, which Plinko itself does not secure against a malicious server.
Crust is the closest competitor and constrains the design. It defeats selective failure with "crumbs," individual random records downloaded offline that plug the hole left by removing the target index. It does this on top of Piano's linear local hint scan and without addressing updates. Our design differs in three ways. It uses redundancy across two keyed coverings rather than stored plaintext records. It inherits update support from the invertible PRF. And it is weaker in the worst case, since its leakage grows as $k^2/N$.
The linear-scan verifiable schemes, VeriSimplePIR and Verifiable PIR with Small Client Storage, show that full verifiability is achievable when the server pays $O(N)$ work. They mark the regime we are trying to leave.
The privacy of the query set depends on the target being hidden in the submitted set. This is the PIR counterpart of pseudorandomness at a punctured point. Standard puncturing exposes the punctured point (Privately Constrained PRFs from DCR), which is why we rely on uniform query sets rather than shipping punctured keys.
The physics papers supply only the measurement logic, not data. We use the ratio of two tag yields to cancel an unknown total.
Research Program
The work has three parts.
The first part is the construction. Records carry authenticators: a publisher signature, or a membership proof against a public digest. The client builds two Plinko-style hint tables under independent keys $K_1$ and $K_2$. For a query on $x$, it inverts both keys to find hints $h_1$ and $h_2$, sends two punctured-and-plugged sets, reconstructs candidate values $y_1$ and $y_2$, and outputs whichever verifies. It then refreshes both consumed hints from backups. This action is identical across the four outcomes (both verified, only $y_1$, only $y_2$, neither), so the only query-dependent event is double failure.
The second part is proof. We will prove the $k^2/N$ bound against a server that chooses its corruptions adaptively during the offline stream. We will also check whether hint refresh and Plinko-style updates add any further dependence on $x$. Updates are the delicate case, because an updated record must be patched in both tables. The proof must show that the patch traffic, which is $O(\log N)$ communication per key in Plinko, reveals nothing about which hints were contaminated.
The third part is a lightweight audit statistic built on the double-tag analogy. Let $n_{2}$ count queries where both reconstructions verify and $n_{1}$ count queries where exactly one does. Under corruption density $\rho$, the ratio $n_1/n_2$ estimates the per-hint contamination rate without the client knowing $k$, in the same way the collider ratio cancels the unknown pair count. A stateful client can then report a calibrated estimate of server misbehaviour, in the spirit of the covert auditing in Verifiable PIR with Small Client Storage.
Baselines
The naive reference points are a linear-scan PIR and Plinko without any malicious protection. The linear scan bounds what verifiability costs when the server touches everything. For it we use SimplePIR timings as reported through Piano, about 11 seconds on a 100GB database, against Piano's 73ms. Unprotected Plinko gives the floor on overhead. We count our design as acceptable if it stays within roughly a factor of two of that floor in online server time and client lookup time, since two reconstructions are inherent.
The strongest existing method is Crust. It reports 6.16 milliseconds of server computation for a verifiable query on a 32GB database and 1000x faster online computation than VeriSimplePIR. Its verifiability adds a factor of 2 to 3 to online computation. We will run Crust and our scheme on the same synthetic databases, from 32MB to 32GB with up to 1 billion records, on the same machine. Both will receive equal parameter-tuning effort, and both will be held to equal client storage budgets where possible.
Beating Crust means one of two things. On static databases we must match its online server time within a small factor. On update-heavy workloads we must outperform it, or Plinko-plus-crumbs, in combined update latency, communication, and client storage, while keeping measured selective-failure leakage within the $k^2/N$ bound.
Two ablations isolate the key ingredient. The first is single hint plus authentication: Plinko with record authenticators but only one key, which should leak at rate $k/\sqrt{N}$. The second is two hints, one key: two preimages taken from a single invertible PRF when available, which tests whether independent keys matter.
A third composite baseline, Plinko plus crumbs, attaches Crust's technique to invertible-PRF lookup. It is the most dangerous comparison, and the next section explains why.
Why not just…?
Why not just bolt Crust's crumbs onto Plinko? This is the real threat. If crumbs carry over cleanly to Plinko's update setting, the result has stronger, non-statistical protection and our scheme loses. Our hypothesis is that crumbs, being stored plaintext records, go stale when records change. Refreshing a stale crumb risks revealing which records the client holds unless the refresh is itself made oblivious. Two keyed hint tables, by contrast, update through the same invertible-PRF path Plinko already uses. We will implement Plinko-plus-crumbs with the most careful crumb-refresh policy we can design and measure update cost and storage under identical workloads. If it matches us on all axes, we will report that and reduce our contribution to the audit statistic.
Why not just repeat the query twice with the same hint table? Two hints drawn from one key may cover overlapping records. If they do, contamination is correlated and the squared bound fails. Plinko's inverter already returns every hint containing $x$, so the same-key ablation is cheap to run. If it achieves the same empirical leakage, the second key is unnecessary and the design simplifies. The experiment settles this directly.
Why not just authenticate records with signatures or a Merkle digest? Authentication detects corruption but does not hide when the client detects it. With one hint, the moment of failure is the leak. The single-hint-plus-authentication ablation measures exactly this, and it should leak at $k/\sqrt{N}$ rather than $k^2/N$.
Why not just use a linear-scan verifiable scheme? These are fully verifiable but pay $O(N)$ server work. Crust's reported 1000x online gap over VeriSimplePIR is the evidence that this regime is too slow for large databases. Verifiable PIR with Small Client Storage does reach 12–17ms at 16GiB with a 512KiB hint, so we include it as a reference point for the storage-constrained setting rather than dismissing it.
Proposed Experiments
Leakage under attack. The decisive check is an attack simulation. An adversarial server corrupts $k$ records during the offline stream, choosing them uniformly, by clustering, and adaptively. Its goal is to tell apart two query indices that the client might be fetching. We will measure its empirical distinguishing advantage over many trials and plot it against $k$ for $N$ from $2^{20}$ to $2^{30}$. The proposal succeeds if the double-key scheme follows $k^2/N$ while the single-hint ablation follows $k/\sqrt{N}$. It fails if same-key pairs leak equally little, which would make independent keys unnecessary, or if leakage exceeds the bound, which would indicate correlation we did not model.
Systems performance. The second check reproduces Crust's synthetic database range and Piano's 100GB, 1.6-billion-entry setting. We will report online server time, client lookup time, client storage (Piano reports 839MB of hints at 100GB, the reference point for the two-table overhead), offline streaming bandwidth, and update time and communication. Update workloads will change between 0.01% and 1% of records between queries.
Audit statistic. The third check validates the double-tag audit. We plant known corruption densities and test whether the $n_1/n_2$ estimator recovers them, with confidence intervals that narrow at the expected $1/\sqrt{Q}$ rate in the number of queries $Q$. That rate follows because the estimator is a ratio of binomial counts.
Plinko, the Optimal single-server PIR construction, and the DCR constrained-PRF paper report no empirical numbers. For those comparisons we will rely on our own implementations and say so explicitly.
References
- Plinko: Single-Server PIR with Efficient Updates via Invertible PRFs
- Absolute Measurement of Hadronic Branching Fractions of the<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:msubsup><mml:mi>D</mml:mi><mml:mi>s</mml:mi><mml:mo>+</mml:mo></mml:msubsup></mml:math>Meson
- Improved measurements of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:msup><mml:mi>D</mml:mi><mml:mn>0</mml:mn></mml:msup><mml:mo stretchy="false">→</mml:mo><mml:msup><mml:mi>K</mml:mi><mml:mo>−</mml:mo></mml:msup><mml:msup><mml:mo>ℓ</mml:mo><mml:mo>+</mml:mo></mml:msup><mml:msub><mml:mi>ν</mml:mi><mml:mo>ℓ</mml:mo></mml:msub></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:msup><mml:mi>D</mml:mi><mml:mo>+</mml:mo></mml:msup><mml:mo stretchy="false">→</mml:mo><mml:msup><mml:mover accent="true"><mml:mi>K</mml:mi><mml:mo stretchy="false">¯</mml:mo></mml:mover><mml:mn>0</mml:mn></mml:msup><mml:msup><mml:mo>ℓ</mml:mo><mml:mo>+</mml:mo></mml:msup><mml:msub><mml:mi>ν</mml:mi><mml:mo>ℓ</mml:mo></mml:msub></mml:math>
- Piano: Extremely Simple, Single-Server PIR with Sublinear Server Computation
- Limits of Preprocessing for Single-Server PIR
- Crust: Verifiable And Efficient Private Information Retrieval with Sublinear Online Time
- VeriSimplePIR: Verifiability in SimplePIR at No Online Cost for Honest Servers
- Verifiable PIR with Small Client Storage
- Privately Constrained PRFs from DCR: Puncturing and Bounded Waring Rank