論文の概要: Super-Quadratic Quantum Speed-ups and Guessing Many Likely Keys

• arxiv url: http://arxiv.org/abs/2509.06549v1
• Date: Mon, 08 Sep 2025 11:03:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-09 14:07:04.078777
• Title: Super-Quadratic Quantum Speed-ups and Guessing Many Likely Keys
• Title（参考訳）: 超量子量子スピードアップと多くの類似キーの誘導
• Authors: Timo Glaser, Alexander May, Julian Nowakowski,
• Abstract要約: 暗号鍵を推測する根本的な問題について検討する。 マルチキー設定では、キーごとの推算コストはシングルキー設定よりもかなり小さいことがわかった。
• 参考スコア（独自算出の注目度）: 43.5605535402594
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the fundamental problem of guessing cryptographic keys, drawn from some non-uniform probability distribution $D$, as e.g. in LPN, LWE or for passwords. The optimal classical algorithm enumerates keys in decreasing order of likelihood. The optimal quantum algorithm, due to Montanaro (2011), is a sophisticated Grover search. We give the first tight analysis for Montanaro's algorithm, showing that its runtime is $2^{H_{2/3}(D)/2}$, where $H_{\alpha}(\cdot)$ denotes Renyi entropy with parameter $\alpha$. Interestingly, this is a direct consequence of an information theoretic result called Arikan's Inequality (1996) -- which has so far been missed in the cryptographic community -- that tightly bounds the runtime of classical key guessing by $2^{H_{1/2}(D)}$. Since $H_{2/3}(D) < H_{1/2}(D)$ for every non-uniform distribution $D$, we thus obtain a super-quadratic quantum speed-up $s>2$ over classical key guessing. As another main result, we provide the first thorough analysis of guessing in a multi-key setting. Specifically, we consider the task of attacking many keys sampled independently from some distribution $D$, and aim to guess a fraction of them. For product distributions $D = \chi^n$, we show that any constant fraction of keys can be guessed within $2^{H(D)}$ classically and $2 ^{H(D)/2}$ quantumly per key, where $H(\chi)$ denotes Shannon entropy. In contrast, Arikan's Inequality implies that guessing a single key costs $2^{H_{1/2}(D)}$ classically and $2^{H_{2/3}(D)/2}$ quantumly. Since $H(D) < H_{2/3}(D) < H_{1/2}(D)$, this shows that in a multi-key setting the guessing cost per key is substantially smaller than in a single-key setting, both classically and quantumly.
• Abstract（参考訳）: 我々は、LPN、LWE、パスワードのegとして、不均一な確率分布$D$から引き出された暗号鍵を推測する根本的な問題について検討する。 最適化された古典的アルゴリズムは、可能性の順序の減少で鍵を列挙する。 Montanaro (2011) による最適量子アルゴリズムは、洗練されたグロバー探索である。 モンタナロのアルゴリズムの最初の厳密な解析を行い、その実行時間は$2^{H_{2/3}(D)/2}$であり、$H_{\alpha}(\cdot)$はパラメータ$\alpha$でRenyiエントロピーを表す。 興味深いことに、これはArikan's Inequality (1996) と呼ばれる情報理論結果の直接的な結果であり、暗号コミュニティでは見逃されている。 H_{2/3}(D) < H_{1/2}(D)$ はすべての非一様分布に対して$D$ であるから、古典的な鍵推定よりも超四進量子スピードアップ $s>2$ が得られる。 もう一つの主要な結果として、マルチキー設定における推測の最初の徹底的な解析を提供する。 具体的には、いくつかのディストリビューションから独立してサンプリングされた多数のキーを攻撃し、その一部を推測するタスクについて検討する。 積分布について、$D = \chi^n$ に対して、古典的には $2^{H(D)} と $2 ^{H(D)/2} の範囲内において、任意の一定数の鍵を推測できることを示し、$H(\chi)$ はシャノンエントロピーを表す。 対照的に、有観の不等式は、一つの鍵を推測するのに古典的に$2^{H_{1/2}(D)} 、量子的に$2$2^{H_{2/3}(D)/2} がかかることを意味する。 H(D) < H_{2/3}(D) < H_{1/2}(D)$ であるから、マルチキー設定では、キー当たりの推測コストは古典的にも量子的にも、シングルキー設定よりもかなり小さい。

関連論文リスト

• Geometric Discord of any arbitrary dimensional bipartite system and its application in quantum key distribution [0.0]
  絡み合った量子状態は、量子鍵分布プロトコルにおける鍵資源と見なされる。 我々は、幾何量子不協和(GQD)として知られる量子相関のそのような尺度に焦点をあてる。 一定の範囲のGQDに対して、秘密鍵の生成が成功することは保証されない。
  論文  参考訳（メタデータ） (2025-09-05T08:46:24Z)
• Quantum Security Analysis of the Key-Alternating Ciphers [2.5383384004287937]
  キー交換暗号(KAC)の量子セキュリティについて検討する。 Q1$モデルのマルチラウンドKACに対する最初の非自明な量子鍵回収攻撃を与える。
  論文  参考訳（メタデータ） (2024-12-06T13:23:29Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。 次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
  論文  参考訳（メタデータ） (2023-11-07T04:59:02Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
  確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。 我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。 クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-25T15:32:37Z)
• Fast Rates for Maximum Entropy Exploration [52.946307632704645]
  エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。 本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。 訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。 軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-14T16:51:14Z)
• Post-Quantum Security of the Even-Mansour Cipher [14.141778162933013]
  Even-Mansour暗号は古典的な攻撃に対して安全である。 偶数マンスールは、自然の「後量子」環境でも安全であることが証明できる。
  論文  参考訳（メタデータ） (2021-12-14T16:43:34Z)
• The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
  量子回路 $C$ on $n$ qubits とサンプル $z in 0,1n$ のとき、ベンチマークは$|langle z|C|0n rangle|2$ の計算を伴う。 任意の $varepsilon ge frac1mathrmpoly(n)$ に対して、サンプル $z$ を出力することは、平均で $|langle z|C|0nrangle|2$ に対して最適な 1-クエリであることを示す。
  論文  参考訳（メタデータ） (2020-08-20T01:04:32Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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