論文の概要: A Tight Quantum Algorithm for Multiple Collision Search

• arxiv url: http://arxiv.org/abs/2509.13909v1
• Date: Wed, 17 Sep 2025 11:15:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-18 18:41:50.832011
• Title: A Tight Quantum Algorithm for Multiple Collision Search
• Title（参考訳）: 多重衝突探索のためのタイト量子アルゴリズム
• Authors: Xavier Bonnetain, Johanna Loyer, André Schrottenloher, Yixin Shen,
• Abstract要約: ランダム関数における衝突の探索は、基本的な計算問題である。 残りの最適範囲に対処するアルゴリズムを新たに提供し,問題を解消する。 我々のアルゴリズムはクエリーにおいて(最大1要素まで)厳密であり、また量子RAMの仮定の下でも間に合う。
• 参考スコア（独自算出の注目度）: 4.913876853745498
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Searching for collisions in random functions is a fundamental computational problem, with many applications in symmetric and asymmetric cryptanalysis. When one searches for a single collision, the known quantum algorithms match the query lower bound. This is not the case for the problem of finding multiple collisions, despite its regular appearance as a sub-component in sieving-type algorithms. At EUROCRYPT 2019, Liu and Zhandry gave a query lower bound $\Omega(2^{m/3 + 2k/3})$ for finding $2^k$ collisions in a random function with m-bit output. At EUROCRYPT 2023, Bonnetain et al. gave a quantum algorithm matching this bound for a large range of $m$ and $k$, but not all admissible values. Like many previous collision-finding algorithms, theirs is based on the MNRS quantum walk framework, but it chains the walks by reusing the state after outputting a collision. In this paper, we give a new algorithm that tackles the remaining non-optimal range, closing the problem. Our algorithm is tight (up to a polynomial factor) in queries, and also in time under a quantum RAM assumption. The idea is to extend the chained walk to a regime in which several collisions are returned at each step, and the ``walks'' themselves only perform a single diffusion layer.
• Abstract（参考訳）: ランダム関数における衝突の探索は基本的な計算問題であり、対称および非対称な暗号解析における多くの応用がある。 単一の衝突を探索すると、既知の量子アルゴリズムはクエリの下位境界に一致する。 これは、シービング型アルゴリズムのサブコンポーネントとして定期的に現れるにもかかわらず、複数の衝突を見つけるという問題ではない。 EUROCRYPT 2019で、LiuとZhandryは、mビット出力を持つランダム関数で2^k$の衝突を見つけるために、$\Omega(2^{m/3 + 2k/3})のクエリを下げた。 EUROCRYPT 2023で、Bonnetainらは、この境界を広い範囲の$m$と$k$と一致する量子アルゴリズムを与えたが、全ての許容値ではない。 従来の衝突フィニングアルゴリズムと同様に、これらのアルゴリズムはMNRS量子ウォークフレームワークに基づいているが、衝突を発生させた後に状態を再利用することでウォークをチェーンする。 本稿では,残りの非最適範囲に対処し,問題を解消するアルゴリズムを提案する。 我々のアルゴリズムは、クエリーにおいて(多項式係数まで)厳密であり、また量子RAMの仮定の下でも間に合う。 この考え方は、チェーンされたウォークを各ステップでいくつかの衝突が返される体制に拡張し、`walks'自体が単一の拡散層のみを実行するというものである。

関連論文リスト

• Distributed quantum algorithm for divergence estimation and beyond [12.925989807145301]
  本稿では,$rm Tr(f(A)g(B))$を付加誤差$varepsilon$内で計算する分散量子アルゴリズムフレームワークを提案する。 このフレームワークは、様々な分散量子コンピューティングタスクに適用可能である。
  論文  参考訳（メタデータ） (2025-03-12T14:28:22Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。 次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
  論文  参考訳（メタデータ） (2023-11-07T04:59:02Z)
• The NISQ Complexity of Collision Finding [2.9405711598281536]
  現代の暗号における基本的なプリミティブである衝突耐性ハッシュは、同じハッシュ値を生成する入力を効率的に見つける方法がないことを保証している。 現在、量子敵はNISQのパワーを備えたフルスケールのコンピュータを必要とする。 本稿では, NISQアルゴリズムの3つの異なるモデルについて検討する。
  論文  参考訳（メタデータ） (2022-11-23T13:55:28Z)
• Optimal exact quantum algorithm for the promised element distinctness problem [0.2741266294612775]
  要素差分問題は、文字列$x=(x_1,ldots,x_N)$の$N$要素が同じ値の2つの要素を含むかどうかを決定することである。 保証問題に対する厳密な量子アルゴリズムを提案するが、これにはO(N2/3)$クエリが必要である。
  論文  参考訳（メタデータ） (2022-11-10T09:33:13Z)
• Finding many Collisions via Reusable Quantum Walks [1.376408511310322]
  衝突発見は暗号解析におけるユビキタスな問題である。 本稿では,この問題に対するアルゴリズムを改良し,特に許容可能なパラメータの範囲を広げる。 応用として、最短ベクトル問題に対する量子シービングアルゴリズムを改善する。
  論文  参考訳（メタデータ） (2022-05-27T14:50:45Z)
• 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)

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

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