Private Information Retrieval for Large-Scale DNA-Based Data Storage

Gökberk Erdoğan, Daniella Bar-Lev, Rawad Bitar, Antonia Wachter-Zeh, Zohar YakhiniarXiv 2026 · arXiv

TL;DR

This paper introduces the first multi-server Private Information Retrieval (PIR) protocols specifically designed for synthetic DNA-based data storage. By exploiting the low cost of random primer synthesis and the parallel nature of PCR amplification, the proposed protocols achieve information-theoretic privacy without requiring economically prohibitive targeted primer synthesis or impossible in-pool DNA computations.

What Problem Does This Paper Address?

DNA-based data storage offers unprecedented density and durability for long-term archiving, but its access model is fundamentally different from conventional electronic memory. In classical digital PIR, a user hides their query by distributing it across multiple non-colluding servers using algebraic operations like XOR. However, DNA storage relies on biochemical processes like Polymerase Chain Reaction (PCR) for random access via unique sequence "barcodes" (addresses).

Directly porting classical PIR to DNA would require a server to synthesize a unique primer for every single file in the database per query—an $O(n)$ operation that is economically impossible for large-scale databases. Furthermore, DNA pools cannot perform in-memory algebraic computations before sequencing. This paper addresses the challenge of designing efficient, privacy-preserving retrieval protocols compatible with the constraints of molecular biology.

Methods

The authors propose a framework where data is stored as DNA strands containing a unique barcode, a payload, and a universal primer binding site.

Fig. 1. A schematic representation of the database setup. From left to right: the universe U, the set of barcodes in the database B ⊆U, and the corresponding database D, where the barcodes act as indices of the stored strands. The universal primer u is not depicted as it is the same for all records.

Instead of targeted queries, the user generates a query by biochemically synthesizing a large pool of random primers combined with the single target primer of interest.

Fig. 2. A schematic representation of the user’s query preparation.

They present two main protocols using a two-server setup:

  1. Base Counter Approach: Each server performs PCR with the query primers, sequences the results, and counts the occurrences of each nucleotide (A, C, G, T) at every position. The user reconstructs the file by finding the differences between the servers' counts.
Fig. 3. Schematic representations of the subroutines Answer1 and Recovery1.
  1. XOR Approach: To drastically reduce communication overhead, servers convert sequenced strands into binary sequences digitally and return a single compressed sequence representing the bitwise XOR of all retrieved strands.
Fig. 4. Schematic representations of the subroutines Answer2 and Recovery2.

The paper analyzes these protocols across three scenarios varying in the user's biochemical capabilities (e.g., whether they can filter out the target barcode from the random pool).

Datasets

Not discussed in the paper. (The work is entirely theoretical and validated through mathematical proofs and probabilistic simulations rather than empirical datasets).

Key Insights and Ideas

  • Exploiting Molecular Asymmetry: While targeted DNA synthesis is expensive, generating degenerate (random) primer pools is highly cost-effective, and PCR amplifies multiple targets simultaneously without increasing time. The authors flip the PIR paradigm to exploit what biology does cheaply.
  • The Danger of Fixed-Size Pools: Intuitively, one might think a random pool of a fixed size $r$ provides privacy. However, the authors prove that a fixed $r$ always leaks information because the server can probabilistically deduce whether the target is in the pool based on the total count of amplified strands.
Fig. 5. Leakage for fixed r. u ≈1.1 · 1012, n ≈2.7 · 109. H(F) = 31.36.
  • Binomial Sampling for Perfect Privacy: To achieve perfect information-theoretic privacy (zero leakage), the random primers must be sampled according to a Binomial distribution ($Bin(u-1, p)$) with $p=1/2$.
Fig. 6. Leakage for fixed p. u ≈1.1 · 1012, n ≈2.7 · 109. H(F) = 31.36.

Key Results

  • The XOR Approach achieves a highly efficient PIR rate of $1/m$ (where $m=2$ servers), requiring the download of only $2\ell$ bits per server, compared to the $O(\ell \log n)$ bits required by the Base Counter Approach.
  • Under Scenario 1 (where the user can ensure the target barcode isn't accidentally generated in the random pool), perfect information-theoretic privacy ($\epsilon = 0$) is mathematically proven when the binomial sampling probability $p = 1/2$.
  • For scenarios where the user cannot check the random pool (Scenarios 2 and 3), the authors provide explicit bounds on the number of server pairs needed to keep the retrieval failure probability negligibly low ($m \ge 2\lambda / \log(1/p)$).

Limitations and Future Work

The current framework assumes a noiseless biochemical environment (perfect PCR amplification, no cross-talk between similar barcodes, and perfect pool copying). The authors explicitly note that future work must address real-world experimental noise, including:

  • PCR primer cross-talk: Where primers accidentally amplify unintended, similar barcodes.
  • Strand dropouts and amplification bias: Unequal representation of sequences during PCR.
  • Sequencing errors: Noise introduced during the digital read-out phase.
  • Imperfect pool copying: The impact of stochastic sampling when splitting molecular volumes.

Summary updated

Abstract

We investigate Private Information Retrieval (PIR) in the context of synthetic DNA-based data storage. While PIR is a well-studied primitive for digital databases, extending it to DNA-based databases presents unique challenges arising from biochemical query mechanisms and their complexity. We propose two approaches for adapting two-server PIR protocols to DNA-based storage, balancing privacy, efficiency, and feasibility. These approaches illustrate how information-theoretic privacy trade-offs manifest in DNA-based storage systems.
BibTeX
@misc{erdogan2026private,
  author = {Gökberk Erdoğan and Daniella Bar-Lev and Rawad Bitar and Antonia Wachter-Zeh and Zohar Yakhini},
  title = {{Private Information Retrieval for Large-Scale DNA-Based Data Storage}},
  year = {2026},
  eprint = {2606.14557},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.14557},
}

Loading related content...

Figure