論文の概要: Poly Versus Polyval

• arxiv url: http://arxiv.org/abs/2610.41565v1
• Date: Fri, 30 Oct 2026 10:58:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-02 22:05:31.688001
• Title: Poly Versus Polyval
• Title（参考訳）: Poly Versus (複数形 Poly Versuss)
• Abstract要約: 我々は、GF(2n)$以上のバイナリ拡張フィールド上でPolyと呼ぶ暗号評価に基づくハッシュ関数の基本的な構成を再検討する。 GHASHとは異なり、NISTの標準評価ベースのハッシュ関数は$n=128$で、Polyは各$n$-bitブロックの不要なビット反転を実行しない。 我々は、通常の還元とモンゴメリー還元を効率的にする既約表現を表す分野の適切な選択を同定する。
• 参考スコア（独自算出の注目度）: 2.069755423622365
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We revisit the basic construction of polynomial evaluation based hash function, which we call Poly, over binary extension fields over $GF(2^n)$, where $n=64k$ and $k\geq 2$. Unlike GHASH, the NIST standard polynomial evaluation based hash function for $n=128$, Poly does not perform the unnecessary bit reversals of each $n$-bit block, and consequently is faster than GHASH. Further, Poly differs from Polyval, -- a faster alternative to GHASH, -- in that Poly performs usual reduction, while Polyval performs Montgomery reduction. We identify suitable choices of the field representing irreducible polynomials which makes usual and Montgomery reductions efficient. We provide detailed algorithms, and associated proofs of correctness for both kinds of reductions. Based on the algorithms, we report carefully optimised assembly implementation of both Poly and Polyval for $n=128,256$ and $512$. Our theoretical analysis and experimental timing results show that for $n=128$, Polyval is faster than Poly, while for $n=256$ and $512$ (as well as for higher values of $n$), Poly is faster than Polyval. The cases $n=128$ and $256$ are of current relevance due to the ongoing NIST process for developing cryptographic accordions.
• Abstract（参考訳）: 多項式評価に基づくハッシュ関数の基本的な構成を再検討し、この関数はPolyと呼ばれ、$GF(2^n)$上の二項拡張体上で、$n=64k$と$k\geq 2$である。 GHASHとは異なり、NISTの標準多項式評価に基づくハッシュ関数は$n=128$で、Polyは各$n$-bitブロックの不要ビットリバースを実行せず、したがってGHASHよりも高速である。 さらにPolyは、GHASHの高速な代替であるPolyvalと異なり、Polyは通常のリダクションを実行し、Polyvalはモンゴメリーリダクションを実行する。 我々は、通常の還元とモンゴメリー還元を効率的にする既約多項式を表す場の適切な選択を同定する。 両種類の削減に対して,詳細なアルゴリズムと関連する正しさの証明を提供する。 アルゴリズムに基づいて、PolyとPolyvalのアセンブリ実装を慎重に最適化し、$n=128,256$と$512$で報告する。 理論的解析と実験時間の結果から,PolyvalはPolyvalよりも高速であるのに対し,Polyvalは$n=256$で$512$であるのに対し,PolyvalはPolyvalより高速であることがわかった。 n=128$と256$のケースは、暗号アコーディオンを開発するためのNISTプロセスが進行中であるため、現在の関係にある。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials [2.5199066832791535]
  ブールハイパーキューブ上でのサロゲートの学習問題について検討する。 通常の$L$型保証よりも、均一な$L_infty$-error保証が必要です。 本結果は,最適化セーフなサロゲートを学習する際のサンプルの複雑さの厳密な証明を提供する。
  論文  参考訳（メタデータ） (2026-06-15T22:00:03Z)
• Exact and Approximate Algorithms for Polytree Learning [9.426097667758627]
  ポリツリーは、有向森林として$n$変数の集合間の条件依存を捉えようとするベイズネットワークのサブクラスである。 最適なポリツリーを学習する問題はNPハードであるため、どの制限がより引きやすいか研究する。 任意に小さい$> 0$と任意の定数の直交境界に対して、時間$O((2+)n)$で最適なポリツリーを求めるアルゴリズムを考案する。
  論文  参考訳（メタデータ） (2026-05-05T10:50:14Z)
• Matrix inversion polynomials for the quantum singular value transformation [3.718165623644259]
  量子特異値変換(QSVT)を持つ量子反転行列は、1/x$の近似を必要とする。 文献からのいくつかのメソッドは、既知の複雑性を$mathcalO(kappalog(kappa/varepsilon))$で実現している。 ここでは,テイラー展開,チェビシェフ,凸最適化に基づく解析的ショートカットを最適に導出する。
  論文  参考訳（メタデータ） (2025-07-21T12:04:56Z)
• Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields [2.069755423622365]
  AXUハッシュ関数deBRWHashはBernsteinRabin-Winograd(BRW)に基づいている 4-decBRWHashは、数百バイトのメッセージではより高速で、数キロバイトのメッセージ長で約16%のスピードアップを実現している。
  論文  参考訳（メタデータ） (2025-07-09T02:27:33Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。 効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。 また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
  論文  参考訳（メタデータ） (2025-02-25T19:08:26Z)
• Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
  点や線である可能性のある特徴間の3D--2D対応に基づくポーズ推定の特定の問題を再検討する。 得られた解法は数値的に安定かつ高速であることを示す。
  論文  参考訳（メタデータ） (2024-04-25T12:09:16Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)

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

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