Trace zero cryptography

In the year 1998 Gerhard Frey firstly purposed using trace zero varieties for cryptographic purpose. These varieties are subgroups of the divisor class group on a low genus hyperelliptic curve defined over a finite field. These groups can be used to establish asymmetric cryptography

Mathematical backgroud

A hyperelliptic curve C of genus g over a prime field $\mathbb {F} _{q}$ where q = pⁿ (p prime) of odd characteristic is defined as

$C:~y^{2}+h(x)y=f(x),$

where f monic, deg(f) = 2g+1 and deg(h) ≤ g. The curve has at least one $\mathbb {F} _{q}$-rational Weierstraßpoint.

The Jacobian variety $J_{C}(\mathbb {F} _{q^{n}})$ of C is for all finite extension $\mathbb {F} _{q^{n}}$ isomorphic to the ideal class group $\operatorname {Cl} (C/\mathbb {F} _{q^{n}})$. With the Mumford's representation it is possible to represent the elements of $J_{C}(\mathbb {F} _{q^{n}})$ with a pair of polynomials [u, v], where u, v ∈ $\mathbb {F} _{q^{n}}[x]$.

The Frobenius endomorphism σ is used on an element [u, v] of $J_{C}(\mathbb {F} _{q^{n}})$ to raise the power of each coefficient of that element to q: $sigma([u, v]) = [u^q(x), v^q(x)]. The characteristic polynomial of this endomorphism has the following form:

$\chi (T)=T^{2g}+a_{1}T^{2g-1}+\dots +a_{g}T^{g}+\dots +a_{1}q^{g-1}T+q^{g},$ where a_i in ℤ

With the Hasse-Weil theorem it is possible to receive the group order of any extension field $\mathbb {F} _{q^{n}}$ by using the complex roots τ_i of χ(T):

$|J_{C}(\mathbb {F} _{q^{n}})|=\prod _{i=1}^{2g}(1-\tau _{i}^{n})$

Let D be an element of the $J_{C}(\mathbb {F} _{q^{n}})$ of C, then it is possible to define an endomorphism of $J_{C}(\mathbb {F} _{q^{n}})$, the so called \textit{trace of D}:

$\operatorname {Tr} (D)=\sum _{i=0}^{n-1}\sigma ^{i}(D)=D+\sigma (D)+\dots +\sigma ^{n-1}(D)$

Based on this endomorphism one can reduce the Jacobian variety to a subgroup G with the property, that every element is of trace zero:

$G=\{D\in J_{C}(\mathbb {F} _{q^{n}})~|~{\text{Tr}}(D)={\textbf {\textit {0}}}\},~~~({\textbf {\textit {0}}}{\text{ neutral element in }}J_{C}(\mathbb {F} _{q^{n}})$

G is the kernel of the trace endomorphism and thus G is a group, the so called trace zero (sub)variety (TZV) of $J_{C}(\mathbb {F} _{q^{n}})$.

The intersection of G and $J_{C}(\mathbb {F} _{q})$ is produced by the n-torsion elements of $J_{C}(\mathbb {F} _{q})$. If the greatest common divisor $\gcd(n,|J_{C}(\mathbb {F} _{q})|)=1$ the intersection is empty and one can compute the group order of G:

$|G|={\dfrac {|J_{C}(\mathbb {F} _{q^{n}})|}{|J_{C}(\mathbb {F} _{q})|}}={\dfrac {\prod _{i=1}^{2g}(1-\tau _{i}^{n})}{\prod _{i=1}^{2g}(1-\tau _{i})}}$

There exist three different cases of cryptograpghical relevance for TZV:

• g = 1, n = 3
• g = 1, n = 5
• g = 2, n = 3