Koblitz curve cryptosystems

Hyperelliptic curves over finite fields are used in cryptosystems. To reach better performance, Koblitz curves, i.e. subfield curves, have been proposed. We present fast scalar multiplication methods for Koblitz curve cryptosystems for hyperelliptic curves enhancing the techniques published so far. For hyperelliptic curves, this paper is the first to give a proof on the finiteness of the Frobenius-expansions involved, to deal with periodic expansions, and to give a sound complexity estimate. As a second topic we consider a different, even faster set-up. The idea is to use a τ-adic expansion as the key instead of starting with an integer which is then expanded. We show that this approach has similar security and is especially suited for restricted devices as the requirements to perform the operations are reduced to a minimum.