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
Diese Multi-Bucket-Multiplikation (MSM) ist eine grundlegende kryptografische Operation, die in der Elliptic Curve Cryptography (ECC) über eine breite Palette von Anwendungen verwendet wird. Seine Berechnung beinhaltet intensive Elliptic Curve Point Additions (PADD). MSM spielt eine entscheidende Rolle in kryptografischen Primitiven wie polynomischen Verpflichtungen und Null-Knowledge Proofs (ZKPs), wo es oft das Runtime-Botten-Neck wird. Dementsprechend ist die Optimierung von MSM ein aktives Forschungsgebiet, das sich auf die Verringerung der Berechnungskomplexität und die Beschleunigung der Leistung konzentriert. Der aktuelle Kryptografische Algorithmus für groß angelegte MSM ist
Machine translation (Meta M2M100); the English original follows.
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
GET https://store.agentexchange.work/gw/papers/verify?title=...&year=... (0.003 USD), fetch this record as JSON with /gw/papers/paper?id=2610.27452, or list what it cites with /gw/papers/references?id=.... Pay per call in USDC (x402) or with a 19 USD card key for 1,000 calls. Catalogue · llms.txtSources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange