<p>Crypto currencies such as bitcoin will always be a step ahead.</p>

<p><a href="http://en.wikipedia.org/wiki/Post-quantum_cryptography/" rel="nofollow">Post-quantum Cryptography</a> is already being researched to combat quantum computers before they have even evolved enough to be considered a threat.</p>

CC BY-SA 3.0
2013-07-09T23:10:11.513Z
2013-07-09T23:10:11.513Z
Bill
<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-04-27T19:25:02.900Z
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
CC BY-SA 3.0
2013-04-27T19:31:59.407Z
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
CC BY-SA 3.0
2013-04-27T19:34:06.040Z
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
CC BY-SA 3.0
2013-04-27T19:34:31.573Z
Ah. So the _protocol_ is quantum-proof, just that the _standard protocol_ (the in-built script that all clients use) is not.
Manishearth
CC BY-SA 3.0
2013-04-27T19:35:34.547Z
Basically, yeah. The protocol is just a script that communicates signatures and hashes - what algo you choose to do the signing and hashing can be swapped out lego-style.
David Perry
CC BY-SA 3.0
2013-04-27T19:42:28.613Z
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
CC BY-SA 3.0
2013-04-27T19:22:00.993Z
2013-04-27T19:30:51.323Z
2013-04-27T19:30:51.323Z
David Perry
<p>Assuming that quantum computers are implemented some time in the near-ish future, how vulnerable is Bitcoin to decryption via <a href="http://en.wikipedia.org/wiki/Quantum_algorithm" rel="noreferrer">quantum algorithms</a>? For example, <a href="http://en.wikipedia.org/wiki/Shor%27s_algorithm" rel="noreferrer">Shor's algorithm</a> enables a quantum computer to prime factorize in polynomial time. A variant of it <a href="https://security.stackexchange.com/questions/34940/is-ecdsa-breakable-by-quantum-computers">can crack ECDSA</a>.</p>
<p>However, Bitcoin relies on a <a href="https://en.bitcoin.it/wiki/Script" rel="noreferrer">scripting system</a>, so if quantum computers are created, one probably can just switch to a secure script<sup>1</sup></p>
<p>Is Bitcoin vulnerable to attacks from quantum computers? Are these vulnerabilities fixable<sup>2</sup>?</p>
<p><sup>1.  Then again, there are limits to scripting and quantum computing may make it impossible for any script to work.</sup></p>
<p><sup>2. &quot;Fixable&quot; 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.</sup></p>

CC BY-SA 3.0
2013-04-27T18:49:58.380Z
relevant (foud out about it after I posted the question): http://pqcrypto.org/
Manishearth
CC BY-SA 3.0
2013-04-29T18:00:59.603Z
Related: http://bitcoin.stackexchange.com/questions/6062/what-effects-would-a-scalable-quantum-computer-have-on-bitcoin
halftimepad
<security><script><ecdsa><quantum-computing>
How vulnerable is bitcoin to quantum algorithms?
Manishearth
# How vulnerable is bitcoin to quantum algorithms?

(Asked by: username_0 on 2013-04-27)

Assuming that quantum computers are implemented some time in the near-ish future, how vulnerable is Bitcoin to decryption via [quantum algorithms](http://en.wikipedia.org/wiki/Quantum_algorithm)? For example, [Shor's algorithm](http://en.wikipedia.org/wiki/Shor%27s_algorithm) enables a quantum computer to prime factorize in polynomial time. A variant of it [can crack ECDSA](https://security.stackexchange.com/questions/34940/is-ecdsa-breakable-by-quantum-computers).

However, Bitcoin relies on a [scripting system](https://en.bitcoin.it/wiki/Script), 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.

**Tags:** security, script, ecdsa, quantum-computing

> **Comments:**
> **username_0**: relevant (foud out about it after I posted the question): http://pqcrypto.org/  
> **username_1**: Related: http://bitcoin.stackexchange.com/questions/6062/what-effects-would-a-scalable-quantum-computer-have-on-bitcoin  

---

## 2 answers

### Answer by username_3 on 2013-04-27. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: 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)  
> **username_3**: 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.  
> **username_3**: 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.  
> **username_0**: Ah. So the _protocol_ is quantum-proof, just that the _standard protocol_ (the in-built script that all clients use) is not.  
> **username_3**: Basically, yeah. The protocol is just a script that communicates signatures and hashes - what algo you choose to do the signing and hashing can be swapped out lego-style.  
> **username_0**: 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?)  

---

### Answer by username_2 on 2013-07-09. Score: 3

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

[Post-quantum Cryptography](http://en.wikipedia.org/wiki/Post-quantum_cryptography/) is already being researched to combat quantum computers before they have even evolved enough to be considered a threat.


---

