Welcome to the resource topic for 2024/038
Title:
On Computing the Multidimensional Scalar Multiplication on Elliptic Curves
Authors: Walid Haddaji, Loubna Ghammam, Nadia El Mrabet, Leila Ben Abdelghani
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. 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.
ePrint: https://eprint.iacr.org/2024/038
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .