Background
When thinking about quantum computing, the focus is on Shor’s algorithm impacting ECC, and to a lesser extent Grover’s algorithm impacting hash functions.
If I understand correctly, Grover’s algorithm can theoretically find a preimage with the square root of the operations of a classical computer, in other words the bits of security is cut in half (e.g. HASH160 addresses are reduced to 80 bits of security, and P2WSH addresses are reduced to 128 bits of security).
Since 128 bits is secure, SHA256 still appears secure in a world with Grover’s algorithm.
Question
However I learned about the Brassard-Høyer-Tapp (BHT) algorithm as well, which is relevant to finding collisions. It seems that it could reduce the collision security of SHA256 from half the bits (birthday paradox) to one third of the bits, about 85 bits, which is below typical standards.
There is at least one context where a collision attack is relevant: in a collaborative multisignature scenario. In fact this scenario is what prompted P2WSH avoiding HASH160 (80 bits of collision security) and instead just use SHA256 (reference).
It’s a bit of a niche issue (it seems to have been overlooked when designing P2SH) and I haven’t seen mention of it in the post-quantum discussions. In fact, I wonder if the current version of proposed BIP 360 overlooks this, because the proposed P2TSH address follows BIP 173, using only 32 bytes (256 bits). But could this abstract issue warrant a larger address, like was done with P2WSH?
Related articles
