Template:Orphan 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 using the discrete logarithm problem as cryptographical primitive.

## Mathematical background

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

${\displaystyle 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 ${\displaystyle \mathbb{F}_{q}}$-rational Weierstraßpoint.

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

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

${\displaystyle \chi(T) = T^{2g} + a_1T^{2g-1} + \dots + a_gT^g + \dots + a_1q^{g-1}T + q^g, }$ where ai in Template:Unicode

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

${\displaystyle |J_C(\mathbb{F}_{q^n})| = \prod_{i=1}^{2g} (1 - \tau_i^n) }$

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

${\displaystyle \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:

${\displaystyle 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 ${\displaystyle J_C(\mathbb{F}_{q^n})}$.

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

${\displaystyle |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)} }$

The actual group used in cryptographic applications is a subgroup G0 of G of a large prime order l. This group may be G itself. [1] [2]

There exist three different cases of cryptograpghical relevance for TZV[3]:

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

## Arithmetic

The arithmetic used in the TZV group G0 based on the arithmetic for the whole group ${\displaystyle J_C(\mathbb{F}_{q^n})}$, But it is possible to use the Frobenius endomorphism σ to speed up the scalar multiplication. This can be archived if G0 is generated by D of order l then σ(D) = sD, for some integers s. For the given cases of TZV s can be computed as follows, where ai come from the characteristic polynomial of the Frobenius endomorphism :

• For g = 1, n = 3: ${\displaystyle s = \dfrac {q-1} {1 - a_1} \bmod{\ell} }$
• For g = 1, n = 5: ${\displaystyle s = \dfrac {q^2-q-a_1^2q+a_1q+1} {q-2a_1q+a_1^3-a_1^2+a_1-1} \bmod{\ell} }$
• For g = 2, n = 3: ${\displaystyle s = - \dfrac {q^2-a_2+a_1} {a_1q-a_2+1} \bmod{\ell}}$

Knowing this, it is possible to replace any scalar multiplication mD (|m| ≤ l/2) with:

${\displaystyle m_0D + m_1\sigma(D) + \dots + m_{n-1}\sigma^{n-1}(D), ~~~~\text{where }m_i = O(\ell^{1/(n-1)}) = O(q^g) }$

With this trick the multiple scalar product can be reduced to about 1/(n-1)th of doublings necessary for calculating mD, if the implied constants are small enough.[4][5]

## Security

The security of cryptographic systems based on trace zero subvarieties according of the results of the papers [6] [7] comparable to the security of hyper-elliptic curves of low genus g' over ${\displaystyle \mathbb{F}_{p'}}$, where p' ~ (n-1)(g/g' ) for |G| ~128 bits.

For the cases where n = 3, g = 2 and n = 5, g = 1 it is possible to reduce the security for at most 6 bits, where |G| ~ 2256, because one can not be sure that G is contained in a Jacobian of a curve of genus 6. The security of curves of genus 4 for similar fields are far less secure.

## An attack on a trace zero crypto-system

The attack published in [8] shows, that the DLP in trace zero groups of genus 2 over finite fields of characteristic diverse than 2 or 3 and a field extension of degree 3 can be transformed into a DLP in a class group of degree 0 with genus of at most 6 over the base field. In this new class group the DLP can be attacked with the index calculus methods. This leads to a reduction of the bit length 1/6th.

## Résumé

The first advantage to mention is, that the trace zero varieties feature a better scalar multiplication performance than elliptic curves. This allows a fast arithmetic in this groups, which can speed up the calculations with a factor 3 compared with elliptic curves.

Also is it easily possible to construct groups of cryptographically relevant size and the order of the group can simply be calculated using the characteristic polynomial of the Frobenius endomorphism. Alternatively, one can find cryptographically secure groups by searching a family of randomly chosen curves.[9].

However to represent an element of the trace zero variety more bits are needed compared with elements of elliptic or hyperelliptic curves.

Another point to keep in mind, is the fact, that it is possible to reduce the security of the TZV of 1/6th of the bit length using the described attack.

## Notes

1. G. Frey and T. Lange: "Mathematical background of public key cryptography"
2. T. Lange: "Trace zero subvariety for cryptosystems"
3. R. M. Avanzi and E. Cesena: "Trace zero varieties over ﬁelds of characteristic 2 for cryptographic applications"
4. R. M. Avanzi and E. Cesena: "Trace zero varieties over ﬁelds of characteristic 2 for cryptographic applications"
5. T. Lange: "Trace zero subvariety for cryptosystems"
6. T. Lange: "Trace zero subvariety for cryptosystems"
7. R. M. Avanzi and E. Cesena: "Trace zero varieties over ﬁelds of characteristic 2 for cryptographic applications"
8. C. Diem and J. Scholten: "An attack on a trace-zero cryptosystem"
9. A. V. Sutherland: "A generic approach to searching for Jacobians"

## References

• G. Frey and T. Lange: "Mathematical background of public key cryptography", Technical report, 2005
• R. M. Avanzi and E. Cesena: "Trace zero varieties over ﬁelds of characteristic 2 for cryptographic applications", Technical report, 2007
• T. Lange: "Trace zero subvariety for cryptosystems", Technical report, 2003
• C. Diem and J. Scholten: "An attack on a trace-zero cryptosystem"
• M. Wienecke: "Cryptography on Trace-Zero Varieties", ITS-Seminar paper, http://www.crypto.rub.de/its_seminar_ws0708.html, 2008
• A. V. Sutherland: "101 useful trace zero varieties", http://www-math.mit.edu/~drew/TraceZeroVarieties.html, 2007
• A. V. Sutherland: "A generic approach to searching for Jacobians", http://arxiv.org/abs/0708.3168v2, 2007.