A New Generic Algorithm for Scalar Multiplication

In this paper, we present a generic algorithm for evaluating the multiple of a point on an elliptic curve;or more generally, for computing an exponentiation in arbitrary Abelian group. Our algorithm uses a ternary representation for scalars and achieves both fast performance and resistivity against SPA attacks and safe error attacks. Moreover, our algorithm nicely works in parallel. Comparisons show that our proposed algorithm establishes a faster scalar multiplication. The most important observation is that our proposed algorithm makes greater improvements for Hessian form curve over fields of characteristic three than any other curves overlarge prime fields or binary fields.