Speeding Up Multi-Scalar Multiplications for Pairing-Based zkSNARKs

Xinxin Fan; Veronika Kuchta; Francesco Sica; Lei Xu

Paper 2024/750

Speeding Up Multi-Scalar Multiplications for Pairing-Based zkSNARKs

Xinxin Fan, IoTeX, Menlo Park, CA 94025

Veronika Kuchta

, Florida Atlantic University

Francesco Sica

, Florida Atlantic University

Lei Xu, Kent State University

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.
Keywords: Multiscalar multiplication acceleration methods ZK-SNARK implementation
Contact author(s): xinxin @ iotex io
vkuchta @ fau edu
sicaf @ fau edu
lxu12 @ kent edu
History: 2024-05-20: approved; 2024-05-16: received; See all versions
Short URL: https://ia.cr/2024/750
License: CC BY

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},
      note = {\url{https://eprint.iacr.org/2024/750}},
      url = {https://eprint.iacr.org/2024/750}
}