Paper 2023/1384

Application of Mordell-Weil lattices with large kissing numbers to acceleration of multi-scalar multiplication on elliptic curves

Dmitrii Koshelev, École Normale Supérieure de Lyon
Abstract

This article aims to speed up (the precomputation stage of) multi-scalar multiplication (MSM) on ordinary elliptic curves of $j$-invariant $0$ with respect to specific ''independent'' (a.k.a. ''basis'') points. For this purpose, 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 get 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, the article results can strongly affect performance of today's real-world elliptic cryptography, since MSM is a widespread primitive (often the unique bottleneck) in modern protocols. Moreover, the new (re)generation technique is prone to further improvements by considering Mordell--Weil lattices with even greater kissing numbers.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
elliptic curves of $j$-invariant $0$kissing numberminimal pointsMordell-Weil latticesmulti-scalar multiplication
Contact author(s)
dimitri koshelev @ gmail com
History
2023-09-18: approved
2023-09-15: received
See all versions
Short URL
https://ia.cr/2023/1384
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2023/1384,
      author = {Dmitrii Koshelev},
      title = {Application of Mordell-Weil lattices with large kissing numbers to acceleration of multi-scalar multiplication on elliptic curves},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1384},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1384}},
      url = {https://eprint.iacr.org/2023/1384}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.