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)
Brassard, Høyer & Tapp
Speedup Type
Polynomial Speedup
Difficulty
★★★★☆
The Problem
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.
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.
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.