CaltechTHESIS
  A Caltech Library Service

Coding for Security and Reliability in Distributed Systems

Citation

Huang, Wentao (2017) Coding for Security and Reliability in Distributed Systems. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z9P26W5C. http://resolver.caltech.edu/CaltechTHESIS:06042017-212503971

Abstract

This dissertation studies the use of coding techniques to improve the reliability and security of distributed systems. The first three parts focus on distributed storage systems, and study schemes that encode a message into n shares, assigned to n nodes, such that any n - r nodes can decode the message (reliability) and any colluding z nodes cannot infer any information about the message (security). The objective is to optimize the computational, implementation, communication and access complexity of the schemes during the process of encoding, decoding and repair. These are the key metrics of the schemes so that when they are applied in practical distributed storage systems, the systems are not only reliable and secure, but also fast and cost-effective.

Schemes with highly efficient computation and implementation are studied in Part I. For the practical high rate case of r ≤ 3 and z ≤ 3, we construct schemes that require only r + z XORs to encode and z XORs to decode each message bit, based on practical erasure codes including the B, EVENODD and STAR codes. This encoding and decoding complexity is shown to be optimal. For general r and z, we design schemes over a special ring from Cauchy matrices and Vandermonde matrices. Both schemes can be efficiently encoded and decoded due to the structure of the ring. We also discuss methods to shorten the proposed schemes.

Part II studies schemes that are efficient in terms of communication and access complexity. We derive a lower bound on the decoding bandwidth, and design schemes achieving the optimal decoding bandwidth and access. We then design schemes that achieve the optimal bandwidth and access not only for decoding, but also for repair. Furthermore, we present a family of Shamir's schemes with asymptotically optimal decoding bandwidth.

Part III studies the problem of secure repair, i.e., reconstructing the share of a (failed) node without leaking any information about the message. We present generic secure repair protocols that can securely repair any linear schemes. We derive a lower bound on the secure repair bandwidth and show that the proposed protocols are essentially optimal in terms of bandwidth.

In the final part of the dissertation, we study the use of coding techniques to improve the reliability and security of network communication.

Specifically, in Part IV we draw connections between several important problems in network coding. We present reductions that map an arbitrary multiple-unicast network coding instance to a unicast secure network coding instance in which at most one link is eavesdropped, or a unicast network error correction instance in which at most one link is erroneous, such that a rate tuple is achievable in the multiple-unicast network coding instance if and only if a corresponding rate is achievable in the unicast secure network coding instance, or in the unicast network error correction instance. Conversely, we show that an arbitrary unicast secure network coding instance in which at most one link is eavesdropped can be reduced back to a multiple-unicast network coding instance. Additionally, we show that the capacity of a unicast network error correction instance in general is not (exactly) achievable. We derive upper bounds on the secrecy capacity for the secure network coding problem, based on cut-sets and the connectivity of links. Finally, we study optimal coding schemes for the network error correction problem, in the setting that the network and adversary parameters are not known a priori.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Secret sharing; Security; Coding theory; Network coding; Distributed storage; Reliability; Distributed system; Communication complexity; Computational complexity; Capacity; Reduction
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Bruck, Jehoshua
Thesis Committee:
  • Bruck, Jehoshua (chair)
  • Low, Steven H.
  • Hassibi, Babak
  • Effros, Michelle
  • Langberg, Michael
Defense Date:15 May 2017
Non-Caltech Author Email:yelohuang (AT) gmail.com
Record Number:CaltechTHESIS:06042017-212503971
Persistent URL:http://resolver.caltech.edu/CaltechTHESIS:06042017-212503971
DOI:10.7907/Z9P26W5C
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/ISIT.2016.7541529DOIArticle adapted for Ch. 3 and Ch. 4.
https://doi.org/10.1109/TIT.2016.2616144DOIArticle adapted for Ch. 8.
https://doi.org/10.1109/ISIT.2015.7282477DOIArticle adapted for Ch. 15.
https://doi.org/10.1109/ISIT.2015.7282931DOIArticle adapted for Ch. 17.
https://doi.org/10.1109/ISIT.2014.6874804DOIArticle adapted for Ch. 16.
https://doi.org/10.1109/ALLERTON.2014.7028486DOIArticle adapted for Ch. 15.
https://doi.org/10.1109/NetCod.2013.6570814DOIArticle adapted for Ch. 14.
https://doi.org/10.1109/INFCOM.2013.6566776DOIArticle adapted for Ch. 17.
ORCID:
AuthorORCID
Huang, Wentao0000-0003-0963-3624
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10269
Collection:CaltechTHESIS
Deposited By: Wentao Huang
Deposited On:07 Jun 2017 00:16
Last Modified:15 Jun 2017 16:56

Thesis Files

[img]
Preview
PDF - Final Version
See Usage Policy.

3665Kb

Repository Staff Only: item control page