論文の概要: Quantum Security Analysis of the Key-Alternating Ciphers

• arxiv url: http://arxiv.org/abs/2412.05026v2
• Date: Fri, 23 May 2025 20:27:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 14:32:53.005381
• Title: Quantum Security Analysis of the Key-Alternating Ciphers
• Title（参考訳）: キー交換暗号の量子セキュリティ解析
• Authors: Chen Bai, Mehdi Esmaili, Atul Mantri,
• Abstract要約: キー交換暗号(KAC)の量子セキュリティについて検討する。 Q1$モデルのマルチラウンドKACに対する最初の非自明な量子鍵回収攻撃を与える。
• 参考スコア（独自算出の注目度）: 2.5383384004287937
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we study the quantum security of key-alternating ciphers (KAC), a natural multi-round generalization of the Even-Mansour (EM) cipher underlying many block cipher constructions, including AES. While the classical security of KAC and the quantum security of the $1$-round KAC (i.e. Even-Mansour) cipher are well understood, the quantum resistance of multi-round KAC remains largely unexplored. We focus on the $2$-round KAC construction, defined using public $n$-bit permutations $P_1$, $P_2$ and keys $k_0$, $k_1$, and $k_2$ as $E(x) = P_2(P_1(x \oplus k_0) \oplus k_1) \oplus k_2$. Our main contributions are as follows: 1. Quantum Lower Bounds. We provide the first formal analysis showing that a $2$-round KAC is quantum-secure in both the $Q1$ and $Q2$ models. Specifically, in the $Q1$ model, a (non-adaptive) adversary must make at least $2^{2n/5}$ quantum queries to the public permutations and at least $2^{2n/5}$ classical queries to the cipher in order to distinguish it from a random permutation (in contrast to the classical lower bound of $2^{2n/3}$ queries). As a corollary, we show that in the $Q2$ model, a (non-adaptive) adversary requires $2^{n/4}$ quantum queries. To achieve such a result, we employ the quantum hybrid method along with recently proposed lifting theorems in the ideal cipher and random permutation oracle model. 2. Quantum Key-Recovery Attack. We give the first nontrivial quantum key-recovery attack on multi-round KAC in the $Q1$ model. Our quantum attack applies to any $t$-round KAC and achieves quantum query complexity $O(2^{\alpha n})$, where $\alpha = \frac{t(t+1)}{(t+1)^2 + 1}$, improving over the best known classical bound of $O(2^{\alpha' n})$, where $\alpha' = \frac{t}{t+1}$, from Bogdanov et al. (EUROCRYPT 2012). The attack leverages a novel application of quantum walk algorithms specifically adapted to the KAC structure.
• Abstract（参考訳）: 本研究では,鍵交換暗号 (KAC) の量子セキュリティについて検討する。これは,AESを含む多くのブロック暗号構造を基盤とした,Even-Mansour (EM) 暗号の自然な多ラウンド一般化である。 古典的なKACのセキュリティと1ドル単位のKAC暗号の量子セキュリティはよく理解されているが、マルチラウンドのKACの量子抵抗はほとんど探索されていない。 我々は、公開$n$-bit置換$P_1$, $P_2$とキー$k_0$, $k_1$, $k_2$ as $E(x) = P_2(P_1(x \oplus k_0) \oplus k_1 \oplus k_2$で定義される2ドルのKAC構成に焦点を当てる。 主な貢献は以下の通りである。 最初の公式解析では、$Q1$と$Q2$モデルの両方において、2ドル単位のKACが量子セキュアであることが示されている。 具体的には、Q1$モデルにおいて、(非適応的な)敵は、ランダムな置換と区別するために、公開置換に対する少なくとも2^{2n/5}$の量子クエリと、暗号に対する少なくとも2^{2n/5}$の古典的なクエリを、暗号に対する少なくとも2^{2n/3}$の量子クエリにしなければならない(古典的な2$2n/3の下位境界とは対照的に)。 結論として、$Q2$モデルでは、(非適応的な)逆元は2^{n/4}$量子クェリを必要とすることを示す。 このような結果を得るために、我々は最近提案された理想暗号およびランダム置換オラクルモデルにおける持ち上げ定理とともに量子ハイブリッド法を用いる。 量子鍵回収攻撃 Q1$モデルのマルチラウンドKACに対する最初の非自明な量子鍵回収攻撃を与える。 我々の量子攻撃は任意の$t$のKACに適用され、量子クエリの複雑さを$O(2^{\alpha n})$, $\alpha = \frac{t(t+1)}{(t+1)^2 + 1}$, $O(2^{\alpha' n})$, $\alpha' = \frac{t}{t+1}$, from Bogdanov et al (EUROCRYPT 2012)。 この攻撃は、KAC構造に特異的に適応した量子ウォークアルゴリズムの新たな応用を活用している。

関連論文リスト

• Towards Unconditional Uncloneable Encryption [1.18749525824656]
  Uncloneablecryptは、古典的なメッセージを量子暗号文に暗号化する暗号化プリミティブである。 関連するセキュリティゲームにおける敵の成功確率は、キー数を表す$K$が1/2+1/ (2sqrtK)$に2次収束し、1/2$は自明に達成可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-30T14:40:06Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。 次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
  論文  参考訳（メタデータ） (2023-11-07T04:59:02Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  古典的AES様対称暗号のための変分量子攻撃アルゴリズム(VQAA)を提案する。 VQAAでは、既知の暗号文は、正規グラフを通して構築されるハミルトンの基底状態として符号化される。
  論文  参考訳（メタデータ） (2022-05-07T03:15:15Z)
• Post-Quantum Security of the Even-Mansour Cipher [14.141778162933013]
  Even-Mansour暗号は古典的な攻撃に対して安全である。 偶数マンスールは、自然の「後量子」環境でも安全であることが証明できる。
  論文  参考訳（メタデータ） (2021-12-14T16:43:34Z)
• Beyond quadratic speedups in quantum attacks on symmetric schemes [30.01567358439495]
  我々は,古典的クエリのみを用いて,対称ブロック暗号設計に対する最初の量子鍵回復攻撃を報告した。 我々の攻撃は、いくつかの対称構造の構造をこの限界を克服するために利用することができることを示している。
  論文  参考訳（メタデータ） (2021-10-06T15:10:31Z)
• Efficient Quantum Public-Key Encryption From Learning With Errors [1.8021287677546958]
  我々の主な成果は、外挿二面コセット問題(EDCP)に基づく量子公開鍵暗号方式である。 公開鍵数に制限がある場合、提案方式は情報理論的に安全である。
  論文  参考訳（メタデータ） (2021-05-26T18:48:26Z)
• 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)
• 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)
• Succinct Blind Quantum Computation Using a Random Oracle [0.8702432681310399]
  我々は新しい普遍的な盲点量子計算プロトコルを提供する。 プロトコルの最初のフェーズは簡潔であり、その複雑さは回路サイズとは無関係である。
  論文  参考訳（メタデータ） (2020-04-27T07:47:11Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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