論文の概要: The Black-Box Simulation Barrier Persists in a Fully Quantum World
- arxiv url: http://arxiv.org/abs/2409.06317v1
- Date: Tue, 10 Sep 2024 08:17:17 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-11 18:30:15.447491
- Title: The Black-Box Simulation Barrier Persists in a Fully Quantum World
- Title（参考訳）: 完全な量子世界におけるブラックボックスシミュレーションバリア
- Authors: Nai-Hui Chia, Kai-Min Chung, Xiao Liang, Jiahui Liu,
- Abstract要約: 我々は、$mathbfBQP$の言語のみが、定ラウンド$textitfully-quantum$ BBZKを許容していることを示す。
量子ゼロ知識の性質を照らし、量子領域で将来のプロトコルを設計するための貴重な洞察を提供する。
- 参考スコア（独自算出の注目度）: 9.887919546667598
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Zero-Knowledge (ZK) protocols have been intensely studied due to their fundamental importance and versatility. However, quantum information's inherent differences significantly alter the landscape, necessitating a re-examination of ZK designs. A crucial aspect is round complexity, linked to $\textit{simulation}$, which forms the foundation of ZK definition and security proofs. In the $\textit{post-quantum}$ setting, where honest parties and channels are classical but adversaries quantum, Chia et al. [FOCS'21] showed constant-round $\textit{black-box-simulatable}$ ZK arguments (BBZK) for $\mathbf{NP}$ are impossible unless $\mathbf{NP} \subseteq \mathbf{BQP}$. But this problem remains open when all parties and communication are quantum. Indeed, this problem interests the broader theory of quantum computing. Investigating how quantum power alters tasks like the $\textit{unconditional}$ security of QKD and incorporating OT in MiniQCrypt has been crucial. Moreover, quantum communication has enabled round compression for commitments and interactive arguments. Along this line, understanding if quantum computing could fundamentally change ZK protocols is vital. We resolved this problem by proving that only languages in $\mathbf{BQP}$ admit constant-round $\textit{fully-quantum}$ BBZK. This result holds significant implications. Firstly, it illuminates the nature of quantum zero-knowledge and provides valuable insights for designing future protocols in the quantum realm. Secondly, it relates ZK round complexity with the intriguing problem of $\mathbf{BQP}$ vs $\mathbf{QMA}$, which is out of the reach of previous analogue impossibility results in the classical or post-quantum setting. Lastly, it justifies the need for the $\textit{non-black-box}$ simulation techniques or the relaxed security notions employed in existing constant-round fully-quantum BBZK protocols.
- Abstract（参考訳）: Zero-Knowledge (ZK) プロトコルは、その基本的な重要性と汎用性から、非常に研究されている。
しかし、量子情報の固有の違いはランドスケープを大きく変え、ZK設計の再検討を必要とした。
重要な側面はラウンド複雑性であり、ZK定義とセキュリティ証明の基礎となる$\textit{simulation}$に関連付けられている。
$\textit{post-quantum}$ set, where honest parties and channel are classical but adversaries quantum, Chia et al [FOCS'21] showed constant-round $\textit{black-box-simulatable}$ ZK arguments (BBZK) for $\mathbf{NP}$は$\mathbf{NP} \subseteq \mathbf{BQP}$でない限り不可能である。
しかし、すべての当事者とコミュニケーションが量子である場合、この問題は未解決のままである。
実際、この問題は量子コンピューティングのより広範な理論に関心がある。
量子パワーが$\textit{unconditional}$ QKDのセキュリティやMiniQCryptにOTを組み込むようなタスクをどのように変更するかを調べることは、非常に重要です。
さらに、量子通信はコミットメントと対話的議論のためのラウンド圧縮を可能にした。
この線に沿って、量子コンピューティングがZKプロトコルを根本的に変えることができるかどうかを理解することが不可欠である。
この問題は、$\mathbf{BQP}$ admit constant-round $\textit{fully-quantum}$ BBZK の言語のみを許容することを証明することで解決した。
この結果は大きな意味を持つ。
まず、量子ゼロ知識の性質を照らし、量子領域における将来のプロトコルを設計するための貴重な洞察を提供する。
第二に、ZK のラウンド複雑性は $\mathbf{BQP}$ と $\mathbf{QMA}$ の興味深い問題と関連している。
最後に、$\textit{non-black-box}$ シミュレーション技術や、既存の定ラウンド完全量子BBZKプロトコルで使用される緩和されたセキュリティ概念の必要性を正当化する。
関連論文リスト
- Complexity Theory for Quantum Promise Problems [5.049812996253858]
本稿では,量子暗号と複雑性理論の関係,特にImpagliazzoの5つの世界の枠組みについて考察する。
複雑性クラス p/mBQP, p/mQ(C)MA, $mathrmp/mQSZK_hv$, p/mQIP, p/mPSPACE に注目する。
我々は、このフレームワークを暗号に適用し、一方通行状態生成器、擬似ランダム状態、EFIがmQCMAで束縛されていることを示す。
論文 参考訳（メタデータ） (2024-11-06T07:29:52Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Post-Quantum Zero-Knowledge with Space-Bounded Simulation [8.69082943773532]
近距離量子デバイスとより互換性のある,量子後ゼロ知識の詳細な概念を導入する。
対数量子空間 $s$ と古典空間を持つ検証器に対しては、$f(s)=2s$ に対して$(s,f)$-空間有界 QZK が得られることを示す。
超対数量子空間$s$の検証器について、量子後一方向の存在を仮定すると、完全に黒の$(s,f)$空間有界QZKプロトコルが示される。
論文 参考訳（メタデータ） (2022-10-12T11:13:56Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z) - Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's
Post-Quantum Security [67.06003361150228]
作業の証明(英: proof of work、PoW)は、当事者が計算タスクの解決にいくらかの労力を費やしたことを他人に納得させることができる重要な暗号構造である。
本研究では、量子戦略に対してそのようなPoWの連鎖を見つけることの難しさについて検討する。
我々は、PoWs問題の連鎖が、マルチソリューションBernoulliサーチと呼ばれる問題に還元されることを証明し、量子クエリの複雑さを確立する。
論文 参考訳（メタデータ） (2020-12-30T18:03:56Z) - A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds [12.525959293825318]
我々は,統計音性およびブラックボックス$epsilon$-zero-knowledgeを満たすNPのラウンド・インタラクティブ証明を構築した。
我々の研究の核心は、シミュレーターが悪意のある検証者のコミットメッセージを抽出できる新しい量子巻き戻し技術である。
論文 参考訳（メタデータ） (2020-11-05T05:40:05Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z) - Fault-tolerant Coding for Quantum Communication [71.206200318454]
ノイズチャネルの多くの用途でメッセージを確実に送信するために、回路をエンコードしてデコードする。
すべての量子チャネル$T$とすべての$eps>0$に対して、以下に示すゲートエラー確率のしきい値$p(epsilon,T)$が存在し、$C-epsilon$より大きいレートはフォールトトレラント的に達成可能である。
我々の結果は、遠方の量子コンピュータが高レベルのノイズの下で通信する必要があるような、大きな距離での通信やオンチップでの通信に関係している。
論文 参考訳（メタデータ） (2020-09-15T15:10:50Z) - Succinct Blind Quantum Computation Using a Random Oracle [0.8702432681310399]
我々は新しい普遍的な盲点量子計算プロトコルを提供する。
プロトコルの最初のフェーズは簡潔であり、その複雑さは回路サイズとは無関係である。
論文 参考訳（メタデータ） (2020-04-27T07:47:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。