論文の概要: NISQ Security and Complexity via Simple Classical Reasoning
- arxiv url: http://arxiv.org/abs/2509.09900v1
- Date: Thu, 11 Sep 2025 23:31:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-15 16:03:07.947236
- Title: NISQ Security and Complexity via Simple Classical Reasoning
- Title（参考訳）: NISQセキュリティとシンプル古典推論による複雑度
- Authors: Alexandru Cojocaru, Juan Garay, Qipeng Liu, Fang Song,
- Abstract要約: ノイズ中間スケール量子(NISQ)設定における量子ランダムオラクルモデル(QROM)におけるセキュリティゲームに対する新しいリフト定理を提案する。
我々は、量子および古典的クエリの両方を実行できるハイブリッドアルゴリズムに対して、初めてハイブリッドリフト定理を提供する。
平均ケースにおける最初の直接積定理、すなわち、マルチインスタンスセキュリティゲームを解く際のハイブリッドハードネスを決定するためのツールであるハイブリッド設定定理を導出する。
- 参考スコア（独自算出の注目度）: 41.17296890645859
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give novel lifting theorems for security games in the quantum random oracle model (QROM) in Noisy Intermediate-Scale Quantum (NISQ) settings such as the hybrid query model, the noisy oracle and the bounded-depth models. We provide, for the first time, a hybrid lifting theorem for hybrid algorithms that can perform both quantum and classical queries, as well as a lifting theorem for quantum algorithms with access to noisy oracles or bounded quantum depth. At the core of our results lies a novel measure-and-reprogram framework, called hybrid coherent measure-and-reprogramming, tailored specifically for hybrid algorithms. Equipped with the lifting theorem, we are able to prove directly NISQ security and complexity results by calculating a single combinatorial quantity, relying solely on classical reasoning. As applications, we derive the first direct product theorems in the average case, in the hybrid setting-i.e., an enabling tool to determine the hybrid hardness of solving multi-instance security games. This allows us to derive in a straightforward manner the NISQ hardness of various security games, such as (i) the non-uniform hardness of salted games, (ii) the hardness of specific cryptographic tasks such as the multiple instance version of one-wayness and collision-resistance, and (iii) uniform or non-uniform hardness of many other games.
- Abstract（参考訳）: 我々は、ハイブリッドクエリモデル、ノイズオラクル、有界深度モデルなどのノイズ中間スケール量子(NISQ)設定において、量子ランダムオラクルモデル(QROM)におけるセキュリティゲームに対する新しいリフト定理を与える。
我々は、量子クエリと古典クエリの両方を実行できるハイブリッドアルゴリズムのハイブリッドリフト定理と、ノイズの多いオラクルや有界量子深さにアクセス可能な量子アルゴリズムのリフト定理を初めて提供する。
結果の核となるのは、ハイブリットアルゴリズムに特化した、ハイブリット・コヒーレント・コヒーレント・コヒーレント・カウンタ・アンド・プログラミングと呼ばれる、新しい測度・プログラムのフレームワークです。
昇降定理により、古典的推論のみに依存する単一の組合せ量を計算することにより、直接NISQセキュリティと複雑性の結果を証明できる。
応用として、我々は、平均の場合において最初の直接積定理、すなわち、マルチインスタンスセキュリティゲームを解く際のハイブリッドハードネスを決定することができるツールを導出する。
これにより、様々なセキュリティゲーム(例えば、NISQの難しさ)を直接的に引き出すことができます。
(i)ソルトゲームの不均一な硬さ。
二 ワンウェイネスの複数インスタンスバージョン、衝突耐性等の特定の暗号処理の難しさ
(三)他の多くのゲームにおいて一様または一様でない硬さ。
関連論文リスト
- Improved Quantum Lifting by Coherent Measure-and-Reprogram [41.17296890645859]
量子ランダムモデルオラクルにおけるセキュリティゲームに対するより厳密なリフト定理を与える。
私たちの主な成果の中核は、コヒーレント・リプログラミングと呼ばれる新しい測度とリプログラミングのフレームワークです。
論文 参考訳（メタデータ） (2025-09-11T23:15:13Z) - Quantum Lifting for Invertible Permutations and Ideal Ciphers [47.33103206862089]
量子乱数置換と理想的な暗号モデルにおけるセキュリティを確立するための最初の持ち上げ定理を導出する。
これらの定理は、任意の量子逆数の成功確率と、少数の古典的クエリのみを作る古典的アルゴリズムの成功確率を関連付ける。
論文 参考訳（メタデータ） (2025-04-25T09:07:55Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - The NISQ Complexity of Collision Finding [2.9405711598281536]
現代の暗号における基本的なプリミティブである衝突耐性ハッシュは、同じハッシュ値を生成する入力を効率的に見つける方法がないことを保証している。
現在、量子敵はNISQのパワーを備えたフルスケールのコンピュータを必要とする。
本稿では, NISQアルゴリズムの3つの異なるモデルについて検討する。
論文 参考訳（メタデータ） (2022-11-23T13:55:28Z) - A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
古典的AES様対称暗号のための変分量子攻撃アルゴリズム(VQAA)を提案する。
VQAAでは、既知の暗号文は、正規グラフを通して構築されるハミルトンの基底状態として符号化される。
論文 参考訳（メタデータ） (2022-05-07T03:15:15Z) - 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) - Error mitigation and quantum-assisted simulation in the error corrected
regime [77.34726150561087]
量子コンピューティングの標準的なアプローチは、古典的にシミュレート可能なフォールトトレラントな演算セットを促進するという考え方に基づいている。
量子回路の古典的準確率シミュレーションをどのように促進するかを示す。
論文 参考訳（メタデータ） (2021-03-12T20:58:41Z) - On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs
of Sequential Work [10.43571631715192]
我々は、量子ランダムオラクルモデル(QROM)における量子アルゴリズムの分析のために、Zhandryによって導入されたいわゆる圧縮オラクル手法を再考する。
我々の主な技術的貢献は、クエリ複雑性の結果を証明するために圧縮されたオラクル技法の並列クエリの一般化を単純化するフレームワークである。
本手法の具体的な暗号的応用として,Cohen と Pietrzak が提唱した "Simple Proofs of Sequential Work" が量子攻撃に対して安全であることを示す。
論文 参考訳（メタデータ） (2020-10-22T12:44:08Z) - Post-Quantum Multi-Party Computation [32.75732860329838]
我々は、悪質な時間量子敵に対するセキュリティを備えた古典的機能(平易なモデル)のマルチパーティ計算について研究する。
誤差付き学習における超ポリノミカル量子硬度(LWE)とLWEに基づく円形セキュリティ仮定の量子硬度を仮定する。
その過程で、私たちは独立した関心を持つ可能性のある暗号プリミティブを開発します。
論文 参考訳（メタデータ） (2020-05-23T00:42:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。