論文の概要: Quantum Sieving for Code-Based Cryptanalysis and Its Limitations for ISD
- arxiv url: http://arxiv.org/abs/2408.16458v2
- Date: Tue, 24 Dec 2024 12:20:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-25 15:52:57.857705
- Title: Quantum Sieving for Code-Based Cryptanalysis and Its Limitations for ISD
- Title（参考訳）: コードに基づくクリプトアナリシスのための量子シービングとISDの限界
- Authors: Lynn Engelberts, Simona Etinski, Johanna Loyer,
- Abstract要約: 上述したサブルーチンの量子変種を設計することで、コードシービングのための最初の量子アルゴリズムを導入する。
我々の量子ウォークアルゴリズムは、局所性に敏感なフィルタリング層を追加することにより、基礎となる探索問題の構造を利用する。
我々の分析は、このフレームワークが量子IDDアルゴリズムの最先端性を上回るように適応されるべきであることを強調している。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Sieving using near-neighbor search techniques is a well-known method in lattice-based cryptanalysis, yielding the current best runtime for the shortest vector problem in both the classical [BDGL16] and quantum [BCSS23] setting. Recently, sieving has also become an important tool in code-based cryptanalysis. Specifically, using a sieving subroutine, [GJN23, DEEK24] presented a variant of the information-set decoding (ISD) framework, which is commonly used for attacking cryptographically relevant instances of the decoding problem. The resulting sieving-based ISD framework yields complexities close to the best-performing classical algorithms for the decoding problem such as [BJMM12, BM18]. It is therefore natural to ask how well quantum versions perform. In this work, we introduce the first quantum algorithms for code sieving by designing quantum variants of the aforementioned sieving subroutine. In particular, using quantum-walk techniques, we provide a speed-up over the best known classical algorithm from [DEEK24] and over a variant using Grover's algorithm [Gro96]. Our quantum-walk algorithm exploits the structure of the underlying search problem by adding a layer of locality-sensitive filtering, inspired by the quantum-walk algorithm for lattice sieving from [CL21]. We complement our asymptotic analysis of the quantum algorithms with numerical results, and observe that our quantum speed-ups for code sieving behave similarly as those observed in lattice sieving. In addition, we show that a natural quantum analog of the sieving-based ISD framework does not provide any speed-up over the first presented quantum ISD algorithm [Ber10]. Our analysis highlights that the framework should be adapted in order to outperform the state-of-the-art of quantum ISD algorithms [KT17, Kir18].
- Abstract（参考訳）: BDGL16] と量子 [BCSS23] の両方の設定において、最も短いベクトル問題に対して、現在の最適なランタイムが得られる。
近年、シービングはコードベースの暗号解析において重要なツールとなっている。
具体的には,[GJN23, DEEK24] は,暗号的に関連する復号問題を攻撃するためによく用いられる情報集合復号(ISD)フレームワークの変種を示した。
その結果,[BJMM12, BM18] などの復号化問題に対して,最も高性能な古典的アルゴリズムに近い複雑性が得られた。
したがって、量子バージョンの性能を問うのは自然である。
本研究では、上記のサブルーチンの量子変種を設計し、コードシービングのための最初の量子アルゴリズムを紹介する。
特に、量子ウォーク法を用いて、Groverのアルゴリズム [Gro96] を用いて、[DEEK24] および変種から最もよく知られた古典的アルゴリズムを高速化する。
我々の量子ウォークアルゴリズムは,[CL21]から得られる格子を探索するための量子ウォークアルゴリズムに着想を得て,局所性に敏感なフィルタリング層を付加することにより,基礎となる探索問題の構造を利用する。
我々は、量子アルゴリズムの漸近解析と数値計算結果を補完し、コードシービングのための量子スピードアップが格子シービングで観測されたものと同様に振る舞うことを観察する。
さらに,Sieving-based ISD framework の自然量子アナログは,最初の量子 ISD アルゴリズム [Ber10] の高速化を提供していないことを示す。
我々の分析は、このフレームワークが量子ICDアルゴリズム(KT17, Kir18]の最先端技術を上回るように適応されるべきであることを強調している。
関連論文リスト
- Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
本研究は、4つの異なる最適化問題にまたがっていくつかの非フォールト耐性量子コンピューティングアルゴリズムを体系的にベンチマークする。
我々のベンチマークには、変分量子固有解法など、ノイズの多い中間スケール量子(NISQ)アルゴリズムが含まれている。
以上の結果から,FTQC以外のアルゴリズムは全ての問題に対して最適に動作しないことが明らかとなり,アルゴリズム戦略の調整の必要性が浮き彫りになった。
論文 参考訳（メタデータ） (2024-10-30T08:41:29Z) - Quantum superposing algorithm for quantum encoding [5.484168968324708]
本稿では,その有効性と優れた計算性能を実証する,効率的な量子スーパーポーシングアルゴリズムを提案する。
特に、我々のアルゴリズムは最大2n-3制御ノット数(CNOT)を持ち、これまでで最も最適化された結果を示している。
論文 参考訳（メタデータ） (2024-09-29T00:49:21Z) - The Algorithm for Solving Quantum Linear Systems of Equations With Coherent Superposition and Its Extended Applications [8.8400072344375]
コヒーレント重ね合わせを持つ方程式の量子線型系を解くための2つの量子アルゴリズムを提案する。
2つの量子アルゴリズムは、ランクと一般解の両方を1つの測定で計算できる。
分析の結果,提案アルゴリズムは主に軽量対称暗号に対する攻撃に適していることがわかった。
論文 参考訳（メタデータ） (2024-05-11T03:03:14Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Quantum Bayesian Optimization [64.58749619145908]
本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。
O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。
線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
論文 参考訳（メタデータ） (2023-10-09T03:10:42Z) - Iterative Quantum Algorithms for Maximum Independent Set: A Tale of
Low-Depth Quantum Algorithms [0.0]
我々は、反復最大量子アルゴリズム(Iterative Maximum Quantum Algorithms)と呼ばれる、量子最適化のための新しいハイブリッドアプローチのクラスについて研究する。
深度$p=1$のQAOAの場合、このアルゴリズムはMISの古典的欲求アルゴリズムと全く同じ操作と選択を行う。
論文 参考訳（メタデータ） (2023-09-22T18:00:03Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - Quantum Speedup for Higher-Order Unconstrained Binary Optimization and
MIMO Maximum Likelihood Detection [2.5272389610447856]
実数値の高次非制約二項最適化問題をサポートする量子アルゴリズムを提案する。
提案アルゴリズムは,古典的領域におけるクエリの複雑さを低減し,量子領域における2次高速化を実現する。
論文 参考訳（メタデータ） (2022-05-31T00:14:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。