論文の概要: SRE: Accelerating Zero-Knowledge Proofs via Scalar Redundancy Elimination in Multi-Scalar Multiplication
- arxiv url: http://arxiv.org/abs/2610.27452v1
- Date: Tue, 20 Oct 2026 01:00:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-21 21:58:47.576273
- Title: SRE: Accelerating Zero-Knowledge Proofs via Scalar Redundancy Elimination in Multi-Scalar Multiplication
- Title（参考訳）: SRE: マルチスカラ乗算におけるスカラ冗長性除去によるゼロ知識証明の高速化
- Abstract要約: Multi-Scalar Multiplication (MSM) は楕円曲線暗号(ECC)で使用される基本暗号演算である
MSMは、コミットメントやゼロ知識証明(ZKP)のような暗号プリミティブにおいて重要な役割を果たす。
MSMは、計算の複雑さを減らし、性能を加速することに焦点を当てた研究の活発な領域である。
- 参考スコア（独自算出の注目度）: 7.462754090166395
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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.
- Abstract（参考訳）: Multi-Scalar Multiplication (MSM) は、楕円曲線暗号 (ECC) で広く使われている基本的な暗号演算である。
その計算には、集中楕円曲線点加算(PADD)が含まれる。
MSMは、多項式コミットメントやゼロ知識証明(ZKP)のような暗号プリミティブにおいて重要な役割を果たす。
したがって、MSMの最適化は、計算複雑性の低減と性能の向上に焦点をあてた研究の活発な領域である。
現在の大規模MSMの最先端アルゴリズムはPippengerのバケット法であり、ポイントマージ、バケットアグリゲーション、ウィンドウアグリゲーションの3つの主要なステップで構成されている。
これらの中で、ポイントマージのステップはパフォーマンスのボトルネックの主要な部分です。
私たちの仕事は、この大きな計算ボトルネックをターゲットにしています。
本稿では,バニラアレイベースアプローチ,リストベースグレディアプローチ,リストベース網羅的アプローチの3つのアプローチを取り入れた新しいスカラ冗長除去(SRE)アルゴリズムを提案する。
ユースケースによっては、これらの戦略は、Pippengerのバケットメソッドに基づいた修正MSMアルゴリズムに統合することができます。
その結果,SRE法により拡張されたMSMアルゴリズムでは,検索時間を3倍に抑えつつ,演算回数を25倍に減らし,通常のPippengerのバケット法と比較して30倍の高速化を実現した。
これは MSM に大きく依存する様々な ZKP システムにおいて 10 \sim 20\%$ のランタイム削減を意味する。
関連論文リスト
- Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts [41.19401563581682]
非方向エッジ重み付きグラフの最小カット問題は、カットエッジの重み付け和を最小化しながら、ノードの集合を2ブロックに分割するように要求する。
我々の最も高速な正確なアルゴリズムは、問題に対するより良いバウンダリを得るために不正確なアルゴリズムを使用します。
オープンソースパッケージのVieCutで利用可能であり、実世界のインスタンスでは、並列実行時に2.5倍、最大12.9倍の速度で、それまでの最速の解決器を上回っている。
論文 参考訳（メタデータ） (2026-09-07T08:26:05Z) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs [56.246783503873225]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
本稿では,ウィンドウ/リスタートベースアルゴリズムと同様に,より単純な重みに基づくアルゴリズムを提案する。
我々のフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳（メタデータ） (2026-01-03T04:50:21Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Theoretical Study of Conflict-Avoidant Multi-Objective Reinforcement Learning [21.288881065839007]
本稿では,CA と FC という2つのサブプロデューサの選択肢に基づいて,新しい動的重み付けマルチタスク・アクター・クリティック・アルゴリズム (MTAC) を開発した。
MTAC-CAは、タスク間の最小値改善を最大化する競合回避(CA)更新方向と、MTAC-FCターゲットをはるかに高速な収束速度で見つけることを目的としている。
MT10における実験により,既存のMTRL法よりもアルゴリズムの性能が向上したことを示す。
論文 参考訳（メタデータ） (2024-05-25T05:57:46Z) - Fast, Scalable, Warm-Start Semidefinite Programming with Spectral
Bundling and Sketching [53.91395791840179]
我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。
USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
論文 参考訳（メタデータ） (2023-12-19T02:27:22Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for
Scalar Data -- An Algorithm and A Benchmark [8.648433479399857]
本稿では,d-次元単純複素数 K 上で定義される入力片方向線形スカラー場 f を与えられた永続図計算の効率的なアルゴリズムを提案する。
我々はこのアルゴリズムを離散モース理論の設定内で表現し、考慮すべき入力単純さの数を著しく削減する。
また、この問題に対して「サンドウィッチ」と呼ばれる階層化アプローチを導入する。
論文 参考訳（メタデータ） (2022-06-27T10:54:24Z) - TaSPM: Targeted Sequential Pattern Mining [53.234101208024335]
本稿では,高速CM-SPAMアルゴリズムに基づく汎用フレームワークTaSPMを提案する。
また,マイニングプロセスにおける無意味な操作を減らすために,いくつかのプルーニング戦略を提案する。
実験の結果,新たなターゲットマイニングアルゴリズムであるTaSPMは実行時間を短縮し,メモリ消費を低減できることがわかった。
論文 参考訳（メタデータ） (2022-02-26T17:49:47Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳（メタデータ） (2021-02-27T19:28:39Z) - Multiagent Rollout and Policy Iteration for POMDP with Application to
Multi-Robot Repair Problems [1.6939372704265414]
有限状態および制御空間,部分状態観測,マルチエージェント構造を有する無限地平面割引動的プログラミング問題を考える。
本手法は、部分的に観測可能なマルチエージェント問題の計算問題に特に対処する。
論文 参考訳（メタデータ） (2020-11-09T06:51:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。