論文の概要: Quantum Cryptography and Hardness of Non-Collapsing Measurements

• arxiv url: http://arxiv.org/abs/2510.04448v1
• Date: Mon, 06 Oct 2025 02:42:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 16:52:59.661146
• Title: Quantum Cryptography and Hardness of Non-Collapsing Measurements
• Title（参考訳）: 量子暗号と非崩壊測定の硬さ
• Authors: Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa,
• Abstract要約: ワンウェイパズル (OWPuzzs) はワンウェイ関数 (OWFs) の量子アナログである。 本稿では,非折り畳み測定の硬さに基づくOWPuzzsについて述べる。 我々は、新しい原始的、分布的衝突耐性パズル(dCRPuzzs)を導入する。
• 参考スコア（独自算出の注目度）: 10.237675529033163
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: One-way puzzles (OWPuzzs) introduced by Khurana and Tomer [STOC 2024] are a natural quantum analogue of one-way functions (OWFs), and one of the most fundamental primitives in ''Microcrypt'' where OWFs do not exist but quantum cryptography is possible. OWPuzzs are implied by almost all quantum cryptographic primitives, and imply several important applications such as non-interactive commitments and multi-party computations. A significant goal in the field of quantum cryptography is to base OWPuzzs on plausible assumptions that will not imply OWFs. In this paper, we base OWPuzzs on hardness of non-collapsing measurements. To that end, we introduce a new complexity class, $\mathbf{SampPDQP}$, which is a sampling version of the decision class $\mathbf{PDQP}$ introduced in [Aaronson, Bouland, Fitzsimons, and Lee, ITCS 2016]. We show that if $\mathbf{SampPDQP}$ is hard on average for quantum polynomial time, then OWPuzzs exist. $\mathbf{SampPDQP}$ is the class of sampling problems that can be solved by a classical polynomial-time algorithm that can make a single query to a non-collapsing measurement oracle, which is a ''magical'' oracle that can sample measurement results on quantum states without collapsing the states. Such non-collapsing measurements are highly unphysical operations that should be hard to realize in quantum polynomial-time. We also study upperbounds of the hardness of $\mathbf{SampPDQP}$. We introduce a new primitive, distributional collision-resistant puzzles (dCRPuzzs), which are a natural quantum analogue of distributional collision-resistant hashing [Dubrov and Ishai, STOC 2006]. We show that dCRPuzzs imply average-case hardness of $\mathbf{SampPDQP}$ (and therefore OWPuzzs as well). We also show that two-message honest-statistically-hiding commitments with classical communication and one-shot signatures [Amos, Georgiou, Kiayias, Zhandry, STOC 2020] imply dCRPuzzs.
• Abstract（参考訳）: Khurana と Tomer (STOC 2024) によって導入されたワンウェイパズル (OWPuzzs) は、ワンウェイ関数 (OWF) の自然量子アナログであり、OWFが存在しないが量子暗号が可能である'マイクロ暗号'における最も基本的なプリミティブの1つである。 OWPuzzは、ほとんど全ての量子暗号プリミティブによって暗示され、非インタラクティブなコミットメントやマルチパーティ計算などの重要な応用を暗示している。 量子暗号の分野における重要なゴールは、OWPuzzsをOWFを暗示しない有望な仮定に基づけることである。 本稿では,非折り畳み測定の硬さに基づくOWPuzzsについて述べる。 このクラスは、[Aaronson, Bouland, Fitzsimons, and Lee, ITCS 2016]で導入された決定クラスである$\mathbf{PDQP}$のサンプリング版である。 量子多項式時間において、$\mathbf{SampPDQP}$ が平均的に困難であれば、OWPuzzs が存在することを示す。 $\mathbf{SampPDQP}$は、古典多項式時間アルゴリズムによって解けるサンプリング問題のクラスであり、非折り畳み測定オラクルに単一のクエリを作成できる。 このような非折り畳み測定は、量子多項式時間において実現し難い、非常に非物理学的な操作である。 また、$\mathbf{SampPDQP}$の硬さの上限についても検討する。 本稿では, 分散衝突抵抗型ハッシュの自然な量子アナログである, 新しいプリミティブ, 分散衝突抵抗型パズル (dCRPuzzs, STOC 2006) を紹介する。 dCRPuzzsは$\mathbf{SampPDQP}$(したがってOWPuzzsも)の平均ケース硬さを示す。 また、古典的なコミュニケーションとワンショットシグネチャ(Amos, Georgiou, Kiayias, Zhandry, STOC 2020)との2つのメッセージの正直な関係は、dCRPuzzsを暗示している。

関連論文リスト

• Hardness of Quantum Distribution Learning and Quantum Cryptography [11.85957541950196]
  ワンウェイパズル(OWPuzzs)はワンウェイ関数(OWFs)の自然量子アナログを提供する。 本稿では、よく研究された学習モデルの硬さに基づくOWPuzzの完全な特徴付けとして、分布学習を初めて確立する。
  論文  参考訳（メタデータ） (2025-07-02T02:12:38Z)
• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  我々は、ハミルトニアン相状態(HPS)問題と呼ばれる量子硬度仮定を導入する。 我々は、我々の仮定が少なくとも完全に量子的であることを示し、すなわち片方向関数を構成するのに使用できない。 仮定とその変形により、多くの擬似ランダム量子プリミティブを効率的に構築できることを示す。
  論文  参考訳（メタデータ） (2024-10-10T16:10:10Z)
• Quantum Cryptography and Meta-Complexity [2.6089354079273512]
  古典暗号では、ワンウェイ関数(OWF)は最小の仮定であるが、量子暗号ではそうではない。 片方向パズル(OWPuzzs)がGapKが弱量子平均ハードである場合にのみ存在することを示す。 また、量子PRGが存在する場合、GapKは量子平均ハードであることを示す。
  論文  参考訳（メタデータ） (2024-10-02T09:30:06Z)
• 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)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。 我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。 すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
  論文  参考訳（メタデータ） (2023-03-02T14:18:17Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。