Improved Bounds for Codes and Secret Sharing Schemes from Algebraic Curves

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

Kirov, Radoslav M.

关键词: algebraic geometric codes;    error-correcting codes;    linear secret sharing schemes;    hermitian curve;    suzuki curve;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/16738/Kirov_Radoslav.pdf?sequence=2&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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.