論文の概要: Collision Detection is Instance $\widetilde{O}$ptimal Under the Birthday Threshold

• arxiv url: http://arxiv.org/abs/2609.37342v1
• Date: Tue, 29 Sep 2026 12:11:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-30 21:28:47.459863
• Title: Collision Detection is Instance $\widetilde{O}$ptimal Under the Birthday Threshold
• Title（参考訳）: Collision Detection is Instance $\widetilde{O}$ptimal under the Birthday Threshold
• Abstract要約: 我々は,暗号的観点から最も興味深い体制において,衝突検出のための(ほとんど)インスタンス最適化アルゴリズムの存在を証明した。 この結果は、特に、暗号設計者が衝突発見のための純粋に構造的なバックドアを植えることは不可能であることを意味している。
• 参考スコア（独自算出の注目度）: 2.14259086873496
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Can structural knowledge about a hash function help accelerate the (black box) detection of collisions in it? This question is fundamental to cryptography theory given the importance of collision-resistant hash functions, and in this paper we tackle it from the angle of instance optimality, an ultimate notion of beyond worst case algorithm analysis that has gained significant traction in recent years. Instance optimality asks for a single algorithm that, on every input, performs nearly as well as the best correct algorithm that ``knows the structure'' of that specific input. Here we measure algorithms by the number of queries they make to the hash function $f\colon [n]\to [n]$, and we say that an algorithm ``knows the structure'' of the input if, in addition to query access to $f$, it has free access to an unlabeled copy $π^{-1}\circ f\circπ$ of $f$, for an unknown permutation $π$ on $[n]$. We prove the existence of an (almost) instance-optimal algorithm for collision detection in the regime most interesting from a cryptographic perspective: among functions where finding a collision takes significantly less than $\sqrt{n}$ queries. Specifically, we prove the existence of a single algorithm $A$ that, for any input $f$ in which a structure-aware algorithm can find a collision using $q\leq O(\sqrt{n/\log n})$ queries in expectation, $A$ can find a collision in at most $O(q\log n)$ queries. The $O(\log n)$ multiplicative overhead is tight, matching a lower bound of Ben-Eliezer, Grossman, and Naor [ICALP'25], and partially resolving their main open question. Our result implies, in particular, that it is impossible for a cryptographic designer to plant purely structural backdoors for collision finding (for this unlabeled notion of structure): whatever collisions the designer's secret knowledge finds, the public can find with a multiplicative overhead of $O(\log n)$.
• Abstract（参考訳）: ハッシュ関数に関する構造的知識は、衝突の(ブラックボックス)検出を加速するのに役立ちますか? 本論は, 衝突耐性ハッシュ関数の重要性を考慮に入れた暗号理論の基本的問題であり, 本論では, 近年, 最悪のケース・アルゴリズム解析の究極的概念である, 最適性の角度からそれに取り組む。 インスタンスの最適性は、全ての入力に対して、その特定の入力の ``knows the structure''' を最も正しいアルゴリズムと同等に機能する1つのアルゴリズムを要求する。 ここで、ハッシュ関数 $f\colon [n]\to [n]$ に対するクエリ数でアルゴリズムを計測し、もし未知の置換に対して $[n]$ に対して $π^{-1}\circ f\circπ$ のラベルのないコピーに自由にアクセスできるなら、入力の '`knows the structure'''' というアルゴリズムを言う。 暗号的な観点から最も興味深いのは、衝突を検出するための(ほとんど)インスタンス最適化アルゴリズムの存在を証明している。 具体的には、構造認識アルゴリズムが$q\leq O(\sqrt{n/\log n})$クエリを使って衝突を見つけることができる任意の入力$f$に対して、$A$は少なくとも$O(q\log n)$クエリで衝突を見つけることができる。 O(\log n)$ 乗法的オーバーヘッドは厳密であり、ベン=エリツァー、グロスマン、ナオール(ICALP'25)の下界と一致する。 我々の結果は、特に、暗号設計者が衝突発見のための純粋に構造的なバックドアを植えることが不可能であることを意味している(このラベル付けされていない構造概念は、設計者の秘密知識の衝突がどんなに多く見つかろうとも、大衆は$O(\log n)$の乗法的なオーバーヘッドで見つけることができる。

関連論文リスト

• Collision Resistance of Single-Layer Neural Nets [3.2522957478427283]
  単層二層ニューラルネットワークにおける衝突のアルゴリズム的複雑性について検討する。 本研究は, 衝突抵抗の厳密な基準として, オーバーラップギャップ特性を用いた最初の研究である。
  論文  参考訳（メタデータ） (2026-06-02T15:52:45Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• On the instance optimality of detecting collisions and subgraphs [7.055459105099637]
  グラフや関数における部分構造検出問題のラベルなしインスタンス最適性について検討する。 アルゴリズムが任意の入力に対して満足する$A$を許容すれば、問題は$g(n)$-instanceOptimationである。 この結果から,グラフや関数のサブ構造検出問題において,ラベルなしのインスタンス最適性を三分したことが示唆された。
  論文  参考訳（メタデータ） (2023-12-15T20:50:03Z)
• Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint [0.0]
  2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。 提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
  論文  参考訳（メタデータ） (2023-09-21T12:42:52Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Finding many Collisions via Reusable Quantum Walks [1.376408511310322]
  衝突発見は暗号解析におけるユビキタスな問題である。 本稿では,この問題に対するアルゴリズムを改良し,特に許容可能なパラメータの範囲を広げる。 応用として、最短ベクトル問題に対する量子シービングアルゴリズムを改善する。
  論文  参考訳（メタデータ） (2022-05-27T14:50:45Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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