Designing Secure and Robust Distribted and Pervasive Systems with Error Correcting Codes

Abstract

This thesis investigates the role of error-correcting codes in Distributed and Pervasive Computing. The main results are at the intersection of Security and Fault Tolerance for these environments. There are two primary areas that are explored in this thesis.

1. We have investigated protocols for large scale fault tolerant secure distributed storage. The two main concerns here are security and redundancy. In one arm of this research we developed SAFE, a distributed storage system based on a new protocol that offers a two-in-one solution to fault-tolerance and confidentiality. This protocol is based on cryptographic properties of error correction codes. In another arm, we developed esf, another prototype distributed persistent storage; esf facilitates seamless hardware extension of storage units, high resilience to loads and provides high availability. The main ingredient in its design is a modern class of erasure codes known as the {em Fountain Codes}. One problem in such large storage is the heavy overhead of the associated fingerprints needed for checking data integrity. esf deploys a clever integrity check mechanism by use of a data structure known as the {em Merkle Tree} to address this issue.

2. We also investigated the design of a new remote authentication protocol. Applications over long range wireless would benefit quite a bit from this design. We designed and implemented LAWN, a lightweight remote authentication protocol for wireless networks that deploys a randomized approximation scheme based on Error correcting codes. We have evaluated in detail the performance of LAWN; while it adds very low overhead of computation, the savings in bandwidth and power are quite dramatic.