Elliptic Curves subject to Quantum Computer attacks, ramifications for Bitcoin?

[tspacepilot]

I saw this in Slashdot yesterday:


http://it.slashdot.org/story/15/09/09/1938206/cryptographers-brace-for-quantum-revolution

Tokolosh writes:
An article in Scientific American discusses the actions needed to address the looming advent of quantum computing and its ability to crack current encryption schemes. Interesting tidbits from the article: "'I'm genuinely worried we're not going to be ready in time,' says Michele Mosca, co-founder of the Institute for Quantum Computing (IQC) at the University of Waterloo..." and "Intelligence agencies have also taken notice. On August 11, the US National Security Agency (NSA) revealed its intention to transition to quantum-resistant protocols when it released security recommendations to its vendors and clients." Another concern is "intercept now, decrypt later", which presumably refers to the giant facility in Utah.
In related news, an anonymous reader points out that the NSA has updated a page on its website, announcing plans to shift the encryption of government and military data from current cryptographic schemes to new ones that can resist an attack by quantum computers.

Then I looked a bit at the wikipedia page on elliptic curve cryptography and it seems that ECC is especially vuneralble to quantum attacks compared to RSA crypto of equivalent key lengths.  From what I understand, the main advanage to date of ECC over RSA is that you can get equivalent security for shorter key-lengths.  A 256bit ECC key is supposed to provide security on the order of like a 1028bit RSA key. However, apparantely quantum computers nullify this advanage.

Does this have ramifications for bitcoin?  In a worst-case scenario in which our fundamental crypto is broken, would bitcoin be able to upgrade the protocol to use a different crypto system?  How would the UTXO set be secured?

Thanks in advance for educating me you guys.

[1714967318]

1714967318

[1714967318]

1714967318

[1714967318]

1714967318

[1714967318]

1714967318

[1714967318]

1714967318

[shorena]

I saw this in Slashdot yesterday:


http://it.slashdot.org/story/15/09/09/1938206/cryptographers-brace-for-quantum-revolution

Tokolosh writes:
An article in Scientific American discusses the actions needed to address the looming advent of quantum computing and its ability to crack current encryption schemes. Interesting tidbits from the article: "'I'm genuinely worried we're not going to be ready in time,' says Michele Mosca, co-founder of the Institute for Quantum Computing (IQC) at the University of Waterloo..." and "Intelligence agencies have also taken notice. On August 11, the US National Security Agency (NSA) revealed its intention to transition to quantum-resistant protocols when it released security recommendations to its vendors and clients." Another concern is "intercept now, decrypt later", which presumably refers to the giant facility in Utah.
In related news, an anonymous reader points out that the NSA has updated a page on its website, announcing plans to shift the encryption of government and military data from current cryptographic schemes to new ones that can resist an attack by quantum computers.

Then I looked a bit at the wikipedia page on elliptic curve cryptography and it seems that ECC is especially vuneralble to quantum attacks compared to RSA crypto of equivalent key lengths.  From what I understand, the main advanage to date of ECC over RSA is that you can get equivalent security for shorter key-lengths.  A 256bit ECC key is supposed to provide security on the order of like a 1028bit RSA key. However, apparantely quantum computers nullify this advanage.

Does this have ramifications for bitcoin?  In a worst-case scenario in which our fundamental crypto is broken, would bitcoin be able to upgrade the protocol to use a different crypto system?  How would the UTXO set be secured?

Thanks in advance for educating me you guys.

I hope LaudaM chimes in.

Bitcoins main defense against quantum attacks are the hashes. Assuming ECC is broken and a private key can be calculated from a public key within reasonable time, youd still have to get the public key first. Since the address used are not public keys and the public key is only revealed once you signed something. You are "fine" as long as you dont spend your coins and have them on an address that was never used. That would be a very serious problem, but considering that ECC is used not only for bitcoin it might be worse for other systems.

It is certainly possible to switch to an algorithm that is considered to be safe in such an event, but AFAIK its a hard fork.

[moni3z]

DJ Bernstein wrote a book "Post-Quantum Cryptography" which explains what kind of crypto the bitcoin maintainers can use if such a world ever arrives, feel free to read it http://libgen.io/book/index.php?md5=8C2C3D5DAC9B329EF3ED35FE346D78AB

He's also the leading authority on curve side-channel/timing attacks being the author of Curve25519 http://safecurves.cr.yp.to/

There's nothing available right now that can run Shor's/Groovers quantum algorithms and start factoring. https://news.ycombinator.com/item?id=10096943 the D-Wave is just an analysis device for combinatorial/NP-complete problems.

[fenican]

D-Wave is very controversial. Quite a bit of evidence that it is no faster than regular computers and that any efficiency it appears to have in tests appears to be from clever programming not quantum computing.

Goes without saying that Bitcoin kicks D-Wave's ass. If you put every machine D-Wave has ever built to work mining, I doubt the capacity would exceed one $9.95 block erupter. They are that bad.

[tspacepilot]

I hope LaudaM chimes in.

Bitcoins main defense against quantum attacks are the hashes. Assuming ECC is broken and a private key can be calculated from a public key within reasonable time, youd still have to get the public key first. Since the address used are not public keys and the public key is only revealed once you signed something. You are "fine" as long as you dont spend your coins and have them on an address that was never used. That would be a very serious problem, but considering that ECC is used not only for bitcoin it might be worse for other systems.

It is certainly possible to switch to an algorithm that is considered to be safe in such an event, but AFAIK its a hard fork.

Looking forward to what LaudaM might offer.  I guess I more or less have the same understanding as what you expressed, Shorena.

I guess my question was mainly aimed at that "hard fork" you were talking about.  It seems like it woulnd't be enough to merely switch to a new signature algorithm, because what about all the old UTXOs that are only secured with the broken signatures (and whose pubkeys have been revealed)?  Wouldn't there have to be some desperate action to keep all of those vunerable UTXOs from being spent by an attacker?

Anyway, I'm not too worried about this scenario, I'm just curious to here from people with a better understanding than me exactly what the ramifications might be for changing sig algos.

[harrymmmm]

D-Wave is very controversial. Quite a bit of evidence that it is no faster than regular computers and that any efficiency it appears to have in tests appears to be from clever programming not quantum computing.

Goes without saying that Bitcoin kicks D-Wave's ass. If you put every machine D-Wave has ever built to work mining, I doubt the capacity would exceed one $9.95 block erupter. They are that bad.

Dwave computers are optimizing machines; they perform simulated annealing for the purpose.
It's still unsure if there's any actual quantum entanglement involved in their operation I believe.
Physicists call them 'quantum' annealers, just in case.
Either way tho, they are far from a general purpose quantum computer and provide no ability to run such algorithms.

[tspacepilot]

Right, okay, but folks, the actual state of quantum computers is sort of a side issue to my main topic here.  I'm interested in how the plan would go for changing bitcoin's signature algorithm should such a quantum computer be engineered which makes ECC insecure.  The D-WAVE definitely isn't that computer.  Speculations as to how far off such a computer is/may be aren't too far afield, but getting into the specifics of the D-WAVE isn't what I'm after for this thread.

[Come-from-Beyond]

You are "fine" as long as you dont spend your coins and have them on an address that was never used.

Funny that you will never be able to spend these coins, once you broadcast a transaction the adversary can get your private key and send a double-spending with a higher fee.

[killerjoegreece]

thats a bit worrying for bitcoin. i hope it does not become a reality that soon

[Lauda]

I hope LaudaM chimes in.

Your post is quite well explanatory as well.

A few months ago, when shorena and I engaged in some thread related to quantum computing, I had stated that ECDSA would be our first problem. The Eliptic Curve Digital Signature Algorithm (for those that do not know) is used for signing transactions in Bitcoin. To simplify, if the algorithm gets broken, anyone with a quantum computer could extract a private key from any public key and take the Bitcoin stored on it.

However, this is not even remotely as simple as people seem to think. The public key of an address isn't really made public, but your Bitcoin address is (which is a hash of it). In other words, a quantum computer can't derive the public key from your Bitcoin address. Also by the time someone computes your private key and manages to import it you could already send your funds elsewhere.

Symmetric ciphers are theoretically weakened by quantum computing, but not much and certainly not fatally. Quantum computers could effectively cut symmetric key sizes in half, so a 128-bit key space becomes a 64-bit key space when attacked by a quantum computer, meaning that a QC would need to perform some 2^64 sequential operations, after taking advantage of the parallelism provided by superposition. It's likely that no QC will ever be fast enough to make that feasible. But if one ever is, we can always just bump the key size to 256 bits. Bottom line: symmetric cryptography is not threatened by QC.

This also applies to SHA256 which is a symmetric cipher. There was a number of thread on how this would be exploited. Even if it was, the least of our problems would be Bitcoin. Quantum computers can not even break a 128-bit key (in a short period of time), even though a lot of people here believe otherwise. Quantum computers are not infinitely powerful computers. They just work differently and are better at some tasks while being worse at others than traditional computers.

I would also like to state that I do not think that this is going to be a problem within the next 10-15 years. I'm assuming that is why there isn't that much public talk about this. The developers could work on changing the algorithm and apply that fix within the next hard fork that we're going to have. However, who is to say that the new algorithm won't be vulnerable in 10 years?

If you would like to view the whole creation process of the address (it's not just the following: private key - public key - address), press this link.

Update:

Nonsense.

I wouldn't even know where to begin with your post.

[Kprawn]

The reality would be... If this was successful .....Bitcoin would collapse and all coins will become worthless. The success of Bitcoin is in the demand for it... Who will want BTC if

anyone can take it from you? Who will accept it as payment... if you cannot own it or keep it safe? You would kill the cow, that produce the milk.

The price per Bitcoin will drop to zero. 

[coinplus]

When there is a collusion or any kind of threat for bitcoin private key or for bitcoin address. We need not to worry bitcoin will simply shift to new improved algorithm for the protection of our hard earned bitcoins. Bitcoin's core plan lies on its cryptography.

[tsoPANos]

You are "fine" as long as you dont spend your coins and have them on an address that was never used.

Funny that you will never be able to spend these coins, once you broadcast a transaction the adversary can get your private key and send a double-spending with a higher fee.

Well I disagree with that.
Even a quantum computer will take some time to crack your key, most likely several hours!
Provided with a reasonable transaction fee, your transaction will need no more than 15 minutes to confirm!
We are not there yet, and a hard fork could be scheduled to allow addresses using some kind of post-quantum cryptography.

On the other hand, multi-transaction addresses like public casino hot wallets with lots of coins might be problematic.

[Come-from-Beyond]

Even a quantum computer will take some time to crack your key, most likely several hours!

Where is "several hours" pulled from? On a QC factorization takes near the same time as multiplication.

[Amph]

I saw this in Slashdot yesterday:


http://it.slashdot.org/story/15/09/09/1938206/cryptographers-brace-for-quantum-revolution

Tokolosh writes:
An article in Scientific American discusses the actions needed to address the looming advent of quantum computing and its ability to crack current encryption schemes. Interesting tidbits from the article: "'I'm genuinely worried we're not going to be ready in time,' says Michele Mosca, co-founder of the Institute for Quantum Computing (IQC) at the University of Waterloo..." and "Intelligence agencies have also taken notice. On August 11, the US National Security Agency (NSA) revealed its intention to transition to quantum-resistant protocols when it released security recommendations to its vendors and clients." Another concern is "intercept now, decrypt later", which presumably refers to the giant facility in Utah.
In related news, an anonymous reader points out that the NSA has updated a page on its website, announcing plans to shift the encryption of government and military data from current cryptographic schemes to new ones that can resist an attack by quantum computers.

Then I looked a bit at the wikipedia page on elliptic curve cryptography and it seems that ECC is especially vuneralble to quantum attacks compared to RSA crypto of equivalent key lengths.  From what I understand, the main advanage to date of ECC over RSA is that you can get equivalent security for shorter key-lengths.  A 256bit ECC key is supposed to provide security on the order of like a 1028bit RSA key. However, apparantely quantum computers nullify this advanage.

Does this have ramifications for bitcoin?  In a worst-case scenario in which our fundamental crypto is broken, would bitcoin be able to upgrade the protocol to use a different crypto system?  How would the UTXO set be secured?

Thanks in advance for educating me you guys.

I hope LaudaM chimes in.

Bitcoins main defense against quantum attacks are the hashes. Assuming ECC is broken and a private key can be calculated from a public key within reasonable time, youd still have to get the public key first. Since the address used are not public keys and the public key is only revealed once you signed something. You are "fine" as long as you dont spend your coins and have them on an address that was never used. That would be a very serious problem, but considering that ECC is used not only for bitcoin it might be worse for other systems.

It is certainly possible to switch to an algorithm that is considered to be safe in such an event, but AFAIK its a hard fork.

this is exactly what i was talking about in our dispute, that time we were fighting for the whole quantum story in that thread, but i was misunderstood, i or i wan't able to say it clearly

the problem with changing the algo, is that every miners must change their equipments, if you thing that almost 400peta of hash can be changed to a new algo with no problem, you're being naive

[Lauda]

this is exactly what i was talking about in our dispute, that time we were fighting for the whole quantum story in that thread, but i was misunderstood, i or i wan't able to say it clearly

the problem with changing the algo, is that every miners must change their equipments, if you thing that almost 400peta of hash can be changed to a new algo with no problem, you're being naive

You were not misunderstood, you were wrong just as you are once again. Nobody is talking about changing the mining algorithm (which is not susceptible to attacks for now, aside from using brute-force (impossible within out lifetime).
Update:
I do not have any more patience for people who will not admit to being wrong (see Shorena's post for confirmatino). Amph has been put on ignore.

[NorrisK]

You are "fine" as long as you dont spend your coins and have them on an address that was never used.

Funny that you will never be able to spend these coins, once you broadcast a transaction the adversary can get your private key and send a double-spending with a higher fee.

That would mean that the private key would be cracked from the public key withing 10 minutes of broadcasting the transaction right? Would it really become that easy with quantum computing?

[Amph]

this is exactly what i was talking about in our dispute, that time we were fighting for the whole quantum story in that thread, but i was misunderstood, i or i wan't able to say it clearly

the problem with changing the algo, is that every miners must change their equipments, if you thing that almost 400peta of hash can be changed to a new algo with no problem, you're being naive

You were not misunderstood, you were wrong just as you are once again. Nobody is talking about changing the mining algorithm (which is not susceptible to attacks for now, aside from using brute-force (impossible within out lifetime).
If you continue the nonsense from the last thread, I will stay away from this one. I will not waste my time once more.

wut? are you able to read or what, he said that it certainly possible to change the algo, and i said that it is not so easy as he think, simple as that, you are going overboard with your no-sense man...or you have comprehension problem, most likely

also no i was right in that thread i was saying the same excat thing he said in this quote that i quoted(but with different words of course), go back and find the thread you will see

[shorena]

this is exactly what i was talking about in our dispute, that time we were fighting for the whole quantum story in that thread, but i was misunderstood, i or i wan't able to say it clearly

the problem with changing the algo, is that every miners must change their equipments, if you thing that almost 400peta of hash can be changed to a new algo with no problem, you're being naive

You were not misunderstood, you were wrong just as you are once again. Nobody is talking about changing the mining algorithm (which is not susceptible to attacks for now, aside from using brute-force (impossible within out lifetime).
If you continue the nonsense from the last thread, I will stay away from this one. I will not waste my time once more.

wut? are you able to read or what, he said that it certainly possible to change the algo, and i said that it is not so easy as he think, simple as that, you are going overboard with your no-sense man...or you have comprehension problem, most likely

also no i was right in that thread i was saying the same excat thing he said in this quote that i quoted(but with different words of course), go back and find the thread you will see

The mining algorithm is based on SHA 256(SHA 256(data)) which is believed not to be affected by quantum computing. As LaudaM said, a quantum computer is not just a very powerful computer, but its a machine that computes differently and thus handles certain tasks (e.g. factorization, or modul n division[1]) better than a normal computer. It does not handle everything better.

Quantum computing would probably break ECDSA which is used when signing a transaction or message. Considering what Come-from-Beyond said about the times it would render bitcoin useless as you no longer can spend your coins without someone instantly[2] (or at least very fast) calculating your private key from the public key that is part of the transaction. Mining however would not be affected as there is no ECDSA only sha256[3].

[1] Note: factorization is the basis for RSA security, for ECDSA its a modul n divison.
[2] I have no idea how long it would actually take so I will just assume this as a worst case scenario.
[3] https://en.bitcoin.it/wiki/Block_hashing_algorithm

[Amph]

this is exactly what i was talking about in our dispute, that time we were fighting for the whole quantum story in that thread, but i was misunderstood, i or i wan't able to say it clearly

the problem with changing the algo, is that every miners must change their equipments, if you thing that almost 400peta of hash can be changed to a new algo with no problem, you're being naive

You were not misunderstood, you were wrong just as you are once again. Nobody is talking about changing the mining algorithm (which is not susceptible to attacks for now, aside from using brute-force (impossible within out lifetime).
If you continue the nonsense from the last thread, I will stay away from this one. I will not waste my time once more.

wut? are you able to read or what, he said that it certainly possible to change the algo, and i said that it is not so easy as he think, simple as that, you are going overboard with your no-sense man...or you have comprehension problem, most likely

also no i was right in that thread i was saying the same excat thing he said in this quote that i quoted(but with different words of course), go back and find the thread you will see

The mining algorithm is based on SHA 256(SHA 256(data)) which is believed not to be affected by quantum computing. As LaudaM said, a quantum computer is not just a very powerful computer, but its a machine that computes differently and thus handles certain tasks (e.g. factorization, or modul n division[1]) better than a normal computer. It does not handle everything better.

Quantum computing would probably break ECDSA which is used when signing a transaction or message. Considering what Come-from-Beyond said about the times it would render bitcoin useless as you no longer can spend your coins without someone instantly[2] (or at least very fast) calculating your private key from the public key that is part of the transaction. Mining however would not be affected as there is no ECDSA only sha256[3].

[1] Note: factorization is the basis for RSA security, for ECDSA its a modul n divison.
[2] I have no idea how long it would actually take so I will just assume this as a worst case scenario.
[3] https://en.bitcoin.it/wiki/Block_hashing_algorithm

i'm in agreement with you, and i never said that sha256 could be broken directly with quantum, but it could be done indirectly, in the sense that we need to change the algo

because even if miners are not affected, who want to spend it is affected and if bitcoin is useless because of this, miners are also mining useless coins, which mean that they will not continue to mine and bitcoin will die