TY - GEN

T1 - Scalar multiplication on Koblitz curves using double bases

AU - Avanzi, Roberto

AU - Sica, Francesco

PY - 2006/12/1

Y1 - 2006/12/1

N2 - The paper is an examination of double-base decompositions of integers n, namely expansions loosely of the form n = Σi, j ± A iBj for some base {A, B}. This was examined in previous works [5,6], in the case when A, B lie in N. We show here how to extend the results of [5] to Koblitz curves over binary fields. Namely, we obtain a sublinear scalar algorithm to compute, given a generic positive integer n and an elliptic curve point P, the point nP in time O (log n / log lgo n) elliptic curve operations with essentially no storage, thus making the method asymptotically faster than any know scalar multiplication algorithm on Koblitz curves. In view of combinatorial results, this is the best type of estimate with two bases, apart from the value of the constant in the O notation.

AB - The paper is an examination of double-base decompositions of integers n, namely expansions loosely of the form n = Σi, j ± A iBj for some base {A, B}. This was examined in previous works [5,6], in the case when A, B lie in N. We show here how to extend the results of [5] to Koblitz curves over binary fields. Namely, we obtain a sublinear scalar algorithm to compute, given a generic positive integer n and an elliptic curve point P, the point nP in time O (log n / log lgo n) elliptic curve operations with essentially no storage, thus making the method asymptotically faster than any know scalar multiplication algorithm on Koblitz curves. In view of combinatorial results, this is the best type of estimate with two bases, apart from the value of the constant in the O notation.

KW - Double base number systems

KW - Elliptic curves

KW - Koblitz curves

KW - Scalar multiplication

KW - Sublinear algorithms

UR - http://www.scopus.com/inward/record.url?scp=84887303740&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84887303740&partnerID=8YFLogxK

U2 - 10.1007/11958239-9

DO - 10.1007/11958239-9

M3 - Conference contribution

AN - SCOPUS:84887303740

SN - 3540687998

SN - 9783540687993

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 131

EP - 146

BT - Progress in Cryptology, VIETCRYPT 2006 - 1st International Conference on Cryptology in Vietnam, Revised Selected Papers

T2 - 1st International Conference on Cryptology in Vietnam, VIETCRYPT 2006

Y2 - 25 September 2006 through 28 September 2006

ER -