論文の概要: On the practicality of quantum sieving algorithms for the shortest vector problem
- arxiv url: http://arxiv.org/abs/2410.13759v1
- Date: Thu, 17 Oct 2024 16:54:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-18 13:19:57.854588
- Title: On the practicality of quantum sieving algorithms for the shortest vector problem
- Title（参考訳）: 最短ベクトル問題に対する量子シービングアルゴリズムの実用性について
- Authors: Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia,
- Abstract要約: 格子ベースの暗号は、量子後暗号の主要な候補の1つである。
量子攻撃に対する暗号セキュリティは、最短ベクトル問題(SVP)のような格子問題に基づいている
SVPを解くための漸近的な量子スピードアップはGroverの探索に依存している。
- 参考スコア（独自算出の注目度）: 42.70026220176376
- License:
- Abstract: One of the main candidates of post-quantum cryptography is lattice-based cryptography. Its cryptographic security against quantum attackers is based on the worst-case hardness of lattice problems like the shortest vector problem (SVP), which asks to find the shortest non-zero vector in an integer lattice. Asymptotic quantum speedups for solving SVP are known and rely on Grover's search. However, to assess the security of lattice-based cryptography against these Grover-like quantum speedups, it is necessary to carry out a precise resource estimation beyond asymptotic scalings. In this work, we perform a careful analysis on the resources required to implement several sieving algorithms aided by Grover's search for dimensions of cryptographic interests. For such, we take into account fixed-point quantum arithmetic operations, non-asymptotic Grover's search, the cost of using quantum random access memory (QRAM), different physical architectures, and quantum error correction. We find that even under very optimistic assumptions like circuit-level noise of $10^{-5}$, code cycles of 100 ns, reaction time of 1 $\mu$s, and using state-of-the-art arithmetic circuits and quantum error-correction protocols, the best sieving algorithms require $\approx 10^{13}$ physical qubits and $\approx 10^{31}$ years to solve SVP on a lattice of dimension 400, which is roughly the dimension for minimally secure post-quantum cryptographic standards currently being proposed by NIST. We estimate that a 6-GHz-clock-rate single-core classical computer would take roughly the same amount of time to solve the same problem. We conclude that there is currently little to no quantum speedup in the dimensions of cryptographic interest and the possibility of realising a considerable quantum speedup using quantum sieving algorithms would require significant breakthroughs in theoretical protocols and hardware development.
- Abstract（参考訳）: 量子後暗号の主な候補の1つは格子ベースの暗号である。
量子攻撃者に対する暗号的セキュリティは、最短ベクトル問題(SVP)のような格子問題の最悪の難しさに基づいている。
SVPを解くための漸近的な量子スピードアップはGroverの探索に依存している。
しかし,これらのグローバー型量子スピードアップに対する格子ベースの暗号の安全性を評価するためには,漸近的スケーリングを超えて正確な資源推定を行う必要がある。
本研究では,Groverの暗号的関心事の次元探索によって支援されたいくつかのシーヴィングアルゴリズムを実装するために必要なリソースについて,慎重に分析する。
そのため、固定点量子演算、非漸近グロバー探索、量子ランダムアクセスメモリ(QRAM)の使用コスト、異なる物理アーキテクチャ、量子エラー補正を考慮する。
10^{-5}$の回路レベルのノイズ、100 nsのコードサイクル、1$\mu$sの反応時間、最先端の演算回路と量子エラー補正プロトコルなど、非常に楽観的な仮定の下でも、最良のシービングアルゴリズムは$\approx 10^{13}$物理量子ビットと$\approx 10^{31}$のSVPを400の格子上で解くのに何年もかかる。
6GHz帯のシングルコアコンピュータでは,同じ問題を解くのにほぼ同じ時間を要すると推定した。
我々は、現在、暗号的関心の次元において量子スピードアップはほとんど、あるいは全く存在しないと結論し、量子シービングアルゴリズムを用いて相当な量子スピードアップを実現するには、理論的なプロトコルやハードウェア開発において大きなブレークスルーが必要であると結論付けた。
関連論文リスト
- 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) - Variational Quantum Search with Shallow Depth for Unstructured Database
Search [0.0]
変分量子探索(VQS)は、変分量子アルゴリズムとパラメータ化量子回路に基づく新しいアルゴリズムである。
深さ10アンザッツは、$n$+1量子ビットで表される2n$要素のうち、$k$の総確率を増幅できることを示す。
我々は,VQSの深さ56回路がGroverのアルゴリズムの深さ270,989回路を置き換えることを実証した。
論文 参考訳（メタデータ） (2022-12-16T17:16:54Z) - 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) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Iterative Qubits Management for Quantum Index Searching in a Hybrid
System [56.39703478198019]
IQuCSは、量子古典ハイブリッドシステムにおけるインデックス検索とカウントを目的としている。
我々はQiskitでIQuCSを実装し、集中的な実験を行う。
その結果、量子ビットの消費を最大66.2%削減できることが示されている。
論文 参考訳（メタデータ） (2022-09-22T21:54:28Z) - 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) - Lattice sieving via quantum random walks [0.0]
格子ベースの暗号は、量子後暗号の主要な提案の一つである。
最短ベクトル問題(SVP)は、格子ベースの暗号の暗号解析において最も重要な問題である。
我々は、$d$が格子次元であるような20.2570 d + o(d)$のランニング時間を持つアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-12T11:59:30Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。