(2026-05) A New Multiscalar Multiplication Method Resistant to Timing Attacks
2026-05-15
Multiscalar multiplication (MSM) is a core operation in modern cryptographic systems, commonly used in various applications such as Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (ZK-SNARKs) and Homomorphic Encryption. In elliptic curve–based ZK-SNARK constructions, MSM accounts for up to 80–90% of the total proof generation time, making its optimization critical to improving overall protocol performance. Despite significant progress in accelerating MSM through algorithmic techniques such as Pippenger’s method, existing implementations remain vulnerable to timing attacks due to irregular scalar representations and conditional operations on zero digits.\
In this paper, we revisit the original Pippenger’s MSM algorithm, proposing novel modifications that achieve resistance to timing attacks while at the same time increasing its performance by almost 25%. Our main contribution is a new scalar recoding algorithm that transforms conventional -ary representations containing zero digits into equivalent non-zero representations. This ensures that all scalar digits are processed uniformly, eliminating timing-based side-channel leaks. Building on this recoding technique, we introduce a secure variant of Pippenger’s bucket method, that avoids zero digits. Finally, we demonstrate that employing an endomorphism-based splitting yields shorter digit expansions and further efficiency gains. To the best of our knowledge, this is the first MSM algorithm explicitly designed to mitigate timing attacks within the Pippenger bucket method framework.