Efficient algorithms for Koblitz curves over fields of characteristic three (Q1775021)

In Elliptic Curve Cryptosystems based on the Elliptic Curve Discrete Logarithm Problem one needs to find first the cardinal of the base elliptic curve and then to compute scalar multiples of points of this curve. It is therefore interesting to look for \`\` good'' elliptic curves allowing an easy treatment of both problems. \textit{N. Koblitz}, [Proc. Crypto'91, Lect. Notes Comput. Sci. 576, 279--287 (1992; Zbl 0780.14018)] proposed the use of the so called subfield or Koblitz elliptic curves. For these curves the point counting is easy, via the zeta function, and the Frobenius endomorphism allows to speed up the computation of scalar multiples of a point. For curves over fields of characteristic two \textit{J. Solinas} [Designs Codes Cryptography 19, 195--249 (2000; Zbl 0997.94017)] gives an efficient method to compute such scalar multiplication using window-\(\tau\)-adic nonadjacent forms (NAF), with \(\tau\) the Frobenius map. In [Proc. Crypto'98, Lect. Notes Comput. Sci. 1472, 327--337 (1998; Zbl 0971.94012)] \textit{N. Koblitz} studies a family of Koblitz supersingular elliptic curves over fields of characteristic three, showing that point multiplication \(nP\) can be speed up using the NAF of the base- \(\tau\) expansion of \(n\) (NAF defined in the ring \(Z[\omega]\), \(\omega\)\, a primitive 6th root of 1). The purpose of the present paper is to extend the method of Koblitz to window form. Section 3 shows that for any natural number \(w>1\)\, exists a width \(w\)\, window \(\tau\)-NAF for any scalar (the case \(w=2\) corresponds to Koblitz algorithm). When \(w>2\) the method requires a suitable precomputation. Section 4 and last discusses some performance and implementation issues.