# zbMATH — the first resource for mathematics

Extending scalar multiplication using double bases. (English) Zbl 1172.94558
Lai, Xuejia (ed.) et al., Advances in cryptology – ASIACRYPT 2006. 12th international conference on the theory and application of cryptology and information security, Shanghai, China, December 3–7, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-49475-1/pbk). Lecture Notes in Computer Science 4284, 130-144 (2006).
Summary: It has been recently acknowledged that the use of double bases representations of scalars $$n$$, that is an expression of the form $$n = \sum _{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 \in \mathbb N$$. Only R. Avanzi and F. Sica [“Scalar multiplication on Koblitz curves using double bases”, Lect. Notes Comput. Sci. 4341, 131–146 (2006)] 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/\log \log 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 $$\tau$$-NAF for the curves K-409 and K-571. With respect of windowed methods, that can approach our speed but require $$O(\log (n)/\log \log (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.
For the entire collection see [Zbl 1133.94007].

##### MSC:
 94A60 Cryptography 11G15 Complex multiplication and moduli of abelian varieties 11T71 Algebraic coding theory; cryptography (number-theoretic aspects) 11Y16 Number-theoretic algorithms; complexity
Full Text: