We introduce a special class of hyperelliptic curves called Koblitz curves. These are curves over a finite field $\F_{q^n}$, $q$ small prime power, which are already defined over $\F_q$. These curves turn out to be a large source of groups suitable for cryptography. The main operation in for example the Diffie-Hellman key-exchange is the computation of $m$ times a group element. One of the big advantages of these curves is that they allow to speed up this step. We explain how the Frobenius automorphism is used and give details on the involved algorithms. For the performance of the algorithms we establish bounds and give numerical evidence for them. Furthermore we provide several examples of suitable curves.
back