Faster scalar multiplication on Koblitz curves combining point halving with the Frobenius endomorphism

Let E be an elliptic curve defined over F-2n. The inverse operation of point doubling, called point halving, can be done up to three times as fast as doubling. Some authors have therefore proposed to perform a scalar multiplication by an "halve-and-add" algorithm, which is faster than the classical double-and-add method. If the coefficients of the equation defining the curve lie in a small subfield of F-2n, one can use the Frobenius endomorphism tau of the field extension to replace doublings. Since the cost of tau is negligible if normal bases are used, the scalar multiplication is written in "base tau" and the resulting "tau-and-add" algorithm gives very good performance. For elliptic Koblitz curves, this work combines the two ideas for the first time to achieve a novel decomposition of the scalar. This gives a new scalar multiplication algorithm which is up to 14.29% faster than the Robenius method, without any additional precomputation.