Improved Bounds for Codes and Secret Sharing Schemes from Algebraic Curves

Kirov, Radoslav M.

Permalink

https://hdl.handle.net/2142/16738 Copy

Description

Title

Improved Bounds for Codes and Secret Sharing Schemes from Algebraic Curves

Author(s)

Kirov, Radoslav M.

Issue Date

2010-08-20T17:56:22Z

Director of Research (if dissertation) or Advisor (if thesis)

Duursma, Iwan M.

Doctoral Committee Chair(s)

Reznick, Bruce

Committee Member(s)

• Duursma, Iwan M.
• Schenck, Henry K.
• Blahut, Richard E.

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• algebraic geometric codes
• error-correcting codes
• linear secret sharing schemes
• hermitian curve
• suzuki curve

Abstract

The main goal of this work is to improve algebraic geometric/number theoretic constructions of error-correcting codes and secret sharing schemes. For both objects we define parameters that indicate their effectiveness in applications. We explore infeasibility bounds, showing that objects with relatively high parameters cannot exist. The best upper bounds in the theory of error-correcting codes arise from using linear programming on enumerator vectors. We show that similar linear programming techniques are applicable for obtaining infeasibility results for secret sharing schemes. In 1975, V. Goppa established a remarkable connection: function fields of algebraic curves can be used to construct a large class of error-correcting codes. Such codes are called algebraic geometric (AG) codes. AG codes from divisors supported in only one point on the Hermitian curve produce long codes with excellent parameters. Feng and Rao introduced a modified construction that improves the parameters while still using one-point divisors. Their construction is referred to as improved codes. A separate improvement of the parameters was introduced by Matthews; it uses the classical construction but with two-point divisors. We combine those two approaches to produce an infinite family of codes improving on all previously known families of Hermitian codes. The main topic of the thesis is the improvement of lower bounds for the parameters of error-correcting codes and secret sharing schemes using the geometry of divisors on curves. We recall some of the various methods that have been used to obtain improvements of the Goppa lower bound for the minimum distance of an algebraic geometric code. The most successful method is the order bound, which generalizes the Feng-Rao bound. We provide a significant extension of the bound that improves the order bounds by Beelen and by Duursma and Park. Finally, we address ways to efficiently compute the bounds.

Graduation Semester

2010-08

Permalink

http://hdl.handle.net/2142/16738

Copyright and License Information

Copyright 2010 Radoslav M. Kirov

Owning Collections