Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Fast Hashing in Elliptic and Hyperelliptic Curves

    Thumbnail
    View/Open
    Goldman_umd_0117N_12417.pdf (9.617Mb)
    No. of downloads: 451

    Date
    2011
    Author
    Goldman, Michael Ross
    Advisor
    Washington, Lawrence C
    Metadata
    Show full item record
    Abstract
    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 F<sub>p</sub>. 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.
    URI
    http://hdl.handle.net/1903/11873
    Collections
    • Mathematics Theses and Dissertations
    • UMD Theses and Dissertations

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility