論文の概要: Lattice sieving via quantum random walks

• arxiv url: http://arxiv.org/abs/2105.05608v1
• Date: Wed, 12 May 2021 11:59:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-31 08:52:14.311491
• Title: Lattice sieving via quantum random walks
• Title（参考訳）: 量子ランダムウォークによる格子シービング
• Authors: Andr\'e Chailloux and Johanna Loyer
• Abstract要約: 格子ベースの暗号は、量子後暗号の主要な提案の一つである。 最短ベクトル問題(SVP)は、格子ベースの暗号の暗号解析において最も重要な問題である。 我々は、$d$が格子次元であるような20.2570 d + o(d)$のランニング時間を持つアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Lattice-based cryptography is one of the leading proposals for post-quantum cryptography. The Shortest Vector Problem (SVP) is arguably the most important problem for the cryptanalysis of lattice-based cryptography, and many lattice-based schemes have security claims based on its hardness. The best quantum algorithm for the SVP is due to Laarhoven [Laa16 PhD] and runs in (heuristic) time $2^{0.2653d + o(d)}$. In this article, we present an improvement over Laarhoven's result and present an algorithm that has a (heuristic) running time of $2^{0.2570 d + o(d)}$ where $d$ is the lattice dimension. We also present time-memory trade-offs where we quantify the amount of quantum memory and quantum random access memory of our algorithm. The core idea is to replace Grover's algorithm used in [Laa16 PhD] in a key part of the sieving algorithm by a quantum random walk in which we add a layer of local sensitive filtering.
• Abstract（参考訳）: 格子ベースの暗号は量子後暗号の主要な提案の一つである。 最短ベクトル問題(SVP)は、格子ベースの暗号の暗号解析において最も重要な問題であり、格子ベースの多くのスキームはその硬さに基づいてセキュリティクレームを有する。 SVP にとって最高の量子アルゴリズムは Laarhoven [Laa16 PhD] によるもので、(ヒューリスティックな)時間 2^{0.2653d + o(d)}$ で実行される。 本稿では,ラールホーフェンの結果に対する改善について述べるとともに,$d$が格子次元である場合の2^{0.2570 d + o(d)}$のランニング時間を持つアルゴリズムを提案する。 また、我々のアルゴリズムの量子メモリと量子ランダムアクセスメモリの量を定量化する時間メモリトレードオフも提示する。 中心となる考え方は、[Laa16 PhD]で用いられるGroverのアルゴリズムを、局所的な感度フィルタリングの層を追加する量子ランダムウォークによって、シービングアルゴリズムの重要な部分で置き換えることである。

関連論文リスト

• On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
  格子ベースの暗号は、量子後暗号の主要な候補の1つである。 量子攻撃に対する暗号セキュリティは、最短ベクトル問題(SVP)のような格子問題に基づいている SVPを解くための漸近的な量子スピードアップはGroverの探索に依存している。
  論文  参考訳（メタデータ） (2024-10-17T16:54:41Z)
• Quantum Sieving for Code-Based Cryptanalysis and Its Limitations for ISD [0.0]
  上述したサブルーチンの量子変種を設計することで、コードシービングのための最初の量子アルゴリズムを導入する。 我々の量子ウォークアルゴリズムは、局所性に敏感なフィルタリング層を追加することにより、基礎となる探索問題の構造を利用する。 我々の分析は、このフレームワークが量子IDDアルゴリズムの最先端性を上回るように適応されるべきであることを強調している。
  論文  参考訳（メタデータ） (2024-08-29T11:47:33Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。 次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
  論文  参考訳（メタデータ） (2023-11-07T04:59:02Z)
• Finding dense sub-lattices as low-energy states of a Hamiltonian [1.2183430883527995]
  格子ベースの暗号は、量子後暗号の最も顕著な候補の1つである。 最短ベクトル問題(SVP)は、与えられた格子の中で最短の非ゼロベクトルを見つけることである。 我々は、与えられた格子の最も密度の高い$K$-Densest Sub-lattice(K$-DSP)を求めるために、$K$-Densest Sub-lattice Problem(K$-DSP)として知られるSVPの自然な一般化を研究する。
  論文  参考訳（メタデータ） (2023-09-28T08:48:38Z)
• Homomorphic Encryption of the k=2 Bernstein-Vazirani Algorithm [0.4511923587827301]
  代入量子計算に有用な重要な暗号技術である量子同相暗号(QHE)へのこのスキームの適用を見出した。 我々は,完全セキュリティ,$mathcalF$-homomorphism,サーバとクライアント間の相互作用のないQHEスキームを開発し,Mが回路内のゲート数$T$である場合,$O(M)$で束縛された準コンパクト性を示す。
  論文  参考訳（メタデータ） (2023-03-30T14:49:15Z)
• Distributed exact quantum algorithms for Bernstein-Vazirani and search problems [9.146620606615889]
  我々は、$t$の計算ノードを持つ分散Bernstein-Vaziraniアルゴリズム(DBVA)と、未順序データベースの1つのターゲット項目で探索問題を解決する分散型Grover'sアルゴリズム(DEGA)を提供する。 我々は、MindQuantum(量子ソフトウェア)上でDBVAとDEGAの状況を提供し、我々の手法の正確性と実践性を検証する。
  論文  参考訳（メタデータ） (2023-03-19T14:18:49Z)
• 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)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。 本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
  論文  参考訳（メタデータ） (2021-06-11T09:43:09Z)
• 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)

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

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