International Association
for Cryptologic Research

A multidimensional scalar multiplication (d-mul) consists of computing $[a_1]P_1+\cdots+[a_d]P_d$, where $d$ is an integer ($d\geq 2)$, $\alpha_1, \cdots, \alpha_d$ are scalars of size $l\in \mathbb{N}^*$ bits, $P_1, P_2, \cdots, P_d$ are points on an elliptic curve $E$. This operation (d-mul) is widely used in cryptography, especially in elliptic curve cryptographic algorithms. In fact, it is utilized in the digital signature verification algorithm (ECDSA), proving and verification algorithms such as the Succinct Non interactive Argument of Knowledge (zkSNARK) protocol, and in isogeny based post-quantum cryptosystems. Several methods in the literature allow to compute the d-mul efficiently (e.g., the bucket method, the Karabina et al. method). This paper aims to present and compare the most recent and efficient methods in the literature for computing the d-mul operation in terms of with, complexity, memory consumption, and proprieties. We will also present our work on the progress of the optimisation of d-mul in two methods. The first method is useful if $2^d-1$ points of $E$ can be stored. It is based on a simple precomputation function. The second method works efficiently when $d$ is large and $2^d-1$ points of $E$ can not be stored. It performs the calculation on the fly without any precomputation. We show that our first method is $100(1-\frac{1}{d})\%$ more efficient, while our second exhibits a $50\%$ improvement in efficiency. These improvements will be substantiated by assessing the number of operations and practical implementation.