Source-linked AI summary
The Capacity of Private Information Retrieval from Coded Databases
Karim Banawan, Sennur Ulukus
TL;DR
The paper asks for the information-theoretic capacity of privately retrieving one message from non-colluding databases storing coded data. It analyzes linear MDS-coded storage and derives the exact capacity, showing that it depends only on the storage code rate and number of messages. The result establishes a storage–retrieval tradeoff and extends classical replicated-database PIR to coded databases.
Problem
Private information retrieval needs efficient retrieval from non-colluding databases without revealing the desired message identity, while coded storage introduces a storage-reliability and retrieval-cost tradeoff.
Method
The paper uses information-theoretic achievability and converse arguments for linear coded databases whose every K generator-matrix columns are independent.
Results
C = (1 + Rc + Rc^2 + ⋯ + Rc^(M−1))^-1 = (1 − Rc)/(1 − Rc^M), and capacity depends only on Rc and M, not code structure or database count.
Takeaways & Limitations
The result implies optimal separation between storage-code design and PIR-scheme design for fixed code rate and establishes a fundamental storage–retrieval tradeoff.
Takeaways & Limitations
The model restricts storage to linear codes whose every K columns are linearly independent and treats (N, K) dimensions as fixed rather than growing with message size.
Abstract
from arXiv · showhide
We consider the problem of private information retrieval (PIR) over a distributed storage system. The storage system consists of $N$ non-colluding databases, each storing a coded version of $M$ messages. In the PIR problem, the user wishes to retrieve one of the available messages without revealing the message identity to any individual database. We derive the information-theoretic capacity of this problem, which is defined as the maximum number of bits of the desired message that can be privately retrieved per one bit of downloaded information. We show that the PIR capacity in this case is $C=\left(1+\frac{K}{N}+\frac{K^2}{N^2}+\cdots+\frac{K^{M-1}}{N^{M-1}}\right)^{-1}=(1+R_c+R_c^2+\cdots+R_c^{M-1})^{-1}=\frac{1-R_c}{1-R_c^M}$, where $R_c$ is the rate of the $(N,K)$ code used. The capacity is a function of the code rate and the number of messages only regardless of the explicit structure of the storage code. The result implies a fundamental tradeoff between the optimal retrieval cost and the storage cost. The result generalizes the achievability and converse results for the classical PIR with replicating databases to the case of coded databases.
1 Introduction
The paper extends private information retrieval from replicated to coded databases, motivated by storage reliability and the need to reduce retrieval and storage costs. It derives the exact capacity for MDS-coded databases and shows that it depends only on code rate and message count.
- Classical PIR: Classical PIR retrieves a desired message from N identical, non-communicating databases without revealing its identity to any individual database.Its objective is to maximize desired information bits per total downloaded bits under privacy constraints.
- Motivation: Erasure coding can provide storage reliability with less storage cost than repetition coding, which motivates PIR schemes for coded databases.An (N, K) MDS code tolerates up to N − K node failures or erasures while allowing recovery from any K storage nodes.
- Prior work: Prior coded-PIR work included explicit schemes and storage–retrieval tradeoffs, while the best known MDS-coded achievable rate was R = 1 − Rc.The cited scheme is universal but does not establish the exact capacity stated here.
- Contribution: The paper studies non-colluding coded databases under an information-theoretic formulation, restricting the storage code to linear codes whose every K columns are independent.This condition is equivalent to using MDS codes, and the model includes replicated and previously studied coded cases.
- Contribution: The exact PIR capacity is C = (1 + Rc + Rc^2 + ⋯ + Rc^(M−1))^-1 = (1 − Rc)/(1 − Rc^M), independent of generator-matrix structure.The result also improves the best-known lower bound and reduces to the repetition-coded case when Rc = 1.
- Proof strategy: The achievable scheme decodes interference and the desired message through K linearly independent equations, while the converse uses independence across any K storage nodes.The converse generalizes the classical inductive argument through interference lower-bound and interference-conditioning lemmas.
2 System Model
The system stores M independent messages using a linear (N, K) code, with each database holding coded projections generated from message rows. Users send queries, databases return deterministic answer strings, and the desired message must be reliably reconstructed while preserving privacy.
- Storage model: A linear (N, K) distributed storage system stores M independent messages, each represented as a matrix over a sufficiently large finite field.Message elements are selected uniformly and independently, and rows are denoted by w[i]_q.
- Storage model: Each message row is encoded separately through the generator matrix H, whose columns satisfy the required linear-independence condition for the storage code.The resulting coded symbols are stored across the N databases as concatenated projections of all messages.
- Storage model: The code tolerates up to N − K errors by enabling recovery from any K databases.This is the defining reliability property used by the distributed storage model.
- Retrieval protocol: In PIR, each database returns an answer string A[i]_n determined by its query and stored coded bits.The deterministic response relationship allows information-theoretic constraints to be applied through data processing.
- Performance and constraints: The user must reconstruct the requested message reliably from all collected answer strings, and retrieval rate equals message size divided by total download cost.PIR capacity is the supremum of this retrieval rate over all schemes.
- Performance and constraints: The formulation assumes arbitrarily large messages and neglects upload cost relative to download cost.The model reduces to classical PIR when K = 1 and to systematic MDS-coded PIR as a special case.
3 Main Result
The paper gives the exact PIR capacity for coded databases as a function only of the storage code rate and the number of messages. This result is universal across code structures and establishes a storage–retrieval tradeoff.
- Theorem 1 gives the PIR capacity for an (N,K) coded database with code rate R_c and M messages.The supplied theorem passages introduce the exact capacity expression, though its displayed formula is not fully preserved in these excerpts.
- The capacity depends only on R_c and M, not on the generator matrix structure or the number of databases.Therefore, the scheme is universal across coded database systems sharing the same code rate and message count.
- The result makes storage-code/PIR-scheme separation optimal for a fixed R_c.
- As R_c increases, capacity decreases; it approaches 1 as R_c approaches 0 and the trivial all-database retrieval rate as R_c approaches 1.The limiting behavior reflects a tradeoff between storage cost and retrieval download cost.
- For fixed R_c, capacity decreases monotonically with M and converges to 1−R_c as M approaches infinity.The paper explains that more messages require more undesired downloads to conceal the requested message.
- The capacity is strictly larger than the best-known achievable rate R = 1−R_c for every finite number of messages.Repetition coding, with R_c = 1, recovers the classical PIR case.
4 Achievability Proof
The achievable scheme extends classical PIR to coded databases by exploiting symmetry, decoding interference, and using the resulting side information to recover desired coded bits. Query shuffling provides privacy, while repeated downloads across K databases enable reliable decoding.
- 4 Achievability Proof: The scheme generalizes classical PIR by preserving database and message symmetry while adding coded-database decoding steps.The added steps decode interference and desired rows, which are unnecessary in the repetition-coded setting.
- 4.1 Achievable Scheme: Randomly interleaved message-row indices make the rows selected at each database appear independent of the desired message index.The interleaver is private to the user.
- 4.1 Achievable Scheme: The scheme downloads symmetric desired and undesired coded bits across databases and messages to satisfy privacy.The round structure increases the number of undesired equations while preserving the required symmetry.
- 4.1 Achievable Scheme: Groups of K undesired equations from common rows are decoded as aligned sums, producing side information without solving individual components.This interference is then canceled from later equations containing desired-message terms.
- 4.1 Achievable Scheme: The scheme repeats its rounds K times with circularly shifted database order so each desired row is obtained from K databases and reliably decoded.
- 4.1 Achievable Scheme: Uniformly shuffling query order prevents databases from identifying the desired message from the first query.The paper states that this guarantees privacy.
- 4.2 Calculation of the Achievable Rate: The achievable-rate calculation totals desired and undesired equations across the rounds and K repetitions, yielding the stated rate expression.For K = 1, the scheme reduces to the classical achievable scheme and retains its optimality over subsets of messages.
5 Examples
The paper illustrates the scheme with explicit coded-PIR examples, showing how interference is decoded into side information, reused to obtain desired symbols, and repeated across databases for reliable recovery.
- Code (5,3), M = 2: For the (5,3) code with M = 2, three repetitions use circular database shifts so every desired row is received from three databases.
- Code (5,3), M = 2: Grouping coded bits from three databases yields linearly independent equations that decode W2 interference and create side-information rows.
- Code (5,3), M = 2: The decoded side information is canceled from sums involving W1 in the remaining databases, producing additional reliably decodable coded bits.
- Code (5,3), M = 2: In the two-message example, privacy is maintained through symmetric downloads and randomly chosen indices, while interference is fully decoded.
- Three-message example: The three-message construction decodes aligned interference sums, reuses them in later rounds, and then repeats the procedure to decode the desired message.
- Three-message example: The example explicitly avoids solving individual undesired symbols, instead decoding their aligned sum before cancellation.
- Three-message example: In the final round, newly generated side information forms three-message sums before two repetitions complete reliable decoding and query shuffling preserves privacy.
6 Converse Proof
The converse proof derives upper bounds for coded PIR by combining symmetry, privacy, reliability, and independence properties. An induction relation reduces the problem with M messages to a PIR problem with fewer messages.
- Notations and Simplifications: The PIR scheme may be assumed symmetric without changing its retrieval rate.The construction replicates database and message permutations with appropriate time sharing.
- Notations and Simplifications: Privacy permits fixing one database's query independently of the desired message, making its answer independent of that choice.The simplification follows because queries are independent of the desired-message index.
- Independence of Answers: Any K coded databases have statistically independent contents and answer strings under the MDS storage condition.Every K generator-matrix columns are linearly independent, so the corresponding stored contents are statistically equivalent to independent messages.
- Converse Proof for M = 2: For M = 2, the converse lower-bounds interference uncertainty and then upper-bounds the retrieval rate using privacy, reliability, and entropy inequalities.The proof's interference lower bound is the base induction step.
- Converse Proof for M ≥3: The converse proof combines coding, privacy, and interference alignment through independence, fixed-answer privacy, and answer-string relations.These ingredients are identified as the main aspects captured by the key lemma.
7 Conclusions
The paper derives the optimal information-theoretic retrieval rate for PIR from coded, non-colluding databases. Its capacity depends on the storage code rate and message count, generalizes repetition-coded PIR, and exposes a storage–retrieval tradeoff.
- Information-theoretic arguments derive the optimal retrieval rate for any given (N, K) storage code.
- C = (1 − Rc)/(1 − Rc^M) gives the PIR capacity for coded databases.Here Rc is the rate of the storage code and M is the number of messages.
- The optimal retrieval rate is strictly higher than the best-known achievable scheme for any finite number of messages.
- For repetition coding, Rc = 1/N, and the result reduces to the classical PIR capacity.
- The optimal retrieval cost is independent of the storage-code structure and database count, depending only on Rc and M.The result also implies no gain from jointly designing the storage code and retrieval procedure for a fixed code rate.
A Alternative Proof for (77)
The alternative proof establishes the key upper bound used in the converse induction. It relies on the independence of any K answer strings.
- The alternative proof uses independence of any K answer strings to establish the key upper bound in the converse.