Hash Functions Under Quantum Search: Pre-image versus Collision, and Why Grover Does Not Halve Collision Resistance

Abstract

This article works out how quantum search affects hash functions, distinguishing two properties that behave very differently. Pre-image resistance — the difficulty of inverting a hash to find an input with a given output — is a search over the roughly 2^n possible inputs of an n-bit hash, so Grover's algorithm reduces it to about 2^(n/2), halving it just as it halves a key length. Collision resistance is different in two ways. Classically it is already much weaker than pre-image resistance because of the birthday bound, at about 2^(n/2), and the quantum improvement on top of that is small: the Brassard-Hoyer-Tapp algorithm achieves about 2^(n/3), but only with an enormous amount of quantum-accessible memory that makes it impractical, and without that memory, quantum offers essentially no advantage over the classical birthday attack. So the naive intuition that quantum halves everything is wrong for collisions — the real-world quantum speedup against collision resistance is negligible. It presents the concrete numbers for SHA-2 and SHA-3 output sizes and closes on what to use and the AI stakes, where hashing underlies model and data integrity and hash-based signatures. The theme: quantum halves pre-image resistance cleanly, but collision resistance is governed by the birthday bound and the memory cost of the quantum collision-finder, so it is far less affected than a naive halving would suggest.

A hash function offers several security properties, and quantum computers affect them unequally. The intuition from the previous article — that quantum search halves the effective strength — is correct for one property, pre-image resistance, but importantly wrong for another, collision resistance. Understanding why requires distinguishing the two, appreciating the birthday bound that already governs collisions classically, and confronting the enormous memory cost of the quantum collision-finding algorithm. The upshot is reassuring and specific: quantum weakens hashes less than the naive halving suggests, and standard output sizes remain strong.

The two properties, classically

A cryptographic hash maps inputs to fixed-length n-bit outputs, and two of its security properties matter here. Pre-image resistance is the difficulty of inverting the hash: given an output, find any input that produces it. For a good n-bit hash this requires trying about 2^n inputs, since the output looks random and there is no better strategy than search. Collision resistance is the difficulty of finding any two distinct inputs that hash to the same output, without a target output specified in advance.

The crucial classical fact is that these two costs are very different because of the birthday bound. Finding a collision does not require searching the whole output space; by the birthday paradox, among about 2^(n/2) random inputs two are likely to collide, so collision resistance is only about 2^(n/2) — the square root of the pre-image cost. This is why a hash needs twice the output length to resist collisions that it would need to resist pre-images at the same security level: a 256-bit hash gives about 256-bit pre-image resistance but only about 128-bit collision resistance.

This asymmetry is entirely classical and long understood, but it is the key to the quantum analysis, because the two properties start from different baselines and the quantum speedups apply to them differently. Pre-image resistance starts at 2^n and can be attacked by straight search; collision resistance starts already lowered at 2^(n/2) by the birthday effect, and the quantum question is whether it can be pushed lower still. The answer, it turns out, is barely.

Pre-image resistance is about 2^n; collision resistance is only about 2^(n/2) because of the birthday bound.

Pre-image resistance under Grover

Pre-image resistance is a straightforward search problem, and Grover's algorithm applies cleanly. Inverting an n-bit hash means searching the roughly 2^n possible inputs for one that produces the target output, exactly the unstructured search Grover speeds up quadratically. So a quantum attacker finds a pre-image in about 2^(n/2) operations rather than 2^n, halving the pre-image resistance in the same way Grover halves a key length.

The engineering response is the same as for keys: use a longer output. A 256-bit hash offers about 128-bit pre-image resistance against Grover, which is a comfortable margin, and a 384- or 512-bit hash offers correspondingly more. The parallelization caveats from the previous article apply here too — Grover against a hash is just as unparallelizable and depth-hungry as Grover against a cipher — so the real-world pre-image threat is milder than even the 2^(n/2) figure suggests. Pre-image resistance is the property that behaves exactly like key search.

So for pre-image and second-pre-image resistance, the story is the familiar quadratic one, and the remedy is adequate output length. This matters because several important constructions — notably the hash-based signatures covered later in this series — rest on pre-image and second-pre-image resistance rather than collision resistance, and are therefore only quadratically affected, which is why they are considered solidly post-quantum with appropriate parameters. The interesting deviation from the naive story is collision resistance.

\[\text{Pre-image: classical } \approx 2^{n}, \quad \text{Grover} \approx 2^{n/2} \;\; (\text{halved})\]

\[\text{Collision: classical birthday} \approx 2^{n/2}, \quad \text{BHT} \approx 2^{n/3} \;\; (\text{but needs huge memory})\]

Why collision resistance is not naively halved

The naive expectation would be that quantum halves collision resistance too, taking it from 2^(n/2) to 2^(n/4). That is not what happens. The best quantum collision-finding algorithm, due to Brassard, Hoyer, and Tapp, achieves about 2^(n/3) operations — better than the classical 2^(n/2), but by a smaller factor than a full halving, and, critically, only under an assumption that undermines it in practice. The BHT algorithm requires an enormous amount of quantum-accessible memory, on the order of 2^(n/3) storage that can be queried in superposition.

That memory requirement is the catch. Building and maintaining exponentially large quantum-accessible memory is widely regarded as harder than building the quantum processor itself, and when the cost of that memory is properly accounted for, the BHT advantage largely evaporates. Analyses that charge realistic costs for memory and hardware conclude that quantum collision finding offers little or no practical improvement over the classical birthday attack — the classical parallel birthday search, which needs only ordinary memory and parallelizes well, is competitive with or better than the quantum algorithm once memory costs are counted.

The practical conclusion is that collision resistance is governed by the classical birthday bound of about 2^(n/2) even against a quantum adversary. Unlike pre-image resistance, it is not meaningfully halved by quantum computing, because the only quantum improvement is small and rests on infeasible memory. The spectrum of options makes this concrete: the classical birthday attack sits at 2^(n/2), BHT with unlimited quantum memory reaches 2^(n/3), but BHT with realistic memory falls back toward 2^(n/2) — so the effective collision resistance a defender should assume is the classical birthday value.

BHT beats the birthday bound only with infeasible quantum memory; with realistic memory it falls back to the classical cost.

The numbers, what to use, and the AI stakes

Putting the two properties together gives clean guidance, summarized in the table. For an n-bit hash, assume about 2^(n/2) pre-image resistance against Grover and about 2^(n/2) collision resistance from the birthday bound, essentially unchanged by quantum. SHA-256 therefore offers roughly 128-bit pre-image and 128-bit collision resistance in a quantum world — a solid level — while SHA-384 and SHA-512 offer larger margins, which is why NIST points to SHA-384 and above for the highest post-quantum security categories. As with ciphers, the remediation is output length, not new algorithms; SHA-2 and SHA-3 remain sound.

The one subtlety to respect is that collision resistance, not pre-image resistance, is the binding constraint for many uses, and it is already the lower number classically. Applications that depend on collision resistance — digital-signature message hashing, certificate integrity, commitments — should size their hash for the collision bound, meaning a 256-bit hash for 128-bit security, and step up to 384 bits where a larger margin is wanted. The good news is that this sizing is driven by the classical birthday bound that was always there; quantum does not force a change beyond what prudent classical sizing already recommends.

For AI, hashing is the silent workhorse of integrity, and this analysis says it is on firm quantum footing. The integrity of model weights, of training datasets, and of the software supply chain that produces them is enforced by hashing — content-addressed storage, signed model manifests, verifiable data provenance — and these depend on collision and pre-image resistance that 256- or 384-bit hashes provide durably against quantum attack. Hash-based signatures, which secure firmware and long-lived artifacts and rest on pre-image and second-pre-image resistance, are only quadratically affected and remain a conservative post-quantum choice. The reassuring message of this article is that, unlike the public-key upheaval, the hashing layer that guards AI's most valuable artifacts needs no reinvention — adequate output length, which standard hashes already provide, keeps model and data integrity intact into the quantum era.

Hash security properties under quantum attack, per n-bit output.
Property	Classical	Quantum (practical)	Effect
Pre-image	about 2^n	about 2^(n/2) (Grover)	halved
Collision	about 2^(n/2) (birthday)	about 2^(n/2)	essentially unchanged
SHA-256	128-bit collision	about 128-bit	solid floor

✅

Collisions are governed by the birthday bound, not a quantum halving. Grover halves pre-image resistance (use longer output), but collision resistance stays near the classical birthday bound of 2^(n/2), because the quantum collision-finder (BHT) needs infeasible memory. SHA-256 gives about 128-bit quantum security; SHA-384 for more. The hashing layer guarding model and data integrity needs no new algorithms.

Key takeaways

Pre-image resistance is a search over about 2^n inputs, so Grover halves it to about 2^(n/2), exactly like a key length — remediated by longer output.
Collision resistance is already only about 2^(n/2) classically because of the birthday bound, half the output length before any quantum effect.
The quantum collision-finder (Brassard-Hoyer-Tapp) reaches about 2^(n/3) but only with infeasible quantum-accessible memory; with realistic memory it falls back to 2^(n/2).
So collision resistance is essentially unchanged by quantum in practice — the naive intuition that quantum halves everything is wrong for collisions.
SHA-256 gives about 128-bit pre-image and collision resistance in a quantum world; SHA-384/512 give larger margins, with no new algorithms needed.
For AI, hashing secures model, data, and supply-chain integrity, and hash-based signatures rest on pre-image resistance — all durably post-quantum with adequate output length.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

✅Sizing a hash for the quantum erachecklist

Questions for choosing an output length.

Does the use depend on collision resistance (size for 2^(n/2)) or pre-image resistance?
Is a 256-bit output enough (about 128-bit security), or is a larger margin wanted (SHA-384/512)?
Are you assuming the classical birthday bound for collisions, not a quantum halving?
Do hash-based signatures in use rely on pre-image/second-pre-image resistance (only quadratically affected)?
Are model, data, and supply-chain integrity hashes at least 256-bit?

🚀The hash quantum mental modelquickstart

Three facts to hold onto.

Pre-image: halved by Grover (2^n to 2^(n/2)) — use longer output.
Collision: stays near the birthday bound 2^(n/2); BHT needs infeasible memory.
SHA-256 is a solid floor; SHA-384/512 for higher margins.

🔒Hash-sizing stancepolicy

A stub recording the output-length policy.

hash_quantum_sizing:
  preimage:
    classical: 2^n
    grover: 2^(n/2)
  collision:
    classical_birthday: 2^(n/2)
    quantum_practical: 2^(n/2)   # BHT needs infeasible QRAM
  minimums:
    integrity: sha_256
    high_margin: sha_384
  hash_based_signatures: quadratic_only

Illustrative documentation template, not a product config.

Glossary

Pre-image resistance: The difficulty of finding any input that hashes to a given output; about 2^n classically, halved to 2^(n/2) by Grover.
Collision resistance: The difficulty of finding any two distinct inputs with the same hash; about 2^(n/2) classically by the birthday bound.
Birthday bound: The classical fact that a collision is likely among about 2^(n/2) random inputs, making collisions far easier than pre-images.
BHT algorithm: The Brassard-Hoyer-Tapp quantum collision-finder achieving about 2^(n/3), but requiring infeasible quantum-accessible memory.
Quantum-accessible memory (QRAM): Exponentially large memory queryable in superposition, required by BHT and widely considered impractical to build.
Second-pre-image resistance: The difficulty of finding a different input with the same hash as a given one; like pre-image, only quadratically affected by quantum.