Efficient arithmetic on Koblitz curves (Q1976040)

The paper under review is an extended update of \textit{J. Solinas}' article in [Adv. Cryptology -- CRYPTO '97, Lect. Notes Comput. Sci. 1294, 357-371 (1997; Zbl 1032.11062)]. It presents elliptic curves suitable for cryptographic applications that allow a fast method to compute scalar multiples of points. The author reviews exponentiation methods, focusing on signed expansions, and gives examples [cf. \textit{D. Gordon}, J. Algorithms 27, No. 1, 129-146 (1998; Zbl 0915.11064)]. Koblitz curves are curves defined over a small finite field which are then considered over a large extension field. The author considers Koblitz curves over \(\mathbb F_{2^n}\) defined over \(\mathbb F_2\). These curves are among the curves suggested by NIST. They have been introduced by \textit{N. Koblitz} [Adv. Cryptology -- CRYPTO '91, Lect. Notes Comput. Sci. 576, 279-287 (1992; Zbl 0780.14018)] to allow fast arithmetic and easy determination of the number of points. They have been further studied by \textit{W. Meier} and \textit{O. Staffelbach} [Adv. Cryptology -- CRYPTO '92, Lect. Notes Comput. Sci. 740, 333-344 (1993; Zbl 0817.94015)]. The main ingredient to allow this is an efficient usage of the Frobenius endomorphism of the curve. The present article gives details on point counting using Lucas sequences, states extension degrees \(n\) for which the group has almost prime order, and presents a method of \(\tau\)-adic expansion that has length at most \(n\) and density 1/3, thus achieving the lowest number of elliptic operations to compute an integer multiple. This method is 50\% faster than any previously known method and is 4.5 times faster than the standard binary double-and-add method. The author states algorithms to compute this short expansion and proves (almost) sharp bounds on the length of the expansion of an arbitrary element of \(\mathbb Z[\tau]\) depending on its norm. Furthermore he shows how to find an element of minimal norm (hence length) congruent to a given integer using modular reduction in \(\mathbb Z[\tau]\). Congruent means that the operation on the group is equal. All this is also considered for the main subgroup of prime order. Furthermore he investigates the effects of using windowing methods. Koblitz' original approach has been generalized to ground fields \(\mathbb F_{2^d}\) for small \(d\) by \textit{V. Müller} [J. Cryptology 11, 219-234 (1998; Zbl 0945.11024)] and \(\mathbb F_p\), \(p\) (small) odd prime by \textit{N. Smart} [J. Cryptology 12, 141-151 (1999; Zbl 0938.94008)]. For curves of arbitrary genus and a generalization of Solinas' approach see \textit{C. Günther, T. Lange}, and \textit{A. Stein} [Selected areas in cryptography, SAC 2000, Lect. Notes Comput. Sci. 2012, 106-117 (2001; Zbl 0976.94014)] and \textit{T. Lange} [Efficient arithmetic on hyperelliptic curves, Universität Essen (Gesamthochschule). Institut für Experimentelle Mathematik. Preprint 4 (2001; Zbl 1047.94008)].