Collision Detection is Instance $\widetilde{O}$ptimal Under the Birthday Threshold

1 Introduction

• For a uniformly random function, Θ(√n) queries are necessary and sufficient for collision finding; this birthday bound motivates collision resistance in cryptography.A hash-function family is considered collision-resistant when collisions cannot be found much faster than the birthday bound.Source: §1 · p. 1

1.1 Unlabeled instance optimality

• Unlabeled instance optimality compares one fixed algorithm with competitors that know an input’s structure up to relabeling but must remain correct on every function.The benchmark charges competitors for their worst labeling of that structure.Source: §1 · p. 1, §1.1 · p. 2

1.2 Our result

• O(log n)-instance optimality holds for functions whose structure-aware query complexity is at most c√n/log n, and the logarithmic overhead is tight up to a constant.The prior separation in has structure-aware complexity within this class for sufficiently large n.Source: §1 · p. 2, §1.2 · p. 3
• The result concerns query complexity and unlabeled structural advice below the birthday threshold, not a trapdoor tied to the labels.Within that scope, the public all-scales algorithm finds collisions in O(q log n) expected queries when a structure-aware algorithm uses q queries.Source: §1.2 · p. 3

1.3 Technical overview

• The proof puts competitors in an oldest-first normal form and couples their fresh-vertex queries to the all-scales algorithm’s shared random ordering.The oldest-first argument is conditioned on walks not merging, a key reason the guarantee applies only below the birthday threshold.Source: §1.3 · p. 4
• On a good event, the coupling lets all-scales find both edges of a collision witness within twice the competitor’s rounds, each costing O(log n) queries.The good event prevents roots from being skipped, keeping explored walks disjoint until a collision is found.Source: §1.3 · p. 5
• A refined probability analysis uses surrogate boxes fixed before each root is exposed, addressing dependence between sampled roots and protected walk vertices.This sharper bound extends the result’s range by a √log n factor.Source: §1.3 · p. 5

1.4 Related work

• The closest prior work established the logarithmic lower bound and studied related collision problems; generic collision-search work generally does not analyze per-instance complexity.The paper’s model is classical, forward-query, and Las Vegas, with an arbitrary fixed function as input.Source: §1.4 · pp. 6–7

2 Preliminaries

• Collision detection seeks distinct vertices with equal function values; in the black-box model, an algorithm is Las Vegas if it always answers correctly and only its query count is random.The paper identifies f with its directed functional graph, where every vertex has out-degree one.Source: §2 · p. 7
• A correct algorithm needs an explicit collision witness: two discovered edges entering one vertex, while ruling out collisions requires querying every vertex.Otherwise the transcript remains consistent with an input on which the reported answer would be wrong.Source: §2 · p. 8

2.1 The all-scales algorithm

• Aall runs scale-indexed walkers over a shared random ordering, in epochs of doubling length, while retaining discovered edges across epochs.Each walker follows a walk for up to 2^i steps or until it revisits a vertex.Source: §2.1 · p. 8
• The algorithm reports a collision when two distinct known edges enter the same vertex, and reports no collision only after learning all n out-edges.A round uses at most L + 1 queries; known edges can be looked up freely but still use a walker's unit of work.Source: §2.1 · p. 8
• The shared-stream, doubling-epoch variant differs from, whose walkers use independent starting vertices and do not restart; the authors expect that original variant to have the same guarantee, but do not prove it.Aall is Las Vegas and has finite expected query complexity on every input.Source: §2.1 · p. 10

3 Reduction to label-oblivious, oldest-first algorithms

• Relabeling converts any Las Vegas competitor into a label-oblivious one, whose decisions depend only on the unlabeled transcript.Conditioned on that transcript and the algorithm's coins, its embedding into the fixed input is uniform over all consistent embeddings.Source: §3 · pp. 10–11
• Redundant queries can be discarded: before a collision witness, known edges form paths and cycles, and a query either extends a path or starts a new root.An edge entering an interior vertex creates a witness; entering a path's first vertex can merge paths without one.Source: §3 · p. 10
• Among unmerged open paths of equal length, exchangeability permits a virtual simulation to extend the oldest actual path without changing the query distribution.This yields an oldest-first normalization with the same expected query cost on every input.Source: §3 · p. 11
• Thus every competitor can be assumed label-oblivious and oldest-first before a witness-free merge, which the proof's good event prevents in the relevant execution.The normalization combines the relabeling and oldest-first reductions.Source: §3 · pp. 10–11

4 The coupling argument

• The warm-up theorem makes the all-scales algorithm O(log n)-instance optimal for functions with structure-aware query complexity at most c0√(n/log n), for an absolute constant c0.The proof couples a normalized competitor with a single epoch, obtains a constant-probability guarantee, and converts it to expected query complexity.Source: §4 · p. 11

4.1 Setup and coupling

• A random permutation couples fresh-label queries to roots in a shared stream; on the good event, no scan skips a vertex among the first t positions.The competitor uses at most t roots in t queries, and reproducing an edge from a root needs only the corresponding permutation prefix.Source: §4.1 · p. 12

4.2 Boxes and the good event

• At scale i, box Bi contains the first roughly t/2^i positions whose walks survive at least 2^i steps, limiting which roots a t-query competitor can explore that deeply.Each box has size at most ⌈t/2^i⌉, and the boxes are determined by the roots' type vector.Source: §4.2 · p. 12
• The good event G requires that no root other than rk appears on the first 2^i+1 steps from any box position k in Bi.G holds with probability at least 4/5 when t ≤ √n/(15 log n); a sharper bound in Section 5 improves the threshold.Source: §4.2 · p. 13

4.3 The exploration lemma

• The budget bounds each root's reach: a later walk cannot pass depth 2^i+1 unless the number of earlier sufficiently long walks would already exceed t queries.This places the root in the corresponding box Bi and constrains how far its walk can extend.Source: §4.3 · pp. 13–14
• On G, each started root grows its own component as an open path or a cycle, and no discovered edge enters another root.If an edge creates a collision witness, the algorithm halts; otherwise the components remain vertex-disjoint.Source: §4.3 · p. 13
• For open paths, older roots have reach at least that of newer roots, reflecting the competitor's oldest-first schedule.The j-th fresh-label query is made at rj because the permutation scan skips no vertex on G.Source: §4.3 · p. 13
• Every vertex explored by A within its first t queries has the form rk +f ℓ for a box position k ∈ Bi_k and 0 ≤ ℓ ≤ 2^i_k+1.The coverage corollary follows from the exploration invariants on G.Source: §4.3 · p. 14

4.4 The domination lemma

• The oldest-first rule ensures the walker spends at most twice the competitor’s cost on each earlier root before reaching the target edge.For an earlier root, the competitor has paid at least min(ℓ, ρ) queries, while the walker spends min(2m, ρ) ≤ 2 min(ℓ, ρ).Source: §4.4 · pp. 14–15
• Within 2t′ rounds, the coupled isolated epoch run contains any edge the competitor discovers within t′ queries, unless it has already reported a collision.The domination lemma tracks the walker whose cap is the first power of two at least as large as the edge depth.Source: §4.4 · p. 14
• Conditioned on G, a collision found by A within t queries is reported by the coupled epoch run within 2t rounds.The collision’s two witness edges are both in memory by round 2t′, so the run’s round-end check finds the collision.Source: §4.4 · p. 15

4.5 From constant probability to expectation

• 8t/(2p̄ − 1) bounds expected rounds, and (log n + 2) · 8t/(2p̄ − 1) bounds expected queries when an isolated epoch succeeds within 2t rounds with probability p̄ > 1/2.Fresh streams make epoch trials independent; retained memory can only help because the collision check is monotone.Source: §4.5 · p. 15

4.6 From the good event to instance optimality

• A good-event guarantee Pr[G] ≥ 4/5 up to threshold T(n) yields instance optimality for inputs in F_T(n)/20.The proposition applies when 1 ≤ T(n) ≤ n.Source: §4.6 · p. 16
• 20t(log n + 2) bounds Aall’s expected queries, with t bounded by 20 times the best relabeling’s expected query cost.The proof obtains this bound by combining the competitor’s success probability with G and the collision-transfer result.Source: §4.6 · p. 16

4.7 A first bound on the good event

• A type is overpopulated when its stream count exceeds 10 log(2n) · t|Type_i|/n, and Markov’s inequality plus a union bound controls this failure event.The expected count for type i is t|Type_i|/n, and the number of types is at most log(2n).Source: §4.7 · p. 16
• For t ≤ √n/(15 log n) and n ≥ 224, the good event holds with probability at least 4/5.Source: §4.7 · p. 16
• Conditioning on the type vector makes each type’s stream positions a uniform ordered sample, allowing the analysis to bound root-path coincidence events.For a fixed path vertex w of type h, the chance it appears among type-h positions is bounded using N_h/|Type_h|.Source: §4.7 · pp. 16–17

4.8 Proof of the warm-up theorem

• For n ≥ 224, Aall uses at most 400(log n + 2) times the best relabeling’s expected query count on inputs in F_c0√n/log n.The proof sets c0 = 1/300 and uses the first-moment bound to verify the master proposition’s good-event condition.Source: §4.8 · p. 17
• The resulting guarantee is O(log n)-instance optimality for functions whose structure-aware query complexity is at most c0√n/log n.Source: §4.8 · p. 17
• For n < 224, the proof absorbs the finite-size behavior into the hidden constant in the O(log n) factor.It uses a query upper bound depending only on n and a competitor lower bound of at least one query.Source: §4.8 · p. 17

• The improved probability estimate is the only step sensitive to the exact threshold; the coupling, exploration and domination arguments use only the good-event definition.The proof reuses the earlier assembly with the stronger lemma.Source: §5 · pp. 17–18
• At scale i, the proof protects prefixes of length up to 2^i and selects a surrogate box from surviving positions while skipping the target root.This surrogate is fixed before the target is exposed, allowing the danger-set bound.Source: §5 · pp. 17–18
• To bound failure of the good event, expose all roots except a possible target, bound its danger set, then use the target’s uniform location to control its chance of falling inside.A union bound over the t possible target roots completes the failure estimate.Source: §5 · pp. 17–18
• For every f in the stated class, the algorithm uses at most 400(log n + 2) times the best structure-aware expected query cost, up to the theorem’s threshold condition.The guarantee applies to f in F_{c√(n/log n)} and every Las Vegas competitor.Source: §5 · p. 18

The collision conjecture and the merging barrier

• The O(log n) instance-optimality conjecture is proved for F_{c√(n/log n)}, but proving it for the rest of the range, including above the birthday threshold, remains open.Current proof approaches rely on having no merges, whereas merges are common and sometimes unavoidable above the birthday threshold.Source: §6 · p. 19

Single-scale optimality

• It remains open whether some single-scale walker is O(1)-competitive with the structure-aware optimum on every input with a collision.The proposed condition asks for success within C · OPT(f) queries with probability at least 2/3.Source: §6 · p. 19
• If single-scale optimality holds, the logarithmic overhead would be the cost of running all scales rather than a loss inherent in walk-based algorithms.The known Ω(log n) lower bound applies in the theorem’s regime.Source: §6 · p. 19
• The proof does not establish single-scale optimality because a collision witness’s edges may be matched to different walkers, while larger-scale walkers can pay more on long-surviving walks.A possible hard instance could combine components at multiple well-separated scales; whether this defeats every scale remains unresolved.Source: §6 · p. 19

Beyond collisions and beyond unlabeled instance optimality

• For 3-way collision detection and fixed-point detection, prior work shows polynomial separation from unlabeled instance optimality.The paper notes these as related problems whose guarantees differ from collision detection.Source: §6 · p. 19

• The mathematical content and proofs were first conceived and written by the human authors without LLMs, with a stated exception concerning Section 5.The authors take responsibility for all parts of the manuscript.Source: AI Disclosure · pp. 19–20
• LLMs were used for extensive editing, polishing, clarification, an initial introduction draft and literature review.The introduction draft was heavily edited by the human authors.Source: AI Disclosure · p. 20
• Claude Fable 5 found an inaccuracy in the Section 5 proof’s use of randomness and suggested a correction.The authors say both they and the LLM contributed meaningfully to Section 5’s improvement.Source: AI Disclosure · p. 20

• Lazy random relabeling simulates the competitor on the relabeled function with one oracle query per simulated query, preserving correctness and expected query cost.The simulated algorithm’s cost is bounded by the maximum cost over relabelings.Source: A Deferred proofs from Section 3 · p. 23
• The simulator is label-oblivious because concrete labels are a uniformly random injective assignment to placeholders, independent of the competitor’s decision history.Its next simulated operation can therefore be implemented from the unlabeled transcript alone.Source: A Deferred proofs from Section 3 · p. 23
• Conditioned on the unlabeled transcript, the embedding remains uniform over consistent injective labelings as queries reveal vertices and answers.The proof maintains uniformity by conditioning on each answer outcome and mapping embeddings bijectively when a new vertex appears.Source: A Deferred proofs from Section 3 · p. 23
• The coupling keeps a virtual transcript distributed as the original algorithm’s transcript while remapping unmerged equal-length paths to the oldest actual path of that length.Swapping images preserves the uniform distribution over consistent embeddings; the coupled algorithms make the same number of queries and return the same answer.Source: A Deferred proofs from Section 3 · pp. 23–24