UMD Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/3
New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a given thesis/dissertation in DRUM.
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
2 results
Search Results
Item Fast Hashing in Elliptic and Hyperelliptic Curves(2011) Goldman, Michael Ross; Washington, Lawrence C; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The BLS Digital Signature Algorithm is a cryptographic scheme using elliptic curves over finite fields. In the BLS Digital Signature Algorithm, we require a function that maps a arbitrary element of a finite field to an elliptic curve in that field. There is a simple, naive way to do this, but it is not particularly fast. In a recent paper, Paulo S. L. M. Barreto and Hae Y. Kim described an algorithm that speeds up the computation significantly (by about two orders of magnitude). This speed up in computation is due to avoiding square roots in these finite fields. Square root computation in these fields leads to speeds of O(r^3). Barreto and Kim's techniques uses the fact that cubing in a finite field of characteristic 3 is a fast, linear operation on the order of O(r). Barreto and Kim's complete algorithm takes O(r^2) steps, a major improvement. However, this algorithm is only for specific elliptic curves of the form x^3 - x + b = y^2. The goal of this paper is to extend this algorithm to significantly more elliptic curves in characteristic 3. To do so, we consider other elliptic curves of similar construction (of the form x^3 + x + b = y^2), and then we reduce much more general cases to these two curves. We also describe the limitations of these techniques for other elliptic curves. We then extend this algorithm to a more general case of hyperelliptic curves in characteristic p. Similarly to the case in characteristic 3, raising to the p-th power is a fast operation in characteristic p. We first look at a more simple case, where the elliptic curve is described as x^p + &beta x + b = y^2, where &beta is in the base field of Fp. Then we seek to generalize to where &beta is any element in our field. Once again, we describe the limitations of these techniques when applying them to other curves. After initial setup costs, the algorithm remains at the speed O(r^2). In certain cases, the algorithm will converge at a rate 1/p, and in other cases, the algorithm will be deterministic.Item Number Theoretic Algorithms For Elliptic Curves(2008-05-09) Belding, Juliana V.; Washington, Lawrence; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)We present new algorithms related to both theoretical and practical questions in the area of elliptic curves and class field theory. The dissertation has two main parts, as described below. Let O be an imaginary quadratic order of discriminant D< 0, and let K be the associated quadratic imaginary field. The class polynomial H_D of O is the polynomial whose roots are precisely the j-invariants of elliptic curves with complex multiplication by O. Computing this polynomial is useful in constructing elliptic curves suitable for cryptography, as well as in the context of explicit class field theory. In the first part of the dissertation, we present an algorithm to compute H_D p-adically where p is a prime inert in K and not dividing D. This involves computing the canonical lift of a pair (E,f) where E is a supersingular elliptic curve and f is an embedding of O into the endomorphism ring of E. We also present an algorithm to compute H_D modulo p for p inert which is used in the Chinese remainder theorem algorithm to compute H_D. For an elliptic curve E over any field K, the Weil pairing is a bilinear map on the points of order n of E. The Weil pairing is a useful tool in both the theory of elliptic curves and the application of elliptic curves to cryptography. However, for K of characteristic p, the classical Weil pairing on the points of order p is trivial. In the second part of the dissertation, we consider E over the dual numbers of K and define a non-degenerate ``Weil pairing on p-torsion." We show that this pairing satisfies many of the same properties of the classical pairing. Moreover, we show that it directly relates to recent attacks on the discrete logarithm problem on the p-torsion subgroup of an elliptic curve over a finite field of characteristic p. We also present a new attack on the discrete logarithm problem on anomalous curves using a lift of E over the dual numbers of the finite field of p elements.