Koblitz curve cryptosystems (Q1779327): Difference between revisions

In elliptic and hyperelliptic Public Key Cryptography one needs to compute scalar multiples of a point of the curve or a divisor of its Jacobian. It is then crucial having methods to speed up such an arithmetic operation. In her Ph.D. Thesis [Efficient arithmetic on hyperelliptic curves, University Essen (2001; Zbl 1047.94008)] and several papers the author addressed the problem of efficiently carring out the arithmetic in hyperelliptic curves. The present paper investigates the use of Koblitz hyperelliptic curves (curves defined over and small finite field and consider over a large extension field). The use of Koblitz curves was proposed by \textit{N. Koblitz}, [Crypto'91, Lect. Notes Comput. Sci. 576, 279--287 (1992; Zbl 0780.14018)]. For these curves the point counting is easy and \textit{A. J. Menezes} and \textit{S. Vanstone} [Auscrypt 90, Lect. Notes Comput. Sci. 453, 2--13 (1990; Zbl 0722.94012)] proposed the use of the Frobenius endomorphism to speed up the computation of scalar multiples of a point, using a certain scalar's expansion. Several authors studied the generalization of Koblitz idea to hyperelliptic curves. This paper presents new techniques to apply the Frobenius endomorphism to the computation of scalar multiples and investigates the properties of the expansions. The author claims that her approach is different from alternative ones [\textit{Y. Choie} and \textit{J. W. Lee}, Indocrypt 2002, Lect. Notes Comput. Sci. 2551, 285--295 (2002; Zbl 1033.11504); \textit{Y.-H. Park, S. Jeong} and \textit{J. Lim}, Eurocrypt 2002, Lect. Notes Comput. Sci. 2332, 197--208 (2002; Zbl 1055.94022)] ``as our expansions are shorter and are proven to be finite''. Section 2 and 3 recall the needed mathematical background. The core of the paper is Section 4 where the main results and algorithms are provided. The author shows that for \(m\sim q^{gn}\)\, the computation of \(mD\) needs only \(\sim n^{(q^g-1)/q^g}\) group operations (the drawback is that \((q^g-1/2)\) elements need to be precomputed and stored). As an alternative approach the paper (Section 5) investigates the idea (due to Koblitz) of using an expansion of fixing length, not caring to which integer it corresponds. Section 6 provides a concrete example for a binary curve of genus three.