Let G be a finite cyclic group. Solving the equation g^x = y for a given generator g and y is called the discrete logarithm problem. This problem is at the core of many modern cryptographic transformations. In this paper we provide a survey of algorithms to attack this problem, including the function field sieve, the fastest known algorithm applicable to the multiplicative group of a finite field. We also discuss the index calculus algorithm and some techniques improving its performance: the Coppersmith's algorithm and the polynomial sieving. The most important contribution of this paper is a C-language implementation of the function field sieve and its application to real inputs.

Let K/Fq be an algebraic function field with full constant field Fq and genus g. Then the divisor class number hK of K/Fq is the order of the quotient group, D0K /P(K), degree zero divisors of K over principal divisors of K. The classification of the function fields K with hK = 1 is done by MacRea, Leitzel, Madan and Queen and the classification of the extensions with class number two is done by Le Brigand. Determination of the necessary and the sufficient conditions for a function field to have class number three is done by H&uml / ulya T&uml / ore. Let k := Fq(T) be the rational function field over the finite field Fq with q elements. For a polynomial N &isin / Fq[T], we construct the Nth cyclotomic function field KN. Cyclotomic function fields were investigated by Carlitz, studied by Hayes, M. Rosen, M. Bilhan and many other mathematicians. Classification of cyclotomic function fields and subfields of cyclotomic function fields with class number one is done by Kida, Murabayashi, Ahn and Jung. Also the classification of function fields with genus one and classification of those with class number two is done by Ahn and Jung. In this thesis, we classified all algebraic function fields and subfields of cyclotomic function fields over finite fields with class number three.

Advancement in cryptography over the past few decades has enabled a spectrum of security mechanisms and protocols for many applications. Despite the algorithmic security of classic cryptography, there are limitations in application and implementation of standard security methods in ultra-low energy and resource constrained systems. In addition, implementations of standard cryptographic methods can be prone to physical attacks that involve hardware level invasive or non-invasive attacks. Physical unclonable functions (PUFs) provide a complimentary security paradigm for a number of application spaces where classic cryptography has shown to be inefficient or inadequate for the above reasons. PUFs rely on intrinsic device-dependent physical variation at the microscopic scale. Physical variation results from imperfection and random fluctuations during the manufacturing process which impact each device’s characteristics in a unique way. PUFs at the circuit level amplify and capture variation in electrical characteristics to derive and establish a unique device-dependent challenge-response mapping. Prior to this work, PUF implementations were unsuitable for low power applications and vulnerable to wide range of security attacks. This doctoral thesis presents a coherent framework to derive formal requirements to design architectures and protocols for PUFs. To the best of our knowledge, this is the first comprehensive work that introduces and integrates these pieces together. The contributions include an introduction of structural requirements and metrics to classify and evaluate PUFs, design of novel architectures to fulfill these requirements, implementation and evaluation of the proposed architectures, and integration into real-world security protocols. First, I formally define and derive a new set of fundamental requirements and properties for PUFs. This work is the first attempt to provide structural requirements and guideline for design of PUF architectures. Moreover, a suite of statistical properties of PUF responses and metrics are introduced to evaluate PUFs. Second, using the proposed requirements, new and efficient PUF architectures are designed and implemented on both analog and digital platforms. In this work, the most power efficient and smallest PUF known to date is designed and implemented on ASICs that exploits analog variation in sub-threshold leakage currents of MOS devices. On the digital platform, the first successful implementation of Arbiter-PUF on FPGA was accomplished in this work after years of unsuccessful attempts by the research community. I introduced a programmable delay tuning mechanism with pico-second resolution which serves as a key component in implementation of the Arbiter-PUF on FPGA. Full performance analysis and comparison is carried out through comprehensive device simulations as well as measurements performed on a population of FPGA devices. Finally, I present the design of low-overhead and secure protocols using PUFs for integration in lightweight identification and authentication applications. The new protocols are designed with elegant simplicity to avoid the use of heavy hash operations or any error correction. The first protocol uses a time bound on the authentication process while second uses a pattern-matching index-based method to thwart reverseengineering and machine learning attacks. Using machine learning methods during the commissioning phase, a compact representation of PUF is derived and stored in a database for authentication.

This thesis focuses upon how to calculate local components of Weil differentials of an elliptic function field. Because Weil differentials constitute a one-dimension vector space then one Weil differential is fixed. An algorithm calculating a local component is developed for the fixed one. The first algorithm computes local components of places of degree one. It is based upon elementary properties of local components. The definition of the Weil differential does not say enough about why it is defined in this way and about why it is useful. Thus there is the relationship between the Weil differential and some objects from complex analysis like the Laurent series and the residue. It provides a better understanding of properties of the Weil differential. The result of this thesis are other two algorithms calculating local components of Weil differentials. The algorithms employ the residue. 1

<p>This thesis surveys the issue of finding rational points on algebraic curves over finite fields. Since Goppa's construction of algebraic geometric codes, there has been great interest in finding curves with many rational points. Here we explain the main tools for finding rational points on a curve over a nite eld and provide the necessary background on ring and field theory. Four different articles are analyzed, the first of these articles gives a complete set of table showing the numbers of rational points for curves with genus up to 50. The other articles provide interesting constructions of covering curves: covers by the Hemitian curve, Kummer extensions and Artin-Schreier extensions. With these articles the great difficulty of finding explicit equations for curves with many rational points is overcome. With the method given by Arnaldo García in [6] we have been able to nd examples that can be used to define the lower bounds for the corresponding entries in the tables given in http: //wins.uva.nl/~geer, which to the time of writing this Thesis appear as "no information available". In fact, as the curves found are maximal, these entries no longer need a bound, they can be given by a unique entry, since the exact value of N_q(g) is now known.</p><p>At the end of the thesis an outline of the construction of Goppa codes is given and the NXL and XNL codes are presented.</p><p> </p>

This thesis surveys the issue of finding rational points on algebraic curves over finite fields. Since Goppa's construction of algebraic geometric codes, there has been great interest in finding curves with many rational points. Here we explain the main tools for finding rational points on a curve over a nite eld and provide the necessary background on ring and field theory. Four different articles are analyzed, the first of these articles gives a complete set of table showing the numbers of rational points for curves with genus up to 50. The other articles provide interesting constructions of covering curves: covers by the Hemitian curve, Kummer extensions and Artin-Schreier extensions. With these articles the great difficulty of finding explicit equations for curves with many rational points is overcome. With the method given by Arnaldo García in [6] we have been able to nd examples that can be used to define the lower bounds for the corresponding entries in the tables given in http: //wins.uva.nl/~geer, which to the time of writing this Thesis appear as "no information available". In fact, as the curves found are maximal, these entries no longer need a bound, they can be given by a unique entry, since the exact value of Nq(g) is now known. At the end of the thesis an outline of the construction of Goppa codes is given and the NXL and XNL codes are presented.

Fundação de Amparo a Pesquisa do Estado de Minas Gerais / In this work, we study geometric Goppa codes and present several results on the so-called generalized Hamming distances. In the particular case of Hermitian codes we present precise results for the first, second and third generalized distances, for almost all Goppa codes supported on one point. / Neste trabalho estudamos códigos de Goppa e apresentamos diversos resultados sobre as assim chamadas distâncias generalizadas de Hamming. No caso particular de códigos Hermitianos, apresentamos resultados exatos para a primeira, segunda e terceira distâncias generalizadas de Hamming, considerando quase todos os códigos suportados em um ponto. / Mestre em Matemática