Post-quantum preimage resistance of HASH160 addresses

Question

It is well understood that quantum computers could make finding 256-bit hash-collisions feasible, and that they could break elliptic-curve public key encryption currently used in Bitcoin. It is also well understood that 160-bit addresses are not collision-resistant, however that is not really a problem for common applications (P2PKH).

What about addresses where the public key was never revealed, would they be safe at rest? Currently HASH160 addresses have 160-bits of security against preimage attacks, but QCs could theoretically bring it down to 80 bits which would be in the "danger zone".

A successful preimage attack would not necessarily yield the original public key, but in the scenario where QCs would be capable of cracking 160-bit hash preimages then they could also trivially find a private key of whatever public key the preimage attack would yield, so some sort of constrained-size quantum preimage search would do?

The only literature I found discussing this is this multi-breakage section in Giechaskiel, I., Cremers, C., Rasmussen, K.B. (2016). On Bitcoin Security in the Presence of Broken Cryptographic Primitives.

Answer 1

We could design a black box function to break both P2PKH and P2SH (and P2WSH, etc.) addresses in 2^80 single-threaded quantum computer cycles. Assuming a clock speed on scale of GHz, this would take about 10 million years. Important to note is that splitting the work and doing it in parallel is not as beneficial as with classic computers because it would offer only a quadratic speedup (Fluhrer, S., Reassessing Grover's Algorithm). In other words, doing the work in 1 year would require building 100 trillion quantum computers because sqrt(100T) == 10M. Therefore, we can say that breaking a 160-bit hash preimage is physically possible because 10M years is a finite amount of time and less than age of the universe. However, it is still infeasible.

Breaking P2PKH

Output locking script template is:

OP_DUP OP_HASH160 OP_DATA_20 pubkey-hash-20 OP_EQUALVERIFY OP_CHECKSIG

so cracking it with a hypothetical quantum computer would require running Grover's algorithm to find some x such that hash160(x) == pubkey-hash-20. Once we'd find x, we'd then apply a much easier Shor's algorithm to find the secret key. The revealed keypair would most likely not be the original keypair, however it wouldn't really matter since the key authentication part of the Script would evaluate to true for any key that would satisfy hash160(x)=pubkey-hash-20.

Breaking P2SH

Output locking script template is:

OP_HASH160 OP_DATA_20 redeem-script-hash-20 OP_EQUAL

however the actual redeem script will be evaluated after authentication against the hash, and it must also pass validation. Therefore, finding any random x such that hash160(x) == redeem-script-hash-20 won't do, because it will most likely be an invalid redeem script. To address this, we could perform a Grover's search for a particular template. We'd do that by designing a function like f(x) = 0x21 || x || 0xac and then crack the composite function hash160(f(x)) as our black box function. The raw bytes appended with x in f(x) definition will make our redeem script match the pay-to-public-key (P2PK) template:

OP_DATA_33 x OP_CHECKSIG.

With Grover's algorithm we'd find x that satisfies hash160(f(x)) = redeem-script-hash-20, and then we'd apply Shor's algorithm to crack the secret key of x. Finally, we could then spend the funds with the public key, signature, and the P2PK redeem script (redeem-script=f(x)).

The discovered redeem script would most likely not be the original redeem script, however it wouldn't really matter since the redeem script authentication part would evaluate to true for any redeem script that would satisfy hash160(redeem-script)=redeem-script-hash-20.

Afterthoughts / potential optimization

I think we could optimize it by embedding public key generation as another function in the composite so we won't need Shor's algorithm at all, because we'd find the secret key directly:

1. Define a function g(x)=p that maps a secret key to a public key.
2. Run Grover's on hash160(f(g(x))) = redeem-script-hash-20

some matching x will be a secret key that satisfies all the requirements, then we compute g(x) to get the public key, then f(g(x)) to get the redeem script, which will be acceptable way to spend because the hash will match that of the address.