.png){kind=icon}
.png){kind=icon}
Return
Computing multi-scalar multiplication on memory-constrained devices
.png){kind=icon}
PRE
AI
DOI：10.1007/s13389-026-00393-z.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Multi-Scalar Multiplication is a critical operation in most pairing-based zero-knowledge proofs. In a lot of studies, memory limitations have often been reported to be the primary bottleneck preventing the calculation of larger MSMs. In this paper, we are particularly interested in the acceleration of this operation on devices with limited memory. Pippenger's algorithm (also known as bucket method) is the most efficient and, consequently, the most widely used method to calculate Multi-Scalar Multiplications. We propose an optimization of Pippenger's algorithm which is at least as efficient as the original, and significantly more effective when operating under limited memory. The main idea is to use an adapted number of buckets depending on the available memory instead of 2(W)-1. We conducted tests on the curve BLS12-381 with Multi-Scalar Multiplications ranging from 2(8) to 2(14) points. The results obtained demonstrate that we have a very significant gain (up to 40%) for very limited memories. This gain gradually decreases as more memory becomes available, until we achieve performance comparable to Pippenger's once memory is no longer limited. For example, in a Multi-Scalar Multiplication with 2(13) points, we observe a gain of 40% with only 1 KB of memory, 20% with 15 KB, 15% with 35 KB, and so on, down to be equivalent to Pippenger's algorithm once memory is no longer a constraint.
Keywords:
Multi-scalar Multiplication
Pippenger algorithm
Bucket method
zk-SNARK
Journal
J
IF:
1.4
Papers:
18
Citations:
649