Newest papers

SRE: Accelerating Zero-Knowledge Proofs via Scalar Redundancy Elimination in Multi-Scalar Multiplication

Jonathan Ku, Guanglei Zhou, Jiawen Wu, Junyao Zhang, Haoxuan Shan, Changchun Zhou, JV Rajendran, Yiran Chen, Hai Li · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.27452 · cited by 0 works (OpenAlex) · open-access PDF

Korean

이 멀티 스케일 곡선 번식 (MSM) 시스템은 광범위한 응용 프로그램을 통해 Elliptic Curve Cryptography (ECC)에서 사용되는 근본적인 암호화 작동입니다. 그것의 계산은 집중적 인 엘리픽 곡선 포인트 추가 (PADD)를 포함합니다. MSM는 대규모 폴리노미얼 실행 약속과 제로 지식 증명 (ZKPs)과 같은 현재의 암호화 원시 알고리즘에서 중요한 역할을합니다. 그 결과, MSM를 최적화하는 것은 계산 복잡성을 줄이고 성능을 가속화하는 연구의 활발한 영역입니다. 현재의 MSM는 대규모 MSM에 대한 암호화 알고리즘은 Pippenger의 버킷 방법으로, 3 가지 주요 단계로 구성됩니다 : 포인트

Machine translation (Meta M2M100); the English original follows.

Abstract

Multi-Scalar Multiplication (MSM) is a fundamental cryptographic operation used in Elliptic Curve Cryptography (ECC) across a wide range of applications. Its computation involves intensive elliptic curve point additions (PADD). MSM plays a critical role in cryptographic primitives such as polynomial commitments and zero-knowledge proofs (ZKPs), where it often becomes the runtime bottleneck. Consequently, optimizing MSM is an active area of research focused on reducing computational complexity and accelerating performance. The current state-of-the-art algorithm for large-scale MSM is Pippenger's bucket method, which consists of three main steps: point merging, bucket aggregation, and window aggregation. Among these, the point merging step is the primary performance bottleneck. Our work targets this major computational bottleneck. To reduce operations for practical applications, we propose a novel Scalar Redundancy Elimination (SRE) algorithm with three approaches: a vanilla array-based approach, a list-based greedy approach, and a list-based exhaustive approach, all incorporating an early stopping technique. Depending on the use case, these strategies can be integrated into our modified MSM algorithm, which is based on Pippenger's bucket method. As a result, our proposed MSM algorithm, enhanced with the SRE technique, incurs less than $3\%$ additional search time, while reducing the number of operations by $25\%$, leading to a $30\%$ speedup in runtime compared to the standard Pippenger's bucket method. This translates to a $10 \sim 20\%$ runtime reduction in various ZKP systems that rely heavily on MSM.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Scalar multiplication, Redundancy (engineering), Computer science, Mathematical proof, Cryptography, Speedup

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange