論文の概要: Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness
- arxiv url: http://arxiv.org/abs/2409.15248v2
- Date: Thu, 10 Oct 2024 17:49:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-06 20:16:59.305465
- Title: Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness
- Title（参考訳）: 量子アドバンテージに基づく量子暗号の創出, あるいは$\mathsf{\#P}$-Hardnessの暗号を目指して
- Authors: Dakshita Khurana, Kabir Tomer,
- Abstract要約: 近年の分離により、階層構造が崩壊しても持続する硬さの源から量子暗号を構築する可能性が高まっている。
量子暗号は、$mathsfP#P notsubseteq mathsf(io)BQP/qpoly$という非常に穏やかな仮定に基づいている。
- 参考スコア（独自算出の注目度）: 10.438299411521099
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent oracle separations [Kretschmer, TQC'21, Kretschmer et. al., STOC'23] have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if the polynomial hierarchy collapses. We realize this possibility by building quantum bit commitments and secure computation from unrelativized, well-studied mathematical problems that are conjectured to be hard for $\mathsf{P^{\#P}}$ -- such as approximating the permanents of complex Gaussian matrices, or approximating the output probabilities of random quantum circuits. Indeed, we show that as long as any one of the conjectures underlying sampling-based quantum advantage (e.g., BosonSampling, Random Circuit Sampling, IQP, etc.) is true, quantum cryptography can be based on the extremely mild assumption that $\mathsf{P^{\#P}} \not\subseteq \mathsf{(io)BQP/qpoly}$. We prove that the following hardness assumptions are equivalent. (1) The hardness of approximating the probability assigned to a randomly chosen string in the support of certain efficiently sampleable distributions (upto inverse polynomial multiplicative error).(2) The existence of one-way puzzles, where a quantum sampler outputs a pair of classical strings -- a puzzle and its key -- and where the hardness lies in finding the key corresponding to a random puzzle. These are known to imply quantum bit commitments [Khurana and Tomer, STOC'24]. (3) The existence of state puzzles, or one-way state synthesis, where it is hard to synthesize a secret quantum state given a public classical identifier. These capture the hardness of search problems with quantum inputs (secrets) and classical outputs (challenges). These are the first constructions of quantum cryptographic primitives (one-way puzzles, quantum bit commitments, state puzzles) from concrete, well-founded mathematical assumptions that do not imply the existence of classical cryptography.
- Abstract（参考訳）: 最近のオラクル分離(Kretschmer, TQC'21, Kretschmer et al , STOC'23)は、多項式階層が崩壊しても持続する硬さの源から量子暗号を構築する可能性を高めている。
我々は、量子ビットのコミットメントを構築し、複雑なガウス行列の永続性を近似したり、ランダムな量子回路の出力確率を近似するなど、$\mathsf{P^{\#P}}$ -- では難しいと推測される、非相対的でよく研究された数学的問題からセキュアな計算を行うことによって、この可能性を実現する。
実際、サンプリングベースの量子優位性(例えば、BosonSampling, Random Circuit Sampling, IQPなど)が真である限り、量子暗号は$\mathsf{P^{\#P}} \not\subseteq \mathsf{(io)BQP/qpoly}$という非常に穏やかな仮定に基づいている。
以下の硬度仮定が等価であることを証明する。
1) ある効率的なサンプリング可能な分布(逆多項式乗算誤差まで)の支持において、ランダムに選択された文字列に割り当てられた確率を近似する難しさ。
2) 量子サンプリング器が一対の古典的な文字列(パズルとその鍵)を出力し、ランダムなパズルに対応する鍵を見つけるのに難しさがある一方向パズルの存在。
これらは量子ビットのコミットメントを暗示することが知られている[Khurana and Tomer, STOC'24]。
(3) 公的な古典的識別子が与えられた秘密量子状態の合成が困難である状態パズル(一方向状態合成)の存在。
これらは探索問題の難しさを量子入力(秘密)と古典出力(カオス)で捉えている。
これらは量子暗号プリミティブ(一方のパズル、量子ビットのコミットメント、状態のパズル)を、古典的な暗号の存在を暗示しない明確な数学的仮定から構築した最初のものである。
関連論文リスト
- Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
我々は、ハミルトニアン相状態(HPS)問題と呼ばれる量子硬度仮定を導入する。
我々は、我々の仮定が少なくとも完全に量子的であることを示し、すなわち片方向関数を構成するのに使用できない。
仮定とその変形により、多くの擬似ランダム量子プリミティブを効率的に構築できることを示す。
論文 参考訳（メタデータ） (2024-10-10T16:10:10Z) - A Meta-Complexity Characterization of Quantum Cryptography [2.8311451575532156]
量子暗号プリミティブの最初のメタ複雑性のキャラクタリゼーションを証明した。
片方向パズルが存在することは、カルモゴロフ複雑性を近似することが困難であるような二進弦の量子サンプリング可能な分布が存在する場合に限る。
論文 参考訳（メタデータ） (2024-10-07T12:29:27Z) - Hard Quantum Extrapolations in Quantum Cryptography [9.214658764451348]
普遍外挿タスクの量子アナログについて検討する。
量子コミットメントが存在すれば困難であり、量子空間にとって容易であることを示す。
論文 参考訳（メタデータ） (2024-09-25T00:09:42Z) - Commitments from Quantum One-Wayness [0.0]
本研究は、片方向関数の自然な量子緩和である片方向状態発生器を研究する。
根本的な問題は、このタイプの量子ワンウェイネスが量子暗号を実現するのに十分であるかどうかである。
我々は、純粋な状態出力を持つ一方通行状態生成器が量子ビットのコミットメントを暗示し、セキュアなマルチパーティ計算を行うことを証明した。
論文 参考訳（メタデータ） (2023-10-17T18:48:22Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - 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) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。