論文の概要: Solving Degree Bounds For Iterated Polynomial Systems
- arxiv url: http://arxiv.org/abs/2310.03637v2
- Date: Mon, 4 Mar 2024 10:03:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-17 17:10:47.119710
- Title: Solving Degree Bounds For Iterated Polynomial Systems
- Title（参考訳）: 反復多項式系に対するDegree境界の解法
- Authors: Matthias Johann Steiner,
- Abstract要約: 我々は,MIMC,Feistel-MiMC,Feistel-MiMC-Hash,Hades,GMiMCに対する攻撃に対する正則性評価を行った。
我々の境界は、これらの設計に対するGr"オブナーベースアタックの仮定された複雑さと一致している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: For Arithmetization-Oriented ciphers and hash functions Gr\"obner basis attacks are generally considered as the most competitive attack vector. Unfortunately, the complexity of Gr\"obner basis algorithms is only understood for special cases, and it is needless to say that these cases do not apply to most cryptographic polynomial systems. Therefore, cryptographers have to resort to experiments, extrapolations and hypotheses to assess the security of their designs. One established measure to quantify the complexity of linear algebra-based Gr\"obner basis algorithms is the so-called solving degree. Caminata \& Gorla revealed that under a certain genericity condition on a polynomial system the solving degree is always upper bounded by the Castelnuovo-Mumford regularity and henceforth by the Macaulay bound, which only takes the degrees and number of variables of the input polynomials into account. In this paper we extend their framework to iterated polynomial systems, the standard polynomial model for symmetric ciphers and hash functions. In particular, we prove solving degree bounds for various attacks on MiMC, Feistel-MiMC, Feistel-MiMC-Hash, Hades and GMiMC. Our bounds fall in line with the hypothesized complexity of Gr\"obner basis attacks on these designs, and to the best of our knowledge this is the first time that a mathematical proof for these complexities is provided. Moreover, by studying polynomials with degree falls we can prove lower bounds on the Castelnuovo-Mumford regularity for attacks on MiMC, Feistel-MiMC and Feistel-MiMC-Hash provided that only a few solutions of the corresponding iterated polynomial system originate from the base field. Hence, regularity-based solving degree estimations can never surpass a certain threshold, a desirable property for cryptographic polynomial systems.
- Abstract（参考訳）: Arithmetization-Oriented暗号とハッシュ関数について、Gr\"オブナーベースアタックは、一般的に最も競争力のあるアタックベクターであると考えられている。
残念ながら、Gr\"オブナー基底アルゴリズムの複雑さは特別な場合のみ理解されており、これらの場合がほとんどの暗号多項式系には適用されないことは言うまでもない。
そのため、暗号学者は、設計の安全性を評価するために、実験、外挿、仮説に頼らなければならない。
線形代数ベースのGr\"オブナー基底アルゴリズムの複雑さを定量化するための確立された尺度は、いわゆる解次数である。
カミナタ・アンド・ゴラは、多項式系上のある一般性条件の下では、解次数は常にカステルヌオボ・マンフォード正則性によって上界であり、従ってマコーレー境界(英語版)(Macaulay bound)によって下界され、入力多項式の次数と変数の数だけを考慮に入れている。
本稿では、その枠組みを対称暗号とハッシュ関数の標準多項式モデルである反復多項式系に拡張する。
特に、MIMC、Feistel-MiMC、Feistel-MiMC-Hash、Hades、GMiMCに対する様々な攻撃に対する解度境界を証明した。
我々の境界は、これらの設計に対する「Gr\」基本攻撃の仮定された複雑さと一致しており、我々の知る限り、これらの複雑さの数学的証明が提供されるのはこれが初めてである。
さらに、次数降下の多項式を研究することで、対応する反復多項式系のいくつかの解が基底場に由来することを条件に、MIMC, Feistel-MiMC および Feistel-MiMC-Hash に対する攻撃に対するカステルヌオボ-マンフォード正則性の低い境界を証明できる。
したがって、正則性に基づく解度推定は、暗号多項式系において望ましい性質である特定のしきい値を超えることは決してできない。
関連論文リスト
- Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。
我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。
また、異なるアンサンブルを区別する新しい問題も分析できます。
論文 参考訳（メタデータ） (2024-04-29T14:33:24Z) - The Complexity of Algebraic Algorithms for LWE [0.0]
我々は、LWEシステム上でのGr"オブナー基底計算の複雑さを研究するために、Arora-Geモデルを再検討する。
我々は、Semaev & TentiのGr"obner基底アルゴリズムを有限の正則性を持つ任意の系に一般化する。
論文 参考訳（メタデータ） (2024-02-12T17:59:26Z) - Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators [0.3177496877224142]
量子マックスカット(QMC)問題は、局所ハミルトン問題に対する近似アルゴリズムを設計するためのテスト確率として登場した。
本稿では、QMCの代数構造、特に量子マックスカットハミルトニアンと対称群の表現理論の関係を用いてこの問題に対処する。
論文 参考訳（メタデータ） (2023-07-28T16:45:16Z) - A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium [0.3749861135832073]
我々は,少なくとも1つの解を持つシステム向けに設計されたMultiというアルゴリズムで,この戦略を実装した。
我々は,最大ステップ数のマルチステップ戦略を用いることで,Multiの最適複雑性が達成されることを証明し,その結果,単一のステップからなる戦略である標準的な推測・決定戦略が最悪の選択であることを示す。
論文 参考訳（メタデータ） (2023-04-16T16:09:14Z) - Unitary property testing lower bounds by polynomials [0.15229257192293197]
我々は、量子アルゴリズムにブラックボックスのユニタリへのクエリアクセスを与えるユニタリプロパティテストについて研究する。
これらの問題の複雑さを特徴づけるには、新しいアルゴリズム技術と低いバウンド法が必要である。
我々は、$mathsfQMA$と$mathsfQMA(2)$の間のオラクル分離に対するユニタリなプロパティテストベースのアプローチを示す。
論文 参考訳（メタデータ） (2022-10-12T03:01:00Z) - The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
本稿では,Robins と Monro のセミナル近似フレームワークを一般化し拡張するリーマンアルゴリズムの族を提案する。
ユークリッドのそれと比較すると、リーマンのアルゴリズムは多様体上の大域線型構造が欠如しているため、はるかに理解されていない。
ユークリッド・ロビンス=モンロスキームの既存の理論を反映し拡張するほぼ確実な収束結果の一般的なテンプレートを提供する。
論文 参考訳（メタデータ） (2022-06-14T12:30:11Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。
それらの構造的特性について検討する。
論文 参考訳（メタデータ） (2020-12-01T13:53:23Z) - Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。
大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。
応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
論文 参考訳（メタデータ） (2020-08-05T17:52:10Z) - Formal Power Series on Algebraic Cryptanalysis [0.0]
正則度と第一降下次数の上限は、しばしば暗号解析で用いられる。
十分に大きなフィールド上での計算システムの第一降下次数に関する理論的仮定を提供する。
論文 参考訳（メタデータ） (2020-07-29T10:36:20Z) - Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
我々は「ハード」体制におけるスパースPCA問題(主成分分析)の変種について検討する。
問題に自然に関連付けられた様々なギブズ測度に対する自由エネルギー井戸の深さの有界性を示す。
我々は、オーバーラップギャップ特性(OGP)がハードレジームの重要な部分を占めていることを証明した。
論文 参考訳（メタデータ） (2020-06-18T17:18:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。