Brassard–Høyer–Tapp (BHT) Quantum Collision Algorithm and Post-Quantum Security

Introduction and Overview

The Brassard–Høyer–Tapp (BHT) algorithm is a quantum algorithm discovered in 1997 that finds collisions in hash functions faster than classical methods. In cryptography, a collision means finding two different inputs that produce the same hash output, undermining the hash’s collision resistance. The BHT algorithm theoretically reduces the time complexity of finding collisions from the classical birthday-paradox bound of about O(2^n/2) (for an n-bit hash) down to O(2^n/3) using quantum computation. This represents a significant (though not as dramatic as Grover’s) quantum speedup: for example, a 256-bit hash has ~128-bit collision security classically, but only ~85-bit security under a hypothetical BHT attack.

However, as we’ll explore, practical impact of the BHT algorithm is nuanced. While it theoretically weakens hash functions more than Grover’s algorithm does, it also demands enormous quantum resources (especially memory) that make it far less feasible in practice.

The BHT Algorithm: Quantum Collision-Finding

Brassard–Høyer–Tapp (BHT) is a quantum algorithm for the collision problem, first published by Gilles Brassard, Peter Høyer, and Alain Tapp in 1997. The problem is: given a function with a large range (like a hash function outputting n bits), find two distinct inputs that produce the same output. Classically, the best generic method is a birthday attack, which requires on the order of 2^n/2 trials to find a collision (due to the birthday paradox). The BHT algorithm combines Grover’s search (quantum amplitude amplification) with random sampling in a clever way to achieve an expected O(2^n/3) queries to the function. In other words, it provides a cubic-root speedup: for an n-bit output, the generic collision search drops from 2^n/2 operations (classical) to 2^n/3 (quantum). This meets the theoretical lower bound for quantum collision-finding (proven to be Ω(2^n/3)), so BHT is essentially optimal in the black-box model.

How it works (in brief)

The algorithm first queries the hash function on about N^1/3 random inputs (where N = 2ⁿ is the size of the output space). If by chance any two of those collide, it’s done. If not (which is overwhelmingly likely if only ~2^n/3 values are sampled, since this is far below the ~2^n/2 needed for an expected collision), then it uses Grover’s algorithm to search for a new input that produces one of the previously seen hash outputs. Grover’s search finds such a colliding input in ~O(√(N / N^1/3)) = O(N^1/3) steps.

In total, on the order of 2^n/3 hash evaluations are performed, dramatically less than the 2^n/2 required classically. The BHT algorithm thus leverages both classical random sampling and quantum amplitude amplification to reach a collision faster than either alone could achieve. Intuitively, it optimizes the trade-off between the resources spent building the initial classical sample set (related to the birthday paradox) and the time Grover’s algorithm takes to search the remaining space for a match within that set.

Comparison to Grover’s algorithm

Recall that Grover’s algorithm by itself is a general quantum search method that finds a single target item out of N possibilities in O(√N) steps. Grover’s is applicable to tasks like brute-forcing a key or finding a preimage of a specific hash output (a preimage attack). Grover provides a quadratic speedup, halving the effective exponent of the brute-force complexity. For example, finding a preimage on an ideal n-bit hash takes ~2ⁿ trials classically but ~2^n/2 with Grover. The BHT algorithm is more specialized – it targets collisions. While Grover provides a quadratic speedup over classical preimage attacks (reducing the exponent from n to n/2), BHT provides a smaller speedup factor over classical collision attacks (reducing the exponent from n/2 to n/3). For context:

• Classical preimage search (n-bit hash or key search): ~2ⁿ operations.
• Quantum preimage search (Grover’s algorithm): ~2^n/2 operations.
• Classical collision search (birthday attack): ~2^n/2 operations (producing ~2^n/2 hash outputs to expect a collision).
• Quantum collision search (BHT algorithm): ~2^n/3 operations.

In short, Grover’s affects preimage resistance and symmetric key search, whereas BHT affects collision resistance of hash functions. BHT’s improvement (cube-root vs. square-root) is smaller than Grover’s, but it still lowers the security exponent. For instance, SHA-256 (256-bit output) offers 128-bit collision security classically, but under BHT it would offer about 85 bits of security. Achieving a full 128-bit quantum collision security would require a larger hash (≥384-bit output, since 384/3 ≈ 128). Indeed, using SHA-384 instead of SHA-256 restores the ~128-bit security level even against BHT in theory.

Practical Challenges: Memory Requirements and Feasibility

While the BHT algorithm is impressive in theory, its practical applicability is highly questionable with foreseeable quantum technology. The algorithm’s strategy of precomputing ~2^n/3 hash outputs and then using Grover’s search implies needing to store and quickly query on the order of 2^n/3 data in a quantum memory (often dubbed QRAM). This is an astronomically large number for typical hash sizes. For SHA-256, 2^256/3 ≈ 2^85.3 ≈ 4×10²⁵ entries would be required! Even just counting bits, that’s on the order of 2⁸⁵ qubits needed to store the hash outputs – an utterly unrealistic quantum memory demand with any technology we can foresee.

In addition to memory, the time complexity ~2⁸⁵ for SHA-256 collisions is itself enormous (though lower than 2¹²⁸ classically), and the quantum circuit depth required for Grover’s portion is also huge.

Crucially, researchers have pointed out that if one considers overall cost (time and hardware), the BHT algorithm offers no practical advantage over the best classical strategies for finding collisions. A notable comparison is with the parallel rho algorithm (a classical collision search method that uses many processors in parallel). Daniel J. Bernstein analyzed that a classical parallel rho method can find a collision in time about 2^n/4 using 2^n/4 parallel units. For a 256-bit hash, that means time ~2⁶⁴ with 2⁶⁴ parallel computations. The BHT algorithm, in contrast, would take time ~2⁸⁵ and also requires on the order of 2⁸⁵ quantum hardware elements (qubits/memory) working in concert. This is far worse on both time and hardware fronts. In Bernstein’s words, “all known quantum algorithms to find collisions in hash functions are less cost-effective than traditional cryptanalytic hardware, even under optimistic assumptions regarding the speed of quantum computers”. In fact, given the difficulties of long sequential quantum computations, even Grover’s algorithm for key search loses some of its theoretical advantage unless massively parallelized (which again raises hardware requirements). BHT, with its huge memory requirement, is even more impractical to run in a real quantum device.

To put it simply, BHT’s O(2^n/3) speed comes at an exorbitant cost in quantum circuit size and memory. As of now, no known architecture can provide quantum random-access memory any near the scale needed for BHT. Some more recent research has proposed variants or trade-offs that reduce the quantum memory needed (for example, using more quantum computation in place of storage). A 2017 paper by Chailloux et al. presented a more memory-efficient quantum collision search algorithm, but even these “improved” methods still require extremely large (if somewhat lower) quantum memory and their overall runtime remains high.

In essence, quantum collision finding doesn’t scale well when all costs are accounted. This reality is acknowledged in cryptographic standards circles: for instance, one analysis notes that BHT’s memory demands are unrealistically large, which is probably why NIST did not specify a reduced quantum complexity in the definitions of security levels 2 and 4 (the levels related to hash collisions). Instead, as we’ll see next, NIST treats collision resistance largely from a classical-cost perspective, given the lack of practical quantum speedup.

NIST’s Analysis and Security Level Assessments

NIST (National Institute of Standards and Technology) has been actively evaluating the impact of quantum algorithms, including Grover’s and BHT, on cryptographic security. As early as the NISTIR 8105 “Report on Post-Quantum Cryptography” (2016) and subsequent documents, NIST recognized that hash functions and symmetric ciphers are affected differently by quantum attacks. They explicitly note the theoretical complexity distinctions (preimage search vs collision search) and also emphasize a more comprehensive cost-based analysis rather than just counting exponents.

When NIST launched its Post-Quantum Cryptography (PQC) standardization project, it defined five security strength categories. These were deliberately tied to well-understood reference problems involving both classical and quantum attacks. Notably:

• Category 1 was defined as security at least as hard as breaking AES-128 by brute-force (exhaustive key search). In the quantum context, Grover’s algorithm can theoretically break AES-128 in about 2⁶⁴ steps. However, NIST defines Category 1 based on the high practical cost (in terms of quantum gates and circuit depth) required to execute this attack. This is the baseline “low” post-quantum security level.
• Category 2 was defined as security at least as hard as finding a collision in SHA-256. Classically, that means ~2¹²⁸ hash operations (birthday attack). Quantumly, in theory, the BHT algorithm could find a SHA-256 collision in ~2⁸⁵ operations. However, and this is key, NIST treated this collision problem in terms of practical cost, effectively assuming that no efficient quantum speedup (beyond classical cost) would be realized for collision-search. Indeed, NIST’s call for PQC submissions defined the hardness of Level 2 based on an estimated cost of 2¹⁴⁶ classical gates to find a collision in SHA-256. Implicitly, when accounting for the massive memory and hardware requirements of BHT, no known quantum attack significantly improves upon that overall cost. In other words, they assumed for security category purposes that breaking SHA-256 remains a very hard task (comparable to AES-128) even with quantum, due to the BHT algorithm’s impracticality.
• Category 3 corresponds to AES-192 key search (harder than SHA-256 collisions), and Category 4 corresponds to SHA-384 collision resistance. SHA-384 has a 384-bit output, giving 192-bit classical collision strength and ~128-bit under BHT. Category 5 corresponds to AES-256 key search (or equivalently 256-bit key, ~128-bit security even under Grover). Categories 4 and 5 thus both target ~128-bit quantum-security, achieved either through a larger hash or a larger key.

The above mapping shows that NIST did account for the BHT algorithm’s existence in setting these categories. For example, they placed SHA-256 collision resistance as a lower security category (Level 2) than AES-192 (Level 3), reflecting that theoretically 256-bit hash collisions are easier to achieve (2⁸⁵ quantum steps) than a 192-bit key search (2⁹⁶ quantum steps). In fact, NIST noted that “a brute-force collision attack on SHA-256 will be feasible before a brute-force key search on AES-192”, hence the ordering of categories.

However, NIST’s cost-based approach adds an important nuance. Rather than simply trusting the O(2⁸⁵) vs O(2⁹⁶) theoretical gap, they considered the actual resources needed. Because the BHT attack needs enormous quantum memory and circuit size, NIST did not explicitly assign a reduced quantum gate count to collision attacks akin to how they did for Grover’s key search. In their reference estimates, NIST gave a ballpark figure for breaking SHA-256 via collision: ~2¹⁴⁶ classical gates (and implicitly, no known quantum attack that improves upon that). By contrast, for AES-128 key search they estimated ~2¹⁷⁰ quantum logical gates (if done serially) or effectively less if massive parallelism is used. The takeaway is that NIST views quantum collision-finding as not offering a meaningful speedup in practice, given current understanding. Thus, they are comfortable considering SHA-256 as providing adequate protection at Security Level 2 (roughly equivalent to the effort of breaking AES-128) once practical constraints are included. In fact, NIST’s official guidance (e.g. SP 800-57) has stated that AES-128 and SHA-256 are expected to remain secure beyond 2030 for most applications, acknowledging the existence of Grover/BHT but judging them cost-prohibitive for the foreseeable future.

To summarize NIST’s stance: theoretical vulnerability does not automatically equate to practical vulnerability. The BHT algorithm might reduce the asymptotic exponent, but unless quantum computers with massive stable memory emerge, SHA-256 is not significantly easier to break than it would be classically. NIST’s PQC project incorporated BHT into its reasoning by making collision-resistance a separate security category, yet at the same time, NIST’s cost modeling effectively neutralized BHT’s impact by treating its resource requirements as prohibitively high.

Should We Worry About BHT Attacks Now?

For most practitioners and use-cases today and in the near future, the BHT algorithm is more of a theoretical concern than an imminent threat. There are several reasons why one might not lose sleep over BHT in the current era:

• Quantum Computers Are Not There Yet: As of 2025, quantum computers are still far from the scale needed to perform Grover’s algorithm on 2⁶⁴ operations (for AES-128) let alone to implement the BHT algorithm on 2⁸⁵ operations with huge memory. We are decades away from cryptanalytically relevant quantum machines that could attempt something like a SHA-256 collision search. This means our current hash functions and symmetric keys are safe from direct quantum brute-force for the time being.
• Memory Remains a Huge Bottleneck: Even optimistic roadmaps for quantum computing focus on qubit counts and error rates, but the quantum RAM needed for BHT is a qualitatively different challenge. Creating a random-access quantum memory of size 2⁸⁵ (or even vastly smaller) is not even on the horizon. Many experts suspect we may never see such a memory, or if we do, it would be one of the last milestones in the development of full-scale quantum computers.
• Classical Attacks Still Rule for Collisions: If someone wanted to break a hash function’s collision resistance today, they wouldn’t bother with nascent quantum algorithms – they would use classical cryptanalysis or brute force techniques (e.g., distinguished-point collision search, parallel rho method, or try to find structural weaknesses in the hash). Those methods are currently far cheaper and more effective than any quantum approach. In fact, as discussed, the best known quantum approach to collision-finding doesn’t beat optimized classical parallel attacks in cost. Until quantum technology achieves certain leaps, BHT offers no real shortcut for attackers.
• NIST’s Confidence in SHA-256: NIST still assigns SHA-256-based constructions to security Category 2 (which they deem acceptable for 128-bit security in a post-quantum sense). They have not warned against using SHA-256 in a post-quantum world for general applications – quite the opposite, NIST expects SHA-256 to hold up at least until we approach the limits of currently envisioned quantum tech. (For example, NIST’s draft recommendations have allowed AES-128 and SHA-256 usage beyond 2030 with the understanding that quantum attacks are not yet practical threats in that timeframe.)

In summary, if you are a cybersecurity professional or developer, you do not need to immediately drop all 256-bit hashes or 128-bit keys due to BHT. The algorithm is an important theoretical consideration for long-term cryptographic planning, but it is not something that undermines current systems in practice. As of now, no adversary has the capability to execute such a collision-finding attack, and it’s unlikely they will for a long time.

Future-Proofing and Recommendations

Even though BHT is impractical today, forward-looking security planning should still account for its implications. Systems that require long-term security (10–20+ years into the future) or protect highly sensitive data might consider a conservative approach:

• Use Larger Hash Functions for Critical Systems: To hedge against future advances, you can choose hash functions with longer outputs. For instance, using SHA-384 or SHA-512 (or the 512-bit output of SHA-3) instead of SHA-256 ensures that even a BHT-style quantum collision attack would need on the order of 2¹²⁸ steps (providing ~128-bit post-quantum collision security). This aligns with recommendations from high-security agencies. In fact, the U.S. National Security Agency’s Commercial National Security Algorithm (CNSA) Suite 2.0 guidance (for classified and national security systems) explicitly mandates using SHA-384 or SHA-512 for hashing, citing the need for a full 128-bit security margin against quantum collision attacks. If your data must remain secure for many decades, it’s wise to follow this lead and avoid 256-bit hashes for new systems, opting for 384-bit or higher. The performance cost of larger hashes is usually minimal for most applications, and it provides a cushion against uncertainty in quantum progress.
• Use Larger Symmetric Keys for Long-Term Security: Similarly, while AES-128 is considered safe for now (Grover’s algorithm reduces its effective strength to ~64-bit complexity, though the practical cost remains high), using AES-256 is a cheap way to double the key length and ensure ~256-bit classical / 128-bit quantum security. Many organizations are already standardizing on AES-256 for future-proofing. NIST’s and NSA’s post-quantum recommendations both favor 256-bit keys for symmetric encryption (and 256-bit primitives like SHA-256 or SHA3-256 for MACs) as a baseline, since doubling the key length counters Grover’s algorithm’s effect. Essentially, if you can choose a 256-bit key or algorithm, doing so is a prudent move for long-lived systems.
• Monitor Quantum Computing Developments: The landscape can change if breakthroughs occur in quantum memory or algorithmic techniques. Researchers are continuously refining quantum algorithms (e.g., trying to reduce BHT’s memory requirements) and hardware is gradually improving. Organizations should stay updated with the latest guidance from NIST’s PQC program and other authorities. NIST’s PQC standards (expected to be finalized by 2024–2025) will include new asymmetric algorithms designed to be safe against quantum attacks. Alongside those, NIST will likely issue recommendations for symmetric key sizes and hash functions to use in a post-quantum world. Thus far, their position has been that current symmetric primitives just need a modest increase in size (if that) to withstand quantum attacks. Keep an eye on official communications – for example, if one day large-scale quantum computers appear more imminent, NIST might suggest transitioning to SHA-384/512 for broader use, echoing NSA’s cautious stance.
• Crypto Agility: Design your systems with crypto agility in mind. This means it should be relatively easy to swap out algorithms and parameters. If, for example, a new discovery made quantum collision-finding easier (or a new quantum algorithm faster than BHT emerged), you’d want the ability to move to larger hashes or different constructions without a complete system overhaul. Protocols and software that can support multiple hash sizes or have versioning for algorithms will be in a better position to adapt.

In practice, for most applications today, the recommendation is to continue using standard approved algorithms (like SHA-256, HMAC-SHA-256, AES-128/256, etc.) as per current guidelines, since they are still considered safe against quantum attacks in the near term. But for new systems that aim to be crypto-secure for many years, it does no harm – and potentially much good – to choose the larger security parameter (e.g., SHA-384 over SHA-256, AES-256 over AES-128) to account for the worst-case quantum scenario. The performance differences are usually small, and you align with the highest security level (Category 5 or CNSA-grade) from the start.

Conclusion

The Brassard–Høyer–Tapp (BHT) algorithm is a fascinating example of how quantum computing can change the rules of cryptography – in this case, by speeding up collision searches for hash functions beyond the classical limit. The existence of BHT means that, in theory, some hash functions (like 256-bit hashes) have a lower security margin against quantum adversaries than one might assume if only considering Grover’s algorithm. This has informed how we categorize post-quantum security levels and how we plan for a future with quantum computers. NIST has analyzed BHT’s impact and effectively concluded that while the algorithm lowers the exponent in theory, its practical cost is so high that it does not undermine the security of today’s hash standards at present. Consequently, NIST’s current guidance and security categorizations take BHT into account but do not deem it an urgent threat. For most users, this means SHA-256 and similar primitives remain safe to use, and the sky is not falling.

That said, cryptographers and security agencies are not ignoring the BHT algorithm either. For systems with long-term secrets or extreme security requirements, the cautious approach (advocated by bodies like NSA’s CNSA 2.0) is to assume the worst-case quantum capabilities and choose algorithms accordingly – e.g., favoring hash functions with larger output (384+ bits) and using the maximum key sizes available, to retain a comfortable security margin against even BHT-type attacks. This duality of perspectives – theoretical vs practical – is reflected in how standards are being developed: NIST’s post-quantum effort balances optimism about practical constraints with contingency plans for stronger cryptographic options.

In conclusion, we do not “have to worry” about BHT in our day-to-day security just yet, but we do have to plan for a future where quantum attacks are possible. By understanding algorithms like BHT and Grover, we can make informed decisions: either trust the current assessments (which say these attacks are expensive and unlikely to be realized soon) or take a conservative stance by using bigger keys and hashes proactively. In either case, awareness is key. The BHT algorithm serves as a reminder that the cryptographic landscape can shift with new computational models, and staying ahead of that curve – through research, standardization, and agile security designs – is the best defense.