Point multiplication on ordinary elliptic curves over fields of characteristic three (Q1396701)

The implementation of elliptic curve cryptosystems has been broadly studied for finite fields of characteristic two and for prime fields \(\mathbb{F}_p\), with \(p\) large, but little attention has been paid to other cases. In the paper the authors consider the case of ordinary (non-supersingular) elliptic curves over finite fields of characteristic three, and they carry out a comparative study of the computational efficiency of several methods to perform the multiplication of points on those curves, based on elliptic curve cryptography. The paper investigates the problem for elliptic curves in the classical Weierstrass form and also in the so-called Hessian form (\(x^3 +y^3+1 = Dxy\), see \textit{N. Smart} [Cryptographic Hardware and Embedded Systems -- CHES 2001, Springer, Lect. Notes Comput. Sci. 2162, 118--125 (2001; Zbl 1021.94522)]), considering for the points affine coordinates as well as several types of projective coordinates (ordinary projective, Jacobian projective and Lopez Dahad projective). It is shown that it is better to use Jacobian projective coordinates for curves in Weierstrass form and ordinary projective coordinates for curves in the Hessian form. It is also shown that, for sufficiently large security parameters, the Hessian method (mixed binary window method) is always better than the Weierstrass method (mixed nonary algorithm). The paper also gives tables with timings for a C++ implementation of the various algorithms and compares them with timings for point exponentiations on an even characteristic curve with a similar security parameter. In the conclusion the authors declare that ``we have demonstrated that Hessian arithmetic in characteristic three offers an alternative to traditional even characteristic and large prime variants of elliptic curve cryptography'', and they express the hope that in the future these curves are considered ``as practical cryptographic tools''.