論文の概要: EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity
- arxiv url: http://arxiv.org/abs/2609.11901v1
- Date: Thu, 10 Sep 2026 17:54:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-11 23:53:35.479785
- Title: EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity
- Title（参考訳）: EFIが片道のパズルなしで対決:Oracleはコミュニケーションの複雑さから切り離す
- Abstract要約: 片道パズルは EFI 対であり、ホールドがオープンかどうかを暗示する。
単方向パズルが存在しない1つの古典的オラクルを、有界検証器でも構成する。
EFIペアは、古典的に神託をクエリするすべての区別器を生き残り、それについてアドバイスし、最後に1つの重ね合わせクエリを作る。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: EFI pairs (Brakerski, Canetti, and Qian, ITCS 2023) and one-way puzzles (Khurana and Tomer, STOC 2024) are the leading candidates for the minimal assumption of quantum cryptography. The first are efficiently preparable quantum states, statistically far yet computationally indistinguishable; the second are classical puzzles, easy to sample and hard to solve. One-way puzzles imply EFI pairs, and whether the converse holds is open. We construct a single classical oracle relative to which one-way puzzles do not exist, even with an unbounded verifier, while an EFI pair survives every distinguisher that queries the oracle classically throughout and holds advice about it, making its one superposition query at the end. The oracle answers every question about the output probabilities of quantum samplers, which removes the puzzles, and hides a Haar-random half-dimensional subspace. To prove security we reduce it to communication complexity. An adversary whose knowledge of the subspace arrives as classical query answers can be simulated inside a two-party protocol against the party holding it, so it does no better than the best classical protocol for Vector-in-Subspace (Klartag and Regev, STOC 2011), whatever the oracle computes. That argument does not cover the superposition query, which we bound instead using tools from random matrix theory. The same attack gives a classical simulation of any quantum party in a classical-message protocol with no entanglement shared in advance, so relative to the oracle there is no proof of quantumness either. Quantum polynomial time therefore offers no advantage on any task with classical inputs and outputs, while the two quantum states stay indistinguishable. We state conjectures on removing the restriction on superposition queries.
- Abstract（参考訳）: EFIペア (Brakerski, Canetti, Qian, ITCS 2023) と片方向パズル (Khurana, Tomer, STOC 2024) が量子暗号の最小仮定の候補である。
1つは効率的に準備可能な量子状態であり、統計的には遠いが計算的に区別できない。
片方向パズルは EFI 対であり、逆ホールドが開か否かを暗示する。
単方向のパズルが存在しないような古典的オラクルを1つ構築し、一方、EFI対は古典的にそのオークをクエリする全ての区別器を生き残り、最後に1つの重ね合わせクエリを作る。
オラクルは量子サンプリング器の出力確率に関するあらゆる疑問に答え、パズルを除去し、ハールランダム半次元部分空間を隠す。
セキュリティを証明するために、通信の複雑さを減らします。
古典的な問合せの回答としてサブスペースの知識が届く敵は、それを保持する当事者に対する2つのプロトコルの中でシミュレートできるので、神託が計算したものはVector-in-Subspace(Klartag and Regev, STOC 2011)の最も優れた古典的なプロトコルに勝る。
この議論は重ね合わせのクエリをカバーしていないが、代わりにランダムマトリクス理論のツールを使ってバウンドする。
同じ攻撃は、前もって絡み合いが共有されていない古典的メッセージプロトコルにおける量子パーティの古典的なシミュレーションを与えるため、オラクルと比較して量子性の証明も存在しない。
したがって、量子多項式時間(英語版)は古典的な入力と出力を持ついかなるタスクにも利点を与えないが、2つの量子状態は区別できない。
重畳クエリの制限を取り除くための予想を述べる。
関連論文リスト
- Verifiable quantum advantage in extremely low depth [52.51019642214249]
浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。
浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
論文 参考訳（メタデータ） (2026-09-01T15:54:34Z) - Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM [9.538313445597385]
我々は、完全完全量子計算、古典通信(QCCC)鍵合意の不完全性に向けて前進する。
量子鍵契約に対する最初の無条件攻撃を、以下の制限された設定で構築する。
論文 参考訳（メタデータ） (2026-08-18T10:19:27Z) - Impersonating Quantum Secrets over Classical Channels [10.75127981612396]
古典的なコミュニケーションに耳を傾ける単純な盗聴器は、いずれかの当事者を偽装することができる。
付加的な応用として、古典的な問合せのみで検証できる量子マネースキームは、情報理論上は安全でないことを示す。
論文 参考訳（メタデータ） (2026-01-03T03:40:28Z) - 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) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Succinct Classical Verification of Quantum Computation [30.91621630752802]
量子計算のための古典的簡潔な対話的引数(BQP)を構築する。
我々のプロトコルは、識別不能難読化(iO)と学習エラー(LWE)の事後セキュリティを前提として安全である。
論文 参考訳（メタデータ） (2022-06-29T22:19:12Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - 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) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。