Paper 2026/1902 Original: eprint.iacr.org/2026/1902 ↗

Optimal Bucket Set Construction for Multi-scalar Multiplication with Endomorphisms

Abstract

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.