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

Filters

20111

Settings

Author: search.filters.author.Goldman, Michael Ross

Search Results

Now showing 1 - 1 of 1
  • Thumbnail Image
    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.