# Fast Hashing in Elliptic and Hyperelliptic Curves

 dc.contributor.advisor Washington, Lawrence C en_US dc.contributor.author Goldman, Michael Ross en_US dc.date.accessioned 2011-10-08T05:33:47Z dc.date.available 2011-10-08T05:33:47Z dc.date.issued 2011 en_US dc.identifier.uri http://hdl.handle.net/1903/11873 dc.description.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 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. en_US dc.title Fast Hashing in Elliptic and Hyperelliptic Curves en_US dc.type Thesis en_US dc.contributor.publisher Digital Repository at the University of Maryland en_US dc.contributor.publisher University of Maryland (College Park, Md.) en_US dc.contributor.department Mathematics en_US dc.subject.pqcontrolled Mathematics en_US dc.subject.pquncontrolled Cryptography en_US dc.subject.pquncontrolled Elliptic Curves en_US dc.subject.pquncontrolled Hashing en_US
﻿