論文の概要: On the computational hardness needed for quantum cryptography
- arxiv url: http://arxiv.org/abs/2209.04101v2
- Date: Thu, 24 Nov 2022 23:47:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-27 05:33:42.274904
- Title: On the computational hardness needed for quantum cryptography
- Title（参考訳）: 量子暗号に必要な計算硬度について
- Authors: Zvika Brakerski, Ran Canetti, Luowen Qian
- Abstract要約: 大規模な量子暗号アプリケーションにはEFIペアが必要であることを示す。
我々は、最小限のコミットメントスキーム、曖昧な転送、そして一般的なセキュアなマルチパーティ証明からEFIペアを構築する。
これは、量子暗号の多くにおいて、EFIペアが古典的な環境でのOWFと同じような役割を果たすことを示唆している。
- 参考スコア（独自算出の注目度）: 10.760579667794476
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In the classical model of computation, it is well established that one-way
functions (OWF) are minimal for computational cryptography: They are essential
for almost any cryptographic application that cannot be realized with respect
to computationally unbounded adversaries. In the quantum setting, however, OWFs
appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and
Yamakawa 2022), and the question of whether such a minimal primitive exists
remains open.
We consider EFI pairs -- efficiently samplable, statistically far but
computationally indistinguishable pairs of (mixed) quantum states. Building on
the work of Yan (2022), which shows equivalence between EFI pairs and
statistical commitment schemes, we show that EFI pairs are necessary for a
large class of quantum-cryptographic applications. Specifically, we construct
EFI pairs from minimalistic versions of commitments schemes, oblivious
transfer, and general secure multiparty computation, as well as from
$\mathsf{QCZK}$ proofs from essentially any non-trivial language. We also
construct quantum computational zero knowledge ($\mathsf{QCZK}$) proofs for all
of $\mathsf{QIP}$ from any EFI pair.
This suggests that, for much of quantum cryptography, EFI pairs play a
similar role to that played by OWFs in the classical setting: they are simple
to describe, essential, and also serve as a linchpin for demonstrating
equivalence between primitives.
- Abstract（参考訳）: 古典的な計算モデルでは、一方通行関数 (OWF) は計算暗号において最小限であることがよく理解されている。
しかし、量子環境では、OWFは必須ではないように見える(Kretschmer 2021, Ananth et al., Morimae and Yamakawa 2022)。
EFI対 -- 効率的にサンプリング可能、統計的に遠いが、(混合された)量子状態の対は計算的に区別できない。
EFIペアと統計的コミットメントスキームの等価性を示すYan (2022) の研究に基づいて、EFIペアは大規模な量子暗号アプリケーションに必要であることを示す。
具体的には、最小限のコミットメントスキーム、曖昧な転送、一般的なセキュアなマルチパーティ計算、および本質的には自明でない言語からの$\mathsf{QCZK}$証明からEFIペアを構築する。
また、任意のefiペアから$\mathsf{qip}$の全ての証明に対して量子計算ゼロ知識(\mathsf{qczk}$)を構築します。
これは、量子暗号の多くにおいて、efiペアは古典的設定においてowfsが演じているものと同様の役割を担っていることを示唆している:それらは記述が簡単であり、本質的であり、プリミティブ間の等価性を示すためのlinchpinとしても機能する。
関連論文リスト
- A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID [16.5193119873963]
EFI対が存在する量子ユニタリオラクルが存在することを示すが、OWSGは存在しない。
私たちは、オラクル、QEFID、片道パズルを通じて、OWSGや他のMicrocryptプリミティブから切り離しています。
論文 参考訳（メタデータ） (2024-10-04T14:11:56Z) - Oracle Separation Between Quantum Commitments and Quantum One-wayness [0.6882042556551611]
量子コミットメントが存在するが、(効果的に検証可能な)片方向状態生成器が存在しないような、ユニタリな量子オラクルが存在することを示す。
最近の研究は、一方の状態発生器からコミットメントを構築することができることを示したが、他方の方向は未解決のままである。
論文 参考訳（メタデータ） (2024-10-04T12:26:21Z) - Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - Pseudo-Entanglement is Necessary for EFI Pairs [0.0]
我々は、新しい量子資源、擬似絡み合いを考察し、EFI対の存在が擬似絡み合いの存在を意味することを示す。
この結果は,計算暗号の分野において重要な意味を持つ。
論文 参考訳（メタデータ） (2024-06-11T01:44:16Z) - Exponential Quantum One-Wayness and EFI Pairs [18.481934628015004]
古典暗号では、一方通行関数は最小の計算仮定であると広く考えられている。
片方向関数の探索量子一般化は片方向状態発生器(OWSG)である。
その結果,IV-OWSGs は EFI 対と正確に等価であり,比例的に減少することがわかった。
論文 参考訳（メタデータ） (2024-04-21T15:55:00Z) - 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) - One-Wayness in Quantum Cryptography [9.09597656634436]
本研究では,一方向関数の量子アナログである一方向状態発生器(OWSG)の特性について検討する。
量子デジタル署名はOWSGと等価であることを示す。
我々は、秘密に検証可能で統計的に可逆なOWSGと呼ばれるOWSGの変種を紹介する。
論文 参考訳（メタデータ） (2022-10-07T08:21:21Z) - Computation-aided classical-quantum multiple access to boost network
communication speeds [61.12008553173672]
我々は,2次元のcq-MACに対する計算特性を持つ符号の達成可能な量子通信速度を定量化する。
従来の設計では実現不可能な通信速度(シングルユーザ容量)を最大化できることを示す。
論文 参考訳（メタデータ） (2021-05-30T11:19:47Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z) - Efficient simulatability of continuous-variable circuits with large
Wigner negativity [62.997667081978825]
ウィグナー負性性は、いくつかの量子計算アーキテクチャにおいて計算上の優位性に必要な資源であることが知られている。
我々は、大きく、おそらくは有界で、ウィグナー負性を示し、しかし古典的に効率的にシミュレートできる回路の広大な族を同定する。
我々は,高次元離散可変量子回路のシミュラビリティとボソニック符号とのリンクを確立することにより,本結果の導出を行う。
論文 参考訳（メタデータ） (2020-05-25T11:03:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。