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. / Doctor of Philosophy / Coding theory finds applications in various places such as data transmission, data storage, and even post-quantum cryptography. The goal of data transmission is to ensure fast and efficient information transfer. It is ideal to correct maximum number of errors introduced during transmission by noisy channels. We provide a new construction of expander codes (graph-based codes) and provide a linear-time decoding algorithm which corrects a constant-fraction of errors for these codes given any expansion factor. In this context, channel noise causes distortion of symbols, so that received symbols may be different than those originally sent. We are also interested in codes for erasure recovery, meaning those which restore missing symbols. A recent technique to recover the sent messages is by accesing a small subset of this received information, called locality. We analyze the locality properties of Tanner codes equipped with specific inner code. Code-based cryptography is a leading candidate in the post-quantum setting, meaning it is believed to be secure against quantum algorithms. The McEliece cryptosystem in which the underlying code is a Goppa code is popularly studied and is a top candidate in the NIST competition. However, the adoption of this system is not immediate due to its large key sizes. Code-based cryptosystems based on codes other than Goppa codes might provide a solution. We provide constructions of a new family of codes, called twisted algebraic geomtery codes which may provide alternatives of Goppa codes in the McEliece cryptosystem.

Codes from curves over finite fields were first developed in the late 1970's by V. D. Goppa and are known as algebraic geometry codes. Since that time, the construction has been tailored to fit particular applications, such as erasure recovery and error correction using less received information than in the classical case. The Hermitian-lifted code construction of L'opez, Malmskog, Matthews, Piñero-González, and Wootters (2021) provides codes from the Hermitian curve over $F_{q^2}$ which have the same locality as the well-known one-point Hermitian codes but with a rate bounded below by a positive constant independent of the field size. However, obtaining explicit expressions for the code is challenging. In this dissertation, we consider codes from norm-trace curves, which are a generalization of the Hermitian curve. We develop norm-trace-lifted codes and demonstrate an explicit basis of the codes. We then consider fractional decoding of codes from norm-trace curves, extending the results obtained for codes from the Hermitian curve by Matthews, Murphy, and Santos (2021). / Doctor of Philosophy / Coding theory focuses on recovering information, whether that data is corrupted and changed (called an error) or is simply lost (called an erasure). Classical codes achieve this goal by accessing all received symbols. Because long codes, meaning those with many symbols, are common in applications, it is useful for codes to be able to correct errors and recover erasures by accessing less information than classical codes allow. That is the focus of this dissertation. Codes with locality are designed for erasure recovery using fewer symbols than in the classical case. Such codes are said to have locality $r$ and availability $s$ if each symbol can be recovered from $s$ disjoint sets of $r$ other symbols. Algebraic curves, such as the Hermitian curve or the more general norm-trace curves, offer a natural structure for designing codes with locality. This is done by considering lines intersected with the curve to form repair groups, which are sets of $r+1$ points where the information from one point can be recovered using the rest of the points in the repair group. An error correction method which uses less data than the classical case is that of fractional decoding. Fractional decoding takes advantage of algebraic properties of the field trace to correct errors by downloading only a $lambda$-proportion of the received information, where $lambda < 1$. In this work, we consider a new family of codes resulting from norm-trace curves, and study their locality and availability, as well as apply the ideas of fractional decoding to these codes.

Made available in DSpace on 2015-05-15T11:45:58Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 634504 bytes, checksum: ce035cc957832598c53dda96372e7cb7 (MD5) Previous issue date: 2011-02-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work, based on algebraic function fields, we give constructions of disjoint linear codes. In addition,we study the asymptotic behavior of disjoint linear codes from our constructions. / Neste trabalho, baseados em corpos de funções algébricas, forneceremos construções de códigos lineares disjuntos. Além disso, nós estudaremos comportamentos assintóticos de códigos lineares disjuntos a partir da nossa construção.