論文の概要: Formal Power Series on Algebraic Cryptanalysis

• arxiv url: http://arxiv.org/abs/2007.14729v3
• Date: Fri, 20 Sep 2024 01:09:22 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-09 15:57:56.173675
• Title: Formal Power Series on Algebraic Cryptanalysis
• Title（参考訳）: 代数的クリプトアナリシスに関するフォーマルパワーシリーズ
• Authors: Shuhei Nakamura,
• Abstract要約: 正則度と第一降下次数の上限は、しばしば暗号解析で用いられる。 十分に大きなフィールド上での計算システムの第一降下次数に関する理論的仮定を提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the complexity estimation for an attack that reduces a cryptosystem to solving a system of polynomial equations, the degree of regularity and an upper bound of the first fall degree are often used in cryptanalysis. While the degree of regularity can be easily computed using a univariate formal power series under the semi-regularity assumption, determining an upper bound of the first fall degree requires investigating the concrete syzygies of an input system. In this paper, we investigate an upper bound of the first fall degree for a polynomial system over a sufficiently large field. In this case, we prove that the first fall degree of a non-semi-regular system is bounded above by the degree of regularity, and that the first fall degree of a multi-graded polynomial system is bounded above by a certain value determined from a multivariate formal power series. Moreover, we provide a theoretical assumption for computing the first fall degree of a polynomial system over a sufficiently large field.
• Abstract（参考訳）: 多項式方程式の系を解くための暗号系を減少させる攻撃の複雑性推定において、第1の転落次数の正則度と上界は、しばしば暗号解析において用いられる。 正則性の次数は半正則性仮定の下で単変量形式列を用いて容易に計算できるが、第1の転位次数の上界を決定するためには、入力システムの具体的なシジーを調べる必要がある。 本稿では,多項式系における第1降下次数の上界を十分に大域にわたって検討する。 この場合、非半正則系の第一降下次数は正則度で上界し、多階多項式系の第一落下次数は、多変量形式的級数列から決定される一定の値で上界することを示す。 さらに、多項式系の最初の転倒次数を計算するための理論的な仮定を十分に大きな場上で提供する。

関連論文リスト

• 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)
• Solving Degree Bounds For Iterated Polynomial Systems [0.0]
  我々は,MIMC,Feistel-MiMC,Feistel-MiMC-Hash,Hades,GMiMCに対する攻撃に対する正則性評価を行った。 我々の境界は、これらの設計に対するGr"オブナーベースアタックの仮定された複雑さと一致している。
  論文  参考訳（メタデータ） (2023-10-05T16:10:14Z)
• The complexity of solving a random polynomial system [3.420117005350141]
  本稿では,多変量系の解法に用いる一般アルゴリズムの概要について述べる。 次に、ランダムなシステム、特に"ランダム"が私たちにとって何を意味するかについて話します。 このようなランダムシステムの正則度と解度の両方に上限を与える。
  論文  参考訳（メタデータ） (2023-09-07T17:14:59Z)
• A Hybrid System for Systematic Generalization in Simple Arithmetic Problems [70.91780996370326]
  本稿では,記号列に対する合成的および体系的推論を必要とする算術的問題を解くことができるハイブリッドシステムを提案する。 提案システムは,最も単純なケースを含むサブセットでのみ訓練された場合においても,ネストした数式を正確に解くことができることを示す。
  論文  参考訳（メタデータ） (2023-06-29T18:35:41Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。 アルファベットのサイズについては、定値対分離の複雑さがある。
  論文  参考訳（メタデータ） (2023-01-22T22:08:28Z)
• Renormalized von Neumann entropy with application to entanglement in genuine infinite dimensional systems [0.0]
  フォン・ノイマン量子エントロピーは、一般に無限次元の場合において有限で連続である。 再正規化量子エントロピーは、フレドホルム行列式理論の明示的な利用によって定義される。 偏極化理論のいくつかの特徴は、この論文で証明されたように、導入された再正規化の下で保存される。
  論文  参考訳（メタデータ） (2022-11-10T12:56:07Z)
• Unitary property testing lower bounds by polynomials [0.15229257192293197]
  我々は、量子アルゴリズムにブラックボックスのユニタリへのクエリアクセスを与えるユニタリプロパティテストについて研究する。 これらの問題の複雑さを特徴づけるには、新しいアルゴリズム技術と低いバウンド法が必要である。 我々は、$mathsfQMA$と$mathsfQMA(2)$の間のオラクル分離に対するユニタリなプロパティテストベースのアプローチを示す。
  論文  参考訳（メタデータ） (2022-10-12T03:01:00Z)
• Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
  最大相対エントロピーとその滑らかなバージョンは、量子情報理論の基本的な道具である。 我々は、精製された距離に基づいて最大相対エントロピーを滑らかにする量子状態の小さな変化の崩壊の正確な指数を導出する。
  論文  参考訳（メタデータ） (2021-11-01T16:35:41Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
  我々は「ハード」体制におけるスパースPCA問題(主成分分析)の変種について検討する。 問題に自然に関連付けられた様々なギブズ測度に対する自由エネルギー井戸の深さの有界性を示す。 我々は、オーバーラップギャップ特性(OGP)がハードレジームの重要な部分を占めていることを証明した。
  論文  参考訳（メタデータ） (2020-06-18T17:18:02Z)

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

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