Maximal curves, zeta functions, and digital signatures - Malmskog, Beth, author; Pries, Rachel, advisor; Achter, Jeffrey, committee member; Penttila, Tim, committee member; Roberts, Jacob, committee member (Colorado State University. Libraries, 2011)
Curves with as many points as possible over a finite field Fq under the Hasse-Weil bound are called maximal curves. Besides being interesting as extremal objects, maximal curves have applications in coding theory. A maximal curves may also have a great deal of symmetry, i.e. have an automorphism group which is large compared to the curve's genus. In Part 1, we study certain families of maximal curves and find a large subgroup of each curve's automorphism group. We also give an upper bound for the size of the automorphism group. In Part 2, we study the zeta functions of graphs. The Ihara zeta function of a graph was defined by Ihara in the 1960s. It was modeled on other zeta functions in its form, an infinite product over primes, and has some analogous properties, for example convergence to a rational function. The knowledge of the zeta function of a regular graph is equivalent to knowledge of the eigenvalues of its adjacency matrix. We calculate the Ihara zeta function for an infinite family of irregular graphs and consider how the same technique could be applied to other irregular families. We also discuss ramified coverings of graphs and a joint result with Michelle Manes on the divisibility properties of zeta functions for graphs in ramified covers. Part 3 is joint work with Jeremy Muskat. Gauss's curve, with equation x2t2 + y2t2 + x2y2 - t4 = 0 defined over Fp was the subject of the last entry in Gauss' mathematical diary. For p equivalent to 3 ≡ 4, we give a proof that the zeta function of C is ZC(u) = (1 + pu2)(1 + u)2/(1 - pu)(1 - u). Using this, we find the global zeta function for C. The best algorithms for solving some lattice problems, like finding the shortest vector in an arbitrary lattice, are exponential in run-time. This makes lattice problems a potentially good basis for cryptographic protocols. Right now, lattices are especially important in information security because there are no known quantum computer algorithms that solve lattice problems any faster than traditional computing. The learning with errors problem (LWE) is provably as hard as certain lattice problems. Part 4 of the dissertation is a description of a digital signature scheme based on the learning with errors problem over polynomial rings. The search version of LWE is to find a hidden vector s, given access to many pairs of noisy inner products with random vectors (ai, bi = ai • s + ei). The context can be shifted to a polynomial ring over Z/q, giving rise to the problem of learning with errors over a ring (R-LWE). In this joint work with Kristin Lauter, Michael Naehrig, and Vinod Vaikuntanathan, we devise a digital signature scheme based on R-LWE and outline a proof of security for certain parameter choices.
Keywords: Ihara zeta function; maximal curves