An improved algorithm for uP+vQ on a family of elliptic curves

The computational performance of cryptographic protocols based on elliptic curves strongly depends on the efficiency of multi scalar multiplications of uP+vQ, where P and Q are points on an elliptic curve. An efficient way to compute uP+vQ is to compute two scalar multiplications simultaneously, rather than computing each scalar multiplication separately. Koblitz introduced a family of curves which admit especially fast elliptic multi scalar multiplication and Solinas brought forward an improved algorithm for kP using the τ-expansion of Koblitz curves. We give a new algorithm for uP+vQ on Koblitz curves based on the τ-expansion with the additional speedup of the new joint spare form, which is called τ-NJSF, where P and Q are on an Koblitz curve defined over F₂^m. We also present an efficient algorithm to obtain the τ-NJSF and prove its average joint Hamming density (AJHD) is 27/56 via the method of stochastic process. Computing uP+vQ by our algorithm can reduce the computational complexity in more than 95% cases, and the running time is reduced by 3.6% on average, while compared with computation that by using τ-JSF.