How Much Does Bad Randomness Leak in Coded Private Retrieval?

Private information retrieval (PIR) lets a user fetch one record from a database spread across several servers without any single server learning which record was fetched. The recent protocols that work over practical, cheaply repairable storage codes all rest on the same assumption: the user holds a supply of perfectly uniform random symbols, and each server's query is masked by that randomness so completely that it is statistically independent of the requested index. Physical randomness does not behave that way. DRAM and memristor noise sources are biased and correlated, and sampling a uniform field element through floating-point arithmetic introduces drift. Nobody has measured what happens to a coded PIR protocol's privacy when its randomness is imperfect. Nobody has measured how much of that imperfection reaches what a server actually observes, either.

This note proposes that measurement, run in a setting where the privacy matters. An auditor checking a city's reported emissions retrieves inventory records for the grid cells that its sensors' "footprints" cover, meaning the upwind areas that influence each sensor. The pattern of those retrievals reveals which region is under scrutiny. The central claim is that leakage should be predicted from how sensitive a protocol's server view is to source bias, not from the raw source's entropy deficit, and that this sensitivity differs substantially across code constructions. If the claim holds, practitioners get a principled budget for how much randomness to extract per query. If it fails, and leakage simply tracks the source deficit, the recommendation is to extract fully every time, and we learn that too.

Core Claim

Write the query sent to server $n$ as $Q_n = f_n(\theta, S)$, where $\theta$ is the requested record index and $S$ is the user's private randomness. The protocol is private when $Q_n$ has the same distribution for every $\theta$ whenever $S$ is uniform. If instead $S$ is within statistical distance $\varepsilon$ of uniform, the triangle inequality gives

$$\max_{\theta,\theta'} \mathrm{TV}\big(Q_n \mid \theta,\; Q_n \mid \theta'\big) \le 2\varepsilon ,$$

where TV is total variation distance. This worst-case bound treats every bit of bias as potentially visible. Two things about the gap between the bound and reality are unknown, and they are what we will measure. The first is how far below $2\varepsilon$ the true leakage sits for real code families and real bias patterns, since much of $S$ is cancelled algebraically at decoding and may never shape the server view. The second is whether schemes built to use little randomness are more fragile per unit of bias. The weakly secure schemes of On the Information Leakage in Private Information Retrieval Systems are the main example: they use uniformly decomposable codes, meaning codes that split evenly into pieces the user can choose among at random, to reach zero individual leakage with no shared key and message size $N-1$. The asymmetric, decomposition-based schemes of Improved Private Information Retrieval for Coded Storage From Code Decomposition are also candidates. Our hypothesis is that these lean schemes turn source bias into view bias more directly than symmetric-code protocols, so they need proportionally more extraction.

Relation to Prior Work

Two papers motivate the gap. The PIR-over-linear-codes line establishes the protocols we test, and in every case it assumes ideal randomness. Achieving Maximum Distance Separable Private Information Retrieval Capacity With Linear Codes and An MDS-PIR Capacity-Achieving Protocol for Distributed Storage Using Non-MDS Linear Codes show that the code's symmetry, rather than the maximum-distance property, is what lets query noise cancel. Local Reconstruction Codes: A Class of MDS-PIR Capacity-Achieving Codes and Asymmetry Helps extend capacity to locally repairable codes, which are codes where a failed server can be rebuilt from a small group of others, by using unequal download sizes. On the Information Leakage in Private Information Retrieval Systems maps the tradeoff between leakage and shared randomness. All of these are proofs under uniform randomness, and none implements or stress-tests the random source. Real-time seedless post-processing for quantum random number generators supplies an extractor but never feeds it to a downstream protocol. It builds a deterministic two-source extractor on an FPGA that runs at 64 Gbps against a prior 18.8 Gbps, under the assumption that each source keeps more than half its bits' worth of min-entropy (worst-case unpredictability).

Other work supplies methods we reuse. Seeded hashing via the leftover hash lemma, analyzed in Games for extracting randomness, On Recent Advances in Key Derivation via the Leftover Hash Lemma, and Why Simple Hash Functions Work, gives our standard extractors. Random Variate Generation with Formal Guarantees shows that library samplers drift from their stated distributions and that exact samplers use 2.6x to 142x fewer random bits than GSL. We use its exact-sampling approach to draw uniform elements of prime fields, and we compare it against the floating-point floor(u*q) idiom. The weak sources we emulate follow QUAC-TRNG for DRAM and A novel true random number generator based on a stochastic diffusive memristor for memristors.

The application borrows its workload from the atmospheric inversion studies. Mesoscale inversion: first results from the CERES campaign with synthetic data and Lessons from a 6-year atmospheric inversion over Paris define realistic sensor footprints and gridded inventory priors. The Paris study notes that its data ingestion is open and centralized. We do not propose a new inversion method. The inversions only tell us which records get queried and how often.

Research Program

We will build an open testbed. It will implement five PIR protocols over one shared record store: replication PIR, MDS-coded PIR, locally-repairable-code PIR with asymmetric downloads, the decomposition protocol of Lin et al. applied to their [10,6] code and to larger locally repairable codes of length 20 to 40, and the weakly secure uniformly-decomposable scheme with no shared key. For field sizes and code lengths where it is feasible, we compute the exact distribution of each server's view given any source distribution on $S$. The engine enumerates or convolves over $S$, which is possible because $f_n$ is linear. Where exact computation is too expensive, we use plug-in estimators and trained distinguishers on sampled views.

Randomness comes from a controlled ladder of sources. The ladder runs from synthetic Markov-biased bitstreams with a set min-entropy rate, to emulated DRAM and memristor streams, to raw bits from a commodity-DRAM TRNG built following QUAC-TRNG. Each source is fed to the protocols in one of six ways: unprocessed, through floating-point field sampling, through exact field sampling, through 2-universal seeded hashing, through a two-source inner-product extractor, or through an operating-system cryptographic generator. For each combination of protocol, source, and post-processing, we record the worst-case view distinguishability, the leakage accumulated over sequences of queries, the number of raw bits consumed per query, and the wall-clock cost of extraction.

Running the decomposition algorithm on codes beyond $n=10$ has a side benefit. It closes part of the scaling gap that Improved Private Information Retrieval for Coded Storage From Code Decomposition acknowledges, and it lets us check numerically whether that paper's Conjecture 1, $\tau^* = \max_r r/d_r(\mathcal{C})$, where $d_r$ is the $r$-th generalized Hamming weight, predicts the achieved rate on those codes.

Baselines

The naive reference point is raw weak bits fed straight into each protocol, with no extraction. This is the configuration whose leakage is unknown, and it bounds the problem from below. The practical reference is the operating system's cryptographic generator. It is what a competent engineer would deploy, and it should show view leakage indistinguishable from uniform at our measurement resolution. Every other method is judged against it on cost as well as leakage.

The strongest principled competitor is full seeded extraction with 2-universal hashing, following the leftover hash lemma analyses cited above. It is run on the same source bits and set to the output error $\varepsilon$ that the $2\varepsilon$ bound requires for a target leakage. It has a known guarantee and is fast. Our alternative is scheme-aware extraction, which extracts only as many bits as the measured view sensitivity demands. That alternative beats full extraction only if it reaches the same measured leakage while consuming measurably fewer raw source bits per query. The seedless two-source extractor of Li and Zhou is run whenever two emulated sources meet its min-entropy-rate-above-one-half condition. When a source falls below that threshold, we report failure to meet the condition, not a leakage number.

On the retrieval side, the rate baselines are trivial download-everything, replication PIR, and MDS-PIR. For decomposition protocols, the reference number is Lin et al.'s reported PIR download rate of approximately 0.343 on the [10,6] code, against 0.333 for their Protocol A. Our reimplementation must reproduce 0.343 before any larger-code result is trusted. For empirical leakage under weak randomness in any coded PIR protocol, we found no reported result on Lacuna, so our measurements have no published figure to beat and serve as the first reference point. The key ablation holds the protocol and source fixed and varies only the post-processing: none, floating-point sampling, exact sampling, full hashing, and scheme-aware hashing. This isolates how much of the leakage comes from sampling arithmetic and how much from source bias.

Why not just…?

Why not just use the operating system's cryptographic generator and stop there? This is the most serious alternative, and for deployments that accept computational security it is probably sufficient. We keep it as the ceiling rather than argue against it. The proposal remains useful for three reasons. Information-theoretic PIR schemes claim a guarantee that does not rest on computational hardness, and a pseudorandom generator quietly replaces that guarantee with one that does. Floating-point field sampling can reintroduce bias downstream of an excellent generator. And sensor-side or embedded deployments may draw directly on hardware noise. If our measurements show that raw and float-sampled sources already leak negligibly across all protocols, we will report that coded PIR is robust to realistic randomness, which is a clean negative result.

Why not just extract fully every time, since hashing is cheap? Hashing throughput is high, so saving extraction cost matters only when entropy is scarce, for example with slow memristor sources or battery-limited nodes. If scheme-aware extraction saves few raw bits, the budgeting claim fails. The leakage-sensitivity measurements would still tell practitioners which protocols are dangerous without extraction, and the ablation above settles which case holds.

Why not just download the whole inventory, or store it with an MDS code? Downloading everything achieves perfect privacy at rate $1/K$, where $K$ is the number of records. For national inventories at hourly, 1 km resolution, $K$ is large enough that this cost dominates, and we report it as the reference line. MDS codes have established PIR capacity, but they need expensive repair when a server fails, which is why storage systems use locally repairable codes (Local Reconstruction Codes). Both are included as protocols in the testbed, so any privacy advantage they show under weak randomness will appear directly in the results.

Proposed Experiments

The first decisive check is on synthetic sources. For each protocol, we sweep the source min-entropy rate from 0.3 to 1 and plot measured view distinguishability against the $2\varepsilon$ bound. The hypothesis predicts that the ratio of measured leakage to the bound differs across protocols by at least an order of magnitude, with the uniformly decomposable, no-shared-key scheme the most sensitive. A flat ratio across protocols would refute the scheme-sensitivity claim.

The second check measures arithmetic drift in isolation. We compare 32-bit and 64-bit floating-point sampling of uniform elements of prime fields around $2^{16}$ against exact sampling, using an ideal bit source, to test whether drift alone produces measurable leakage.

The third check is the application test. We build a coded store of gridded emission priors with the structure of the Paris inventory setup, meaning an hourly 1 km grid with rural cells filled from ODIAC. We then generate query sequences from sensor footprints for the two CERES towers, Marmande and Biscarosse, over a 300 by 300 km domain. An adversarial server trains a classifier to infer from its views which tower's footprint region is being audited. Chance is 50 percent. We report the adversary's accuracy for every combination of source and post-processing, as a function of the number of queries observed. The proposal succeeds if raw or float-sampled sources yield above-chance inference that grows with the number of queries, while CSPRNG, full hashing, and scheme-aware hashing all hold the adversary at chance. Among those three, the result that decides the budgeting claim is how many raw source bits each consumes per query.

The final check is the rate-and-runtime table for decomposition on codes of length 20 to 40. It reports the rate achieved, the decomposition search time, and whether Conjecture 1's $\max_r r/d_r$ matches the achieved rate on each code.