論文の概要: 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) - Lossy Cryptography from Code-Based Assumptions [7.880958076366762]
高度な暗号プリミティブの拡散は、複雑性クラス$SZK$の難しい問題を暗示している。
これは、コードベースの仮定から高度なプリミティブを構築するための障壁となる。
我々は、Dense-Sparseという、複雑性クラス$BPPSZK$に該当する新しいコードベースの仮定を提案する。
論文 参考訳（メタデータ） (2024-02-06T02:17:08Z) - 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) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳（メタデータ） (2023-03-05T15:11:14Z) - 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) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。