Extending Scalar Multiplication Using Double Bases

It has been recently acknowledged [4,6,9] that the use of double bases representations of scalars

n

, that is an expression of the form

n

= ∑

e

,

s

,

t

(–1)

e

A

s

B

t

can speed up significantly scalar multiplication on those elliptic curves where multiplication by one base (say

B

) is fast. This is the case in particular of Koblitz curves and supersingular curves, where scalar multiplication can now be achieved in

o

(log

n

) curve additions.

Previous literature dealt basically with supersingular curves (in characteristic 3, although the methods can be easily extended to arbitrary characteristic), where

A

,

B

∈ℕ. Only [4] attempted to provide a similar method for Koblitz curves, where at least one base must be non-real, although their method does not seem practical for cryptographic sizes (it is only asymptotic), since the constants involved are too large.

We provide here a unifying theory by proposing an alternate recoding algorithm which works in all cases with

optimal

constants. Furthermore, it can also solve the until now untreatable case where both

A

and

B

are non-real. The resulting scalar multiplication method is then compared to standard methods for Koblitz curves. It runs in less than log

n

/loglog

n

elliptic curve additions, and is faster than any given method with similar storage requirements already on the curve K-163, with larger improvements as the size of the curve increases, surpassing 50% with respect to the

τ

-NAF for the curves K-409 and K-571. With respect of windowed methods, that can approach our speed but require

O

(log(

n

)/loglog(

n

)) precomputations for optimal parameters, we offer the advantage of a fixed, small memory footprint, as we need storage for at most two additional points.