Paper 2024/038
On Computing the Multidimensional Scalar Multiplication on Elliptic Curves
Abstract
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. Several methods in the literature allow to compute the $d$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 $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^d1$ 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^d1$ points of $E$ 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 $100(1\frac{1}{d})\%$ more efficient than that of previous works, while our second exhibits a $50\%$ improvement in efficiency. These improvements will be substantiated by assessing the number of operations and practical implementation.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 Elliptic curvesmultidimensional scalar multiplicationscalar multiplicationcomplexity
 Contact author(s)

haddajiwalid95 @ gmail com
ubna ghammam @ itkengineering de
nadia elmrabet @ emse fr
leila benabdelghani @ fsm rnu tn  History
 20240328: last of 2 revisions
 20240109: received
 See all versions
 Short URL
 https://ia.cr/2024/038
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/038, author = {Walid Haddaji and Loubna Ghammam and Nadia El Mrabet and Leila Ben Abdelghani}, title = {On Computing the Multidimensional Scalar Multiplication on Elliptic Curves}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/038}, year = {2024}, url = {https://eprint.iacr.org/2024/038} }