論文の概要: Oracle-Based Multistep Strategy for Solving Polynomial Systems Over Finite Fields and Algebraic Cryptanalysis of the Aradi Cipher
- arxiv url: http://arxiv.org/abs/2506.09950v1
- Date: Wed, 11 Jun 2025 17:18:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-13 06:35:03.163194
- Title: Oracle-Based Multistep Strategy for Solving Polynomial Systems Over Finite Fields and Algebraic Cryptanalysis of the Aradi Cipher
- Title（参考訳）: Oracleによる有限フィールド上の多項式系の解法とアラディ暗号の代数的クリプタリシス
- Authors: La Scala Roberto, Sharwan Kumar Tiwari,
- Abstract要約: 本稿では,Depth-First Search戦略に基づく新しいアルゴリズムの実装を提案する。
本稿では,低遅延ブロック暗号Aradiの暗号解析に多段解法を適用した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The multistep solving strategy consists in a divide-and-conquer approach: when a multivariate polynomial system is computationally infeasible to solve directly, one variable is assigned over the elements of the base finite field, and the procedure is recursively applied to the resulting simplified systems. In a previous work by the same authors (among others), this approach proved effective in the algebraic cryptanalysis of the Trivium cipher. In this paper, we present a new implementation of the corresponding algorithm based on a Depth-First Search strategy, along with a novel complexity analysis leveraging tree structures. We further introduce the notion of an "oracle function" as a general predictive tool for deciding whether the evaluation of a new variable is necessary to simplify the current polynomial system. This notion allows us to unify all previously proposed variants of the multistep strategy, including the classical hybrid approach, by appropriately selecting the oracle function. Finally, we apply the multistep solving strategy to the cryptanalysis of the low-latency block cipher Aradi, recently introduced by the NSA. We present the first full round algebraic attack, raising concerns about the cipher's actual security with respect to its key length.
- Abstract（参考訳）: 多変量多項式系が直接解ける計算不可能な場合、1つの変数が基底有限体の要素に割り当てられ、その手順は結果として単純化されたシステムに再帰的に適用される。
同じ著者(他の研究者も)による以前の研究で、このアプローチはトリビウム暗号の代数的暗号解析に有効であることが証明された。
本稿では,木構造を利用した新しい複雑性解析とともに,Depth-First Search戦略に基づく新しいアルゴリズムの実装を提案する。
さらに、現在の多項式系を単純化するためには、新しい変数の評価が必要であるかどうかを判断するための一般的な予測ツールとして「オラクル関数」の概念を導入する。
この概念は、オラクル関数を適切に選択することで、古典的ハイブリッドアプローチを含む、以前に提案された多段階戦略のすべての変種を統一することを可能にする。
最後に, NSA が最近導入した低遅延ブロック暗号 Aradi の暗号解析に多段解法を適用した。
我々は、最初の丸い代数攻撃を提示し、暗号の鍵長に関する実際のセキュリティに関する懸念を提起する。
関連論文リスト
- Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
量子コンピュータはShorのアルゴリズムを使って最新の暗号システムを破ることができる。
我々はまず、量子攻撃に対して安全とされるコードベースのスキームであるMcEliece暗号システムについて検討する。
次に,最短ベクトル問題を解くことの難しさを基礎とした格子型システムNTRUについて検討する。
論文 参考訳（メタデータ） (2025-05-06T03:42:38Z) - VLWE: Variety-based Learning with Errors for Vector Encryption through Algebraic Geometry [1.3824176915623292]
格子ベースの暗号はポスト量子セキュリティの基礎である。
この研究は代数幾何学に基づく新しい構造格子問題であるバラエティ-LWE(VLWE)を導入する。
VLWEのセキュリティは、複数の独立したインスタンスに分散し、古典的および量子的攻撃に対するレジリエンスを示すことによって証明する。
論文 参考訳（メタデータ） (2025-02-11T06:04:24Z) - Cryptanalysis via Machine Learning Based Information Theoretic Metrics [58.96805474751668]
本稿では,機械学習アルゴリズムの新たな2つの応用法を提案する。
これらのアルゴリズムは、監査設定で容易に適用でき、暗号システムの堅牢性を評価することができる。
本稿では,DES,RSA,AES ECBなど,IND-CPAの安全でない暗号化スキームを高精度に識別する。
論文 参考訳（メタデータ） (2025-01-25T04:53:36Z) - From Exponential to Polynomial Complexity: Efficient Permutation Counting with Subword Constraints [0.0]
置換による異なる置換を数えることは、特に複数のサブワードを含む場合、分析における長年の課題である。
本稿では,置換による異なる置換を計算するための閉形式式を示す新しいフレームワークを提案する。
次に、新たな式を開発することにより、基本公式を複数のサブワードを扱うように拡張する。
論文 参考訳（メタデータ） (2024-11-23T19:52:11Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Complementary polynomials in quantum signal processing [0.0]
与えられた$P$を実装するには、まず対応する補完的な$Q$を構築しなければならない。
この問題に対する既存のアプローチでは、明示的な誤り解析には適さない数値的手法が採用されている。
複素解析を用いた補体系に対する新しいアプローチを提案する。
論文 参考訳（メタデータ） (2024-06-06T16:47:11Z) - Modeling Linear and Non-linear Layers: An MILP Approach Towards Finding Differential and Impossible Differential Propagations [1.5327660568487471]
本稿では,暗号内での差動伝播と不可能伝播を探索する自動ツールを提案する。
このツールは、Lilliput、GIFT64、SKINNY64、Klein、M.IBSの5つの軽量ブロック暗号に適用できる。
論文 参考訳（メタデータ） (2024-05-01T10:48:23Z) - A Neural Rewriting System to Solve Algorithmic Problems [47.129504708849446]
ネストされた数学的公式を解くための一般的な手順を学習するために設計されたモジュラーアーキテクチャを提案する。
シンボリック人工知能の古典的なフレームワークである書き換えシステムに触発され、アーキテクチャには3つの専門的で対話的なモジュールが含まれます。
我々は、系統的な一般化に特化した最近のモデルであるNeural Data Routerと、先進的なプロンプト戦略で探索された最先端の大規模言語モデル(GPT-4)とを比較した。
論文 参考訳（メタデータ） (2024-02-27T10:57:07Z) - 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) - Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
本稿では,大域最適化に基づく二乗ジグソーパズルの解法を提案する。
この手法は完全に自動化されており、事前情報を前提とせず、未知または未知のピースオリエンテーションでパズルを扱うことができる。
論文 参考訳（メタデータ） (2023-03-26T18:53:51Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。