論文の概要: Explicit cost analysis of Toom-4 multiplication for incomplete NTT in lattice-based cryptography

• arxiv url: http://arxiv.org/abs/2605.17505v1
• Date: Sun, 17 May 2026 15:34:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-19 17:57:48.122389
• Title: Explicit cost analysis of Toom-4 multiplication for incomplete NTT in lattice-based cryptography
• Title（参考訳）: 格子暗号における不完全NTTに対するToom-4乗算の明示的コスト解析
• Authors: Sakura Oku, Momonari Kudo,
• Abstract要約: 格子ベースの暗号では、多項式乗法が基本である。 本稿では,具体的なToom-4の実装と,係数場上の加算/減算と乗算を分離する明示的な演算数の導出について述べる。
• 参考スコア（独自算出の注目度）: 0.14323566945483493
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Polynomial multiplication is fundamental in lattice-based cryptography. While the Number Theoretic Transform (NTT) enables fast multiplication, it imposes constraints on the modulus of the coefficient field. Hafiz et al. (2025) addressed this limitation by analyzing the incomplete NTT, which combines a truncated NTT with conventional multiplication methods In this work, we revisit Toom-4 multiplication in the context of incomplete NTT. Although Toom-4 is asymptotically faster than Karatsuba, its precise cost has not been expressed in a form compatible with the incomplete NTT framework. We present a concrete Toom-4 implementation and derive explicit operation counts that separate additions/subtractions and multiplications over the coefficient field. Our analysis based on addition chains yields a simple cost model for incomplete NTT. Using this model, we analyze hybrid strategies combining Toom-4, Karatsuba, and incomplete NTT. We identify parameter ranges where Toom-4 is advantageous and validate the predicted behavior experimentally.
• Abstract（参考訳）: 格子ベースの暗号では、多項式乗法が基本である。 Number Theoretic Transform (NTT) は高速な乗法を可能にするが、係数場の係数に制約を課す。 Hafiz et al (2025) はこの制限に対処し、不完全NTTを解析し、未完全NTTと従来の乗算法を組み合わせ、不完全NTTの文脈でToom-4乗算を再検討した。 Toom-4はカラツバよりも漸近的に速いが、その正確なコストは不完全なNTTフレームワークと互換性のある形で表現されていない。 本稿では,具体的なToom-4の実装と,係数場上の加算/減算と乗算を分離する明示的な演算数の導出について述べる。 付加鎖に基づく解析により不完全NTTの簡易コストモデルが得られる。 このモデルを用いて,Toom-4,Karatsuba,および不完全NTTを組み合わせたハイブリッド戦略を解析した。 Toom-4が有利なパラメータ範囲を特定し、予測された振る舞いを実験的に検証する。

関連論文リスト

• Convergence Bound and Critical Batch Size of Muon Optimizer [1.2289361708127877]
  4つの実践的な設定にまたがって、Muon の収束証明を提供する。 重み付け崩壊の付加は、より厳密な理論的境界をもたらすことを示す。 トレーニングの計算コストを最小限に抑えた,Muonのクリティカルバッチサイズを導出する。
  論文  参考訳（メタデータ） (2025-07-02T11:03:13Z)
• Benchmarking TCL4: Assessing the Usability and Reliability of Fourth-Order Approximations [2.1035679343924643]
  我々は、偏りのあるスピン-ボソンモデルの数値的正確性に対して、TCL4マスター方程式をベンチマークする。 以上の結果から,TCL4法は温度が低く,正確な数値解法よりも効率が高いことが判明した。
  論文  参考訳（メタデータ） (2025-01-08T00:01:51Z)
• Conformal Fields from Neural Networks [1.497481482212619]
  埋め込み形式を使い、$D$次元の共形体を構成する。 スペクトルを解明する4次元共形ブロック分解を行う。 ディープ・ネットワークへの拡張は、各層における共形場を構成する。
  論文  参考訳（メタデータ） (2024-09-18T18:00:00Z)
• Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods [59.779795063072655]
  CoT(Chain-of-Thought)の促進とその変種は、多段階推論問題を解決する効果的な方法として人気を集めている。 統計的推定の観点からCoTのプロンプトを解析し,その複雑さを包括的に評価する。
  論文  参考訳（メタデータ） (2024-08-25T04:07:18Z)
• Benign Overfitting in Deep Neural Networks under Lazy Training [72.28294823115502]
  データ分布が適切に分離された場合、DNNは分類のためのベイズ最適テスト誤差を達成できることを示す。 よりスムーズな関数との補間により、より一般化できることを示す。
  論文  参考訳（メタデータ） (2023-05-30T19:37:44Z)
• D4FT: A Deep Learning Approach to Kohn-Sham Density Functional Theory [79.50644650795012]
  コーンシャム密度汎関数論(KS-DFT)を解くための深層学習手法を提案する。 このような手法はSCF法と同じ表現性を持つが,計算複雑性は低下する。 さらに,本手法により,より複雑なニューラルベース波動関数の探索が可能となった。
  論文  参考訳（メタデータ） (2023-03-01T10:38:10Z)
• Sample-Then-Optimize Batch Neural Thompson Sampling [50.800944138278474]
  我々はトンプソンサンプリング(TS)ポリシーに基づくブラックボックス最適化のための2つのアルゴリズムを提案する。 入力クエリを選択するには、NNをトレーニングし、トレーニングされたNNを最大化してクエリを選択するだけです。 我々のアルゴリズムは、大きなパラメータ行列を逆転する必要性を助長するが、TSポリシーの妥当性は保たれている。
  論文  参考訳（メタデータ） (2022-10-13T09:01:58Z)
• Identifying good directions to escape the NTK regime and efficiently learn low-degree plus sparse polynomials [52.11466135206223]
  広帯域2層ニューラルネットワークはターゲット関数に適合するためにTangent Kernel(NTK)とQuadNTKを併用可能であることを示す。 これにより、終端収束が得られ、NTKとQuadNTKの双方に対して証明可能なサンプル改善が保証される。
  論文  参考訳（メタデータ） (2022-06-08T06:06:51Z)
• Controlling the Complexity and Lipschitz Constant improves polynomial nets [55.121200972539114]
  多項式ネットの結合CP分解(CCP)モデルとNested Coupled CP分解(NCP)モデルに対する新しい複雑性境界を導出する。 本研究では、6つのデータセットで実験的に評価し、モデルが逆摂動に対して頑健であるとともに精度も向上することを示す。
  論文  参考訳（メタデータ） (2022-02-10T14:54:29Z)
• Bounding the Complexity of Formally Verifying Neural Networks: A Geometric Approach [1.9493449206135296]
  ReLUニューラルネットワーク(NN)の複雑さを正式に検証することを検討する。 本稿では,2つの異なるNNに対して,検証問題は2種類の制約を満たすことを示す。 両方のアルゴリズムは、NNパラメータをハイパープレーンを用いてNNアーキテクチャの効果に効率的に変換する。
  論文  参考訳（メタデータ） (2020-12-22T00:29:54Z)

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

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