Group Law Computations on Jacobians of Hyperelliptic Curves

Craig Costello, Kristin E. Lauter

TL;DR

This paper introduces a novel, geometrically inspired method for computing group operations on the Jacobians of hyperelliptic curves. By leveraging linear algebra over finite fields, the authors provide explicit formulas that are significantly faster than previous methods, particularly for genus 2 curves, and offer a unified approach for arbitrary genus.

What Problem Does This Paper Address?

Public-key cryptography often relies on the difficulty of solving discrete logarithm problems in finite groups. While elliptic curves offer a good balance of security and efficiency, hyperelliptic curves of higher genus can provide equivalent security with smaller key sizes. However, performing group operations (addition and doubling) on the Jacobian of a hyperelliptic curve is computationally expensive, especially as the genus increases. Existing algorithms, like Cantor's, involve complex polynomial arithmetic. This paper aims to bridge this gap by developing more efficient and explicit formulas for these computations, making hyperelliptic curve cryptography more practical.

Methods

The core contribution of this paper is a new approach to the "composition phase" of group law computations on hyperelliptic curve Jacobians. Instead of relying on polynomial arithmetic over finite fields (as in Cantor's algorithm), the authors use a geometric interpretation of the group law. This allows them to formulate the problem as solving a linear system over the base field, directly using the Mumford coordinates of the group elements.

Key techniques include:

  • Geometric Interpretation: Visualizing the group law on the curve to understand the relationships between points and divisors.
  • Mumford Representation: Using a standard polynomial representation for divisors on the Jacobian.
  • Linear Systems: Formulating the problem of finding interpolating functions as solving linear systems over the finite field. This avoids explicit polynomial arithmetic and directly yields field operations.
  • Explicit Formulas: Deriving concrete, implementation-ready formulas for addition and doubling, especially for genus 2 curves.
  • Generalization: Extending the method to arbitrary genus hyperelliptic curves.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm development and provides MAGMA scripts for verification, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Geometry Simplifies Algebra: The geometric understanding of the group law provides a more direct path to efficient algebraic computation, bypassing complex polynomial manipulations.
  • Linear Systems are Key: Framing the problem as solving linear systems over the base field (Fq) is a significant departure from previous methods that operated in polynomial rings (Fq[x]). This leads to more direct and efficient computations.
  • Unified Approach: The method is generalizable to arbitrary genus, offering a consistent framework for hyperelliptic curve cryptography.
  • Genus 2 Efficiency: The derived formulas for genus 2 curves are shown to be faster than existing state-of-the-art methods.

Key Results

The paper presents explicit formulas for group operations on the Jacobians of hyperelliptic curves. For genus 2 curves, their affine and projective formulas are demonstrated to be more efficient than previous methods, particularly when using prime fields. The authors provide detailed cost analyses in terms of field operations (multiplications and squarings) in Table 1 and Table 2, showing competitive or superior performance. The method is also generalized for arbitrary genus, offering a unified approach.

Limitations and Future Work

The authors acknowledge that for very low genus implementations, existing methods might still be competitive. They also suggest that further optimizations could be achieved by:

  • Special Cases: Developing tailor-made formulas for specific curve forms or special input divisors (e.g., divisors of degree less than g).
  • Characteristic Two: Adapting the methods for curves over fields of characteristic two.
  • Projective Coordinates: Exploring extensions to the projective coordinate system for even greater efficiency.
  • Solving Linear Systems: Investigating specialized methods for solving the linear systems that arise, particularly for higher genera.
  • Simultaneous Operations: Applying the technique to more complex operations like simultaneous additions and doublings, and exploring its utility in pairing computations.

Summary updated

BibTeX
@article{costello2011group,
  author = {Craig Costello and Kristin E. Lauter},
  title = {{Group Law Computations on Jacobians of Hyperelliptic Curves}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2011},
}
Figure