論文の概要: Quantum Cryptography in Algorithmica
- arxiv url: http://arxiv.org/abs/2212.00879v2
- Date: Tue, 2 May 2023 18:57:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-04 18:23:01.353082
- Title: Quantum Cryptography in Algorithmica
- Title（参考訳）: algorithmicaにおける量子暗号
- Authors: William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal
- Abstract要約: ブラックボックス設定では、一方の関数が存在しなくても擬似ランダム状態に基づく量子暗号が可能であることを示す。
また、我々の結果をマルチコピー安全な擬似ランダム状態に一般化する予想も導入する。
- 参考スコア（独自算出の注目度）: 0.7524721345903025
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We construct a classical oracle relative to which $\mathsf{P} = \mathsf{NP}$
yet single-copy secure pseudorandom quantum states exist. In the language of
Impagliazzo's five worlds, this is a construction of pseudorandom states in
"Algorithmica," and hence shows that in a black-box setting, quantum
cryptography based on pseudorandom states is possible even if one-way functions
do not exist. As a consequence, we demonstrate that there exists a property of
a cryptographic hash function that simultaneously (1) suffices to construct
pseudorandom states, (2) holds for a random oracle, and (3) is independent of
$\mathsf{P}$ vs. $\mathsf{NP}$ in the black-box setting. We also introduce a
conjecture that would generalize our results to multi-copy secure pseudorandom
states.
We build on the recent construction by Aaronson, Ingram, and Kretschmer (CCC
2022) of an oracle relative to which $\mathsf{P} = \mathsf{NP}$ but
$\mathsf{BQP} \neq \mathsf{QCMA}$, based on hardness of the OR $\circ$
Forrelation problem. Our proof also introduces a new discretely-defined variant
of the Forrelation distribution, for which we prove pseudorandomness against
$\mathsf{AC^0}$ circuits. This variant may be of independent interest.
- Abstract（参考訳）: 古典オラクルは、$\mathsf{p} = \mathsf{np}$ しかし、単一コピーのセキュアな疑似ランダム量子状態が存在する。
インパグリアッツォの5つの世界の言語では、これは"Algorithmica"における擬似ランダム状態の構成であり、従ってブラックボックスの設定では、一方の関数が存在しなくても擬似ランダム状態に基づく量子暗号が可能であることを示す。
その結果、(1)擬似乱数状態を構成するのに十分であり、(2)ランダムなオラクルを保ち、(3)ブラックボックス設定における$\mathsf{P}$対$\mathsf{NP}$とは独立である暗号ハッシュ関数の性質が示されている。
また、我々の結果をマルチコピー安全な擬似ランダム状態に一般化する予想も導入する。
Aaronson, Ingram, and Kretschmer (CCC 2022) によるオラクルの最近の構成に基づき、OR $\circ$ Forrelation 問題の硬さに基づき、$\mathsf{P} = \mathsf{NP}$ と $\mathsf{BQP} \neq \mathsf{QCMA}$ が成り立つ。
我々の証明はまた、 Forrelation 分布の新しい離散的に定義された変種を導入し、$\mathsf{AC^0}$ 回路に対して擬似ランダム性を証明する。
この変種は独立した興味を持つかもしれない。
関連論文リスト
- Quantum-Computable One-Way Functions without One-Way Functions [0.6349503549199401]
古典的なオラクルを構築し、$mathsfP = MathsfNP$, but quantum-computable quantum-secure trapdoor one-way function が存在する。
この結果から,複数コピーの擬似乱数状態と擬似乱数ユニタリー,古典通信の公開鍵暗号,シグネチャ,暗黙の転送方式が示唆された。
論文 参考訳（メタデータ） (2024-11-04T19:40:01Z) - Quantum State Learning Implies Circuit Lower Bounds [2.2667044928324747]
状態トモグラフィー、擬似ランダム性、量子状態、回路下界の接続を確立する。
わずかに自明な量子状態トモグラフィーアルゴリズムでさえも量子状態合成に関する新しい言明に繋がることを示した。
論文 参考訳（メタデータ） (2024-05-16T16:46:27Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
計算基底の部分集合である$S$に対する部分集合状態は [ frac1sqrt|S|sum_iin S |irangle である。
固定された部分集合サイズ $|S|=s$ に対して、$s = 2n/omega(mathrmpoly(n))$ と $s=omega(mathrmpoly(n))$ が与えられたとき、ランダムな部分集合状態は情報理論上はHaarランダム状態と区別できないことを示す。
論文 参考訳（メタデータ） (2023-12-23T15:52:46Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - The Acrobatics of BQP [1.7136832159667206]
量子時間(mathsfBQP$)の挙動をブラックボックスで設定すると、$mathsfNP$のような古典的な複雑性クラスと著しく分離できることが示される。
また、独立した関心を持つかもしれない新しいツールも導入します。
ランダム制限法の「量子対応」バージョン、$mathsfAC0$回路のブロック感度に対する集中定理、スパースオークスに対するアーロンソン・アンバイニス・コンジェクチャの(証明可能な)アナログを含む。
論文 参考訳（メタデータ） (2021-11-19T19:40:05Z) - Quantum Pseudorandomness and Classical Complexity [0.08158530638728499]
暗号擬似乱数量子状態と擬似乱数ユニタリ変換が存在することを示す。
本稿では、暗号、複雑性理論、量子トモグラフィーにおけるこれらの結果の影響について論じる。
論文 参考訳（メタデータ） (2021-03-16T20:54:12Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。
我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。
補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
論文 参考訳（メタデータ） (2020-09-29T08:41:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。