論文の概要: Indistinguishability Lifting for Keyed Oracles, Compressed Ideal Cipher, and More Applications

• arxiv url: http://arxiv.org/abs/2610.04674v1
• Date: Sat, 03 Oct 2026 17:43:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-11 17:51:52.322779
• Title: Indistinguishability Lifting for Keyed Oracles, Compressed Ideal Cipher, and More Applications
• Title（参考訳）: キーとなるOracleの区別不能なリフティング、圧縮された理想暗号、さらに多くのアプリケーション
• Abstract要約: 暗号のセキュリティ証明は 敵がより大きな 鍵を握った神託と 相互作用することが多い このような2つの鍵を持つオラクル間の量子的不容易性を示すことは、敵によって作られた単一のクエリは、ベースオーラックのすべてのインスタンスを同時にカバーする重ね合わせを含むため、難しい。 2つの基底オラクルが量子クェリで区別できない場合、その対応するキー付きオラクルもO(q2)乗算損失によって利点を区別できることが示される。
• 参考スコア（独自算出の注目度）: 1.0936043362876648
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Cryptographic security proofs often involve an adversary interacting with a larger, keyed oracle that consists of (potentially exponentially) many independent instances of a smaller, base oracle. However, showing quantum indistinguishability between two such keyed oracles can be tricky, since a single query made by an adversary may involve a superposition that covers all instances of the base oracles simultaneously. In this paper, we establish a generic indistinguishability lifting theorem of the following form: if the two base oracles are indistinguishable under quantum queries, then their corresponding keyed oracles are too, up to an O(q^2) multiplicative loss in distinguishing advantage, where q is the number of queries made by the adversary. Our lifting theorem applies to both statistical and computational settings, and to oracles that are stateful as well. It is also optimal in that it matches the obvious Grover search attack for a certain (contrived) choice of oracles. As an immediate application, we extend Carolan's compressed permutation oracle to an efficiently implementable compressed ideal cipher, and use it to prove preimage resistance of the Davies-Meyer compression function in the quantum ideal cipher model. Thanks to our lifting theorem, the soundness of our compressed ideal cipher reduces to that of Carolan's oracle, and any further improvement on the latter would automatically carry over to the former. As our second application, we give a modular construction that doubles the message length of any quantum-secure strong pseudorandom permutation. Along the way, we show that an existing two-round tweakable Feistel construction is indistinguishable from a random permutation under quantum bidirectional queries. This is done via a dedicated polynomial-method argument, which may be of independent interest.
• Abstract（参考訳）: 暗号のセキュリティ証明は、(潜在的に指数関数的に)小さな基底オラクルの多くの独立したインスタンスからなる、より大きな鍵を持つオラクルと相互作用する敵を巻き込むことが多い。 しかし、このような2つの鍵を持つオークル間の量子的不連続性を示すことは、敵によって作られた単一のクエリは、基底のオークルの全てのインスタンスを同時にカバーする重ね合わせを含むため、難解である。 本稿では,2つの基本オラクルが量子的クエリで区別不能である場合,対応するキー付きオラクルも O(q^2) 乗算的損失(q は相手が生成したクエリの数である)に等しいという,一般的な不明瞭性持ち上げ定理を定めている。 我々の持ち上げ定理は、統計的および計算的設定の両方に適用され、またステートフルなオーラクルにも適用されます。 また、オーラクルの特定の(選択された)選択に対して、明らかなグロバー探索攻撃と一致することが最適である。 直近の応用として、Carolanの圧縮置換オラクルを効率よく実装可能な圧縮理想暗号に拡張し、量子イデアル暗号モデルにおけるデイビース・メイヤー圧縮関数の事前抵抗を証明する。 我々の持ち上げ定理のおかげで、圧縮された理想暗号の音質はキャロランのオラクルの音に還元され、後者のさらなる改良は自動的に前者へと引き継がれる。 第2の応用として、量子セキュアな強い擬似乱数置換のメッセージ長を2倍にするモジュラ構造を与える。 その過程で、既存の2ラウンドの調整可能なFeistel構造は、量子双方向クエリの下でのランダムな置換と区別できないことを示す。 これは、独立した興味を持つような専用多項式-メソッドの議論によって行われる。

関連論文リスト

• On The Simplest Quantum-Secure Block Cipher [4.199844472131922]
  We show that two-round Even-Mansour cipher is theoretically secure in the ideal permutation model (IPM)。 また、この構成は、一般に1つの呼び出しによって構築される暗号が量子的に安全でないという意味で、最小限であることも示している。
  論文  参考訳（メタデータ） (2026-09-30T17:59:10Z)
• Compressed Permutation Oracles [0.6768558752130311]
  我々は、圧縮された置換オラクルの音質を発達させ、証明する。 我々は、基本的にすべての既知の量子クエリの低い境界をランダムな置換モデルで再証明する。
  論文  参考訳（メタデータ） (2025-09-23T03:13:48Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  クローンゲーム解析のための新しいツールキットを提案する。 このフレームワークにより、バイナリフェーズ状態に基づいて新しいクローンゲームを分析することができる。 連成位相の変分最適境界は、ブラックホールの理想化されたモデルで衝突する情報について定量的な洞察を与えることを示す。
  論文  参考訳（メタデータ） (2024-11-07T14:09:32Z)
• (Quantum) Indifferentiability and Pre-Computation [50.06591179629447]
  微分可能性(Indifferentiability)は、理想的なオブジェクトのセキュリティを分析するための暗号パラダイムである。 その強さにもかかわらず、前処理攻撃に対するセキュリティを提供する無差別性は知られていない。 本稿では、構成可能であるだけでなく、任意の事前計算を考慮に入れた微分可能性の強化を提案する。
  論文  参考訳（メタデータ） (2024-10-22T00:41:47Z)
• 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)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。 これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
  論文  参考訳（メタデータ） (2023-01-05T11:05:22Z)
• Adaptive versus Static Multi-oracle Algorithms, and Quantum Security of a Split-key PRF [7.281231789947833]
  本論文の前半では,複数のオーラクルを適応的にクエリ可能な任意のオーラクルアルゴリズムを変換する汎用コンパイラについて述べる。 論文の後半では、Giacon, Heuer, Poettering が提案した非常に効率的なハッシュベースのスプリットキー PRF の安全性を示すために、コンパイラを使用します。
  論文  参考訳（メタデータ） (2022-06-16T12:48:58Z)
• Verifiable Quantum Advantage without Structure [15.701707809084716]
  ランダムなオラクルをSHA2のような具体的な暗号ハッシュ関数に置き換える。 以上の結果の最小限のインスタンス化が可能である。
  論文  参考訳（メタデータ） (2022-04-05T08:58:24Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
  論文  参考訳（メタデータ） (2022-01-06T03:10:53Z)

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

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