Sequential Random Sampling PIR with Multiple Colluding Servers in DNA-Based Data Storage

• DNA storage uses unordered pools of synthetic strands recovered by sequencing, and sequencing cost and latency motivate reducing the number of reads.Source: §I · p. 1
• Many existing PIR schemes assume direct access to specific files and server computation over stored data, assumptions that do not hold for unordered DNA strands.Prior DNA-oriented PIR schemes were proposed to address this mismatch.Source: §I · p. 1
• The model partitions files without replication among equal-size random-sampling servers, with adaptive server selection and stopping based on observed responses.The paper considers the worst case in which all servers collude, and measures leakage from their combined responses.Source: §I · p. 1
• For equal-size colluding servers, the paper derives general tradeoff lower bounds, proves one tight for α = 2, and constructs schemes for arbitrary server sizes.The arbitrary-size schemes apply single-server schemes to randomly selected subsets of servers.Source: §I · p. 1

• A random-sampling server returns one of its α stored files independently and uniformly with replacement; retrieval therefore requires repeated queries until the target appears.Source: §II · p. 2
• A scheme may stop or choose the next server based on the desired file and prior returned files, and must recover the target from its response sequence.Source: §II · p. 2
• Files are uniformly likely to be desired and partitioned without replication among m equal-size servers, so n = mα.Source: §II · p. 2
• The least-cost scheme repeatedly queries the server holding the desired file until it is returned, costing α queries in expectation while revealing the desired file identity.Source: §II · p. 2
• The full-download scheme queries servers in fixed order until every file is collected, costing nHα expected queries and yielding zero leakage.Source: §II · p. 2
• The system-model section frames the objective as characterizing the region of achievable download-cost and privacy-leakage pairs.Source: §II · p. 2

III. LOWER BOUNDS ON THE COST-LEAKAGE TRADEOFF

• For each server, E[|R_Bj|] ≥ E[g(Dj)] ≥ g(E[Dj]), where g(k) is the expected queries needed to obtain k distinct files.Summing these per-server bounds relates total download cost to the numbers of distinct files returned.Source: §III · p. 3
• E_m,α(L) ≥ max{α, m·g(α^2−L)} gives a download-cost lower bound combining the per-file retrieval floor with a leakage-dependent bound.The expected queries are at least α because the desired file is sampled from its server with probability 1/α per query.Source: §III · p. 3
• The privacy-leakage lower bound minimizes an entropy expression over feasible probabilities for the queried server and the target file’s position among distinct returns.The feasible probabilities are constrained by the scheme’s induced distributions and expected download cost.Source: §III · p. 4
• For α = 2, the privacy lower bound is tight, but its optimization has order mα^(m+1) variables and is hard to solve for large m and α.The section states tightness for α = 2; the complexity caveat concerns large values of both parameters.Source: §III · p. 4

IV. CONSTRUCTIONS OF SRS DNA PIR SCHEMES

• The section gives two constructions, one attaining the lower bound for α = 2 and another applicable to any integers m and α.The constructions are presented as the section’s two approaches.Source: §IV · p. 5
• The paper gives two constructions of SRS DNA PIR schemes: the first shows that the lower bound in Theorem 3 is tight for α = 2, while the second works for any integers m and α.Source: §IV · p. 5
• The second construction works for any integers m and α.Source: §IV · p. 5

A. Optimal Scheme for Servers of Size Two

• The scheme samples a server order, queries through the server holding the desired file, then draws a terminal coverage vector and continues sampling as needed.After the first query to the desired-file server, it distinguishes whether the desired file arrived immediately or requires a second distinct file.Source: A. Optimal Scheme for Servers of Size… · pp. 5–6
• For a terminal coverage vector d, expected queries equal the number of visited servers plus two for each visited server from which both files are obtained.For α = 2, the first pass uses one query per visited server, and obtaining the second distinct file takes two expected queries.Source: A. Optimal Scheme for Servers of Size… · p. 5
• For α > 2, the construction’s key inference no longer works: one query reveals only whether K = 1 or K ∈ [2, α].With two files per server, the first query distinguishes K = 1 from K = 2.Source: A. Optimal Scheme for Servers of Size… · p. 6

B. Construction for Servers of Any Size

• For any m and α, the s-subset construction applies a single-server scheme to s servers, selecting a uniformly random subset containing the server that stores the desired file.The ordering of queried servers must not depend on which server stores the desired file, or that order would reveal its location.Source: B. Construction for Servers of Any Size · p. 6
• For a single-server scheme with download cost E and privacy leakage L, the s-subset scheme has download cost sE and privacy leakage L + log m.This holds for every s ∈ [m].Source: B. Construction for Servers of Any Size · p. 6
• With s = 1 and the full-download single-server scheme, the construction has download cost αHα and privacy leakage log α when m = α.The user downloads all files from the server storing the desired file.Source: B. Construction for Servers of Any Size · p. 6
• Mixing two schemes gives a convex combination of their download costs and an upper bound on privacy leakage by the same convex combination.This interpolation can cover download-cost gaps left by subset-size choices, such as (3, 4) when α = 2.Source: B. Construction for Servers of Any Size · pp. 6–7

V. NUMERICAL COMPARISON

• For α = 2 and m = 3, Construction 1 attains the tight Theorem 3 lower bound, while mixed s-subset schemes lie close to the optimal tradeoff.The Corollary 1 lower bound is not tight, and computing the optimal tradeoff requires numerically solving the optimization problem.Source: §V · p. 7
• For α = 5 and m = 4, Theorem 3 gives a tighter lower bound than Corollary 1, and mixed s-subset schemes are close to it.The optimal tradeoff lies between those schemes and the Theorem 3 lower bound, so it is determined up to a small gap for these parameters.Source: §V · p. 7

VI. CONCLUSION AND EXTENSIONS

• The study concerns download cost versus privacy leakage for equal-sized, colluding random-sampling servers.Source: §VI · p. 7
• Fig. 2 plots privacy leakage against download cost for α = 5 and m = 4.Source: Figure 2 · p. 7
• Schemes for servers of any size are close to a lower bound in the paper’s numerical examples.The optimal tradeoff for servers storing more than two files remains unresolved.Source: §VI · p. 7
• The optimal tradeoff for servers storing more than two files remains open; partial collusion, unequal server sizes, and overlapping contents are further directions.Source: §VI · p. 7

AI STATEMENT

• Claude helped write the numerical-evaluation code and produce Figs. 1 and 2 in Section V.Source: AI STATEMENT · p. 7
• Claude and ChatGPT were used to revise wording written by the authors in the other sections.Source: AI STATEMENT · p. 7
• The authors take full responsibility for the paper’s content, including its results, constructions, and proofs.Source: AI STATEMENT · p. 7