Toward Optimal Secure Distributed Storage Systems With Exact Repair

Ravi Tandon, SaiDhiraj Amuru, Thomas Charles Clancy, Richard Michael BuehrerIEEE Trans. Information Theory 2016 · OpenReview

TL;DR

This paper tackles the challenge of designing secure distributed storage systems (DSSs) that can perfectly repair lost data while protecting against eavesdroppers. The authors establish fundamental limits on the trade-off between storage capacity and repair bandwidth, revealing that for strong security against repair data eavesdropping (Type-II attacks), only the most bandwidth-efficient storage configurations (MBR points) are optimal, unlike less stringent security scenarios.

What Problem Does This Paper Address?

Storing vast amounts of data reliably is crucial, and distributed storage systems (DSSs) are a common solution. These systems store data across multiple nodes, allowing recovery even if some nodes fail. However, two critical challenges arise: exact repair and security. Exact repair means a failed node must be replaced with an identical copy, crucial for sensitive data. Security is paramount, especially against adversaries who might eavesdrop on stored data (Type-I attack) or, more insidiously, on the data used to repair failed nodes (Type-II attack). Existing work often focused on functional repair (where the repaired node doesn't need to be an exact replica) or less stringent security models. This paper aims to characterize the optimal trade-off between storage per node (α) and repair bandwidth (dβ) for DSSs that guarantee both exact repair and security against both Type-I and Type-II eavesdropping, particularly for smaller system sizes (n ≤ 4) and generalizable to larger systems under specific conditions.

Methods

The paper employs information-theoretic tools, specifically focusing on converse proofs to establish upper bounds on achievable storage-bandwidth trade-offs. The core of their contribution lies in developing novel converse proofs for the more challenging Type-II adversarial scenario. They analyze the system using concepts like entropy and mutual information to quantify information leakage. By carefully constructing sequences of inequalities based on file regeneration, exact repair, and security constraints, they derive fundamental limits on the maximum file size that can be stored securely. For achievability, they leverage existing coding schemes for specific points (like MBR) and propose new constructions for other points, demonstrating that their derived bounds are indeed tight.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Type-II security is a significant bottleneck: The paper demonstrates that the stringent security requirement against eavesdropping on repair data (Type-II attacks) fundamentally limits the achievable storage-bandwidth trade-off.
  • MBR is the only optimal point for Type-II security: Unlike Type-I attacks where a spectrum of storage-bandwidth configurations can be optimal, for Type-II attacks, only the Minimum Bandwidth Regenerating (MBR) point (where storage α is proportional to repair bandwidth dβ) offers an optimal trade-off. This means you can't achieve higher storage efficiency beyond MBR while maintaining Type-II security.
  • Exact repair adds complexity: The requirement for exact repair, while practical, further constrains the design space and necessitates careful information-theoretic analysis.
  • Novel converse proofs are key: The paper's main technical contribution is the development of new information-theoretic converse proofs that rigorously establish these trade-off bounds, particularly for the Type-II scenario.

Key Results

The paper provides optimal characterizations of the secure storage-vs-exact-repair-bandwidth trade-off regions for specific DSS configurations:

  • (3,2,2)-DSS with l=1:
    • Type-I security: $B \le \min(\alpha, \beta)$
    • Type-II security: $B \le \min(2, \beta)$
  • (4,2,3)-DSS with l=1:
    • Type-I security: $B \le \min(\alpha, 2\beta)$
    • Type-II security: $B \le \min(\frac{2}{3}\alpha, \frac{2}{3}\beta)$
  • (4,3,3)-DSS with l=1:
    • Type-I security: $B \le \min(\alpha, 2\beta) + \min(\alpha, \beta)$ and $B \le \frac{\alpha+6\beta}{3}$
    • Type-II security: $B \le \min(\alpha, 3\beta)$
  • (4,3,3)-DSS with l=2:
    • Type-I security: $B \le \min(\alpha, \beta)$
    • Type-II security: $B \le \min(\frac{1}{3}\alpha, \beta)$
  • (n, n-1, n-1)-DSS with l=n-2:
    • Type-I security: $B \le \min(\alpha, \beta)$
    • Type-II security: $B \le \frac{\alpha}{n-1}$

These results highlight the gap between Type-I and Type-II security, with Type-II security imposing stricter limitations, often forcing the system to operate at the MBR point.

Limitations and Future Work

  • General (n, k, d)-DSS: While the paper makes progress for specific small values of n (up to 4) and for the (n, n-1, n-1) case, a complete characterization for a general (n, k, d)-DSS with Type-II security remains an open problem.
  • Practical Implementation: The paper focuses on theoretical limits. Translating these optimal codes into practical, efficient implementations for large-scale systems is a significant engineering challenge.
  • Other Adversarial Models: The paper considers passive eavesdroppers. Future work could explore more active adversarial models.
  • Extending to other parameters: The authors suggest that extending these results to other values of 'l' (number of compromised nodes) and different DSS parameters is part of their ongoing work.

Summary updated

Abstract

Distributed storage systems (DSSs) in the presence of an external wiretapper are considered. A DSS is parameterized by (n, k, d), in which the data are stored across n nodes (each with storage capacity α), and must be recoverable by accessing the contents stored on any k out of n nodes. If a node fails, any d ≥ k out of (n - 1) nodes help in the repair (regeneration) of the failed node (by sending dβ units of repair data, where β ≤ α), so that the data can still be recovered from the DSS. For such a (n, k, d)-DSS, security from the two types of wiretappers is investigated: 1) Type-I (node data) wiretapper, which can read the data stored on any ℓ <; k nodes and 2) Type-II (repair data) wiretapper, which can read the data that is used to repair a set of ℓ failed nodes. The focus of this paper is on the optimal tradeoff between the storage (α) and the repair bandwidth (dβ) in presence of a Type-I/Type-II wiretapper and the practically relevant constraint of exact repair in which a failed node must be replaced by its exact replica. In this paper, several new results and outer bounds for the storage-versus-exact-repair-bandwidth tradeoff(s) are obtained for the Type-I and Type-II security problems. Furthermore, new outer bounds are presented for the Type-II problem, which hold for general (n, k, d, ℓ) parameters. It is shown that these outer bounds strictly improve upon the existing cutset-based outer bounds. The key technical contribution of this paper is in developing novel information theoretic converse proofs for these problems. From our optimal characterization results, we show that in a Type-II setting, the only efficient point in the storage-versus-exact-repair-bandwidth tradeoff is the minimum bandwidth regenerating (MBR) point corresponding to α = dβ. This is in sharp contrast to the Type-I setting in which the optimal tradeoff allows a spectrum of operating points beyond the MBR point.
BibTeX
@article{tandon2016toward,
  author = {Ravi Tandon and SaiDhiraj Amuru and Thomas Charles Clancy and Richard Michael Buehrer},
  title = {{Toward Optimal Secure Distributed Storage Systems With Exact Repair}},
  journal = {IEEE Trans. Information Theory},
  year = {2016},
  url = {https://openreview.net/forum?id=LI9N_2FERSr},
}
Figure