Topic: Elliptic Curves subject to Quantum Computer attacks, ramifications for Bitcoin? - page 2. (Read 1585 times)
September 13, 2015, 02:27:27 AM
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.
September 13, 2015, 01:20:56 AM
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.
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.
September 13, 2015, 12:30:29 AM
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.
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.
September 12, 2015, 08:06:37 PM
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.
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.
September 12, 2015, 07:34:53 PM
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.
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.
September 12, 2015, 05:10:32 PM
I saw this in Slashdot yesterday:
http://it.slashdot.org/story/15/09/09/1938206/cryptographers-brace-for-quantum-revolution
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.
http://it.slashdot.org/story/15/09/09/1938206/cryptographers-brace-for-quantum-revolution
Quote
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.
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.
September 10, 2015, 01:45:34 PM
I saw this in Slashdot yesterday:
http://it.slashdot.org/story/15/09/09/1938206/cryptographers-brace-for-quantum-revolution
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.
http://it.slashdot.org/story/15/09/09/1938206/cryptographers-brace-for-quantum-revolution
Quote
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.
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.
Jump to: