Cryptography Reading Group - Guiwen Luo

Title: Speeding up Multi-Scalar Multiplication over Fixed Points towards Efficient zkSNARKs

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 pairing-based trusted setup zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs), thus fast algorithms of MSM over fixed points are desirable for practical applications. In order to speed up MSM over fixed points with the help of precomputation, a new construction of bucket set that can be utilized in the context of Pippenger's bucket method is proposed. If instantiating the proposed construction over BLS12-381 curve whose order is about $2^{255}$, when computing MSM with the number of scalar multiplications being in the range of $2^{16}$ to $2^{23}$, the proposed construction saves more than $20\%$ additions comparing to the original Pippenger's bucket method, and saves $5\%$ to $13\%$ additions comparing to the most popular variant of Pippenger's bucket method.