論文の概要: Gröbner Basis Cryptanalysis of Ciminion and Hydra
- arxiv url: http://arxiv.org/abs/2405.05040v2
- Date: Mon, 23 Dec 2024 12:20:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-24 15:50:36.699736
- 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は、最近導入された2つの対称鍵 Pseudo-Random- Functions for Multi-Party Computation である。
効率性のために、両プリミティブは2次置換をラウンドレベルで利用する。
システム問題解決に基づく攻撃がこれらのプリミティブに深刻な脅威をもたらすことを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- 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 linear transformations. With the Gr\"obner basis we can simplify cryptanalysis since we do not need to impose genericity assumptions anymore to derive complexity estimations. For Hydra, with the help of a computer algebra program like SageMath we construct a DRL Gr\"obner basis for the iterated model via linear transformations and a linear change of coordinates. In the Hydra proposal it was claimed that $r_\mathcal{H} = 31$ rounds are sufficient to provide $128$ bits of security against Gr\"obner basis attacks for an ideal adversary with $\omega = 2$. However, via our Hydra Gr\"obner basis standard term order conversion to a lexicographic (LEX) Gr\"obner basis requires just $126$ bits with $\omega = 2$. Moreover, via a dedicated polynomial system solving technique up to $r_\mathcal{H} = 33$ rounds can be attacked below $128$ bits for an ideal adversary.
- Abstract（参考訳）: CiminionとHydraは、最近導入された2つの対称キーPseudo-Random関数である。
効率性のために、両プリミティブは2次置換をラウンドレベルで利用する。
したがって、多項式システムに基づく攻撃はこれらのプリミティブに深刻な脅威をもたらす。
シミニオンの場合、線形変換により反復多項式モデルに対する2次逆レキシコグラフ(DRL)Gr\"オブナー基底を構築する。
Gr\"オブナー基底では、複雑さの見積を導出するために、より一般的な仮定を強制する必要がなくなるため、暗号解析を単純化することができる。
ハイドラにとって、SageMathのような計算機代数プログラムの助けを借りて、線形変換と座標の線形変換を通じて反復モデルに対するDRL Gr\"オブナー基底を構築する。
Hydraの提案では、$r_\mathcal{H} = 31$のラウンドは、$\omega = 2$の理想的な敵に対して、Gr\に対する128$のセキュリティを提供するのに十分であると主張した。
しかし、Hydra Gr\"obner basisの標準項順序変換をlexicographic (LEX) Gr\"obner basisは、$\omega = 2$の126$bitsしか必要としない。
さらに、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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。