Paper 2024/038 Original: eprint.iacr.org/2024/038 ↗

On Computing the Multidimensional Scalar Multiplication on Elliptic Curves

Abstract

Multiscalar multiplication on elliptic curves is used in wide cryptographic domains such as digital signatures, zero knowledge proofs, and verifiable computation, where it enables efficient and secure cryptographic protocols. In this work, we present two methods for optimizing multi scalar multiplication over elliptic curves. The first method is used when $3^d - 1$ points of the target curve can be stored. The second method is suitable for large values of $d$, where storing $3^d - 1$ points becomes infeasible. Our first method achieves up to $24\%$ better performance on elliptic curves with efficient tripling, speeding up ECDSA signing by $2.88\times$ and verification by $1.67\times$. The second method achieves an efficiency improvement of $11.34\%$ compared to the similar existing approach. These improvements are supported by operation counts and practical benchmarks.