論文の概要: On the Intractability of Chaotic Symbolic Walks: Toward a Non-Algebraic Post-Quantum Hardness Assumption

• arxiv url: http://arxiv.org/abs/2505.22644v1
• Date: Wed, 28 May 2025 17:56:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-29 17:35:50.785319
• Title: On the Intractability of Chaotic Symbolic Walks: Toward a Non-Algebraic Post-Quantum Hardness Assumption
• Title（参考訳）: カオス的シンボリックウォークの難易度について--非代数的ポストクエンタム硬度推定に向けて-
• Authors: Mohamed Aly Bouke,
• Abstract要約: シンボリックパス反転問題 (SPIP) は、Z2 上の有界雑音を持つ収縮アフィン写像によって生成されるシンボリックトラジェクトリに基づく新しい計算硬度仮定である。 従来のシステムとは異なり、SPIPは本質的に非代数的であり、計算的に不可能な逆転を描画するためにカオス的な記号進化と丸め誘導された非射影に依存する。 我々はSPIPがPSPACE-hardおよび#P-hardであることを証明し、短い記号列でさえ1つのエンドポイントに対して500以上の有効な軌道を生成できることを経験的シミュレーションによって証明した。
• 参考スコア（独自算出の注目度）: 2.44755919161855
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Most classical and post-quantum cryptographic assumptions, including integer factorization, discrete logarithms, and Learning with Errors (LWE), rely on algebraic structures such as rings or vector spaces. While mathematically powerful, these structures can be exploited by quantum algorithms or advanced algebraic attacks, raising a pressing need for structure-free alternatives. To address this gap, we introduce the Symbolic Path Inversion Problem (SPIP), a new computational hardness assumption based on symbolic trajectories generated by contractive affine maps with bounded noise over Z2. Unlike traditional systems, SPIP is inherently non-algebraic and relies on chaotic symbolic evolution and rounding-induced non-injectivity to render inversion computationally infeasible. We prove that SPIP is PSPACE-hard and #P-hard, and demonstrate through empirical simulation that even short symbolic sequences (e.g., n = 3, m = 2) can produce over 500 valid trajectories for a single endpoint, with exponential growth reaching 2256 paths for moderate parameters. A quantum security analysis further shows that Grover-style search offers no practical advantage due to oracle ambiguity and verification instability. These results position SPIP as a viable foundation for post-quantum cryptography that avoids the vulnerabilities of algebraic symmetry while offering scalability, unpredictability, and resistance to both classical and quantum inversion.
• Abstract（参考訳）: 整数分解、離散対数、Learning with Errors (LWE)を含む古典的およびポスト量子暗号の仮定の多くは、環やベクトル空間のような代数的構造に依存している。 数学的には強力であるが、これらの構造は量子アルゴリズムや高度な代数的攻撃によって利用でき、構造自由な代替手段の必要性が高まっている。 このギャップに対処するために、Z2上の有界雑音を持つ契約アフィン写像によって生成されるシンボリックな軌跡に基づく新しい計算硬度仮定であるSymbolic Path Inversion Problem (SPIP)を導入する。 従来のシステムとは異なり、SPIPは本質的に非代数的であり、計算的に不可能な逆転を描画するためにカオス的な記号進化と丸め誘導された非射影に依存する。 SPIP は PSPACE-hard および #P-hard であることが証明され,短い記号列 (eg , n = 3, m = 2) であっても単一終点に対して500以上の有効な軌道を生成でき,指数的成長は中等パラメータに対して 2256 パスに達することを示した。 量子セキュリティ分析により、Groverスタイルの探索は、オラクルの曖昧さと検証の不安定性のために、実用的な利点を示さないことが示された。 これらの結果から、SPIPは、古典的および量子的逆転に対するスケーラビリティ、予測不可能性、抵抗性を提供しながら、代数対称性の脆弱性を避けるために、量子後暗号の有効な基盤として位置づけられる。

関連論文リスト

• Efficient quantum pseudorandomness under conservation laws [4.8120624300714665]
  局所的に生成するユニタリ設計の効率は、量子擬似ランダム性の統計的概念を捉える。 任意の局所対称回路が効率的に2次元設計を生成できるかどうかという問題は、それを行うのが確実な回路構造を持たないままである。 直接的応用として、我々の構成は、ほぼ最適に近い量子誤り訂正符号を効率的に生成するのに利用できる。
  論文  参考訳（メタデータ） (2024-11-07T17:32:04Z)
• (Quantum) Indifferentiability and Pre-Computation [50.06591179629447]
  微分可能性(Indifferentiability)は、理想的なオブジェクトのセキュリティを分析するための暗号パラダイムである。 その強さにもかかわらず、前処理攻撃に対するセキュリティを提供する無差別性は知られていない。 本稿では、構成可能であるだけでなく、任意の事前計算を考慮に入れた微分可能性の強化を提案する。
  論文  参考訳（メタデータ） (2024-10-22T00:41:47Z)
• Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
  近年の分離により、階層構造が崩壊しても持続する硬さの源から量子暗号を構築する可能性が高まっている。 量子暗号は、$mathsfP#P notsubseteq mathsf(io)BQP/qpoly$という非常に穏やかな仮定に基づいている。
  論文  参考訳（メタデータ） (2024-09-23T17:45:33Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか? 我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。 我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)
• Quantum computational advantage with string order parameters of 1D symmetry-protected topological order [0.0]
  一次元対称性で保護された位相秩序の一般基底状態に対する非局所ゲームに対する有利な戦略を示す。 本研究では,SPTOの文字列順序パラメータが十分に大きいことが,非条件計算分離に有用な大域的制約付き相関の指標であることを示す。
  論文  参考訳（メタデータ） (2020-07-31T16:27:22Z)
• Efficient simulatability of continuous-variable circuits with large Wigner negativity [62.997667081978825]
  ウィグナー負性性は、いくつかの量子計算アーキテクチャにおいて計算上の優位性に必要な資源であることが知られている。 我々は、大きく、おそらくは有界で、ウィグナー負性を示し、しかし古典的に効率的にシミュレートできる回路の広大な族を同定する。 我々は,高次元離散可変量子回路のシミュラビリティとボソニック符号とのリンクを確立することにより,本結果の導出を行う。
  論文  参考訳（メタデータ） (2020-05-25T11:03:42Z)

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

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