論文の概要: Compressed Oracle Duality: A simple framework for knowing what quantum adversaries know
- arxiv url: http://arxiv.org/abs/2611.00609v1
- Date: Sat, 31 Oct 2026 04:12:27 GMT
- ステータス: 情報取得中
- システム内更新日: 2026-11-03 19:28:46.391882
- Title: Compressed Oracle Duality: A simple framework for knowing what quantum adversaries know
- Title（参考訳）: Compressed Oracle Duality: 量子敵が知っていることを知るためのシンプルなフレームワーク
- Abstract要約: 私たちは"Compressed Oracle Duality"というフレームワークを提示します。
量子対のメモリにアイソメトリを適用することにより、一対の圧縮オラクルが得られる。
そこで本研究では,新しい圧縮オラクルデータベースを,敵の記憶に極めて優れた測定値を適用した結果について述べる。
- 参考スコア（独自算出の注目度）: 8.438148845727445
- License:
- Abstract: Given a quantum adversary that queries a random oracle, how do we characterize the information that they "know"? The Compressed Oracle method of Zhandry (CRYPTO 2019) is one method that records the queries that the adversary makes; this recording serves as a representation of the information that is learned. However, a significant limitation of the Compressed Oracle method is that it may continue to store information that the adversary has "forgotten." This issue is especially pertinent in the space-bounded setting, where the adversary may uncompute information to free up space, while the information may still reside in the compressed oracle. In this work, we present a simple and interpretable framework called "Compressed Oracle Duality," which extends the Compressed Oracle method for space-bounded algorithms. By applying an isometry to the memory of a quantum adversary, we obtain a pair of compressed oracles with identical marginal distributions and classical correlations which correspond to the knowledge the adversary retains. In fact, we show that the outcome of measuring the new compressed oracle database corresponds exactly to applying the pretty-good measurement on the adversary's memory. As an application of our framework for collision search, we give a simplified proof of the recent $T^2S = Ω(N\log N)$ quantum time-space tradeoff for label-symmetric algorithms due to Magniez-Zur (arXiv:2609.10808); we also prove a stronger classical tradeoff of $TS=Ω(N\log N)$ assuming label symmetry. The proofs under our framework do not require representation theory and instead bound the mutual information between the compressed oracle pairs. This highlights both how the label symmetry assumption bypasses known proof barriers as well as the challenges that remain in achieving unconditional quantum time-space tradeoffs.
- Abstract（参考訳）: ランダムなオラクルを問う量子逆数を考えると、どのようにしてそれらが「知っている」情報を特徴付けるのか?
Compressed Oracle method of Zhandry (CRYPTO 2019)は、相手が行うクエリを記録する方法の1つである。
しかし、Compressed Oracleの手法の重大な制限は、敵が「忘れた」情報を保存し続けることである。
この問題は特に、敵が情報を計算せずに空間を解放し、一方情報がまだ圧縮された神託の中に存在するような空間境界設定において関係している。
本研究では,空間有界アルゴリズムに対する圧縮Oracle法を拡張した,シンプルかつ解釈可能なフレームワーク"Compressed Oracle Duality"を提案する。
量子敵の記憶にアイソメトリを適用することにより、その敵が持つ知識に対応する、同じ限界分布と古典的相関を持つ一対の圧縮オラクルを得る。
実際、新しい圧縮オラクルデータベースの測定結果が、敵の記憶にかなり良い測定値を適用するのと正確に一致していることが示される。
衝突探索のためのフレームワークの応用として、Magniez-Zur (arXiv:2609.10808) によるラベル対称アルゴリズムに対する最近の$T^2S = Ω(N\log N)$量子時空間トレードオフの単純化された証明を与える。
我々の枠組みの下での証明は表現論を必要とせず、代わりに圧縮されたオラクル対の間の相互情報を束縛する。
このことは、ラベル対称性の仮定が既知の証明障壁をバイパスする方法と、無条件の量子時空間トレードオフを達成する際の課題の両方を強調している。
関連論文リスト
- Indistinguishability Lifting for Keyed Oracles, Compressed Ideal Cipher, and More Applications [1.0936043362876648]
暗号のセキュリティ証明は 敵がより大きな 鍵を握った神託と 相互作用することが多い
このような2つの鍵を持つオラクル間の量子的不容易性を示すことは、敵によって作られた単一のクエリは、ベースオーラックのすべてのインスタンスを同時にカバーする重ね合わせを含むため、難しい。
2つの基底オラクルが量子クェリで区別できない場合、その対応するキー付きオラクルもO(q2)乗算損失によって利点を区別できることが示される。
論文 参考訳（メタデータ） (2026-10-03T17:43:49Z) - Oracle Distillation [0.6445605125467574]
オラクル蒸留は、ノイズの多いオラクルへの多くのクエリを単一の高忠実なオラクルに蒸留する手順である。
我々は、任意のブールオラクルを蒸留する明示的プロトコルを構築し、入力量子ビットの定割合を劣化させる逆ノイズと、各量子ビットの定レートで雑音を非偏極化するという2つの条件で構成する。
この結果から、雑音に対して頑健に学習し、頑健なコンピュータセンシングへの道を開く上で、量子的優位性を大いに生かしている。
論文 参考訳（メタデータ） (2026-09-25T17:52:52Z) - EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity [0.0]
片道パズルは EFI 対であり、ホールドがオープンかどうかを暗示する。
単方向パズルが存在しない1つの古典的オラクルを、有界検証器でも構成する。
EFIペアは、古典的に神託をクエリするすべての区別器を生き残り、それについてアドバイスし、最後に1つの重ね合わせクエリを作る。
論文 参考訳（メタデータ） (2026-09-10T17:54:55Z) - Tight Quantum Lower Bound for k-Distinctness [52.10197476419622]
我々は新しい量子クエリローバウンドフレームワークを導入する。
このフレームワークが入力文字列の等しい要素を見つけるという問題に対してどのように振る舞うかを示す。
特に、k-distinctness問題に対する最初の厳密な量子クエリローバウンドを証明することによって、そのパワーを実証する。
論文 参考訳（メタデータ） (2026-04-06T19:52:58Z) - Cloning Games, Black Holes and Cryptography [50.022147589030304]
クローンゲーム解析のための新しいツールキットを提案する。
このフレームワークにより、バイナリフェーズ状態に基づいて新しいクローンゲームを分析することができる。
連成位相の変分最適境界は、ブラックホールの理想化されたモデルで衝突する情報について定量的な洞察を与えることを示す。
論文 参考訳（メタデータ） (2024-11-07T14:09:32Z) - The NISQ Complexity of Collision Finding [2.9405711598281536]
現代の暗号における基本的なプリミティブである衝突耐性ハッシュは、同じハッシュ値を生成する入力を効率的に見つける方法がないことを保証している。
現在、量子敵はNISQのパワーを備えたフルスケールのコンピュータを必要とする。
本稿では, NISQアルゴリズムの3つの異なるモデルについて検討する。
論文 参考訳（メタデータ） (2022-11-23T13:55:28Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - 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) - On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs
of Sequential Work [10.43571631715192]
我々は、量子ランダムオラクルモデル(QROM)における量子アルゴリズムの分析のために、Zhandryによって導入されたいわゆる圧縮オラクル手法を再考する。
我々の主な技術的貢献は、クエリ複雑性の結果を証明するために圧縮されたオラクル技法の並列クエリの一般化を単純化するフレームワークである。
本手法の具体的な暗号的応用として,Cohen と Pietrzak が提唱した "Simple Proofs of Sequential Work" が量子攻撃に対して安全であることを示す。
論文 参考訳（メタデータ） (2020-10-22T12:44:08Z) - Parallelising the Queries in Bucket Brigade Quantum RAM [69.43216268165402]
量子アルゴリズムは、しばしばデータベースのような方法で格納された情報にアクセスするために量子RAM(QRAM)を使用する。
本稿では,Clifford+Tゲートの並列性を利用して,効率的なクエリ時間を大幅に短縮する手法を提案する。
理論的には、フォールトトレラントバケットの量子RAMクエリは古典的なRAMの速度とほぼ一致する。
論文 参考訳（メタデータ） (2020-02-21T14:50:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。