The arithmetic of computing multiple scalar multiplications in an elliptic curve group then adding them together is called multi-scalar multiplication (MSM). 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. The proposed construction shrinks down the bucket size to $q/(2\ell)$ for prime radix $q$ and small integer $\ell$, thus permitting an algorithm that computes $n$-scalar multiplication in an elliptic curve group with order $r$ using at most $nh+q/(2\ell)$ additions, with the help of $\ell$$nh$ precomputed points, where $h = \lceil log_{q}(r)\rceil$.

The authors of this work are Guiwen Luo and Guang Gong.

Bio: Dr. Guang Gong is a professor and University Research Chair in the Department of Electrical and Computer Engineering at the University of Waterloo. Her research interests are in the areas of pseudorandom generation, cryptography, and communication security. She serves/served as an Associate Editor for several journals, including an Associate Editor for the IEEE Transactions on Information Theory and on Dependable and Secure Computing, and for the Journal of Cryptography and Communications. She is an IEEE Fellow (2014).