Paper 2026/1902
Optimal Bucket Set Construction for Multi-scalar Multiplication with Endomorphisms
, Florida Atlantic University, Florida Atlantic UniversityAbstract
We develop the method of Luo, Fu and Gong (LFG) - as extended by Fan, Kuchta, Sica and Xu (FKSX) to use endomorphism scalars - in order to find best families suitable for multi-scalar multiplication (MSM) for any number $n$ of points and with adjustable storage. In particular we lower storage requirements by an average of 67% and decrease the number of curve operations by an average of 7% (and up to 10.6%), relative to the LFG method. Compared to Pippenger's variant (standard when $n$ is large), we manage to improve performance by an average 6% for an MSM with $n\in [2^{10},2^{21}]$, while at the same time decreasing storage by up to 15.8% using the BLS12-381 curve. We also improve the FKSX performance, due to a smaller bucket set, by around 7%. This is done by finding the optimal bucket set in the endomorphism case and by providing a fast algorithm to generate an associated Hamiltonian path with short edges. The proposed method is suitable for immediate software deployment at all sizes where MSM is currently used commercially, such as for Zcash and blockchain. Code to generate all ordered bucket sets is provided in a repository.
Note: Full version of the ASIACRYPT 2026 paper, including appendices.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2026
- Keywords
- Multi-scalar multiplicationzk-SNARKPippenger’s bucket methodElliptic curve endomorphisms.
- Contact author(s)
-
namle2024 @ fau edu
sicaf @ fau edu - History
- 2026-09-10: approved
- 2026-09-06: received
- See all versions
- Short URL
- https://ia.cr/2026/1902
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1902,
author = {Nam Hoai Le and Francesco Sica},
title = {Optimal Bucket Set Construction for Multi-scalar Multiplication with Endomorphisms},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1902},
year = {2026},
url = {https://eprint.iacr.org/2026/1902}
}
