論文の概要: Post-Quantum Security of the Even-Mansour Cipher

• arxiv url: http://arxiv.org/abs/2112.07530v1
• Date: Tue, 14 Dec 2021 16:43:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-04 14:14:19.033981
• Title: Post-Quantum Security of the Even-Mansour Cipher
• Title（参考訳）: 偶数マンソル暗号の量子後セキュリティ
• Authors: Gorjan Alagic and Chen Bai and Jonathan Katz and Christian Majenz
• Abstract要約: Even-Mansour暗号は古典的な攻撃に対して安全である。 偶数マンスールは、自然の「後量子」環境でも安全であることが証明できる。
• 参考スコア（独自算出の注目度）: 14.141778162933013
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation $E$ from a public random permutation~$P:\{0,1\}^n \rightarrow \{0,1\}^n$. It is secure against classical attacks, with optimal attacks requiring $q_E$ queries to $E$ and $q_P$ queries to $P$ such that $q_E \cdot q_P \approx 2^n$. If the attacker is given \emph{quantum} access to both $E$ and $P$, however, the cipher is completely insecure, with attacks using $q_E, q_P = O(n)$ queries known. In any plausible real-world setting, however, a quantum attacker would have only \emph{classical} access to the keyed permutation~$E$ implemented by honest parties, even while retaining quantum access to~$P$. Attacks in this setting with $q_E \cdot q_P^2 \approx 2^n$ are known, showing that security degrades as compared to the purely classical case, but leaving open the question as to whether the Even-Mansour cipher can still be proven secure in this natural, "post-quantum" setting. We resolve this question, showing that any attack in that setting requires $q_E \cdot q^2_P + q_P \cdot q_E^2 \approx 2^n$. Our results apply to both the two-key and single-key variants of Even-Mansour. Along the way, we establish several generalizations of results from prior work on quantum-query lower bounds that may be of independent interest.
• Abstract（参考訳）: Even-Mansour暗号は、公開乱数置換~$P:\{0,1\}^n \rightarrow \{0,1\}^n$から(鍵付き)擬似乱数置換$E$を構成する単純な方法である。 古典的な攻撃に対して安全であり、$q_E$クエリを$E$に、$q_P$クエリを$P$に、$q_E \cdot q_P \approx 2^n$に、最適な攻撃である。 しかし、攻撃者が$E$と$P$の両方へのアクセスを許可された場合、暗号は完全に安全ではなく、$q_E, q_P = O(n)$クエリを攻撃している。 しかし、任意の有望な実世界設定では、量子攻撃者は、—$P$への量子アクセスを維持しながら、正直な関係者によって実装されたキー付き置換~$E$にのみアクセスする。 q_E \cdot q_P^2 \approx 2^n$ による攻撃は知られており、セキュリティが純粋に古典的なケースに比べて劣化することを示しているが、この自然の「ポスト量子」設定では、偶数マンソル暗号が依然として安全かどうかという疑問は残る。 この問題は、$q_E \cdot q^2_P + q_P \cdot q_E^2 \approx 2^n$である。 この結果は、Even-Mansourの2鍵変種とシングルキー変種の両方に適用できる。 その過程で、独立な関心を持つかもしれない量子待ち行列の下界に関する先行研究の結果のいくつかの一般化を確立する。

関連論文リスト

• Towards Unconditional Uncloneable Encryption [1.18749525824656]
  Uncloneablecryptは、古典的なメッセージを量子暗号文に暗号化する暗号化プリミティブである。 関連するセキュリティゲームにおける敵の成功確率は、キー数を表す$K$が1/2+1/ (2sqrtK)$に2次収束し、1/2$は自明に達成可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-30T14:40:06Z)
• Pseudorandom Permutations from Random Reversible Circuits [1.9567015559455132]
  固定された最寄りのアーキテクチャにおいて,各層が$approx n/3$のランダムゲートからなる深さ$n cdot tildeO(k2)$のランダム回路がほぼ$k$の独立な置換をもたらすことを示す。 また、擬似乱数関数からの擬似乱数置換のLuby-Rack-off構成は可逆回路で実装可能であることを示す。
  論文  参考訳（メタデータ） (2024-04-23T00:50:57Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。 次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
  論文  参考訳（メタデータ） (2023-11-07T04:59:02Z)
• Pseudorandom Isometries [6.0709446838151715]
  我々は$cal Q$-secure pseudorandom isometries (PRI)という新しい概念を導入する。 PRIは、$n$-qubit状態を$(n+m)$-qubit状態にマッピングする効率的な量子回路である。 我々は、量子擬似ランダム性の概念に対する長さ拡張定理を含む、PRIの多くの暗号的応用を実証する。
  論文  参考訳（メタデータ） (2023-11-06T06:27:14Z)
• Quantum forgery attacks against OTR structures based on Simon's algorithm [3.845166861382186]
  Simon のアルゴリズムを用いた OTR 構造に対する量子偽造攻撃を提案する。 OTR構造の変種(Pr/ost-OTR-Even-Mansour構造)を提案する。 攻撃者がその中の1つのブロックを変更することを許された場合、任意のメッセージの正しいタグを生成するのは容易である。
  論文  参考訳（メタデータ） (2023-10-01T15:16:43Z)
• Quantum security of subset cover problems [1.4072904523937533]
  多くのハッシュベースのシグネチャスキームのセキュリティは、サブセットカバー問題やこの問題の変種に依存する。 我々は、任意の量子アルゴリズムが、基礎となるハッシュ関数に対する$Omegaleft(k+1)-frac2k+1-1cdot Nfrac2k-12k+1-1right)$クエリを作成する必要があることを証明した。 また、一般的な$(r,k)$-subsetカバー問題のセキュリティも解析する。
  論文  参考訳（メタデータ） (2022-10-27T12:58:27Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• 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)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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