Quote from: BlueSword on October 08, 2017, 08:56:02 PM

To brute-force pre-image resistance of hash functions such as SHA256, a quantum computer would still need to perform a number of operations proportional to the square root of the number of operations performed by a normal computer. Therefore, simply doubling the number of bits (e.g., switching from SHA256 to SHA512) would provide quantum-resistant security equivalent to existing security against normal computers. (Note that sqrt(2^512) = 2^256.)

No need to move to SHA512, because bitcoin security is currently 128 bits for solving the ECDSA problem. After efficient quantum computers finally become available (if ever) the SHA256 will still be as secure as ECDSA is now, which is 128 bits. And I assume quantum computers will be much slower in trying out 2^128 different possibilities than 1000:s of current computers counting in parallel are.

Quote from: BlueSword on October 08, 2017, 08:56:02 PM

The vast majority of Bitcoin UTXOs include only a hash of a ECDSA public key, not the ECDSA key itself. Therefore, if the public key has not already been revealed, an attacker would need to (1) sniff a transaction as it is entered into the mempool, (2) crack the private key, (3) create a new transaction using the private key, and (4) get this new transaction committed to a block before the legitimate owner's transaction. To guard against this attack, Bitcoin would need to add support for quantum-resistant asymmetric cryptography. Unfortunately, this field is still immature, and existing quantum-resistant asymmetric cryptographic schemes (see, e.g., https://en.wikipedia.org/wiki/Post-quantum_cryptography) are much less practical than ECDSA. But it is likely that they will develop to be the point of being practical before quantum computing poses a severe risk to Bitcoin. In fact, it is not even known for sure that quantum computing will ever economically scale to the point where it can attack 256-bit ECDSA.

Yep. It depends on how long it would take for a quantum computer to solve ECDSA. If it takes more than 30min, then it will still be too slow for this approach. (at least if the transaction was made with sufficient transaction fee)

Would be interesting to know how secure P2SH is against quantum computers. Because it does not necessarily use ECDSA.