論文の概要: Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM
- arxiv url: http://arxiv.org/abs/2608.03824v1
- Date: Tue, 04 Aug 2026 15:33:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-05 15:30:23.268349
- Title: Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM
- Title（参考訳）: QROMにおける完全完全多言語キーアグリーメントの不可能性
- Abstract要約: 完全に完全な量子鍵合意プロトコル(QKA)をブラックボックス方式で量子的にセキュアなワンウェイ関数(OWF)から構築することは不可能である。
本稿では,古典的なメッセージから,$O(((q_mathsfA+q_mathsfB)5)$古典的なオラクルクエリを使って共有鍵を確実に復元できるeavesdropperが存在することを示す。
- 参考スコア（独自算出の注目度）: 7.423478193398542
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper proves that it is impossible to construct perfectly complete quantum key agreement protocols (QKA) from quantumly secure one-way functions (OWFs) in a black-box manner. Specifically, consider any protocol in which Alice and Bob exchange only classical messages, make at most $q_{\mathsf{A}}$ and $q_{\mathsf{B}}$ quantum queries, respectively, to a Boolean-valued random oracle, and agree on a shared key with certainty. This paper shows that there exists an eavesdropper, given the classical messages, that can recover the shared key with certainty using $O((q_{\mathsf{A}}+q_{\mathsf{B}})^5)$ classical oracle queries. The bound is independent of the number of rounds, transcript length, key length, and oracle-domain size. Previous results only applies to two-round key agreement (Li et al. CRYPTO 26) or relies on unproven conjectures (Austrin et al. CRYPTO 22). GPT-5.6 Sol Ultra found this proof in a one-shot conversation and drafted a preliminary version of this paper. The authors are fully responsible for the correctness, writing and discussions of this paper.
- Abstract（参考訳）: 本稿では,完全完全量子鍵合意プロトコル(QKA)を,ブラックボックス方式で量子的に安全な一方向関数(OWF)から構築することは不可能であることを示す。
具体的には、アリスとボブが古典的なメッセージのみを交換するプロトコルを考え、少なくとも$q_{\mathsf{A}}$と$q_{\mathsf{B}}$の量子クエリをブール値のランダムなオラクルにそれぞれ交換し、共有鍵に確実に同意する。
本稿では、古典的なメッセージから、$O(((q_{\mathsf{A}}+q_{\mathsf{B}})^5)$古典的なオラクルクエリを使って共有鍵を確実に復元できるeavesdropperが存在することを示す。
境界は、ラウンド数、書き起こしの長さ、キーの長さ、およびオラクルドメインサイズに依存しない。
以前の結果は、2ラウンドの鍵合意 (Li et al CRYPTO 26) にのみ適用されるか、証明されていない予想 (Austrin et al CRYPTO 22) に依存している。
GPT-5.6 Sol Ultraはこの証明をワンショット会話で発見し、この論文の予備版を起草した。
著者らは,本論文の正確性,執筆,議論に全責任を負っている。
関連論文リスト
- EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity [0.0]
片道パズルは EFI 対であり、ホールドがオープンかどうかを暗示する。
単方向パズルが存在しない1つの古典的オラクルを、有界検証器でも構成する。
EFIペアは、古典的に神託をクエリするすべての区別器を生き残り、それについてアドバイスし、最後に1つの重ね合わせクエリを作る。
論文 参考訳（メタデータ） (2026-09-10T17:54:55Z) - Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM [9.538313445597385]
我々は、完全完全量子計算、古典通信(QCCC)鍵合意の不完全性に向けて前進する。
量子鍵契約に対する最初の無条件攻撃を、以下の制限された設定で構築する。
論文 参考訳（メタデータ） (2026-08-18T10:19:27Z) - Computational Monogamy of Entanglement and Non-Interactive Quantum Key Distribution [21.219588497290115]
量子鍵分布(QKD)により、アリスとボブは秘密鍵を公開の信頼できない量子チャネル上で交換することができる。
従来のキー交換と比較して、QKDは永続的なセキュリティを実現している。
量子情報を用いても、永続的なセキュリティを提供する非対話的プロトコルは知られていない。
論文 参考訳（メタデータ） (2025-10-01T11:41:04Z) - Cryptomania v.s. Minicrypt in a Quantum World [5.885896375772235]
我々は,完全完全量子公開鍵暗号(QPKE)を,ブラックボックス方式で量子セキュアなワンウェイ関数(OWF)の古典鍵で構築することは不可能であることを証明した。
論文 参考訳（メタデータ） (2025-04-08T06:07:40Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Towards the Impossibility of Quantum Public Key Encryption with
Classical Keys from One-Way Functions [0.5999777817331317]
量子公開鍵を考えると、一方通行関数(OWF)からの公開鍵暗号(PKE)が可能であることが最近示されている。
本稿では,従来の公開鍵を用いたPKEのブラックボックス分離とOWFからの量子暗号文に着目した。
論文 参考訳（メタデータ） (2023-11-06T20:41:25Z) - Robust Quantum Public-Key Encryption with Applications to Quantum Key
Distribution [16.06159998475861]
量子鍵分布(QKD)により、アリスとボブは公開(信頼できない)量子チャネル上で通信しながら共有秘密鍵に合意することができる。
i)鍵は無条件に攻撃者の目に隠されており、(ii)そのセキュリティは認証された古典的なチャンネルの存在のみを前提としている。
本稿では,量子セキュアな片方向関数の存在を前提として,永続的セキュリティを満たす2メッセージQKDプロトコルを提案する。
論文 参考訳（メタデータ） (2023-04-06T11:14:55Z) - 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) - Succinct Classical Verification of Quantum Computation [30.91621630752802]
量子計算のための古典的簡潔な対話的引数(BQP)を構築する。
我々のプロトコルは、識別不能難読化(iO)と学習エラー(LWE)の事後セキュリティを前提として安全である。
論文 参考訳（メタデータ） (2022-06-29T22:19:12Z) - 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) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。