Source-linked AI summary
Private Information Retrieval for Coded Storage
Terence H. Chan, Siu-Wai Ho, Hirosuke Yamamoto
TL;DR
The paper asks how to perform private information retrieval from coded storage while controlling download cost for large records. It proposes general linear storage codes and retrieval schemes, derives conditions for privacy and error-free recovery, and characterizes storage–retrieval tradeoffs. For MDS-based storage, randomly constructed retrieval schemes can be optimal or very likely to satisfy privacy and error-free retrieval.
Problem
PIR research largely assumes uncoded storage, whose repeated copies have high storage cost, while this paper studies private retrieval from coded storage with large records and download-focused cost.
Method
The paper proposes a general class of linear storage codes specified by parity-check matrices and associated PIR schemes, then derives conditions for privacy and error-free retrieval.
Results
The paper obtains storage–retrieval tradeoffs, shows optimality for MDS-based storage, and reports that randomly constructed retrieval schemes can be optimal or very likely private and error-free.
Takeaways & Limitations
For large records, the proposed coded-storage framework provides a way to analyze private retrieval through download cost and its tradeoff with storage cost.
Abstract
from arXiv · showhide
Private information retrieval scheme for coded data storage is considered in this paper. We focus on the case where the size of each data record is large and hence only the download cost (but not the upload cost for transmitting retrieval queries) is of interest. We prove that the tradeoff between storage cost and retrieval/download cost depends on the number of data records in the system. We also propose a fairly general class of linear storage codes and retrieval schemes and derive conditions under which our retrieval schemes are error-free and private. Tradeoffs between the storage cost and retrieval costs are also obtained. Finally, we consider special cases when the underlying storage code is based on an MDS code. Using our proposed method, we show that a randomly generated retrieval scheme is indeed very likely to be private and error-free.
I. INTRODUCTION
The paper studies private information retrieval for coded storage, focusing on download cost when records are large. It develops general coded-storage PIR schemes and analyzes privacy, error-free retrieval, and storage–retrieval tradeoffs.
- Motivation: Coded storage reduces storage cost relative to replication but introduces a storage–repair-cost tradeoff.Erasure codes recover lost content from coded data, while repair requires more transferred data than replication.
- Motivation: PIR protects the identity of a retrieved record, but downloading every record has retrieval cost that grows linearly with N.The paper motivates more efficient schemes for private retrieval from cloud storage.
- Related work: Existing PIR work largely assumes uncoded storage, requiring every storage node to store every data record.This paper considers coded storage where that requirement need not hold.
- Related work: Prior coded-storage PIR work achieves very low download cost by allowing the number of storage nodes and storage cost to grow with record size, unlike this paper’s fixed-node setting.The paper contrasts its assumptions with prior work and focuses on large records, where download cost dominates.
- Contributions: The paper permits general underlying storage codes, derives storage–retrieval tradeoffs, and shows optimality when MDS codes are used.It also states that the tradeoff depends on the number of data records.
- Contributions: The proposed framework develops PIR schemes for coded storage and derives sufficient conditions for privacy and error-free retrieval.The paper organizes these results around scheme construction and storage–retrieval tradeoffs.
Notations:
The paper establishes notation for random variables, their realizations, entropy, mutual information, and indexed collections of variables.
- Notations: Entropy is denoted by H(X), mutual information by I(X; Y), and indexed collections such as (Xi, i ∈ α) by Xα.Capital letters denote random variables, lowercase letters their realizations, and calligraphic letters sample spaces.
- Notations: Capital letters denote random variables, lowercase letters denote their realizations, and calligraphic letters denote sample spaces.
- Notations: A set of random variables indexed by α can be written compactly as Xα.
A. System Formulation
The system stores N records across K nodes using a storage code, then retrieves a selected record through randomized queries, node responses, and decoding. Storage cost, retrieval cost, error-free recovery, and privacy are defined for this framework.
- System model: The model contains N independent uniformly distributed records stored across K data storage nodes.The records share a common sample space, and the node contents are generated by a storage code.
- Storage code: The storage code must permit recovery of all records from the node contents, while additional requirements may support repair after node corruption.The formulation allows storage codes to satisfy recovery criteria for failed nodes.
- Cost measures: Storage cost measures bits stored per information bit at each node, using log |Xk| rather than entropy because compression is not assumed.The paper notes that total storage cost differs from its per-node measure by a constant factor K for its code.
- Retrieval scheme: A retrieval scheme generates randomized queries, receives node responses, and decodes the requested record from the queries and answers.The query generation distribution and response mappings specify the retrieval scheme.
- Correctness and privacy: A scheme is error-free when the requested record can always be decoded, and Φ-private when colluding node subsets learn nothing about its identity.The collusion pattern is the collection Φ of node subsets considered for privacy.
- Cost measures: Retrieval cost measures the number of answer bits downloaded per information bit of the requested record.Because records are large, the paper focuses on retrieval cost rather than query upload cost.
B. Achievability
The paper defines N-achievability and strong achievability for private, error-free retrieval, then constructs schemes using secret-sharing queries and coded storage. Its examples show achievable storage–retrieval tradeoffs and establish that N-achievability need not imply strong achievability.
- N-achievability requires a storage code and private, error-free retrieval scheme attaining the specified storage and retrieval costs.Strong achievability instead requires a sequence of such tuples indexed by a parameter.
- A secret-sharing construction generates private query shares whose responses allow the user to decode the desired record.Each storage node returns a linear response to its query, and the secret-sharing property provides privacy against the specified collusions.
- The coded-storage example stores two records across three nodes with storage cost 1/2 and achieves retrieval cost 1/2.The construction uses the records and their combinations as node contents, while the responses permit recovery of the requested record.
- (1/2, 1/2) is 2-achievable but not strongly achievable.Its achievability follows from the coded-storage example, while non-strong achievability is established separately.
- N-achievability and strong achievability differ, so the storage–retrieval tradeoff depends on the number of data records.A strongly achievable tuple is N-achievable for any fixed N, but the converse does not hold generally.
III. LINEAR PIR CODES
The paper defines a broad class of linear storage codes and associated PIR schemes, then gives conditions ensuring error-free recovery and privacy. The construction supports varying storage-retrieval cost tuples and has costs independent of the number of records.
- Storage-code construction: The proposed linear storage code encodes each record separately using mappings specified by a parity-check matrix.The code is defined for records of length (K − S)L over GF(q), with each storage node holding a concatenated vector of coded pieces.
- Retrieval scheme: The retrieval scheme ΘV uses a matrix V to generate queries sent to each storage node.A user initializes a random matrix, generates R query vectors per node, and receives inner-product responses Ar,k = Qr,k^⊤Xk.
- Retrieval scheme: Each storage node returns R symbols, which determines the retrieval cost of the scheme.The returned responses are used to form a linear system whose solution recovers the requested record.
- Correctness and privacy: The retrieval scheme is error-free when its associated linear system has a unique solution.Under the retrievability condition, the user can uniquely decode dM from the queries and answers.
- Correctness and privacy: The scheme is Φ-private when the privacy condition holds for every allowed collusion pattern.The proof shows that the colluding nodes’ query vectors are uniformly and independently distributed regardless of the requested record.
- Cost properties: The proposed codes and retrieval schemes are well-defined for every number of data records, so any achievable cost tuple is strongly achievable.This establishes that the storage and retrieval costs remain the same as the number of records varies.
IV. TRADEOFF ANALYSIS
The paper derives a storage-retrieval tradeoff for its linear PIR framework and shows that MDS storage codes attain the resulting lower bound. It also gives a parameter-specific impossibility result for K = 3.
- Tradeoff bound: Privacy implies R ≤ T, constraining the number of responses per storage node relative to the query-randomness parameter.This inequality is used in deriving the storage-retrieval lower bound.
- Tradeoff bound: Theorem 3 establishes a lower-bound tradeoff between storage cost and retrieval cost for schemes satisfying retrievability and privacy.The bound applies to any storage code and retrieval scheme in the proposed class that meets both conditions.
- Tradeoff bound: When K = 3, no storage code and retrieval scheme satisfying the retrievability and privacy conditions can meet the excluded parameter regime.The corollary follows directly from Theorem 3.
- MDS optimality: The optimal storage-retrieval tradeoff can be achieved using maximum distance separable storage codes.For fixed K and S, the paper constructs a (K, K − S) MDS code and an error-free, private retrieval scheme attaining the lower bound.
- MDS optimality: For the constructed MDS scheme, the retrieval-to-storage cost relation is RC(ΘV, ∆P) = SC(∆P) KSC(∆P) −1.The paper states that this equality expresses tightness of the lower bound.
V. CONCLUSION
The paper addresses PIR over coded storage rather than primarily studied uncoded storage, whose repeated copies incur high storage cost. It proposes general linear codes and retrieval schemes, characterizes when they are private and error-free, and shows that MDS schemes can achieve optimal tradeoffs.
- Scope and motivation: The paper studies private information retrieval when storage nodes need not each store every data record.This contrasts with the uncoded-storage setting emphasized in prior PIR work.
- Contributions: The proposed framework specifies linear storage codes through parity-check matrices and pairs them with an associated retrieval scheme.The construction is described as a fairly general class of linear storage codes.
- Contributions: The paper identifies conditions under which its retrieval scheme is error-free and private.It also derives storage-retrieval tradeoffs for the proposed schemes.
- Contributions: The storage and retrieval costs of the proposed scheme are the same for any number of data records.The conclusion highlights this as a property of the scheme.
- Contributions: For MDS-based coded storage, a randomly constructed retrieval scheme is optimal in minimizing retrieval costs.The conclusion reports this result for the specific MDS setting considered.
APPENDIX A PROOF OF THEOREM 1
The proof assumes a strongly achievable storage-retrieval cost tuple of (1/2, 1/2) and derives entropy and mutual-information constraints from privacy, error-free retrieval, and storage-code conditions. These constraints lead to a contradiction as the parameter c approaches 1/2.
- Contradiction setup: The proof begins by assuming that the storage-retrieval cost tuple (1/2, 1/2) is strongly achievable.This yields sequences of storage codes and private, error-free retrieval schemes.
- Information-theoretic constraints: Independence between M and (Qk, Xk, Dn∗, Ak) follows from the entropy equalities and privacy conditions.The argument also uses that H(Dn) is constant across records.
- Information-theoretic constraints: The proof establishes an intermediate entropy and mutual-information inequality using a direct joint-entropy expansion.The resulting expression contains nonnegative mutual-information and entropy terms.
APPENDIX B PROOF OF THEOREM 4
The proof constructs a retrieval matrix for an MDS-based storage code and shows that retrievability and privacy can simultaneously hold with high probability for sufficiently large fields. The argument uses a deterministic construction for retrievability and the Schwartz-Zippel lemma for random matrix choices.
- MDS construction: For sufficiently large GF(q), a (K, K −S) MDS code with parity-check matrix P can be constructed.The induced storage code has storage cost SC(∆P) = 1/(K −S).
- Retrievability: The retrieval matrix V is constructed so that the retrievability condition is satisfied by the MDS parity-check structure.The proof uses the fact that sufficiently large subsets of parity-check coordinates force all corresponding coefficients to vanish.
- Joint construction: The same matrix must satisfy both retrievability and privacy, so the proof reformulates the retrieval equations in a unified notation.The matrix is chosen with R = T = K −S and L = S, making V square.
- Randomized guarantee: Retrievability holds with high probability when the matrix entries are chosen randomly over a sufficiently large field.The determinant governing the linear system is a nonzero polynomial, so the Schwartz-Zippel lemma applies.
- Randomized guarantee: Privacy also holds with probability arbitrarily close to 1 for sufficiently large q under random generation of V.Together with the retrievability result, this proves the theorem for randomly generated retrieval schemes.