Metraipolis › archive › dc_82ceff51ef7a
Collision Detection is Instance $\widetilde{O}$ptimal Under the Birthday Threshold — arXiv:2609.37342
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.37342
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T17:27:08.677Z
- SHA-256 of the archived text
63c7a01c273e84bfcf7d983e914ac9f1ea66eb5c7f08bc97f0589e3ee43b22f3- Stable URL of this page
https://metraipolis.com/documento/dc_82ceff51ef7a
How to cite
Collision Detection is Instance $\widetilde{O}$ptimal Under the Birthday Threshold — arXiv:2609.37342 — arXiv (en), https://arxiv.org/abs/2609.37342 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_82ceff51ef7a (Metraipolis archive dc_82ceff51ef7a, sha256 63c7a01c273e84bfcf7d983e914ac9f1ea66eb5c7f08bc97f0589e3ee43b22f3)
BibTeX
@misc{dc82ceff51ef7a,
title = {Collision Detection is Instance $widetildeO$ptimal Under the Birthday Threshold — arXiv:2609.37342},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.37342},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_82ceff51ef7a; sha256 63c7a01c273e84bfcf7d983e914ac9f1ea66eb5c7f08bc97f0589e3ee43b22f3},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.37342. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\pi^{-1}\circ f\circ\pi$ of $f$, for an unknown permutation $\pi$ 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)$.
Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-30 in cs.CR).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC); Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2609.37342 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T16:58:17.387Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).