論文の概要: 2G2T: Constant-Size, Statistically Sound MSM Outsourcing

• arxiv url: http://arxiv.org/abs/2602.23464v1
• Date: Thu, 26 Feb 2026 19:44:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-02 19:48:24.112385
• Title: 2G2T: Constant-Size, Statistically Sound MSM Outsourcing
• Title（参考訳）: 2G2T:定サイズで統計的にMSMアウトソーシング
• Authors: Majid Khabbazian,
• Abstract要約: マルチスカラー乗算(マルチスカラー乗算、英: Multi-scalar multiplication、MSM)は、離散対数暗号において支配的な計算カーネルである。 MSMを信頼できないサーバにアウトソーシングするためのプロトコルである2G2Tを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-scalar multiplication (MSM), defined as MSM(P, x) = sum_{i=1}^n x_i P_i, is a dominant computational kernel in discrete-logarithm-based cryptography and often becomes a bottleneck for verifiers and other resource-constrained clients. We present 2G2T, a simple protocol for verifiably outsourcing MSM to an untrusted server. After a one-time keyed setup for fixed bases P = (P1, ..., Pn) that produces a public merged-bases vector T and client secret state, the server answers each query x = (x1, ..., xn) with only two group elements: A claimed to equal MSM(P, x) and an auxiliary value B claimed to equal MSM(T, x). Verification requires a single length-n field inner product and a constant number of group operations (two scalar multiplications and one addition), while the server performs two MSMs. In our Ristretto255 implementation, verification is up to ~300x faster than computing the MSM locally using a highly optimized MSM routine for n up to 2^18, and the server-to-client response is constant-size (two compressed group elements, 64 bytes on Ristretto255). Despite its simplicity and efficiency, 2G2T achieves statistical soundness: for any (even computationally unbounded) adversarial server, the probability of accepting an incorrect result is at most 1/q per query, and at most e/q over e adaptive executions, in a prime-order group of size q.
• Abstract（参考訳）: MSM(P, x) = sum_{i=1}^n x_i P_i と定義されるマルチスカラー乗算(MSM)は離散対数暗号において支配的な計算カーネルであり、検証者やその他のリソース制約のあるクライアントのボトルネックとなることが多い。 MSMを信頼できないサーバにアウトソーシングするための単純なプロトコルである2G2Tを提案する。 公開マージベースベクトルTとクライアントシークレット状態を生成する固定ベースP = (P1, ..., Pn) に対する1回のキー付きセットアップの後、サーバは、各クエリ x = (x1, ..., xn) に、MSM(P, x) に等しいと主張される A と MSM(T, x) に等しいと主張される補助値 B の2つのグループ要素だけを答える。 検証には1つの長さnのフィールド内積と一定数のグループ演算(2つのスカラー乗算と1つの加算)が必要であるが、サーバは2つのMSMを実行する。 Ristretto255の実装では、nが2^18まで高度に最適化されたMSMルーチンを使用して、MSMをローカルに計算するよりも最大300倍高速で、サーバからクライアントへの応答は一定サイズである(圧縮された2つのグループ要素、64バイトはRistretto255)。 その単純さと効率性にもかかわらず、2G2T は統計的な健全性を実現している:任意の(計算的に非有界な)逆サーバに対して、不正な結果を受け入れる確率はクエリ毎に1/qであり、e適応的な実行よりも高い e/q は、サイズ q の素順序群である。

関連論文リスト

• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。 クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。 我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
  論文  参考訳（メタデータ） (2026-02-05T14:16:47Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• Benchmarking Multi-modal Semantic Segmentation under Sensor Failures: Missing and Noisy Modality Robustness [61.87055159919641]
  マルチモーダルセマンティックセグメンテーション(MMSS)は、モーダル間で補完情報を統合することで、単一モーダルデータの制限に対処する。 顕著な進歩にもかかわらず、マルチモーダルデータ品質の変動と不確実性により、研究と実世界の展開の間に大きなギャップが持続する。 Intire-Missing Modality (EMM)、Random-Missing Modality (RMM)、Noisy Modality (NM)の3つのシナリオでMMSSモデルを評価する頑健性ベンチマークを導入する。
  論文  参考訳（メタデータ） (2025-03-24T08:46:52Z)
• Distributed quantum algorithm for divergence estimation and beyond [12.925989807145301]
  本稿では,$rm Tr(f(A)g(B))$を付加誤差$varepsilon$内で計算する分散量子アルゴリズムフレームワークを提案する。 このフレームワークは、様々な分散量子コンピューティングタスクに適用可能である。
  論文  参考訳（メタデータ） (2025-03-12T14:28:22Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications [33.21958331056391]
  マルチシーケンス近似(Multi-sequence Approximation, SA)は、信号処理や機械学習の分野において、多列SA(Multi-sequence SA)として知られる複数の結合配列を含む。 固定点の滑らかさを仮定することなく,MSSAに対してより厳密な単一時間スケール解析を行う。 これらの理論的知見を双方向の最適化と通信効率のよい分散学習に適用することにより、性能保証を伴う緩和された仮定および/またはより単純なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-10-17T16:39:53Z)
• SZKP: A Scalable Accelerator Architecture for Zero-Knowledge Proofs [10.603449308259496]
  ZKPは検証可能なコンピューティングにおける創発的なパラダイムである。 証明生成における2つの重要なプリミティブは、Number Theoretic Transform(NTT)とMulti-scalar multiplication(MSM)である。 我々は,チップ上での証明全体を高速化する最初のASICであるスケーラブルなアクセラレータフレームワークであるSZKPを提案する。
  論文  参考訳（メタデータ） (2024-08-12T01:53:58Z)
• Are More LLM Calls All You Need? Towards Scaling Laws of Compound Inference Systems [76.69936664916061]
  LM呼び出し回数がVotteとFilter-Voteのパフォーマンスに与える影響について検討する。 意外なことに、複数の言語タスクにおいて、VoteとFilter-Voteの両方のパフォーマンスは、まず増大するが、LM呼び出しの回数の関数として減少する可能性がある。
  論文  参考訳（メタデータ） (2024-03-04T19:12:48Z)
• Comparison of parallel SMC and MCMC for Bayesian deep learning [3.4661537979254655]
  この研究は、一貫した(漸近的に偏りのない)ベイズディープラーニングアルゴリズムの並列実装を体系的に比較する。 SMC$_parallel$に対して収束の証明を行い、理論上単一のモノリシックSMCサンプリング器と同じ収束のレベルを達成することを示す。
  論文  参考訳（メタデータ） (2024-02-09T04:13:38Z)
• Quantum Speedups for Multiproposal MCMC [8.580097282861725]
  より高速な量子多目的MCMC戦略であるQPMCMC2を提案する。 QPMCMC2は、多数の提案を計算する際に、ターゲット評価に$mathcalO(P)$と$mathcalO(log P)$ qubitsしか必要としない。 細菌進化ネットワーク上に構築された新しいIsing型モデルにQPMCMC2を適用することで,この柔軟性を示す。
  論文  参考訳（メタデータ） (2023-12-03T14:05:08Z)
• Towards Semantic Communication Protocols: A Probabilistic Logic Perspective [69.68769942563812]
  我々は,NPMを確率論理型言語ProbLogで記述された解釈可能なシンボルグラフに変換することによって構築された意味プロトコルモデル(SPM)を提案する。 その解釈性とメモリ効率を利用して、衝突回避のためのSPM再構成などのいくつかの応用を実演する。
  論文  参考訳（メタデータ） (2022-07-08T14:19:36Z)
• A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization [0.0]
  評価フィードバックコヒーレントIsing Machine(MFB-CIM)、離散断熱量子計算(DAQC)、量子最小探索(DH-QMF)のためのD"urr-Hoyerアルゴリズムの3つの量子アルゴリズムの性能スケーリングについて検討する。 各アルゴリズムに対して、ランダムに生成されたエッジ重みを持つ重み付きグラフインスタンスを1ドルで1ドルから1ドルで、ランダムに生成されたSherrington-Kirkpatrick(SK)スピングラスインスタンスをランダムに生成する。
  論文  参考訳（メタデータ） (2021-05-07T22:35:02Z)
• Online Multi-Object Tracking and Segmentation with GMPHD Filter and Mask-based Affinity Fusion [79.87371506464454]
  本稿では,インスタンス分割結果を入力として利用するMOTS法を提案する。 提案手法は,ガウス混合確率仮説密度 (GMPHD) フィルタ,階層型データアソシエーション (HDA) モデル,マスクベース親和性融合 (MAF) モデルに基づく。 2つの人気のあるMOTSデータセットの実験では、主要なモジュールがいくつかの改善点を示している。
  論文  参考訳（メタデータ） (2020-08-31T21:06:22Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。