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.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Mathematics

Department dc:contributor.department

Mathematics

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2022

Author dc:creator

• Kshirsagar, Rutuja Milind

Chair dc:contributor.committeechair

• Matthews, Gretchen L.

Committee members dc:contributor.committeemember

• Manganiello, Felice
• Mihalcea, Constantin Leonardo
• Loehr, Nicholas A.

• Graph-based code
• decoding
• local recovery
• algebraic geometry code
• code-based cryptography

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Dc Identifier Other

vt_gsexam:33976

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/108879