論文の概要: Gröbner Basis Cryptanalysis of Ciminion and Hydra

• arxiv url: http://arxiv.org/abs/2405.05040v1
• Date: Wed, 8 May 2024 13:14:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-09 14:24:42.484793
• Title: Gröbner Basis Cryptanalysis of Ciminion and Hydra
• Title（参考訳）: Gröbner Basis Cryptanalysis of Ciminion and Hydra
• Authors: Matthias Johann Steiner,
• Abstract要約: 二次システム解決攻撃は、CiminionやHydraのような対称鍵プリミティブに対して深刻な脅威となる。 シミニオンに対しては、アフィン変換による反復モデルに対する次数逆レキシコグラフィ(DRL)Gr"オブナー基底を構築する。 Hydra に対して、Sage のコンピュータ支援による証明として、2次 DRL Gr" 基底が Hydra ヘッドの反復系にすでに含まれていることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Ciminion and Hydra are two recently introduced symmetric key Pseudo-Random Functions for Multi-Party Computation applications. For efficiency both primitives utilize quadratic permutations at round level. Therefore, polynomial system solving-based attacks pose a serious threat to these primitives. For Ciminion we construct a quadratic degree reverse lexicographic (DRL) Gr\"obner basis for the iterated polynomial model via affine transformations. For Hydra we provide a computer-aided proof in SageMath that a quadratic DRL Gr\"obner basis is already contained within the iterated polynomial system for the Hydra heads after affine transformations and a linear change of coordinates. Our Ciminion DRL Gr\"obner basis simplifies cryptanalysis, since one does not need to impose genericity assumptions, like being regular or semi-regular, anymore to derive complexity estimates on key recovery attacks. In the Hydra proposal it was claimed that $r_\mathcal{H} = 31$ rounds for the heads are sufficient to achieve $128$ bits of security against Gr\"obner basis attacks for key recovery. However, for $r_\mathcal{H} = 31$ standard term order conversion to a lexicographic (LEX) Gr\"obner basis for our Hydra DRL Gr\"obner basis requires just $126$ bits. Moreover, via the Eigenvalue Method up to $r_\mathcal{H} = 33$ rounds can be attacked below $128$ bits.
• Abstract（参考訳）: CiminionとHydraは、最近導入された2つの対称キーPseudo-Random関数である。 効率性のために、両プリミティブは2次置換をラウンドレベルで利用する。 したがって、多項式システムに基づく攻撃はこれらのプリミティブに深刻な脅威をもたらす。 シミニオンに対しては、アフィン変換による反復多項式モデルに対する二次次逆レキシコグラフィ(DRL) Gr\"オブナー基底を構築する。 ハイドラに対して、SageMath において、アフィン変換と座標の線形変化の後、二次DRL Gr\"オブナー基底がハイドラヘッドの反復多項式系に既に含まれているというコンピュータ支援の証明を提供する。 私たちのCiminion DRL Gr\"obner basisは、暗号解析を単純化します。 Hydraの提案では、ヘッドに対する$r_\mathcal{H} = 31$のラウンドは、キーリカバリのための"Gr\"ベースアタックに対する128ドルのセキュリティを達成するのに十分であると主張した。 しかし、$r_\mathcal{H} = 31$の標準項順序変換は、我々のHydra DRL Gr\"オブジェクト基底は、わずか126$ビットである。 さらに、Eigenvalue Method を通じて$r_\mathcal{H} = 33$ ラウンドを128$ ビット以下で攻撃することができる。

関連論文リスト

• Post-quantum encryption algorithms of high-degree 3-variable polynomial congruences: BS cryptosystems and BS key generation [0.0]
  本稿では,3変数のBeal-Schurコングルースに基づく量子後暗号アルゴリズムを構築する。 この結果を用いて、単純でセキュアな量子後暗号アルゴリズムを生成する。
  論文  参考訳（メタデータ） (2024-08-14T14:19:46Z)
• Fast computation of 2-isogenies in dimension 4 and cryptographic applications [0.0]
  次元 $ggeq 1$ のアーベル多様体とレベル $n=2$ のtheta-coordinates の間の 2$-isogenies の連鎖を計算するアルゴリズムを提案する。 開始曲線の自己準同型環が、ラップトップ上で数秒以内に未知である場合には、SIDHに対して完全なキーリカバリ攻撃を実行することができる。
  論文  参考訳（メタデータ） (2024-07-22T09:19:20Z)
• A new multivariate primitive from CCZ equivalence [1.8024397171920885]
  2つの秘密アフィン可逆$mathcal S,mathcal T$が$mathcalF$の集合に適用される。 等価値 $mathcal G$ と $mathcal F$ はアフィン同値であると言われている。
  論文  参考訳（メタデータ） (2024-05-31T16:15:02Z)
• Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
  3層ニューラルネットワークを用いた標準ガウス分布における階層関数の学習問題について検討する。 次数$k$s$p$の大規模なサブクラスの場合、正方形損失における階層的勾配によるトレーニングを受けた3層ニューラルネットワークは、テストエラーを消すためにターゲット$h$を学習する。 この研究は、3層ニューラルネットワークが複雑な特徴を学習し、その結果、幅広い階層関数のクラスを学ぶ能力を示す。
  論文  参考訳（メタデータ） (2023-11-23T02:19:32Z)
• Learning to Compute Gröbner Bases [3.8214695776749013]
  本稿では,トランスフォーマーを用いたGr"オブザーバベース学習について,初めて述べる。 トレーニングには、システムの多くのペアと関連するGr"オブナーベースが必要です。 本稿では,トークンを連続バイアスで処理し,語彙集合の成長を回避するためのハイブリッド入力を提案する。
  論文  参考訳（メタデータ） (2023-11-21T11:54:21Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
  線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。 我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。 これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
  論文  参考訳（メタデータ） (2022-05-23T17:59:18Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• Learning Polynomials of Few Relevant Dimensions [12.122488725065388]
  多項式回帰は学習と統計の基本的な原始である。 およそ$N = O_r,d(n log2(1/epsilon) (log n)d)$と$O_r,d(N n2)$である。
  論文  参考訳（メタデータ） (2020-04-28T18:00:18Z)

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

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