論文の概要: Security of Key-Alternating Ciphers: Quantum Lower Bounds and Quantum Walk Attacks
- arxiv url: http://arxiv.org/abs/2412.05026v3
- Date: Thu, 09 Oct 2025 18:14:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-14 04:53:46.698456
- Title: Security of Key-Alternating Ciphers: Quantum Lower Bounds and Quantum Walk Attacks
- Title（参考訳）: キー交換暗号のセキュリティ:量子下界と量子ウォーク攻撃
- Authors: Chen Bai, Mehdi Esmaili, Atul Mantri,
- Abstract要約: キー交換暗号(KAC)の量子セキュリティについて検討する。
我々は、Q1モデルとQ2モデルの両方において、非適応的敵に対する$t$ラウンドKACのセキュリティを証明する。
Q1 モデルで$t$-round KAC に対する最初の非自明な量子鍵復元アルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 5.221158079775365
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the quantum security of key-alternating ciphers (KAC), a natural multi-round generalization of the Even--Mansour construction. KAC abstracts the round structure of practical block ciphers as public permutations interleaved with key XORs. The $1$-round KAC or EM setting already highlights the power of quantum superposition access: EM is secure against classical and Q1 adversaries (quantum access to the public permutation), but insecure in the Q2 model. The security of multi-round KACs remain largely unexplored; in particular, whether the quantum-classical separation extends beyond a single round had remained open. 1) Quantum Lower Bounds. We prove security of the $t$-round KAC against a non-adaptive adversary in both the Q1 and Q2 models. In the Q1 model, any distinguiser requires $\Omega(2^{\frac{tn}{2t+1}})$ oracle queries to distinguish the cipher from a random permutation, whereas classically any distinguisher needs $\Omega(2^{\frac{tn}{t+1}})$ queries. As a corollary, we obtain a Q2 lower bound of $\Omega (2^{\frac{(t-1)n}{2t}})$ quantum queries. Thus, for $t \geq 2$, the exponential Q1-Q2 gap collapses in the non-adaptive setting, partially resolving an open problem posed by Kuwakado and Morii (2012). Our proofs develop a controlled-reprogramming framework within a quantum hybrid argument, sidestepping the lack of quantum recording techniques for permutation-based ciphers; we expect this framework to be useful for analyzing other post-quantum symmetric primitives. 2) Quantum Key-Recovery Attack. We give the first non-trivial quantum key-recovery algorithm for $t$-round KAC in the Q1 model. It makes $O(2^{\alpha n})$ queries with $\alpha = \frac{t(t+1)}{(t+1)^2 + 1}$, improving on the best known classical bound of $O(2^{\alpha' n})$ with $\alpha' = \frac{t}{t+1}$. The algorithm adapts quantum walk techniques to the KAC structure.
- Abstract（参考訳）: 本研究では, キー交換暗号(KAC)の量子セキュリティについて検討する。
KACは、鍵XORをインターリーブした公開置換として、実用的なブロック暗号の丸い構造を抽象化する。
EMは古典的およびQ1の敵(パブリックな置換への量子アクセス)に対して安全であるが、Q2モデルでは安全ではない。
マルチラウンド KAC のセキュリティは未解明のままであり、特に量子古典分離が単一ラウンドを超えて広がるかどうかは未定である。
1)量子下界
我々は、Q1モデルとQ2モデルの両方において、非適応的敵に対する$t$ラウンドKACのセキュリティを証明する。
Q1モデルでは、暗号とランダムな置換を区別するために、任意のディスチネンジャーは$\Omega(2^{\frac{tn}{2t+1}})$ Oracleクエリを必要とするが、古典的には$\Omega(2^{\frac{tn}{t+1}})$クエリが必要である。
結論として、Q2 は$\Omega (2^{\frac{(t-1)n}{2t}})$量子クェリである。
したがって、$t \geq 2$ の場合、指数 Q1-Q2 のギャップは非適応的な設定で崩壊し、クワカドと森井 (2012) によって生じる開問題を部分的に解決する。
量子ハイブリッドの議論において、置換型暗号の量子記録技術が欠如していることから、制御プログラミングの枠組みを構築し、この枠組みが量子後対称プリミティブの解析に有用であると期待する。
2)量子鍵回収攻撃。
Q1 モデルで$t$-round KAC に対する最初の非自明な量子鍵復元アルゴリズムを与える。
これは$O(2^{\alpha n})$クエリを$\alpha = \frac{t(t+1)}{(t+1)^2 + 1}$で作成し、$O(2^{\alpha' n})$を$\alpha' = \frac{t}{t+1}$で改善する。
このアルゴリズムは量子ウォーク法をKAC構造に適応させる。
関連論文リスト
- Quantum Key-Recovery Attacks on FBC Algorithm [2.2002244657481826]
本稿では,異なるクエリ機能を持つFBC量子敵の包括的セキュリティ解析について述べる。
FBC-KF/FK構造に対して、古典的なクエリと量子コンピューティング機能を持つ敵を考慮し、低データ量子鍵回復攻撃を実演する。
論文 参考訳（メタデータ） (2025-08-01T09:08:53Z) - Towards Unconditional Uncloneable Encryption [1.18749525824656]
Uncloneablecryptは、古典的なメッセージを量子暗号文に暗号化する暗号化プリミティブである。
関連するセキュリティゲームにおける敵の成功確率は、キー数を表す$K$が1/2+1/ (2sqrtK)$に2次収束し、1/2$は自明に達成可能であることを示す。
論文 参考訳（メタデータ） (2024-10-30T14:40:06Z) - Entanglement-assisted Quantum Error Correcting Code Saturating The Classical Singleton Bound [44.154181086513574]
量子誤り訂正符号 (EAQECCs) は, 従来のシングルトン境界を, frackn = frac13$以下のコードレートの既知の方法よりも少ない共有エンタングルメントで飽和させる。
古典的な $[n,k,d]_q$ のコードはパラメータ $[n,k,d;2k]]_q$ の EAQECC に変換できる。
論文 参考訳（メタデータ） (2024-10-05T11:56:15Z) - Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
実測値の最初の2Omega(n)$モーメントと無作為位相によるS(N)$置換の指数和が一致することを示す。
我々の証明の核心は、ランダム行列理論における大次元(大きな=N$)展開と方法の間の概念的接続である。
論文 参考訳（メタデータ） (2024-04-25T17:08:34Z) - 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) - Quantum Symmetric Private Information Retrieval with Secure Storage and
Eavesdroppers [32.97918488607827]
X$-secure,$E$-eavesdropped,$T$-colluding symmetric private information search (SPIR)の古典的および量子的変動について考察する。
まず,古典的な$X$-secure,$E$-eavesdropped,$T$-colluding SPIR (XSETSPIR) を,クロス部分空間アライメント (CSA) の修正版に基づいて開発する。
論文 参考訳（メタデータ） (2023-08-21T17:30:38Z) - A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
古典的AES様対称暗号のための変分量子攻撃アルゴリズム(VQAA)を提案する。
VQAAでは、既知の暗号文は、正規グラフを通して構築されるハミルトンの基底状態として符号化される。
論文 参考訳（メタデータ） (2022-05-07T03:15:15Z) - Speeding up Learning Quantum States through Group Equivariant
Convolutional Quantum Ans\"atze [13.651587339535961]
我々はSU$(d)$対称性を持つ畳み込み量子回路の枠組みを開発する。
我々は、$nameSU(d)$と$S_n$ irrepbasesの同値性に関するHarrowの主張を証明する。
論文 参考訳（メタデータ） (2021-12-14T18:03:43Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。