10

Assuming that quantum computers are implemented some time in the near-ish future, how vulnerable is Bitcoin to decryption via quantum algorithms? For example, Shor's algorithm enables a quantum computer to prime factorize in polynomial time. A variant of it can crack ECDSA.

However, Bitcoin relies on a scripting system, so if quantum computers are created, one probably can just switch to a secure script1

Is Bitcoin vulnerable to attacks from quantum computers? Are these vulnerabilities fixable2?

1. Then again, there are limits to scripting and quantum computing may make it impossible for any script to work.

2. "Fixable" can both be client-side fixable, where everyone just tweaks the script they use and transfers all their money to a clean set of addresses (thus securing all their bitcoins with the new script), or protocol-side fixable, where the protocol is tweaked and everyone downloads a new client. The latter is nor preferable, since the old bitcoins will probably be lost in the process.

|improve this question
6

In short, yes, Bitcoin would be vulnerable to some variation of Shor's algorithm and quantum computing, as would basically every kind of crypto we use today. While ECDSA uses the elliptic curve discrete logarithm problem for its security, rather than the prime number factorization problem, you are correct in stating that a variant of Shor's can be used to solve the ECDLP in similar time. I believe there are similar threats with regard to SHA256, which is heavily used in Bitcoin's mining process.

You are also correct in stating that Bitcoin relies on a scripting system and is itself an open-source distributed computing project. Assuming you can arrive at a network consensus it is absolutely possible to change basically any aspect of Bitcoin - you just have to get the whole rest of the network to agree with you. I don't imagine that would be an issue if ECDSA or SHA256 were broken.

It's also entirely possible that the whole project itself could be forked to create an alternate version of Bitcoin similar to others which already exist. There is a variant called Litecoin, for example, which uses scrypt instead of SHA256 for mining - implementing an alternative to ECDSA could be easily done in a similar manner.

This, perhaps, is the true brilliance of Bitcoin: it's a Pandora's box that cannot be un-opened. Bitcoin as it exists today may or may not exist in a decade. Perhaps there is some unforeseen flaw that will soon be discovered, but that flaw will be fixed and the idea will live on. Assuming that there is any reasonable encryption/signing algorithm that is safe from quantum computing, it will be adopted and the cryptocurrency world will move on.

|improve this answer
  • If ECDSA was broken, would the fix involve just telling everyone to use a better script? Or does a better script not exist? (after all, the addresses depend on ECDSA as well) – Manishearth Apr 27 '13 at 19:25
  • 2
    Yes and no. "telling everyone" implies that there is a central authority where there is none. That said, if the devs came out and said "crap guys, ECDSA is broken, here's a new version with a different algorithm, please please install it" I think most people would tend to listen. – David Perry Apr 27 '13 at 19:31
  • Realistically, I think such a break would more likely result in the migration from one blockchain to another. If SHA256 were broken, for example, I would foresee a migration to Litecoin before I would guess at a modification to Bitcoin. This is the one and only redeeming virtue I see in the altcoins, though that's just personal opinion. You're welcome to prefer what you like, I'm just happy cryptocurrency doesn't exist as a monoculture any more. – David Perry Apr 27 '13 at 19:34
  • Ah. So the protocol is quantum-proof, just that the standard protocol (the in-built script that all clients use) is not. – Manishearth Apr 27 '13 at 19:34
  • 1
    Hmm. Wouldn't all scripts be ECDSA dependent, though? The bitcoin addresses (public/private key pairs) are ECDSA. Or is it possible to abandon ECDSA and talk about a new set of key pairs just by changing the script? (Basically, are there any references to the btc address outside of a script block?) – Manishearth Apr 27 '13 at 19:42
3

Crypto currencies such as bitcoin will always be a step ahead.

Post-quantum Cryptography is already being researched to combat quantum computers before they have even evolved enough to be considered a threat.

|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.