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

Simple item page
dc.contributor.authorKshirsagar, Rutuja Milinden
dc.contributor.committeechairMatthews, Gretchen L.en
dc.contributor.committeememberManganiello, Feliceen
dc.contributor.committeememberMihalcea, Constantin Leonardoen
dc.contributor.committeememberLoehr, Nicholas A.en
dc.contributor.departmentMathematicsen
dc.date.accessioned2022-02-26T09:00:25Zen
dc.date.available2022-02-26T09:00:25Zen
dc.date.issued2022-02-25en
dc.description.abstractExpander 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.en
dc.description.abstractgeneralCoding 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.en
dc.description.degreeDoctor of Philosophyen
dc.format.mediumETDen
dc.identifier.othervt_gsexam:33976en
dc.identifier.urihttp://hdl.handle.net/10919/108879en
dc.language.isoenen
dc.publisherVirginia Techen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectGraph-based codeen
dc.subjectdecodingen
dc.subjectlocal recoveryen
dc.subjectalgebraic geometry codeen
dc.subjectcode-based cryptographyen
dc.titleGraph-based and algebraic codes for error-correction and erasure recoveryen
dc.typeDissertationen
thesis.degree.disciplineMathematicsen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.leveldoctoralen
thesis.degree.nameDoctor of Philosophyen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Kshirsagar_RM_D_2022.pdf
Size:
829.73 KB
Format:
Adobe Portable Document Format
Download

Collections

Doctoral Dissertations