International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Speeding Up Multi-Scalar Multiplication over Fixed Points Towards Efficient zkSNARKs

Authors:
Guiwen Luo , Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON, Canada
Shihui Fu , Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON, Canada
Guang Gong , Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON, Canada
Download:
DOI: 10.46586/tches.v2023.i2.358-380
URL: https://tches.iacr.org/index.php/TCHES/article/view/10287
Search ePrint
Search Google
Abstract: The arithmetic of computing multiple scalar multiplications in an elliptic curve group then adding them together is called multi-scalar multiplication (MSM). MSM over fixed points dominates the time consumption in the pairing-based trusted setup zero-knowledge succinct non-interactive argument of knowledge (zkSNARK), thus for practical applications we would appreciate fast algorithms to compute it. This paper proposes a bucket set construction that can be utilized in the context of Pippenger’s bucket method to speed up MSM over fixed points with the help of precomputation. If instantiating the proposed construction over BLS12-381 curve, when computing n-scalar multiplications for n = 2e (10 ≤ e ≤ 21), theoretical analysis ndicates that the proposed construction saves more than 21% computational cost compared to Pippenger’s bucket method, and that it saves 2.6% to 9.6% computational cost compared to the most popular variant of Pippenger’s bucket method. Finally, our experimental result demonstrates the feasibility of accelerating the computation of MSM over fixed points using large precomputation tables as well as the effectiveness of our new construction.
BibTeX
@article{tches-2023-33041,
  title={Speeding Up Multi-Scalar Multiplication over Fixed Points Towards Efficient zkSNARKs},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2023, Issue 2},
  pages={358-380},
  url={https://tches.iacr.org/index.php/TCHES/article/view/10287},
  doi={10.46586/tches.v2023.i2.358-380},
  author={Guiwen Luo and Shihui Fu and Guang Gong},
  year=2023
}