Quote from: DeathAndTaxes on March 16, 2012, 07:32:43 PM

Quote from: wyager on March 16, 2012, 07:26:47 PM

If I'm not mistaken, isn't Bitcoin ownership and signage based on elliptic-curve cryptography, and therefore vulnerable to Shor's algorithm?

I'm probably wrong; I'm a crypto noob and the explanations I've found of Bitcoins crypto system confused me.

Yes... Kinda.

However Shor's algorithm requires you to know the public key. The address is a hash w/ cheksum of the public key. However once you send funds FROM an address the public key is in the blockchain. One could harden themselves by only using addresses once thus no funds are in any address which has a known public key.

No public key = no input for Shor's algorithm.

If quantum computing became powerful enough it would require changes in how you used Bitcoin not necessarily Bitcoin itself. Users, merchants, clients would need to adopt procedures that ensure addresses are used only once and funds never remain in an address with a known public key for long.

OK, that's what I thought. We could also replace elliptic curve crypto with lattice-based or some other post-quantum crypto.

We also have to worry about hash collision detection; I believe collision detection on quantum computers is an ongoing field of study.