論文の概要: Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields

• arxiv url: http://arxiv.org/abs/2604.04833v2
• Date: Wed, 08 Apr 2026 13:27:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-09 14:06:05.080322
• Title: Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields
• Title（参考訳）: 拡張場上の伝説的擬似関数のクリプトアナリシス
• Authors: Daksh Pandey,
• Abstract要約: レジェンドレット擬似関数(Regendre Pseudorandom Function、PRF)は、レジェンドレットシンボル上に構築された高効率な暗号プリミティブである。 最近の関心は拡張フィールドの$mathbbF_pr$よりもインスタンス化に移行している。 本稿では, 1 度レジェンダー PRF を $mathbbF_pr$ で動作させる, 包括的な暗号解析手法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Legendre Pseudorandom Function (PRF) is a highly efficient cryptographic primitive built upon the Legendre symbol, valued for its low multiplicative complexity in Multi-Party Computation (MPC) and Zero-Knowledge Proof (ZKP) protocols. While its security over prime fields $\mathbb{F}_p$ is well-documented, recent interest has shifted toward instantiations over extension fields $\mathbb{F}_{p^r}$. This paper presents the first comprehensive cryptanalysis of the single-degree Legendre PRF operating over $\mathbb{F}_{p^r}$. First, we analyze polynomial input encoding under a standard passive threat model (sequential additive counter queries). We demonstrate that while the absence of polynomial carry-overs causes an asynchronous "no-carry fracture" that neutralizes classical sliding-window collision attacks, the fracture itself is deterministically periodic. By introducing a novel "Differential Signature" bucketing technique, we prove that an adversary can systematically group fractured sequences by their structural shapes to bypass this defense, recovering the secret key in $\mathcal{O}(U \cdot p^r/M)$ operations, where $U$ is the unicity distance. Second, we evaluate the PRF under an active Chosen-Query threat model. We demonstrate that an adversary can circumvent the additive fracture by evaluating the PRF along a geometric sequence generated by a primitive polynomial. This structure invokes strict multiplicative homomorphism over $\mathbb{F}^*_{p^r}$, permitting a direct generalization of state-of-the-art table collision attacks to extract the key in $\mathcal{O}(p^r/M)$ operations. Finally, we establish the cryptographic boundaries of these attacks, formally proving the necessity of higher-degree key variants ($d \ge 2$) to achieve exponential security against structural reduction in extension fields.
• Abstract（参考訳）: Legendre Pseudorandom Function (PRF) は、マルチパーティ計算(MPC)とZero-Knowledge Proof(ZKP)プロトコルにおいて、低乗算複雑性で評価される、レジェンドレットシンボル上に構築された高効率な暗号プリミティブである。 素体上のセキュリティ $\mathbb{F}_p$ はよく文書化されているが、最近の関心は拡大体上のインスタンス化へ向けられている。 本稿では, 1 度レジェンダー PRF を $\mathbb{F}_{p^r}$ 上で動作させた場合の包括的暗号解析について述べる。 まず、標準の受動脅威モデル(逐次加算カウンタクエリ)に基づいて多項式入力符号化を解析する。 本研究では, 多項式キャリアオーバーが存在しないことが, 古典的なすべり窓衝突攻撃を中和させる非同期の「非キャリア破壊」を引き起こす一方で, 破壊自体が決定論的に周期的であることを示す。 新たな「識別シグナチャ」バケット技術を導入することにより、敵は、この防御を回避し、秘密鍵を$\mathcal{O}(U \cdot p^r/M)$演算で復元し、その一様距離が$U$であることを示す。 次に,PRFをアクティブなChosen-Query脅威モデルで評価する。 本研究では, 原始多項式が生成する幾何列に沿ってPSFを評価することにより, 相手が付加骨折を回避できることを実証する。 この構造は、$\mathbb{F}^*_{p^r}$上の厳密な乗法準同型を呼び起こし、最先端のテーブル衝突攻撃を直接一般化して$\mathcal{O}(p^r/M)$演算で鍵を抽出することを可能にする。 最後に、これらの攻撃の暗号的境界を確立し、拡張フィールドの構造的縮小に対する指数的セキュリティを達成するために、高次鍵変種(d \ge 2$)の必要性を正式に証明する。

関連論文リスト

• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Cryptographic transformations over polyadic rings [3.0860863056832826]
  暗号システムは、グループ、リング、フィールド内のバイナリ操作に依存する。 我々は、高アリティの操作を許すことで古典環を一般化する多進環へのシフトを提案する。 この構造を利用する2つの具体的な暗号化手順を提案する。
  論文  参考訳（メタデータ） (2025-12-14T07:15:55Z)
• Semigroup action based on skew polynomial evaluation with applications to Cryptography [0.0]
  我々は、その値と函数の左スキュー積の概念に基づいて、スキュー環 $mathbbF_q[X;, right]$ overmathbbF_q$ の作用を導入する。 私たちはこの事実を利用して、CanettiとKrawczykモデルでセキュアな公開鍵交換プロトコルを構築します。
  論文  参考訳（メタデータ） (2025-12-02T10:08:50Z)
• A Symmetric-Key Cryptosystem Based on the Burnside Ring of a Compact Lie Group [0.0]
  我々は、コンパクトリー群$G$のバーンサイド環$A(G)$で代わりに線形作用が起こる対称鍵暗号系を提案する。 任意の有限長のメッセージは$A(G)$の有限サポート元としてエンコードされ、$k$のBurnside製品を介して暗号化される。 有限ランク部分加群 $W_Lsubset A(O(2))$ 上でのみ作用が制限されることを示し、そのようなデータから鍵の情報理論的非識別性を示す。
  論文  参考訳（メタデータ） (2025-10-13T01:57:22Z)
• Extended c-differential distinguishers of full 9 and reduced-round Kuznyechik cipher [1.4407799786341453]
  9ラウンドの Kuznyechik 暗号に対して,鍵前白を伴わない truncated $c$-differential analysis を導入する。 これは9ラウンドのクズニエチクの派生型に対する最初の実用的区別である。
  論文  参考訳（メタデータ） (2025-07-02T22:27:33Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  クローンゲーム解析のための新しいツールキットを提案する。 このフレームワークにより、バイナリフェーズ状態に基づいて新しいクローンゲームを分析することができる。 連成位相の変分最適境界は、ブラックホールの理想化されたモデルで衝突する情報について定量的な洞察を与えることを示す。
  論文  参考訳（メタデータ） (2024-11-07T14:09:32Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  ターゲットの折り畳みは、公開可能な削除(PVD)を可能にすることを示す。 我々は、弱い暗号的仮定から公開可能な削除を支援する様々なプリミティブを得るために、このフレームワークを構築している。
  論文  参考訳（メタデータ） (2023-03-15T15:00:20Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。 我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。 補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
  論文  参考訳（メタデータ） (2020-09-29T08:41:53Z)

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

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