Graph-based and algebraic codes for error-correction and erasure recovery

Expander codes are sparse graph-based codes with good decoding algorithms. We present a linear-time decoding algorithm for (C,D, alpha, gamma) expander codes based on graphs with any expansion factor given that the minimum distances of the inner codes are bounded below. We also design graph-based codes with hierarchical locality. Such codes provide tiered recovery, depending on the number of erasures. A small number of erasures may be handled by only accessing a few other symbols, allowing for small locality, while larger number may involve a greater number of symbols. This provides an alternative to requiring disjoint repair groups. We also consider availability in this context, relying on the interplay between inner codes and the Tanner graph. We define new families of algebraic geometry codes for the purpose of code-based cryptography. In particular, we consider twisted Hermitian codes, twisted codes from a quotient of the Hermitian curve; and twisted norm-trace codes. These codes have Schur squares with large dimensions and hence could be considered as potential replacements for Goppa codes in the McEliece cryptosytem. However, we study the code-based cryptosystem based on twisted Hermitian codes and lay foundations for a potential attack on such a cryptosystem.