A New Algorithm for Double Scalar Multiplication over Koblitz Curves
This work addresses a specific bottleneck in cryptographic computations for security applications, representing an incremental improvement.
The paper tackles the problem of improving computational speed for double scalar multiplication over Koblitz curves in elliptic curve cryptography by proposing a new algorithm that generates a sparse and joint τ-adic representation, achieving a 12% speed improvement over the state-of-the-art τ-adic joint sparse form.
Koblitz curves are a special set of elliptic curves and have improved performance in computing scalar multiplication in elliptic curve cryptography due to the Frobenius endomorphism. Double-base number system approach for Frobenius expansion has improved the performance in single scalar multiplication. In this paper, we present a new algorithm to generate a sparse and joint $τ$-adic representation for a pair of scalars and its application in double scalar multiplication. The new algorithm is inspired from double-base number system. We achieve 12% improvement in speed against state-of-the-art $τ$-adic joint sparse form.