PaperlayerView exact revision on arXiv

Source-linked AI summary

Private Information Retrieval from MDS Coded Data in Distributed Storage Systems

Razan Tajeddine, Oliver W. Gnilke, Salim El Rouayheb

arXiv:1602.01458v4cs.IT

TL;DR

The paper addresses how to retrieve data privately from MDS-coded distributed storage without downloading the entire system. It constructs linear PIR schemes with low download cost, including universal schemes that do not depend on the code’s generator matrix. For one spy node, the schemes achieve the information-theoretic limit for linear schemes, while broader collusion regimes receive explicit cPoP constructions.

  • Problem

    Private information retrieval from MDS-coded distributed storage must protect requested-file identities from spying nodes while avoiding the infeasible cost of downloading all files.

  • Method

    The paper constructs explicit linear PIR schemes for MDS-coded data, using designs that can apply without jointly redesigning the storage code.

  • Results

    For b = 1, the schemes achieve the information-theoretic lower bound for linear schemes; for 2 ≤ b ≤ n − k, they achieve download cost b + k per unit of requested data.

  • Takeaways & Limitations

    The schemes are universal with respect to the MDS generator matrix and support varying user privacy levels without separate data encodings.

Abstract

from arXiv · show

The problem of providing privacy, in the private information retrieval (PIR) sense, to users requesting data from a distributed storage system (DSS), is considered. The DSS is coded by an $(n,k,d)$ Maximum Distance Separable (MDS) code to store the data reliably on unreliable storage nodes. Some of these nodes can be spies which report to a third party, such as an oppressive regime, which data is being requested by the user. An information theoretic PIR scheme ensures that a user can satisfy its request while revealing, to the spy nodes, no information on which data is being requested. A user can trivially achieve PIR by downloading all the data in the DSS. However, this is not a feasible solution due to its high communication cost. We construct PIR schemes with low download communication cost. When there is $b=1$ spy node in the DSS, we construct PIR schemes with download cost $\frac{1}{1-R}$ per unit of requested data ($R=k/n$ is the code rate), achieving the information theoretic limit for linear schemes. The proposed schemes are universal since they depend on the code rate, but not on the generator matrix of the code. Also, when $b\leq n-δk$, for some $δ\in \mathbb{N^+}$, we construct linear PIR schemes with $cPoP = \frac{b+δk}δ$.

I. INTRODUCTION

The paper studies private information retrieval from MDS-coded distributed storage systems when storage nodes may spy on users’ requests. It develops communication-efficient PIR constructions, including universal schemes and explicit cPoP results for several collusion regimes.

  • System model: MDS-coded distributed storage provides reliable, redundant data availability despite temporary node outages or departures.The system uses an (n, k, d) MDS code that tolerates n − k simultaneous node failures.
  • Problem motivation: Downloading all files achieves PIR but is infeasible because of its high communication cost.This motivates lower-download-cost PIR schemes for coded data rather than replicated databases alone.
  • Example construction: In the four-node example, random query masking lets the user decode the requested file while each individual node’s query remains statistically independent of its index.The returned symbols form an invertible linear system, and the example downloads 4 symbols for a 2-symbol file, giving cPoP = 2 independent of the number of files.
  • Contributions: For 2 ≤ b ≤ d − 1, the paper constructs linear schemes with cPoP = b + k; more generally, its schemes have cPoP independent of m in the stated regime.The paper presents explicit constructions of PIR schemes with efficient communication cost for MDS-coded data.
  • Universality and deployment: The schemes can serve users choosing different privacy levels b without storing separate encodings of the same data.Users may choose their own b at the expense of higher cPoP, while the DSS retains one encoded data set.

II. MODEL

The model stores multiple files across an (n,k,d) systematic MDS-coded distributed storage system and aims to retrieve one file privately using linear PIR queries. The scheme must let the user decode the requested file while revealing no information about its identity to colluding nodes, with communication cost independent of the number of files.

  • Storage model: An (n,k,d) systematic MDS code stores m equal-sized files across n nodes, tolerating d−1 node failures.Each file is divided into α stripes and each stripe into k blocks, then encoded separately using the same k × n generator matrix.
  • Storage model: The encoded data XΛ is stored on the DSS, with the first k generator-matrix columns forming the identity matrix.The user knows the coding coefficients and the layout of data across nodes.
  • PIR model: The user sends each node a ρ × mα query matrix Q_l determined by the requested file.Linear PIR schemes treat query-matrix rows as sub-queries sent to the nodes.
  • PIR model: The requested file X_f must be decodable while b colluding nodes learn no information about f.The user does not know which nodes are colluding, and the privacy requirement is information theoretic.
  • Design objective: The objective is a linear PIR scheme with low cPoP that does not depend on m.The model assumes arbitrarily large files, making download cost dominant over request communication.

2. Download stage: Node l responds by sending the projection of its data onto Ql, i.e.,

During download, each node returns projections of its stored data onto the rows of its query matrix. The resulting responses support private decoding while cPoP measures downloaded bits relative to the requested file size.

  • Download stage: Each query matrix Q_l produces ρ sub-responses by projecting node l’s data onto each query row.This is the download operation performed independently for each node.
  • Privacy condition: Perfect information-theoretic PIR requires H(f|Q_j, j ∈ γ) = H(f) for every node set γ of size b.The condition formalizes that any b colluding nodes obtain no information about the requested-file index.
  • Download stage: The response vector from one node contains one GF(q^w) symbol per sub-query, while each query vector contains m GF(q) symbols.Thus query and response symbols use different field representations and scales.
  • Communication cost: cPoP is the ratio of total downloaded bits to the size of the requested file.It is the inverse of the PIR rate, and download cost dominates when files are arbitrarily large.

III. MAIN RESULTS

The paper constructs explicit linear PIR schemes for MDS-coded storage with colluding nodes, targeting low download cost and universal operation. Its results give cPoP guarantees for one spy and broader collusion regimes, while the optimal colluding-node cPoP remains open.

  • Theorem 1: b = 1 yields an explicit linear PIR scheme achieving perfect privacy and cPoP = 1/(1−R), where R = k/n.The scheme uses the same field as the MDS code and reaches the information-theoretic limit for linear schemes.
  • Theorem 1: The proposed construction is universal because it depends on n, k, and b, but not on the code’s generator matrix.It operates over the same field over which the code is designed.
  • Theorem 2: For 2 ≤ b ≤ d−1, an explicit linear PIR scheme over GF(q) achieves perfect PIR with cPoP = b + k.
  • Theorem 3: For b ≤ n−δk and any δ ≥ 1, an explicit linear scheme achieves cPoP = (b + δk)/δ.Theorem 2 is the special case δ = 1.
  • Open problem: The optimal cPoP for PIR on coded data with colluding nodes remains an open problem.
  • Performance comparison: For n = 16 and b = 1, Theorem 1 improves substantially over Theorems 2 and 3; Theorem 3 improves over Theorem 2 when δ > 1.These comparisons are illustrated through cPoP versus rate.

IV. PIR SCHEME CONSTRUCTION AND PROOF FOR b = 1

For one colluding node, the construction masks the requested file index with random query matrices plus deterministic retrieval patterns. Responses are arranged so interference can be decoded and canceled while desired coded symbols are recovered.

  • Query construction: The user sends each node a query matrix Q_l built from a random matrix U and, for selected nodes, a deterministic matrix E_f,l.Q_l = U + E_f,l for l = 1, …, n−r, while the remaining nodes receive U.
  • Retrieval pattern: The matrices E_f,l place at most one 1 in each row and column, ensuring one coded symbol per node response and no redundant retrieval.
  • Retrieval pattern: Each sub-query marks exactly n−k nodes, leaving k unaltered responses that allow the user to decode a codeword and recover n−k file symbols.
  • Retrieval pattern: Each stripe of the requested file is selected in exactly k matrices, providing the k coded symbols needed to recover the original stripe.
  • Example: For the (15,4,12) example, the scheme uses ρ = 4 sub-queries and α = 11 stripes, with β = 2 and r = 3.Table II records which file symbols are retrieved in each sub-query.
  • Decoding example: In the (5,2,4) example, the construction achieves perfect PIR against b = 1 with cPoP = 1 by querying Q_l = U + E_1,l for four nodes and U for the fifth.
  • Decoding example: The user decodes interference first, cancels it from the remaining equations, and solves for the desired file symbols.The example downloads 2 symbols, matching the bound in Theorem 1.

B. Proof of Theorem 1

The proof establishes decodability and privacy for the b = 1 construction using MDS-code properties. It also derives the communication cost from the number of symbols returned by each node.

  • Decodability: For each sub-query, k nodes receive only the random query vector, so their responses form enough components of a codeword to decode it.Any k coordinates of an MDS code determine the codeword.
  • Decodability: For the other nodes, subtracting the decoded codeword component from each response reveals the privately requested symbol.
  • Decodability: Because exactly k symbols are retrieved from every coded stripe of the requested file, all stripes can be recovered using the MDS property.
  • Privacy: When b = 1, each node’s query matrix is statistically independent of the requested file index, establishing perfect privacy.
  • Communication cost: Each node returns ρ = k symbols, which determines the scheme’s total communication cost and its cPoP.

V. PIR SCHEME CONSTRUCTION AND PROOF FOR b ≤d −1

The section constructs linear PIR schemes for b ≤ d−1 using random queries derived from the MDS code's dual, and proves retrieval and privacy. The construction retrieves the requested file through k sub-queries, with cPoP = k+b in the general scheme.

  • General construction: cPoP = k+b for the general linear PIR scheme against b colluding nodes.The scheme has dimension ρ = k, so it uses k sub-queries.
  • General construction: The scheme applies when b ≤ d−1 and uses random vectors over GF(q) to form query matrices.The random vectors are combined with the parity-check matrix H to generate dual-code query codewords.
  • Decodability: Each sub-query retrieves one systematic symbol of the requested file, so completing the k sub-queries yields all k file symbols.The construction assumes a systematic MDS code and uses the standard basis vector for the requested file index.
  • Example: (5,3,3) DSS: For a (5,3,3) MDS example with b = 2, the construction uses cPoP = 3+b and three sub-queries.The example downloads three packets from each server and decodes the requested symbols.
  • Example: (6,2,5) DSS: For a (6,2,5) example with b = 2, the user decodes a_f and b_f from two sub-queries, achieving cPoP = 4.The example queries four nodes rather than all six nodes.

B. Proof of Theorem 2

The proof establishes decodability and privacy for the proposed scheme. Decodability follows from the response structure, while privacy follows by showing that colluding nodes learn no information about the requested file index.

  • Proof strategy: The proof shows that the scheme ensures decodability and privacy.Theorem 2 is proved using the construction described in Section V-A.
  • Decodability: The user retrieves the requested file by decoding its desired symbols from the node responses without decoding all interference terms.The response to each sub-query is combined across nodes to recover the requested symbol.
  • Privacy: Privacy requires H(f|Q_Sb) = H(f) for every set S_b of b colluding nodes.Q_Sb denotes the query vectors or matrices observed by the colluding nodes.
  • Privacy: The privacy argument uses the independence of the random matrix U_i from the file index and the MDS property to decode U_i from the colluding queries.These facts establish the entropy equalities used in the proof.

VI. PIR SCHEME CONSTRUCTION FOR b ≤n −δk

For b ≤ n−δk, the section develops a construction based on punctured MDS subcodes and compares it with the earlier scheme. The construction uses shared nodes and grouped subcodes to reduce the communication price of privacy.

  • Comparison: As the number of colluding nodes increases, Theorem 3's improvement over Theorem 2 grows.Figure 3 compares cPoP versus rate for n = 16 and b = 1, 3, 5.
  • Construction: The construction partitions δk nodes into δ groups of k nodes and uses b additional common nodes.Each group forms a punctured (b+k,k) MDS code.
  • Privacy: The scheme uses random vectors and dual-code queries to preserve privacy against b colluding nodes.Any b queries are linearly independent, supporting privacy against b colluding nodes.
  • Decodability: The user decodes a_f from one code and a_f+b_f from a second code, thereby retrieving the requested information.This example uses the additional nodes that were omitted in the less efficient construction.

A. General Proof of Theorem 3

The general construction for b ≤ n−δk uses δ punctured MDS codes with b common nodes and applies the Theorem 2 scheme independently to each stripe. It retrieves the requested file while maintaining privacy against b colluding nodes.

  • Construction: The construction assumes n = b+δk and divides the nodes into b common nodes plus δ groups of k nodes.The resulting structure forms δ punctured (b+k,k) MDS codes.
  • Query design: For each subcode, the scheme uses α = δ subdivisions and k queries to process one stripe of the requested file.The query vectors for the b common nodes are the columns of U_i.
  • Decodability: Applying the Theorem 2 scheme to every subcode lets the user decode each stripe and reconstruct the requested file.The construction explicitly concludes that the user can decode x_f.
  • Privacy: The queries are generated from a dual MDS code, making any b queries linearly independent.The construction uses an (δk+b,b,δk+1) MDS code for the queries.
  • Communication cost: The user contacts b+δk nodes to download δ information parts, giving the construction's communication ratio.The stated download configuration uses all b+δk nodes and δ requested parts.

VII. COMPARISON TO FUNDAMENTAL BOUNDS

The paper constructs PIR schemes for MDS-coded storage that protect requested-file identity from spy nodes while reducing download cost. The schemes meet known linear-scheme bounds in the single-spy case and provide a cost expression for multiple colluding nodes.

  • 1/(1−R) per requested-data unit is achieved with one spy node, matching the information-theoretic limit for linear schemes.Here R is the code rate, and the comparison is asymptotic as the number of files m grows.
  • The schemes protect the requested file from nodes that may report the query to a third party.The stated objective is to reveal no information about the requested data identity to the spy nodes.
  • The constructions are universal because they depend on the code rate rather than the specific MDS generator matrix.
  • b+k per requested-data unit is achieved for 2 ≤ b ≤ n−k colluding nodes.The construction is linear and applies to multiple colluding nodes.

IX. APPENDIX

The appendix describes a linear PIR construction using randomized sub-queries over the stored data and derives how node responses are combined to recover the requested file. Its decoding argument uses systematic and parity-node responses whose interference terms cancel.

  • Proof strategy: The proof uses k sub-queries and no subdivisions, and its key distinction is that the user need not decode all interference terms.
  • Decoding: The scheme retrieves one systematic symbol of the requested file in each of k sub-queries.After the kth sub-query, the user obtains all k symbols of the requested file.
  • Query construction: b random vectors of dimension m are generated in each sub-query, and they form the query matrix used by the scheme.The vectors are chosen uniformly from GF(q).
  • Response structure: Systematic-node responses are expressed using the stored rows and the query vectors, with the systematic-code assumption enabling the representation.
  • Response structure: Parity-node responses are written using the MDS generator structure and the coded data stored on parity nodes.
  • Decoding: The decoding combines systematic and parity responses so interference cancels and the requested symbol remains.The proof uses the trace operator and its cyclic trace property.
Loading 1602.01458v4…