Quote from: Foxpup on December 17, 2012, 11:45:34 AM

Quote from: Revalin on December 17, 2012, 09:17:54 AM

Quote from: greyhawk on December 17, 2012, 09:05:59 AM

I thought Shor's algorithm will break elliptic curve encryption once quantum computers are sufficiently large?

It just cuts the effective key size in half. The current 160-bit signatures will be brute forced in 2^80 operations. That sounds weak, but it's going to be a long time before quantum computers reach 160-bit levels (if ever), and even when they do the operations per second will be very low and 2^80 will be infeasible for a long time thereafter.

You're thinking of Grover's algorithm. Shor's algorithm does indeed break ECDSA in polynomial time, though we're a very long way off a useful implementation. And note that Bitcoin public keys are 256 bits, not 160 bits - the hash is 160 bits, but this is not broken by Shor's algorithm.

You are correct. The lame thing is I actually know that. https://bitcointalk.org/index.php?topic=54542.msg651428#msg651428

tl;dr: ECDSA will break terribly, but we can use another pubkey algorithm if necessary, and all addresses with no spent coins should be safe since they're also protected by the hashes.