Application of Mordell–Weil lattices with large kissing numbers to acceleration of multiscalar multiplication on elliptic curves

Abstract This article aims to speed up (the precomputation stage of) multiscalar multiplication (MSM) on ordinary elliptic curves of j -invariant 0 with respect to specific “independent” (also known as “basis”) points. For this purpose, the so-called Mordell–Weil lattices (up to rank 8) with large kissing numbers (up to 240) are employed. In a nutshell, the new approach consists in obtaining more efficiently a considerable number (up to 240) of certain elementary linear combinations of the “independent” points. By scaling the point (re)generation process, it is thus possible to obtain a significant performance gain. As usual, the resulting curve points can be then regularly used in the main stage of an MSM algorithm to avoid repeating computations. Seemingly, this is the first usage of lattices with large kissing numbers in cryptography, while such lattices have already found numerous applications in other mathematical domains. Without exaggeration, MSM is a widespread primitive (often the unique bottleneck) in modern protocols of real-world elliptic curve cryptography. Moreover, the new (re)generation technique is prone to further improvements by considering Mordell–Weil lattices with even greater kissing numbers.