1.1 What is G2HEC?

The G2HEC (Genus 2 HyperElliptic Curve) library is a free portable C++ library providing divisor group operations in the Jacobian of genus 2 (imaginary) hyperelliptic curve. Such curves can be used for discrete-logarithm-based cryptosystems with advantages over elliptic curves (genus 1 curves). Divisor group operations are essential to using genus 2 curves for cryptography.

It is built on top of V. Shoup’s NTL library, "a high performance, portable C++ library providing data structures and algorithms for arbitrary length integers; for vectors, matrices, and polynomials over the integers and over finite fields; and for arbitrary precision floating point arithmetic."

It is recommended to build NTL using GMP (the GNU Multi-Precision package) for best performance. However, the G2HEC library can be built and used with and without the existence of GMP.

This library does not assume users’ familiarity with any non-trivial math background except basic concepts of finite fields and polynomials. No prior knowledge of genus 2 curve is needed to used the library.

The G2HEC library is released under the GNU General Public License. See the file COPYING for details.

The G2HEC library homepage: https://github.com/syncom/libg2hec/.

The NTL library homepage: http://www.shoup.net/ntl/.

The GMP library homepage: http://www.swox.com/gmp/.

1.2 Genus 2 curve basics

Our object of interest, a genus 2 curve, is a nonsingular algebraic curve

over a finite field GF(q), where f(x) is monic (i.e., has leading coefficient 1) of degree 5, h(x) has degree not greater than 2, q is a prime or a power of a prime.

Currently (version 1.0.1) G2HEC only supports odd prime q by default. You can “hack” the header file in include/g2hec_nsfieldtype.h to switch its support to q as a power of an odd prime. However, we do not recommend to do so and it should be avoided except in extreme cases. So far the library is tested only for odd prime numbers q.

There is currently no “hack” to have field types GF2 and GF2E supported (curve singularity test does not work for characteristic 2 yet). Support for characteristic 2 maybe added in the future.

A pair (x_0, y_0) with x_0, y_0\in GF(q) such that x = x_0 and y = y_0 give a solution to the curve equation of C is called a GF(q)-rational point of the genus 2 curve C. Obviously, C has only finitely many GF(q)-rational points. Unlike the case of elliptic curves, the set of GF(q)-rational points of the curve C does not naturally hold a group structure, therefore they cannot be used directly to do discrete-logarithm-based cryptography. Instead, we choose to use the GF(q)-rational points of the Jacobian of the curve C, which is a finite group, to achieve our (cryptographic) goal. It is not necessary for the users of the G2HEC library know how the Jacobian of a genus 2 curve is defined, given the following two facts:

1. The GF(q)-rational points of the Jacobian of a genus 2 curve C, Jac(C, GF(q)), is a finite group of size approximately q^2.
2. An element of Jac(C, GF(q)) is called a divisor class (divisor in short) over GF(q). A divisor (class) D is represented by a pair of polynomials [u(x), v(x)] over GF(q). Several conditions need to be satisfied for a pair [u(x), v(x)] to be a divisor of C.

The unit element of Jac(C, GF(q)) is [1, 0].

By convention, the group operation in the Jacobian of the curve C is written additively. We shall write

for divisor addition, divisor subtraction and divisor scalar multiplication, respectively, where D=[n]D_1 means D=D_1+D_1+...+D_1 for n times.

More information about the math background of the Jacobian of genus 2 curves can be found in the book “Handbook of Elliptic And Hyperelliptic Curve Cryptography” by Cohen et al.

In addition to the high-level functions that operates on curves and divisors, the G2HEC library also exports low-level functions that allow knowledgeable users to take control of mathematical factors of curves and divisors. Our intent is to make the library useful for both mathematicians and cryptographers (or the ones who play both roles).