Optimal Bucket Set Construction for Multi-scalar Multiplication with Endomorphisms

Abstract: Multi-scalar multiplication (MSM), which computes a linear combination of elliptic-curve points of the form $\sum_i a_iP_i$, is a major computational bottleneck in many modern cryptographic protocols, particularly in proof systems. In 2023, Luo, Fu, and Gong (LFG) introduced a framework for accelerating MSM using a bucket set together with a multiplier set, allowing a trade-off between storage and online computation. In 2025, Fan, Sica, Kuchta, and Xu (FKSX) applied the LFG framework to efficient endomorphisms, exploiting units that can be applied essentially on the fly. This raises a natural optimization problem: Can we minimize the bucket size while still admitting an efficient Hamiltonian path for bucket accumulation?

In this talk, I will present our construction from a geometric viewpoint over the Eisenstein integers. I will show how this viewpoint leads to an optimal hexagonal bucket set and also allows us to construct an efficient Hamiltonian path for the bucket accumulation step. Moreover, we generalize the construction to larger multiplier sets, providing further time-memory trade-offs when additional storage is available.

This work will be presented at ASIACRYPT 2026 and is joint work with Francesco Sica.

cryptography and securityMathematics

Audience: advanced learners

Comments: Nam Hoai Le is a PhD student at Florida Atlantic University.

---

Florida Atlantic University Crypto Café

Series comments: A seminar series of the FAU crypto group in the mathematics department. We welcome speakers, both online or in person, to join us and discuss their research or job-related opportunities. Beach lovers - come and believe!

---