論文の概要: Compressed Permutation Oracles

• arxiv url: http://arxiv.org/abs/2509.18586v1
• Date: Tue, 23 Sep 2025 03:13:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-24 20:41:27.678027
• Title: Compressed Permutation Oracles
• Title（参考訳）: Compressed Permutation Oracles
• Authors: Joseph Carolan,
• Abstract要約: 我々は、圧縮された置換オラクルの音質を発達させ、証明する。 我々は、基本的にすべての既知の量子クエリの低い境界をランダムな置換モデルで再証明する。
• 参考スコア（独自算出の注目度）: 0.6768558752130311
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The analysis of quantum algorithms which query random, invertible permutations has been a long-standing challenge in cryptography. Many techniques which apply to random oracles fail, or are not known to generalize to this setting. As a result, foundational cryptographic constructions involving permutations often lack quantum security proofs. With the aim of closing this gap, we develop and prove soundness of a compressed permutation oracle. Our construction shares many of the attractive features of Zhandry's original compressed function oracle: the purification is a small list of input-output pairs which meaningfully reflect an algorithm's knowledge of the oracle. We then apply this framework to show that the Feistel construction with seven rounds is a strong quantum PRP, resolving an open question of (Zhandry, 2012). We further re-prove essentially all known quantum query lower bounds in the random permutation model, notably the collision and preimage resistance of both Sponge and Davies-Meyer, hardness of double-sided zero search and sparse predicate search, and give new lower bounds for cycle finding and the one-more problem.
• Abstract（参考訳）: ランダムで可逆な置換を問う量子アルゴリズムの解析は、暗号における長年の課題である。 ランダムなオラクルに適用する多くのテクニックは失敗し、あるいはこの設定に一般化することが分かっていない。 その結果、置換を含む基礎的な暗号構造は、しばしば量子セキュリティの証明を欠いている。 このギャップを埋めることを目的として、圧縮された置換オラクルの音質を開発し、証明する。 我々の構成は、Zhandryのオリジナルの圧縮関数オラクルの魅力的な特徴の多くを共有している: 浄化は、アルゴリズムのオラクルに関する知識を有意義に反映した入力-出力ペアの小さなリストである。 次に、この枠組みを適用して、7ラウンドのFeistel構造が強い量子RPPであることを示す(Zhandry, 2012)。 特にスポンジとデイビー・メイヤーの衝突と前像抵抗、両面のゼロ探索の硬さとスパース述語探索の硬さ、サイクル探索と1次問題に対する新しい下界を与える。

関連論文リスト

• Permutation Superposition Oracles for Quantum Query Lower Bounds [14.957648729581502]
  入力-出力ペアの述語に対するアルゴリズムの成功確率を、結果のオラクルシミュレーションを用いてバウンドする方法を示す。 本研究では, 1ラウンドスポンジ構成がランダムな置換モデルに対して無条件に事前画像に抵抗可能であることを示す。
  論文  参考訳（メタデータ） (2024-07-12T19:27:13Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• On the Two-sided Permutation Inversion Problem [45.69327512339002]
  オラクルが量子クエリーを、置換の前方方向と逆方向の両方に許容する設定について検討する。 逆問題の結果の変動の硬さを結合するいくつかの定理を証明した。 以上の結果から,逆数に対する逆数アクセスが与えられると,逆数問題はかなり難しくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2023-06-23T18:31:48Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。 これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
  論文  参考訳（メタデータ） (2023-01-05T11:05:22Z)
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
  Zhandryは、量子クエリアルゴリズムとランダム関数に対応する量子オラクルの間の相互作用を研究した。 オラクルがランダム関数の代わりにランダムな置換に対応する場合にも同様の解釈を導入する。 乱数関数と乱数置換の両方がセキュリティ証明において極めて重要であるため、本フレームワークが量子暗号に応用されることを期待する。
  論文  参考訳（メタデータ） (2021-03-16T11:05:48Z)

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

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