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

[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

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

So why is your argument that the mining equipment has to be replaced?

[oblivi]

None. Worrying about SHA256 being broken in our lifetimes is a waste of time. Also, if SHA256 gets broken it will mean the entire society of information is done since most of the encryption behind all kind of infrastructures including traditional banking are backed by SHA256 so it would be game over for everyone not only Bitcoin.

[Lauda]

None. Worrying about SHA256 being broken in our lifetimes is a waste of time. Also, if SHA256 gets broken it will mean the entire society of information is done since most of the encryption behind all kind of infrastructures including traditional banking are backed by SHA256 so it would be game over for everyone not only Bitcoin.

SHA256 has no known vulnerabilities which makes it great. However, if we come to a day where SHA256 is not enough (because for a quantum computer it could be potentially 128bit), then we can upgrade to SHA512. I'm almost sure that aside from software changes, the current hardware would still work.

[Come-from-Beyond]

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?

I would say 10 ms, not minutes.

[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

So why is your argument that the mining equipment has to be replaced?

if they are forced to change the algo, they need to change asic too, i though that it was very clear

[tspacepilot]

None. Worrying about SHA256 being broken in our lifetimes is a waste of time. Also, if SHA256 gets broken it will mean the entire society of information is done since most of the encryption behind all kind of infrastructures including traditional banking are backed by SHA256 so it would be game over for everyone not only Bitcoin.

It seems like there's a lot of half-informed discussion on this thread.   SHA256 isn't the signature algorithm. 

This thread was supposed to be about ECDSA, and as far as I know, a good QC weakens ECC in a way that it doesn't do to RSA.  Shorena's first post in here correctly points out that public keys aren't directly revealed in a transaction which spends to an address (just the hash of them is), so there's some security there for addresses which haven't been reused.

I guess I'm still wondering about how the UTXO set would be protected in the case where a QC which could break ECC was developed.  Clearly some sort of hard-fork, but what would it look like?  How could you get all of the bitcoin owners to take notice and do X to protect their transactions?  It seems like people with paper wallets and cold-storage might have to take action.  How could they be notified?  Maybe I'm missing something obvious, but I'd like to hear discussion on that topic because it's definitely not obvious to me what to do.

I think that all the talk of SHA256 and mining and asics is missing the point of this thread.

[shorena]

None. Worrying about SHA256 being broken in our lifetimes is a waste of time. Also, if SHA256 gets broken it will mean the entire society of information is done since most of the encryption behind all kind of infrastructures including traditional banking are backed by SHA256 so it would be game over for everyone not only Bitcoin.

It seems like there's a lot of half-informed discussion on this thread.   SHA256 isn't the signature algorithm. 

This thread was supposed to be about ECDSA, and as far as I know, a good QC weakens ECC in a way that it doesn't do to RSA.  Shorena's first post in here correctly points out that public keys aren't directly revealed in a transaction which spends to an address (just the hash of them is), so there's some security there for addresses which haven't been reused.

I guess I'm still wondering about how the UTXO set would be protected in the case where a QC which could break ECC was developed.  Clearly some sort of hard-fork, but what would it look like?  How could you get all of the bitcoin owners to take notice and do X to protect their transactions?  It seems like people with paper wallets and cold-storage might have to take action.  How could they be notified?  Maybe I'm missing something obvious, but I'd like to hear discussion on that topic because it's definitely not obvious to me what to do.

I think that all the talk of SHA256 and mining and asics is missing the point of this thread.

I dont think everyone will react in time, but I also have problems with the idea that such an attack comes out of nowhere. My hope is that (similar to suggested RSA key sizes) to switch to a different algorithm will be done in advance.

Its a bit late, but this[1] paper by DJB is probably an interesting read.

[1] http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf