論文の概要: Quantum Attacks without Superposition Queries: the Offline Simon's
Algorithm
- arxiv url: http://arxiv.org/abs/2002.12439v1
- Date: Thu, 27 Feb 2020 21:05:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-01 12:17:30.443383
- Title: Quantum Attacks without Superposition Queries: the Offline Simon's
Algorithm
- Title（参考訳）: スーパーポジションクエリなしの量子攻撃:オフラインSimonのアルゴリズム
- Authors: Xavier Bonnetain, Akinori Hosoyamada, Mar\'ia Naya-Plasencia, Yu
Sasaki, and Andr\'e Schrottenloher
- Abstract要約: 我々はサイモンのサブルーチンを新しい方法で利用する新しい量子アルゴリズムを導入する。
現状の文献に関して量子時間/古典データのトレードオフを改善した。
我々はデータの複雑さを減らし、過去の重ね合わせ攻撃を改善した。
- 参考スコア（独自算出の注目度）: 7.819565615098435
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In symmetric cryptanalysis, the model of superposition queries has led to
surprising results, with many constructions being broken in polynomial time
thanks to Simon's period-finding algorithm. But the practical implications of
these attacks remain blurry. In contrast, the results obtained so far for a
quantum adversary making classical queries only are less impressive. In this
paper, we introduce a new quantum algorithm which uses Simon's subroutines in a
novel way. We manage to leverage the algebraic structure of cryptosystems in
the context of a quantum attacker limited to classical queries and offline
quantum computations. We obtain improved quantum-time/classical-data tradeoffs
with respect to the current literature, while using only as much hardware
requirements (quantum and classical) as a standard exhaustive search with
Grover's algorithm. In particular, we are able to break the Even-Mansour
construction in quantum time $\tilde{O}(2^{n/3})$, with $O(2^{n/3})$ classical
queries and $O(n^2)$ qubits only. In addition, we improve some previous
superposition attacks by reducing the data complexity from exponential to
polynomial, with the same time complexity. Our approach can be seen in two
complementary ways: \emph{reusing} superposition queries during the iteration
of a search using Grover's algorithm, or alternatively, removing the memory
requirement in some quantum attacks based on a collision search, thanks to
their algebraic structure. We provide a list of cryptographic applications,
including the Even-Mansour construction, the FX construction, some Sponge
authenticated modes of encryption, and many more.
- Abstract（参考訳）: 対称暗号解析では、重ね合わせクエリのモデルが驚くべき結果をもたらし、サイモンの周期探索アルゴリズムのおかげで多くの構成が多項式時間で破られた。
しかし、これらの攻撃の実際的な意味はあいまいである。
対照的に、古典的クエリのみを作る量子敵に対するこれまでの結果はあまり印象的ではない。
本稿では,Simonのサブルーチンを新しい方法で利用した新しい量子アルゴリズムを提案する。
我々は、古典的なクエリやオフラインの量子計算に限られる量子攻撃者の文脈で、暗号システムの代数構造をうまく活用する。
我々は、グロバーのアルゴリズムを用いた標準徹底探索として、ハードウェア要件(量子および古典)を同程度だけ使用しながら、現在の文献に関する量子時間/古典データトレードオフを改善した。
特に、量子時間 $\tilde{O}(2^{n/3})$, $O(2^{n/3})$ 古典的クエリと$O(n^2)$ qubits で偶数マンソルの構成を破ることができる。
さらに、指数関数から多項式へのデータ複雑性を同時に減少させることにより、過去の重ね合わせ攻撃を改善する。
グロバーのアルゴリズムを用いた探索の反復中、あるいは、その代数的構造により、衝突探索に基づくいくつかの量子攻撃におけるメモリ要求の除去である。
我々は、均等な構成、fx構成、いくつかのスポンジ認証された暗号化モードなどを含む暗号アプリケーションのリストを提供する。
関連論文リスト
- Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
近年の分離により、階層構造が崩壊しても持続する硬さの源から量子暗号を構築する可能性が高まっている。
量子暗号は、$mathsfP#P notsubseteq mathsf(io)BQP/qpoly$という非常に穏やかな仮定に基づいている。
論文 参考訳（メタデータ） (2024-09-23T17:45:33Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - Grover's oracle for the Shortest Vector Problem and its application in
hybrid classical-quantum solvers [0.38366697175402226]
格子内の最短ベクトルを見つけることは、古典コンピュータと量子コンピュータの両方にとって困難であると考えられている問題である。
SVPのための最も優れた古典的、量子的、あるいはハイブリッドな古典量子アルゴリズムを見つけるためには、十分なセキュリティレベルを提供する暗号系パラメータを選択する必要がある。
グロバーの探索量子アルゴリズムは、一般的な二次的なスピードアップを提供する。
我々はGroverの小さなSVPインスタンスの量子探索と最先端の古典的解法を組み合わせる方法について分析する。
論文 参考訳（メタデータ） (2024-02-21T16:05:49Z) - Opening the Black Box Inside Grover's Algorithm [0.0]
グロバーのアルゴリズムは、量子コンピュータが古典的コンピュータよりも有利であることを示す主要なアルゴリズムである。
我々は,古典的コンピュータ上で動作可能な量子インスパイアされたアルゴリズムを構築し,Groverのタスクを,オラクルへの(シミュレーションの)呼び出し数で線形に実行する。
論文 参考訳（メタデータ） (2023-03-20T17:56:20Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - The NISQ Complexity of Collision Finding [2.9405711598281536]
現代の暗号における基本的なプリミティブである衝突耐性ハッシュは、同じハッシュ値を生成する入力を効率的に見つける方法がないことを保証している。
現在、量子敵はNISQのパワーを備えたフルスケールのコンピュータを必要とする。
本稿では, NISQアルゴリズムの3つの異なるモデルについて検討する。
論文 参考訳（メタデータ） (2022-11-23T13:55:28Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
古典的AES様対称暗号のための変分量子攻撃アルゴリズム(VQAA)を提案する。
VQAAでは、既知の暗号文は、正規グラフを通して構築されるハミルトンの基底状態として符号化される。
論文 参考訳（メタデータ） (2022-05-07T03:15:15Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - Hardware Efficient Quantum Search Algorithm [17.74233101199813]
本稿では,この課題を克服するために,ハードウェアの効率的な量子探索アルゴリズムを提案する。
我々の鍵となる考え方は、グローバル拡散操作を低コストな局所拡散に置き換えることである。
回路コストの削減は、システムの成功率を著しく向上させる。
論文 参考訳（メタデータ） (2021-03-26T01:08:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。