論文の概要: A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium
- arxiv url: http://arxiv.org/abs/2304.07820v2
- Date: Wed, 5 Jun 2024 10:23:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-07 04:46:49.378690
- Title: A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium
- Title（参考訳）: 有限体上の多項式系の多段階解法とストリーム暗号トリビウムに対する新しい代数的攻撃
- Authors: Roberto La Scala, Federico Pintore, Sharwan K. Tiwari, Andrea Visconti,
- Abstract要約: 我々は,少なくとも1つの解を持つシステム向けに設計されたMultiというアルゴリズムで,この戦略を実装した。
我々は,最大ステップ数のマルチステップ戦略を用いることで,Multiの最適複雑性が達成されることを証明し,その結果,単一のステップからなる戦略である標準的な推測・決定戦略が最悪の選択であることを示す。
- 参考スコア（独自算出の注目度）: 0.3749861135832073
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper we introduce a multistep generalization of the guess-and-determine or hybrid strategy for solving a system of multivariate polynomial equations over a finite field. In particular, we propose performing the exhaustive evaluation of a subset of variables stepwise, that is, by incrementing the size of such subset each time that an evaluation leads to a polynomial system which is possibly unfeasible to solve. The decision about which evaluation to extend is based on a preprocessing consisting in computing an incomplete Grobner basis after the current evaluation, which possibly generates linear polynomials that are used to eliminate further variables. If the number of remaining variables in the system is deemed still too high, the evaluation is extended and the preprocessing is iterated. Otherwise, we solve the system by a complete Grobner basis computation. Having in mind cryptanalytic applications, we present an implementation of this strategy in an algorithm called MultiSolve which is designed for polynomial systems having at most one solution. We prove explicit formulas for its complexity which are based on probability distributions that can be easily estimated by performing the proposed preprocessing on a testset of evaluations for different subsets of variables. We prove that an optimal complexity of MultiSolve is achieved by using a full multistep strategy with a maximum number of steps and in turn the standard guess-and-determine strategy, which essentially is a strategy consisting of a single step, is the worst choice. Finally, we extensively study the behaviour of MultiSolve when performing an algebraic attack on the well-known stream cipher Trivium.
- Abstract（参考訳）: 本稿では,有限体上の多変量多項式方程式系を解くための推測・決定・ハイブリッド戦略の多段階一般化を提案する。
特に,変数のサブセットの抜本的な評価を段階的に行うこと,すなわち,評価が解決不可能な多項式系に導かれる度に,そのようなサブセットのサイズを増大させることを提案する。
どの評価を拡張するかの決定は、現在の評価の後、不完全グロブナー基底を演算する前処理に基づいており、さらなる変数を排除するために使用される線形多項式を生成する可能性がある。
システム内の残りの変数数がまだ高すぎると判断された場合、評価は拡張され、前処理が反復される。
そうでなければ、完全なGrobner基底計算によってシステムを解く。
暗号解析の応用を念頭に置いて,少なくとも1つの解を持つ多項式系を設計したMultiSolveというアルゴリズムで,この戦略を実装した。
変数の異なる部分集合に対する評価テストセットで提案した前処理を実行することにより,確率分布に基づく複雑性の公式が容易に推定できることを示す。
マルチソルブの最適複雑性は、最大ステップ数で全マルチステップ戦略を用いて達成され、その結果、単一のステップからなる戦略である標準的な推測・決定戦略が最悪の選択であることを示す。
最後に、よく知られたストリーム暗号 Trivium に対する代数的攻撃を行う際に、MultiSolve の挙動を広範囲に研究する。
関連論文リスト
- A practical, fast method for solving sum-of-squares problems for very large polynomials [10.645318208507213]
正方形最適化(SOS:Sum of squares)は、 as の正則性を強制しなければならない問題を解くための強力な手法である。
私たちのゴールは、現在より大きく、より複雑な問題に対処できるアプローチを考案することにあります。
論文 参考訳（メタデータ） (2024-10-21T12:47:42Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - The complexity of solving a random polynomial system [3.420117005350141]
本稿では,多変量系の解法に用いる一般アルゴリズムの概要について述べる。
次に、ランダムなシステム、特に"ランダム"が私たちにとって何を意味するかについて話します。
このようなランダムシステムの正則度と解度の両方に上限を与える。
論文 参考訳（メタデータ） (2023-09-07T17:14:59Z) - Automatic Solver Generator for Systems of Laurent Polynomial Equations [1.7188280334580197]
同じ単項構造であるが様々な係数を持つ三角系(ローラン系)が与えられたとき、任意の族に対する解をできるだけ早く計算する解法を見つける。
ローラン方程式系に対する自動解法生成器を提案する。
論文 参考訳（メタデータ） (2023-07-01T12:12:52Z) - Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
最適化プログラミング(SP)、最適制御(SOC)、決定プロセス(MDP)に焦点を当てる。
凸多段マルコフ問題の解決の最近の進歩は、動的プログラミング方程式のコスト対ゴー関数の切断面近似に基づいている。
切削平面型法は多段階問題を多段階的に扱えるが、状態(決定)変数は比較的少ない。
論文 参考訳（メタデータ） (2023-03-28T01:30:40Z) - Sparse resultant based minimal solvers in computer vision and their
connection with the action matrix [17.31412310131552]
いくつかのカメラ幾何問題に対して、我々の余剰手法は、最先端のGrobnerベースベースの解法よりも小さく、より安定な解法をもたらすことを示した。
コンピュータビジョンにおける最小限の問題に対して、一般的なベースベースの方法に代わる競争力のある代替手段を提供する。
論文 参考訳（メタデータ） (2023-01-16T14:25:19Z) - Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。
これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。
制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
論文 参考訳（メタデータ） (2022-08-23T18:56:05Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。