Paper 2024/750 Original: eprint.iacr.org/2024/750 ↗
Speeding Up Multi-Scalar Multiplications for Pairing-Based zkSNARKs
Abstract
Multi-scalar multiplication (MSM) is one of the core components of many zero-knowledge proof systems, and a primary performance bottleneck for proof generation in these schemes. One major strategy to accelerate MSM is utilizing precomputation. Several algorithms (e.g., Pippenger and BGMW) and their variants have been proposed in this direction. In this paper, we revisit the recent precomputation-based MSM calculation method proposed by Luo, Fu and Gong at CHES 2023 and generalize their approach. In particular, we presented a general construction of optimal buckets. This improvement leads to significant performance improvements, which are verified by both theoretical analysis and experiments.
Metadata
- Available format(s)
PDF- Category
- Implementation
- Publication info
- Preprint.
- History
- 2025-02-18: last updated
- 2024-05-16: published
- Short URL
- https://ia.cr/2024/750
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2024/750,
author = {Xinxin Fan and Veronika Kuchta and Francesco Sica and Lei Xu},
title = {Speeding Up Multi-Scalar Multiplications for Pairing-Based zkSNARKs},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/750},
year = {2024},
url = {https://eprint.iacr.org/2024/750}
}