論文の概要: 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次問題に対する新しい下界を与える。

関連論文リスト

• Quantum Lifting for Invertible Permutations and Ideal Ciphers [47.33103206862089]
  量子乱数置換と理想的な暗号モデルにおけるセキュリティを確立するための最初の持ち上げ定理を導出する。 これらの定理は、任意の量子逆数の成功確率と、少数の古典的クエリのみを作る古典的アルゴリズムの成功確率を関連付ける。
  論文  参考訳（メタデータ） (2025-04-25T09:07:55Z)
• Permutation Superposition Oracles for Quantum Query Lower Bounds [14.957648729581502]
  入力-出力ペアの述語に対するアルゴリズムの成功確率を、結果のオラクルシミュレーションを用いてバウンドする方法を示す。 本研究では, 1ラウンドスポンジ構成がランダムな置換モデルに対して無条件に事前画像に抵抗可能であることを示す。
  論文  参考訳（メタデータ） (2024-07-12T19:27:13Z)
• Correcting Subverted Random Oracles [55.4766447972367]
  簡単な構成は、少数の入力で元のものと矛盾する「反転」ランダムオラクルを、ランダム関数から微分不可能な対象に変換することができることを証明している。 この結果から, 暗号プリミティブの設計者は, 通常のクリプトグラフィ設定で, ランダムなオラクルを信頼できるブラックボックスとして使用することができる。
  論文  参考訳（メタデータ） (2024-04-15T04:01:50Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
  ランダムなオラクルから構築した擬似乱数発生器(PRG)の(量子)セキュリティについて検討する。 我々は、大まかに言えば、そのようなPRGが、ランダムなオラクルに対して無条件に多くのクエリを結び付ける古典的敵に対して無条件に安全であるならば、同じ意味で(無条件で)量子的敵に対して安全であることを示す「持ち上げ定理」を証明している。
  論文  参考訳（メタデータ） (2024-01-25T17:13:51Z)
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。 我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
  論文  参考訳（メタデータ） (2022-02-10T18:59:52Z)
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
  Zhandryは、量子クエリアルゴリズムとランダム関数に対応する量子オラクルの間の相互作用を研究した。 オラクルがランダム関数の代わりにランダムな置換に対応する場合にも同様の解釈を導入する。 乱数関数と乱数置換の両方がセキュリティ証明において極めて重要であるため、本フレームワークが量子暗号に応用されることを期待する。
  論文  参考訳（メタデータ） (2021-03-16T11:05:48Z)
• Introducing Structure to Expedite Quantum Search [0.0]
  本稿では,非構造化探索問題を1つの有意な要素で解くための新しい量子アルゴリズムを提案する。 我々のアルゴリズムは乗算定数までの基本ゲートの総数で最適である。 本稿では,複数要素を持つ非構造化探索問題の解法に必要な基本ゲートの数をトータルに削減する方法を示す。
  論文  参考訳（メタデータ） (2020-06-10T13:29:47Z)

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

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