PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Locally Repairable and Secure Codes for Distributed Storage Systems

Ankit Singh Rawat, O. Ozan Koyluoglu, Natalia Silberstein, Sriram Vishwanath

arXiv:1210.6954v2cs.IT

TL;DR

The paper asks how distributed storage can jointly provide resilience, security against colluding eavesdroppers, and local repairability. It derives bounds and constructs exact-repair and locally repairable codes, including schemes that combine locality with security. The results include tighter MSR secrecy bounds, optimal minimum-distance locally repairable codes, and repair-bandwidth-efficient secure schemes in specified cases.

  • Problem

    The paper studies the trade-offs among resilience, security against colluding eavesdroppers, and local-repairability in distributed storage systems.

  • Method

    The paper derives secrecy-capacity and minimum-distance bounds, then constructs exact-repair, locally repairable, repair-bandwidth-efficient, and secure codes using existing coding and secrecy techniques.

  • Results

    The paper obtains tighter MSR secrecy bounds, achieves them for selected eavesdropper settings, constructs minimum-distance-optimal locally repairable codes, and develops repair-bandwidth-efficient schemes with and without security.

  • Takeaways & Limitations

    Local-repairability and security can be jointly designed in distributed storage codes, including schemes supporting exact repair and multiple local parity nodes.

Abstract

from arXiv · show

This paper aims to go beyond resilience into the study of security and local-repairability for distributed storage systems (DSS). Security and local-repairability are both important as features of an efficient storage system, and this paper aims to understand the trade-offs between resilience, security, and local-repairability in these systems. In particular, this paper first investigates security in the presence of colluding eavesdroppers, where eavesdroppers are assumed to work together in decoding stored information. Second, the paper focuses on coding schemes that enable optimal local repairs. It further brings these two concepts together, to develop locally repairable coding schemes for DSS that are secure against eavesdroppers. The main results of this paper include: a. An improved bound on the secrecy capacity for minimum storage regenerating codes, b. secure coding schemes that achieve the bound for some special cases, c. a new bound on minimum distance for locally repairable codes, d. code construction for locally repairable codes that attain the minimum distance bound, and e. repair-bandwidth-efficient locally repairable codes with and without security constraints.

I. INTRODUCTION

The paper studies security and local-repairability alongside resilience in distributed storage systems, then develops coding schemes that combine these properties.

  • Motivation: Distributed storage systems require resilience to node failures, while security and local-repairability are additional design challenges.The paper focuses on passive, colluding eavesdroppers and geographically distributed systems where local repair reduces repair participation.
  • Security model: An (ℓ1, ℓ2)-eavesdropper observes stored data from ℓ1 nodes and stored or downloaded repair data from ℓ2 additional nodes.This model generalizes the case where eavesdroppers observe stored data only.
  • Secure regenerating codes: The paper derives a tighter secrecy-capacity upper bound for bandwidth-efficient repairable codes at the MSR point.The bound accounts for information downloaded during repairs, which can expose additional information at the MSR point.
  • Secure regenerating codes: Secure exact-repair coding schemes achieve the secrecy bound for selected eavesdropper settings and provide higher rate than an earlier scheme.The achievability result covers any (ℓ1, ℓ2) with ℓ2 ≤2 when repairs are observed for a set of ℓ1 + ℓ2 (< k) nodes.
  • Locally repairable codes: For vector locally repairable codes, the paper derives a general minimum-distance bound and constructs Gabidulin-code-based codes that attain it.The construction allows multiple local parities per local group and establishes a storage–resilience trade-off.
  • Repair efficiency and security: The paper introduces repair-bandwidth efficiency for locally repairable DSS and combines locally repairable codes with MSR codes to meet file-size bounds.It also develops secure locally repairable schemes using secrecy pre-coding, considering both single and multiple local parity nodes.

B. Information flow graph

The information flow graph models storage, repair, and reconstruction in a DSS, allowing file size to be bounded by network flow and minimum cuts.

  • Graph construction: Each storage node is represented by input and output nodes, with an α-capacity edge enforcing its storage constraint.The input node represents downloaded data, while the output node represents the α symbols stored on the node.
  • Graph construction: A newcomer connects to d live nodes through links of β capacity, representing the data downloaded during repair.The total repair bandwidth is γ = dβ.
  • Data collection: A data collector contacting k storage nodes is modeled as a collector node connected to those nodes by infinite-capacity edges.This models reconstruction from any k live storage nodes.
  • Example: In the example, four live nodes maintain an ‘any 2 out of 4’ property while successive repairs replace x1 and x2 with x5 and x6.The collector reconstructs the information by contacting x5 and x6.
  • Capacity bound: The max-flow-min-cut theorem bounds the file size by the minimum flow from the source to every data collector.Regenerating codes attain the resulting bound, establishing a trade-off between per-node storage α and repair bandwidth γ.
  • Regenerating-code trade-off: MSR codes first minimize per-node storage and then repair bandwidth, whereas MBR codes first minimize repair bandwidth and then storage.For d = n − 1, repair bandwidth is reduced for both MSR and MBR codes.

C. Eavesdropper model

The paper models colluding passive eavesdroppers that observe stored contents and repair downloads, and uses rank-metric precoding within secure DSS constructions.

  • Eavesdropper model: An (ℓ1, ℓ2) eavesdropper observes stored data on any ℓ1 nodes and downloaded repair data for any ℓ2 additional node repairs.This generalizes the model with access only to stored data by allowing ℓ2 = 0.
  • Security definition: Security requires zero mutual information between the secure file and the eavesdropper’s observation for every allowed pair of observation sets.The secure file size is denoted Ms.
  • Security mechanism: The secrecy lemma guarantees zero leakage when randomization has at least the entropy of the observation and is recoverable given the secure file and observation.The random bits are independent of the secure information bits.
  • Pre-coding: The coding schemes use a Gabidulin-code precoding step, exploiting maximum-rank-distance properties over an extension field.Gabidulin codes are constructed by evaluating linearized polynomials at linearly independent points.
  • Pre-coding: Fq-linearity permits recovery from evaluations at linearly independent points and supports further linear operations in the DSS constructions.This property makes Gabidulin codes suitable for precoding before additional coding operations.
  • Rank-metric construction: In the stated MDS-array construction, any s vector symbols correspond to evaluations at min{s, t}α linearly independent points in the message subspace.The construction begins with tα evaluations and then applies an MDS array code.

E. Locally repairable codes

The paper studies vector LRCs with all-symbol locality, extends distance bounds to multiple local parities, and develops constructions addressing locality, repair, and security.

  • Definitions: An (r, δ, α) vector LRC assigns every vector symbol a local group whose punctured code has minimum distance at least δ.The scalar case is recovered when α = 1.
  • Definitions: The locality requirement means each symbol can be repaired from any r other symbols in its local group.The same requirements imply that the local-group entropy is at most rα.
  • Definitions: Local groups are distinct sets Γ(i), and a file is encoded into an LRC codeword whose symbols are stored on distinct DSS nodes.The construction focuses on all-symbol locality, so every encoded symbol belongs to a local group.
  • Distance-optimal constructions: The paper explicitly constructs optimal scalar LRCs with all-symbol locality beyond the restriction (r + δ − 1)|n.Earlier existence results covered the divisible-parameter setting under a field-size condition.
  • Distance-optimal constructions: The paper generalizes the minimum-distance bound from δ = 2 to every δ ≥ 2 and gives optimal vector LRCs with multiple local parity nodes.These codes are optimal with respect to the generalized bound.
  • Motivation and extensions: Multiple local parities can let repair contact more nodes than necessary and finish when enough responses arrive, addressing variable node response times.The paper also identifies stronger resilience to eavesdropping attacks for such LRCs.
  • Secure and efficient LRCs: The paper combines locality and security to develop secure locally repairable DSS codes, while also considering repair-bandwidth efficiency with and without security constraints.It derives a file-size upper bound under a given repair bandwidth and presents minimum-distance-optimal locally repairable codes.

A. Improved bound on secrecy capacity at the MSR point

The paper tightens secrecy-capacity bounds for MSR codes against colluding eavesdroppers and constructs secure codes achieving the bound in specified cases.

  • Bound derivation: The cut argument considers ℓ1 observed stored nodes and ℓ2 subsequent repairs of nodes outside the directly observed set.The resulting max-flow-min-cut analysis gives an upper bound on secure file size at the MSR point.
  • Bound derivation: Theorem 13 provides a generic upper bound on securely stored data for MSR codes, including bandwidth-efficient exact-repairable codes.The bound accounts for information exposed through repair downloads.
  • Achievability: The data collector contacts E1, E2, and the remaining k − (ℓ1 + ℓ2) original nodes to reconstruct the file in the analyzed failure pattern.The proof uses security against the eavesdropper together with recoverability from any k contacted nodes.
  • Repair-subspace analysis: The exact-repair analysis uses repair subspaces Di,j spanned by encoding vectors transmitted from node i when repairing node j.For linear schemes, mutual-information terms can be expressed through dimensions of these subspaces.
  • Achievability: The secure product-matrix construction from is optimal for ℓ2 = 1.The paper’s construction combines secret sharing with an existing exact-repairable MSR code and achieves secrecy capacity for ℓ2 ≤ 2 under its stated conditions.
  • Repair-subspace analysis: Lemma 15 constrains the repair matrices of systematic nodes in exact-repairable linear MSR codes with d = n − 1.The lemma applies to codes using interference alignment for repair.
  • Specialized bound: Corollary 16 gives a specialized bound for interference-alignment MSR codes when ℓ2 ≤ 2, with repair-observation terms differing between ℓ2 = 1 and ℓ2 = 2.The stated terms are β for ℓ2 = 1 and 2β − β(n−k) for ℓ2 = 2.

B. Construction of secure MSR codes with d = n −1

The paper constructs secure MSR codes by concatenating Gabidulin secrecy pre-coding with zigzag codes, obtaining optimal secure file sizes for a class of colluding eavesdroppers while retaining bandwidth-efficient systematic-node repair.

  • Construction: The construction concatenates a Gabidulin secrecy pre-coding stage with a (k+p,k) zigzag code and stores the result across n=k+p nodes.Gabidulin encoding is applied first, followed by zigzag encoding over Fq.
  • Construction: Zigzag repair accesses all d=n−1 surviving nodes through repair sets Yj for systematic node j.The downloaded symbol indices belong to Yj={i:i·ej=0}.
  • Security: Theorem 18 establishes security against an (ℓ1,ℓ2)-eavesdropper with E2⊂[k] for the proposed pre-coded zigzag code.The proof verifies entropy conditions ensuring the observed symbols reveal no secure information.
  • Security: For ℓ2≤2, the construction attains the upper bound on secure file size and therefore characterizes MSR secrecy capacity for restricted download eavesdropping.The restriction is that repaired-data observations concern systematic nodes.
  • Repair efficiency: A related code family extends bandwidth-efficient repair to parity nodes while preserving the security argument and theorem under a new node size α.The original zigzag codes do not provide bandwidth-efficient parity repair.

IV. NEW BOUNDS AND CONSTRUCTIONS FOR LOCALLY REPAIRABLE CODES

This section derives a general minimum-distance upper bound for vector locally repairable codes and gives a Gabidulin–MDS array construction attaining it, including nonlinear codes and multiple local parities.

  • Upper bound: The minimum-distance upper bound applies to (r,δ,α) locally repairable codes, including nonlinear codes and multiple local parity nodes per group.The framework includes vector codes with node size α and locality parameters r and δ.
  • Upper bound: The bound exposes a resilience-versus-storage trade-off: increasing per-node storage α beyond M/k can yield higher minimum distance.This generalizes the single-local-parity setting through a modified entropy-based proof.
  • Construction: The construction combines Gabidulin codes with MDS array codes to attain the derived minimum-distance bound.It is presented as a general code construction for locally repairable codes.
  • Upper bound: Theorem 21 states the generic upper bound on minimum distance for an (r,δ,α) LRC of length n and cardinality |F|^M.The proof constructs a set A with H(c_A)<M and applies the dual definition of minimum distance.
  • Special cases: For δ=2, the bound matches the result of, while for M=k and α=1 it reduces to the scalar-LRC bound from.The specialized scalar expression is dmin(C)≤n−k+1+(⌈k/r⌉−1)(δ−1).

B. Construction of dmin-optimal locally repairable codes

Construction I combines Gabidulin encoding with local MDS or MDS-array encoding to build explicit locally repairable codes that attain the minimum-distance bound across broader parameter settings.

  • Construction I: Construction I first encodes the file with a Gabidulin code, partitions its codeword into local groups, and applies an MDS array code to each group.This generalizes an earlier scalar-LRC construction.
  • Construction I: The construction supports separate cases depending on whether r + δ −1 divides n, with corresponding group sizes and field-dimension requirements.Case 1 uses equal groups; case 2 includes one smaller final group.
  • Distance analysis: Observed nodes correspond to evaluations of the underlying linearized polynomial at Σ_i min{s_i, r}α points, with an additional min{s_g, β0} term in case 2.The evaluation points are linearly independent over Fq.
  • Distance analysis: Any δ −1 + i erasures in one local group become iα rank erasures in the corresponding Gabidulin codeword.This converts local node failures into rank-erasure correction for the outer code.
  • Optimality: For divisible and certain nondivisible lengths, Construction I attains the minimum-distance bound with q ≥ r + δ −1 and stated field-extension conditions.The scalar specialization likewise attains the scalar minimum-distance bound.
  • Examples: The examples realize dmin = 4 for n = 14, M = 9 and dmin = 5 for n = 15, M = 28.In the latter example, four node failures induce at most eight rank erasures, correctable by a Gabidulin code of rank distance nine.

V. REPAIR BANDWIDTH EFFICIENT LOCALLY REPAIRABLE CODES

The paper develops repair-bandwidth-efficient LRCs by deriving a storage bound for a given repair bandwidth and replacing local MDS-array encoding with MSR codes.

  • Repair model: Naïve local repair contacts r nodes in the failed node’s group and downloads all data stored on those nodes.
  • Overview: The section derives an upper bound on file size for locally repairable DSS supporting repair bandwidth dβ and maximum possible failure resilience.The bound targets minimum-distance-optimal LRCs.
  • Overview: MSR-LRCs attain this bound by applying an MSR code within each local group instead of an MDS array code.The resulting construction supports local repairs while minimizing repair bandwidth for the specified locality parameters.

A. File size upper bound for repair bandwidth efficient LRCs

This section bounds the file size of minimum-distance-optimal LRCs under repair-bandwidth constraints and shows that an MSR-based construction achieves the bound when α divides M.

  • Model and bound: The analysis models local repairs with disjoint groups, where a failed node contacts d remaining nodes and downloads β symbols from each.Here r ≤ d ≤ r + δ −2.
  • Model and bound: Theorem 29 gives an upper bound on the file size M for an n-node DSS using an (r, δ, α, β, d) LRC.The proof uses cuts in a dynamic information-flow graph.
  • Repair-bandwidth constraint: Repair feasibility requires (d − i)β ≥ α for i = 0, …, r −1, yielding minimum per-helper download β* = α/(d − r + 1).
  • Achievability: Construction I with MSR local parities attains the file-size bound when α divides M.The theorem applies to the construction using an MSR code in its second encoding stage.
  • Example: For the example with r = 3, δ = 3, α = 4, β = 2, and d = 4, the code stores M = 28 symbols and repairs each failed node bandwidth-efficiently.An exact-MSR code is used within each local group.

VI. SECRECY IN LOCALLY REPAIRABLE DSS

The paper analyzes secrecy capacity for locally repairable DSS against colluding eavesdroppers that observe stored contents and repair downloads. It derives a generic upper bound and identifies conditions and special cases where secure constructions achieve it.

  • Upper bound: The secrecy capacity is the maximum file size that can be stored without leaking information to an eavesdropper.The paper derives this quantity for an (r, δ, α, β, d) LRC under the stated eavesdropping model.
  • Security model: The eavesdropping model separates ℓ1 storage-eavesdropped nodes from ℓ2 download-eavesdropped nodes observed during repair.The analysis classifies these nodes within each local group and associates them with a data collector reconstructing the file.
  • Upper bound: Lemma 32 provides a generic upper bound on secrecy capacity for secure (r, δ, α, β, d) LRCs against an (ℓ1, ℓ2)-eavesdropper.The bound is obtained by considering allowed combinations of eavesdropped nodes and data-collector contacts under the model.
  • Conditions: A non-zero secure file size requires ℓ1 + ℓ2 = ℓ1 + ℓ2 < a parameter-dependent threshold in the considered construction.The supplied proof text states the requirement but truncates the threshold expression.
  • Case distinction: For one local parity per group, repair observations can substantially reduce secrecy capacity, motivating separate analysis of the multiple-parity case.The paper treats δ = 2 and δ > 2 separately because their repair and leakage behavior differs.

A. Case 1: Single local parity per local group (δ = 2)

With a single local parity, repairing an eavesdropped node reveals all information in its local group, sharply constraining secrecy. The paper gives a tight capacity expression and a secure construction, while contrasting this with multiple-parity MSR-LRCs.

  • Single-parity leakage: A single node repair reveals all information in its local group because the newcomer downloads data from the other r nodes.Thus, an eavesdropper observing one repair obtains the entire local-group content.
  • Capacity: Theorem 33 gives the secrecy capacity for an (r, δ = 2, α, β = α, d = r) LRC against an (ℓ1, ℓ2)-eavesdropper.The supplied passage identifies the theorem and parameter regime, while the displayed capacity expression is not included.
  • Secure construction: [µr + h −(ℓ2r + ℓ1)]+ α symbols can be stored securely in the stated single-parity construction.The construction appends (ℓ2r + ℓ1)α random symbols before Gabidulin and dmin-optimal LRC encoding.
  • Security proof: The construction is secure because the eavesdropper can decode the random symbols from its observations, yielding I(f s; e) = 0.The random symbols mask the file contribution in the observed evaluations.
  • Security limits: Each additional observed repair reduces secrecy capacity by rα, and no data can be secured without useful leakage when ℓ2 > µ.These restrictions are stated specifically for locally repairable DSS with a single local parity.
  • Multiple-parity contrast: For multiple local parities, regenerating codes within local groups can improve secrecy capacity against an (ℓ1, ℓ2)-eavesdropper.The paper focuses on MSR-LRCs, whose restriction to each local group is an MSR code, and gives a corresponding upper bound and construction.

VII. CONCLUSION

The paper studies passive colluding eavesdroppers, secure file-size bounds, local-repairability, and bandwidth-efficient LRC constructions. It also identifies open problems involving parity-node observations, uncovered parameters, and cooperative repair.

  • Security model: An (ℓ1, ℓ2)-eavesdropper observes the content of any ℓ1 nodes and downloaded information for any ℓ2 repaired nodes.The model is passive and concerns leakage from stored or repair-transmitted data.
  • Classical DSS: The paper establishes secrecy capacity for ℓ2 ≤ 2 in the classical setting and reports a better rate than existing schemes.This applies when repairs observed by the eavesdropper are restricted to a particular set of k nodes.
  • Locally repairable codes: For locally repairable systems, the paper derives a new minimum-distance upper bound and presents a construction optimal with respect to that bound.It also develops secure codes achieving file-size bounds in special cases.
  • Open problems: The secrecy capacity remains open when eavesdroppers can observe parity nodes in addition to systematic nodes.The paper identifies new codes or improved bounds as needed for secure MSR codes in that setting.
  • Open problems: dmin-optimal LRC constructions remain open for parameters not covered by Theorem 24, and cooperative locally repairable repair is also unstudied.The latter concerns simultaneous node failures, including settings without security constraints.

APPENDIX A PROOF OF LEMMA 4

The appendix develops proof ingredients for leakage and repair properties using entropy identities, linearized-polynomial evaluations, matrix rank, and subspace arguments. It also counts symbols exposed during multiple repairs.

  • Entropy argument: The secrecy proof uses entropy non-negativity, the condition H(e) ≤ H(r), independence of r and f s, and recovery of r given f s and e.These steps establish the zero-leakage argument for the masking construction.
  • Linearized-polynomial representation: An MDS array code maps observed vector symbols to evaluations at linearly independent points over Fq.The rank of the selected submatrix is min{sα, tα}, which yields the independence claim.
  • Subspace proof: The repair analysis uses subspace relationships and induction to establish rank and dimension constraints among participating repair matrices.The contradiction follows when two subspaces exceed the dimension available in their containing subspace.
  • Repair-set structure: Repair sets satisfy |Yj1 ∩Yj2 ∩...∩Yjt| = p^(k−t) for distinct repaired systematic nodes.This intersection property supports counting the distinct symbols exposed across repairs.
  • Leakage counting: For ℓ2 repaired systematic nodes, the eavesdropper’s exposure is counted through the union of repair sets and adjusted for parity symbols functionally determined by exposed systematic symbols.The resulting count bounds the number of linearly independent symbols observed.

APPENDIX E PROOF OF THEOREM 24

The proof shows that Cloc corrects any E = n−(δ−1) node erasures by mapping them to at most D−1 rank erasures in the underlying Gabidulin code. It analyzes worst-case erasure patterns across local groups, including cases determined by divisibility and integer decompositions.

  • Proof strategy: Cloc corrects any E = n−(δ−1) node erasures because they induce at most D−1 rank erasures in the Gabidulin code.The worst case concentrates erasures in as few local groups as possible, maximizing erasures within each affected group.
  • Case analysis: The proof decomposes M as M = α(α1r + β1) + γ1 and treats separately whether r + δ −1 divides n.The decomposition uses 1 ≤ α1 ≤ g, 0 ≤ β1 ≤ r−1, and 0 ≤ γ1 ≤ α−1.
  • Case analysis: When α1 = g, E = (g −α1)(r + δ −1) + (δ −1), corresponding to D−1 = (g−α1)rα rank erasures.These erasures are correctable by the Gabidulin code.
  • Case analysis: When α1 < g, the worst pattern erases complete local groups plus one partial group, producing (g−α1)rα − β1α = D−1 rank erasures.This applies to the corresponding case described using E = (g−α1−1)(r + δ −1) + (r + δ −1−β1).
  • Case analysis: The remaining remainder cases yield rank-erasure counts below D−1, including (g−α1−1)rα + (β0−β1)α −α < D−1.Thus, the Gabidulin code corrects these patterns as well.
Loading 1210.6954v2…