Quote from: haltingprobability on December 24, 2017, 06:55:43 PM

Quote from: nullius on December 24, 2017, 06:39:37 PM

Quote from: haltingprobability on December 24, 2017, 05:55:57 PM

In fact, this is why Bitcoin uses the public-key hash instead of the public-key itself and recommends against address-reuse; in the event of working, at-scale QC, your coins are still secured behind 128-bit-equivalent security as long as you don't reuse addresses or publish the public-keys for your addresses.

0. Actually, that would be 160-bit equivalent security, yes?

No, because the Bitcoin address is RIPEMD160(SHA256(pubkey)), with some additional protocol things tacked onto it. If you can find some reduction of SHA256 to RIPEMD160 such that you can recover any SHA256 preimage more or less for free from the RIPEMD160 preimage, then it would be 160-bit equivalent security. The 128-bit number comes from dividing 256 by two on the assumption that the best way to brute-force a Bitcoin address with a QC is to break the RIPEMD160 (I'm counting this as zero-cost) and then break the SHA256 (I'm counting this as 256-bit / 2 security = 128-bits security).

I think I see what you mean. I got wrong what I said in my nit; but I now have another. Please correct me if I messed up something else here; I think that breaking a keyhash found on blockchain would require the following steps, in this order:

0. Its impossible to recover 256 bits of pseudorandom anything from 160 pigeonholes; so I will infer that to be, find any P0 of the many 256-bit preimages for a given RIPEMD160 hash. With a quantum computer, consider that to be the equivalent of an 80-bit problem. Not what I would call zero.

1. Then, find a string P1 which is a valid secp256k1 public key, and is a SHA256 preimage for the SHA256 image P0. I will wave my hands around various factors which make the search easier by expanding the search set (compressed or uncompressed public keys double the possibilitiesbut only if the output is not for a Segwit address) or harder (need a valid secp256k1 pubkey, not an arbitrary bitstring). For the reason you stated, count this as the equivalent of a 128-bit problem.

2. Wield the almighty Quantum Computer to break the public keythus revealing a private key which can spend for a public key which SHA256 hashes to a bitstring which hashes to the RIPEMD160 hash specified in the Bitcoin output. Breaking the public key would still not be free. I dont know how to quantify that in bits of security.

SoI see the equivalent of 208+x bits of quantum computer work. Did I get it right here?

Quote from: haltingprobability on December 24, 2017, 06:55:43 PM

Mostly agreed. AFAIK, no one has ever shown any evidence that a PGP public key has ever been brute-forced to its private key. I would imagine that the NSA may have built equipment capable of doing that, among other things, if for no other reason than for research purposes, to probe the limits of what's possible (because, the Russians, of course).

Even if they could, why bother to ever apply the fruits of that hypothetical research? Endpoint security is so awful, and rubber hoses/$5 wrenches/long prison sentences are readily available.

Thats another point which should be well remembered by the people worried about hypothetical future post-quantum attacks on Bitcoin: Malware, kidnappings, and similar attacks are the biggest vulnerability for the average user today. Do you even know how to properly secure a computer against even the stupidest commodity skiddie coin stealer? Do you brag about th size of your coin stash on Internet forums, under the doubly false presumption that both Internet posts and bitcoins be anonymous? Dont worry so much about threats which do not currently exist and may perhaps never exist, when shoot your own foot off every day.