論文の概要: Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM
- arxiv url: http://arxiv.org/abs/2608.17610v1
- Date: Tue, 18 Aug 2026 10:19:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-19 21:40:53.304242
- Title: Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM
- Title（参考訳）: QROMにおける完全完全キーアグリーメントの不完全性に向けて
- Abstract要約: 我々は、完全完全量子計算、古典通信(QCCC)鍵合意の不完全性に向けて前進する。
量子鍵契約に対する最初の無条件攻撃を、以下の制限された設定で構築する。
- 参考スコア（独自算出の注目度）: 9.538313445597385
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We make progress towards the impossibility of imperfectly complete quantum-computation, classical-communication (QCCC) key agreement by constructing the first unconditional attacks on quantum key agreement in the following restricted settings. In the two-message setting, we assume that Alice makes only classical queries to the oracle in the first round and that her message to Bob is classical, but otherwise both parties may perform arbitrary quantum computation, make quantum queries, and send a quantum state in the second round. Our attack and analysis are based on the heavy-query learning techniques from Austrin et al. (CRYPTO 2022) and the reprogramming techniques of Katz and Sela (arXiv 2401.14319). In the round-independent setting, we show that the attack of Barak and Mahmoody (CRYPTO 2009; J. Cryptology 2017) can be extended to multiple rounds when Alice and Bob share classical communication and make only classical queries in all but the final round. In both settings, the attacker is computationally unbounded and makes $poly(λ)$ queries to recover the key whenever each honest query bound is at most $poly(λ)$ and the valid agreement probability is inverse-polynomial. As a consequence, we rule out imperfectly correct quantum public-key encryption for classical messages whose length is bounded by a polynomial in $λ$ in the QROM when key generation has classical oracle access, even if encryption, decryption, and the ciphertext are quantum. In particular, the one-bit case applies to the imperfectly correct PKE obtained from two-round OSP by Bartusek and Khurana (CRYPTO 2025) whenever the classical OSP sender makes only classical random-oracle queries.
- Abstract（参考訳）: 我々は、以下の制限された設定で量子鍵合意に対する最初の無条件攻撃を構築することにより、完全完全量子計算、古典通信(QCCC)鍵合意の不確実性に向けて前進する。
2メッセージ設定では、アリスは第1ラウンドで古典的なクエリのみを生成し、ボブへのメッセージは古典的であると仮定するが、そうでなければ両者は任意の量子計算を行い、量子クエリを作成し、第2ラウンドで量子状態を送信することができる。
攻撃と解析は,Austroin et al (CRYPTO 2022) のヘビークリー学習技術と Katz と Sela (arXiv 2401.14319) のプログラミング技術に基づく。
ラウンド非依存の環境では、AliceとBobが古典的なコミュニケーションを共有し、最終ラウンド以外は古典的なクエリのみを作成する場合、バラクとマフムーディの攻撃(CRYPTO 2009; J. Cryptology 2017)が複数ラウンドに拡張可能であることを示す。
どちらの設定でも、攻撃者は計算的に無バウンドで$poly(λ)$クエリを作成し、各正直なクエリバウンドが少なくとも$poly(λ)$で、有効な一致確率が逆ポリノミカルであるときにキーを復元する。
その結果、暗号、復号化、暗号文が量子であっても、鍵生成が古典的なオラクルアクセスを持つ場合、QROMにおいて、長さが$λ$の多項式で束縛された古典的メッセージに対して、完全正の量子公開鍵暗号を除外する。
特に、1ビットのケースは、古典的なOSP送信者が古典的なランダムなランダムなクエリのみを行う場合、Bartusek と Khurana (CRYPTO 2025) の2ラウンド OSP から得られる不完全正の PKE に適用される。
関連論文リスト
- EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity [0.0]
片道パズルは EFI 対であり、ホールドがオープンかどうかを暗示する。
単方向パズルが存在しない1つの古典的オラクルを、有界検証器でも構成する。
EFIペアは、古典的に神託をクエリするすべての区別器を生き残り、それについてアドバイスし、最後に1つの重ね合わせクエリを作る。
論文 参考訳（メタデータ） (2026-09-10T17:54:55Z) - Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM [7.423478193398542]
完全に完全な量子鍵合意プロトコル(QKA)をブラックボックス方式で量子的にセキュアなワンウェイ関数(OWF)から構築することは不可能である。
本稿では,古典的なメッセージから,$O(((q_mathsfA+q_mathsfB)5)$古典的なオラクルクエリを使って共有鍵を確実に復元できるeavesdropperが存在することを示す。
論文 参考訳（メタデータ） (2026-08-04T15:33:42Z) - Cryptomania v.s. Minicrypt in a Quantum World [5.885896375772235]
我々は,完全完全量子公開鍵暗号(QPKE)を,ブラックボックス方式で量子セキュアなワンウェイ関数(OWF)の古典鍵で構築することは不可能であることを証明した。
論文 参考訳（メタデータ） (2025-04-08T06:07:40Z) - On the Power of Oblivious State Preparation [14.520515990983897]
Oblivious State Preparation (OSP) は、古典的なクライアントと対話する量子サーバのコンテキストで開発された技術を統合する暗号プリミティブである。
その結果は、量子サーバー上での'古典的なリーシュ'を確立するアプローチにおける公開鍵暗号の使用を'説明'するのに役立つ。
論文 参考訳（メタデータ） (2024-11-06T19:58:53Z) - 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) - Revocable Cryptography from Learning with Errors [61.470151825577034]
我々は、量子力学の非閉鎖原理に基づいて、キー呼び出し機能を備えた暗号スキームを設計する。
我々は、シークレットキーが量子状態として表現されるスキームを、シークレットキーが一度ユーザから取り消されたら、それらが以前と同じ機能を実行する能力を持たないことを保証して検討する。
論文 参考訳（メタデータ） (2023-02-28T18:58:11Z) - 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) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z) - Security Limitations of Classical-Client Delegated Quantum Computing [54.28005879611532]
クライアントは、古典的なチャネルを使用して量子状態をリモートで準備する。
サブモジュールとして$RSP_CC$を採用することで生じるプライバシ損失は、不明である。
特定の$RSP_CC$プロトコルは、少なくともいくつかのコンテキストにおいて量子チャネルを置き換えることができることを示す。
論文 参考訳（メタデータ） (2020-07-03T13:15:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。