Quantum Algorithms Database
Quantum Collision Finding (Brassard-Høyer-Tapp)
Finds two inputs that produce the same output from a function (a 'collision') faster than classical methods, with direct implications for hash function security.
Year
1997
Inventor(s)
Gilles Brassard, Peter Høyer, and Alain Tapp
Speedup Type
Polynomial Speedup
Difficulty
★★★★☆
Overview
A collision is a pair of different inputs that give the same output of a function. Finding collisions in a cryptographic hash function is the basis of several attacks, such as forging digital signatures or certificates. Classically, the birthday paradox says that for a hash with n-bit output you need about 2 to the n over 2 evaluations to find a collision. The Brassard-Høyer-Tapp algorithm, known as BHT, finds one with about 2 to the n over 3 evaluations on a quantum computer.
This is a polynomial speedup, better than Grover's quadratic improvement for preimage search, and it is the reason that hash functions designed for long-term security often have longer outputs than strictly needed against classical attackers. Later cost analyses, however, show that the practical advantage may be much smaller than the query count suggests.
The problem it solves
Given a function (like a cryptographic hash), find two different inputs that map to the same output — a core building block for breaking certain cryptographic schemes.
History and background
Brassard, Høyer, and Tapp presented the algorithm in 1997 and published it at the LATIN conference in 1998, in a paper titled Quantum Cryptanalysis of Hash and Claw-Free Functions. It was one of the first applications of Grover's algorithm to cryptanalysis beyond brute-force key search.
The quantum query lower bound of Omega of N to the one third was proved by Aaronson and Shi in 2004, based on techniques related to Ambainis's work on the element distinctness problem, so BHT is optimal in the query model. In 2009 Daniel Bernstein argued in a paper on cost analysis of hash collisions that when the cost of memory and parallel hardware is considered, classical algorithms can match BHT, and in 2017 Chailloux, Naya-Plasencia, and Schrottenloher gave a quantum collision algorithm with time about 2 to the 2n over 5 using little quantum memory. Standards bodies, including NIST, have concluded that SHA-256 and SHA-3 remain secure against quantum collision attacks.
How it works
Combines classical preprocessing with Grover-style search to locate colliding pairs using roughly the cube root of the number of classical queries needed.
The birthday paradox is the classical reason collisions are easy: with a table of about the square root of N values, a new value is likely to match one of them. The quantum algorithm keeps that idea but replaces the second half of the search with Grover's algorithm.
BHT first computes the function on a small set T of about N to the one third arbitrary inputs and stores the results in a classical table. It then runs Grover's algorithm over inputs outside T, with the marked condition that the function value is in the table. If a function value from the table appears, the corresponding input and the table entry form a collision.
The numbers balance because of a trade-off. A bigger table makes more inputs marked, so Grover's search is shorter, but filling the table costs queries. Choosing the table size to be N to the one third equalizes the two costs at about N to the one third each.
Step by step
- Choose a table size equal to about N to the one third, where N is the size of the function's domain.
- Evaluate the function on that many inputs, and store the pairs of input and output in a sorted table. If a collision is already present, stop.
- Define an oracle that marks an input x outside the table if f of x equals the output of some table entry.
- Run Grover's algorithm with this oracle. The fraction of marked inputs is about N to the minus two thirds, so about N to the one third iterations are needed.
- Measure to obtain a marked input x, and look up the table entry with the same function value to get a second input y.
- Output the pair x and y, which collide. If Grover's search fails, repeat with a new random table.
A worked example
Take a hash function with 96-bit output, so N is 2 to the 96. The classical birthday attack needs about 2 to the 48 evaluations, which is around 280 trillion. The BHT algorithm needs about 2 to the 32 evaluations in the query model, around 4 billion, but with a table of 2 to the 32 stored values and a quantum computer that runs Grover iterations over that table.
For a 256-bit hash like SHA-256, the classical collision cost is 2 to the 128, and BHT reduces it to about 2 to the 85 queries. That is still beyond any realistic attacker, particularly once the cost of reading a very large table in superposition and running 2 to the 85 sequential steps is counted.
Complexity and resources
| Item | Detail |
|---|---|
| Quantum queries | O(N to the one third) for a hash with N possible outputs |
| Classical queries | Theta of the square root of N (birthday bound) |
| Lower bound | Omega of N to the one third in the query model (Aaronson and Shi, 2004) |
| Memory | About N to the one third classical table entries accessed in superposition (quantum random access to classical memory) |
| Cost in realistic models | Often equal to or worse than parallel classical attacks once memory and hardware costs are counted |
What hardware it needs
- A fault-tolerant quantum computer capable of running Grover iterations over a large table.
- Efficient quantum access to a classical memory of size N to the one third, which is the main practical obstacle.
- Reversible implementations of the hash function inside the oracle.
Applications
- Analyzing the quantum security margin of hash functions such as SHA-2 and SHA-3.
- Attacks on hash-based commitment and signature schemes if outputs are too short.
- Claw-finding and related problems, where two functions must agree on an output.
- Setting hash output lengths for long-term security.
Limitations and caveats
- The advantage depends on cheap quantum access to a very large table, which is unrealistic.
- Parallel classical algorithms with the same hardware budget can match the quantum query count in realistic cost models.
- The algorithm needs Grover iterations that are sequential, so the total run time is large.
Common misconceptions
- BHT does not break SHA-256. The attack would still need around 2 to the 85 steps.
- It does not apply to all cryptographic schemes, only to collision resistance.
- A better query count does not necessarily mean a lower real-world cost.
How it compares
- Grover's algorithm halves the exponent for preimage search, while BHT reduces the exponent for collisions from one half to one third.
- Ambainis's element distinctness algorithm needs N to the two thirds queries for a more general problem and is related by the same quantum walk technique.
- Classical parallel collision search (van Oorschot and Wiener) uses little memory and is competitive with BHT in cost terms.
Real-world impact
Informs security analysis of cryptographic hash functions, helping cryptographers determine appropriate hash output lengths to remain secure even against quantum-equipped attackers.
Why it matters
BHT is the reason cryptographers talk about quantum collision resistance as one third of the output length, instead of one half. It affects how designers choose hash output sizes, though most standards simply keep outputs of 256 bits or more.
It also shows how a theoretical speedup can lose its force under a more careful cost model. Understanding that lesson is essential for judging many claims about quantum cryptanalysis.
Frequently asked questions
What does the BHT algorithm do?
It finds two inputs that give the same output of a function using about N to the one third quantum queries, versus about N to the one half classically.
Does it break SHA-256?
No. Even with the quantum speedup, finding a SHA-256 collision would take around 2 to the 85 steps, and the memory requirements are impractical.
Is the quantum advantage real in practice?
In the query model yes, but cost analyses that include memory and parallel classical hardware suggest that the practical advantage is limited or absent.
What is the lower bound?
Any quantum algorithm needs about N to the one third queries to find collisions, so BHT is optimal in the query model.
What should hash designers do?
Use output lengths that give adequate security margin under conservative assumptions, such as 256 bits or more, which standards already recommend.
Keep learning
- Related algorithm: Grover's Algorithm
- Related algorithm: Quantum Walk Algorithms
- Related algorithm: Quantum Amplitude Amplification
- Related algorithm: Quantum Minimum Finding
This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.