Paper 2024/038

On Computing the Multidimensional Scalar Multiplication on Elliptic Curves

Abstract

A multidimensional scalar multiplication ($$-mul) consists of computing $$, where $$ is an integer ($$, $$ are scalars of size $$ bits, $$ are points on an elliptic curve $$. This operation ($$-mul) is widely used in cryptography, especially in elliptic curve cryptographic algorithms. Several methods in the literature allow to compute the $$-mul efficiently (e.g., the bucket method~\cite{bernstein2012faster}, the Karabina et al. method~\cite{hutchinson2019constructing, hisil2018d, hutchinson2020new}). This paper aims to present and compare the most recent and efficient methods in the literature for computing the $$-mul operation in terms of with, complexity, memory consumption, and proprieties. We will also present our work on the progress of the optimisation of $$-mul in two methods. The first method is useful if $$ points of $$ can be stored. It is based on a simple precomputation function. The second method works efficiently when $$ is large and $$ points of $$ can not be stored. It performs the calculation on the fly without any precomputation. We show that the main operation of our first method is $$ more efficient than that of previous works, while our second exhibits a $$ improvement in efficiency. These improvements will be substantiated by assessing the number of operations and practical implementation.