Do you think quantum computers would break Bitcoin's security?

[Troonetpt]

I don't think quantum computer could  break Bitcoin's security.
When the quantum computer came out, well it still need very long time, the algorithm of bitcoin also can be upgrade.

[1714975096]

1714975096

[1714975096]

1714975096

[BusyBeaverHP]

now, public key are 128 bit

I'm still learning ECC, but considering that the X and Y coordinate of a bitcoin public key are both 256 bits resulting from point addition of 256-bit Generator Point, isn't a bitcoin public key technically 256 bit?

Reference: http://www.royalforkblog.com/2014/07/31/address-gen/

The only caveat I remember, is that even though a given ECC operates in 256-bit space, it has only the equivalent of 128-bits symmetric (e.g. AES) security.

The caveat explained by DeathAndTaxes here: https://bitcointalk.org/index.php?topic=1007619.msg10936084#msg10936084

[Amph]

now, public key are 128 bit

I'm still learning ECC, but considering that the X and Y coordinate of a bitcoin public key are both 256 bits resulting from point addition of 256-bit Generator Point, isn't a bitcoin public key technically 256 bit?

Reference: http://www.royalforkblog.com/2014/07/31/address-gen/

The only caveat I remember, is that even though a given ECC operates in 256-bit space, it has only the equivalent of 128-bits symmetric (e.g. AES) security.

The caveat explained by DeathAndTaxes here: https://bitcointalk.org/index.php?topic=1007619.msg10936084#msg10936084

it seems that it depend also on some wallet, for example on some client private key start from 128 key

here the reference  https://en.bitcoin.it/wiki/Private_key

In Bitcoin, a private key is usually a 256-bit number (some newer wallets may use between 128 and 512 bits)

maybe it's the same for public keys

[Cruxer]

They talk about this but not in bitcoin matter but with cryptography in general matter for many many years.
We don't understand quantum physics well as human species, so no, it won't be happening anytime soon.

[shorena]

-snip-
well my intention was not say that it could break sha256, but all i want to said, is that it could break 128 key, that's it, there is nothing flawed about my logic

But you are using the "QC can break[1] 128 bit asym-crypto" argument to say that any 256 bit key can be broken by a QC, which is nonsense. Firstly it only applies to asymmetric crypto. Secondly bitcoin is more than just pubkey and private key, it also involves hashes which are - for all we currently know - immune to QC as there is no known algorithm to reverse the calculation and a QC is not faster at calculating hashes either.

[1] break as in brute force

[Jybrael]

It does not need to break the cryptography. It only needs a quantum machine that can easily create all private keys and store them all into a database to look up every private key for a public key as on http://directory.io where it happens on the fly.
Sure, calculating and storing 10^79 keys is currently impossible without doing it in hundreads of years. But nobody knows what the future brings up. Remeber Moors law.

A more powerful computer doesn't mean that it will break any cryptography.
Remeber that better computers means only faster brute force attacks.

Ofcourse I will have to agree with you on that one plus the post that you quoted as well. A faster computer just means a faster brute force attack not that it can break any cryptography...it will need some sort of a key to help it break it which would be quite difficult to make...unless we have another savant..

[bennybong]

+1 to whoever posts that picture explaining about how the laws of thermodynamics would have to be broken to crack SHA256...

The original one was posted here and probably a few dozen other places as well.  I thought the background looked a little dull, so I made my own version.

+2 because I like yours more!

[Amph]

-snip-
well my intention was not say that it could break sha256, but all i want to said, is that it could break 128 key, that's it, there is nothing flawed about my logic

But you are using the "QC can break[1] 128 bit asym-crypto" argument to say that any 256 bit key can be broken by a QC, which is nonsense. Firstly it only applies to asymmetric crypto. Secondly bitcoin is more than just pubkey and private key, it also involves hashes which are - for all we currently know - immune to QC as there is no known algorithm to reverse the calculation and a QC is not faster at calculating hashes either.

[1] break as in brute force

well it's true that you can retrieve a 256 key form a 128, i posted a link telling that, but it's not that easy to do anyway

did you read this?

"With a quantum computer, you could easily deduce the private key corresponding to a public key. If you only have an address, which is a hashed public key, the private key is safe. Anyway, to spend a transaction, you need to send the public key. At that point you are vulnerable, but the attack is not straightforward."

unless he talking bullshit(i don't think so, because he made a tl;dr from many quotes, from users here on bitcointalk, and they seems to know what they are talking about)

read this

https://bitcointalk.org/index.php?topic=133425.0

"I don't think you understand his point.  Yes QC could (in theory) be used to determine the private key FROM the public key.  However with Bitcoin the address isn't the public key it is a structured hash of the public key.   The public key isn't known until the first time Bitcoins are spent from a given address.
"

if you reveal your public key there are chance that they can steal your coins

again

"Well, even that isn't entirely true with how Bitcoin uses public key encryption.  Simply publishing a single bitcoin address doesn't actually publish the private key, it publishes a structured hash of the public key.  The actual public key isn't published until the first time funds are spent from that address.  If SHA-256 is subject to being brute forced into collisions by a quantum computer, a different hashing algo may not be, and that could be used instead.  If you use a new address for each transaction, which is how bitcoin does it by default and really is a best practice, it would be very difficult for a quantum breaker to steal your coins.
"

not impossible

[shorena]

-snip-
well my intention was not say that it could break sha256, but all i want to said, is that it could break 128 key, that's it, there is nothing flawed about my logic

But you are using the "QC can break[1] 128 bit asym-crypto" argument to say that any 256 bit key can be broken by a QC, which is nonsense. Firstly it only applies to asymmetric crypto. Secondly bitcoin is more than just pubkey and private key, it also involves hashes which are - for all we currently know - immune to QC as there is no known algorithm to reverse the calculation and a QC is not faster at calculating hashes either.

[1] break as in brute force

well it's true that you can retrieve a 256 key form a 128, i posted a link telling that, but it's not that easy to do anyway

did you read this?

"With a quantum computer, you could easily deduce the private key corresponding to a public key. If you only have an address, which is a hashed public key, the private key is safe. Anyway, to spend a transaction, you need to send the public key. At that point you are vulnerable, but the attack is not straightforward."

unless he talking bullshit(i don't think so, because he made a tl;dr from many quotes, from users here on bitcointalk, and they seems to know what they are talking about)

read this

https://bitcointalk.org/index.php?topic=133425.0

"I don't think you understand his point.  Yes QC could (in theory) be used to determine the private key FROM the public key.  However with Bitcoin the address isn't the public key it is a structured hash of the public key.   The public key isn't known until the first time Bitcoins are spent from a given address.
"

if you reveal your public key there are chance that they can steal your coins

again

"Well, even that isn't entirely true with how Bitcoin uses public key encryption.  Simply publishing a single bitcoin address doesn't actually publish the private key, it publishes a structured hash of the public key.  The actual public key isn't published until the first time funds are spent from that address.  If SHA-256 is subject to being brute forced into collisions by a quantum computer, a different hashing algo may not be, and that could be used instead.  If you use a new address for each transaction, which is how bitcoin does it by default and really is a best practice, it would be very difficult for a quantum breaker to steal your coins.
"

not impossible

Yes, you would have a possible race condition and how well you are connection to the network would be very important. The attack you are talking about here assumes that Eve (attacker) gets the pubkey from Alice (user) before Bob (miner) confirms the transaction. Not only getting the public key, but also calculating the private key from it and creating a competing TX. Thus Eve would have to be in control of all peers Alice is connected to and all nodes Bob is connected to in order to make this a very likely success. If only a single node (of those connected to Alice) is not under Eves control the TX Alice creates will most likely reach Bob before Eve's.

This is a big problem, but it does not mean bitcoin is broken. It makes every single transaction risky until the problem is fixed though.

Depending on the costs to run a QC, this does not seems cost efficient even when possible. Once the first QC's are capable and start messing with TX I suspect[1] someone has a hardfork solution in some drawer.

[1] actually I have no idea how realistic this is, but considering that we have at least a decade Im positive.

[Lauda]

no you are reading that in a wrong way, i said that a 128 key for a quantum is like a 64 for a standard pc, in the sense that a standard pc can break 64 and a QC can break 128

well my intention was not say that it could break sha256, but all i want to said, is that it could break 128 key, that's it, there is nothing flawed about my logic

Your writing is bad. That's the issue. I told you, instead of posting a lot of uninformative posts, time would be better spent learning the language itself.
There is no logic and everything is flawed.

I've told you this already. There is no working quantum computer that can even begin trying to break that key. You should focus on reading rather that replying.

Yes, you would have a possible race condition and how well you are connection to the network would be very important. The attack you are talking about here assumes that Eve (attacker) gets the pubkey from Alice (user) before Bob (miner) confirms the transaction. Not only getting the public key, but also calculating the private key from it and creating a competing TX. Thus Eve would have to be in control of all peers Alice is connected to and all nodes Bob is connected to in order to make this a very likely success. If only a single node (of those connected to Alice) is not under Eves control the TX Alice creates will most likely reach Bob before Eve's.

This is a big problem, but it does not mean bitcoin is broken. It makes every single transaction risky until the problem is fixed though.

Depending on the costs to run a QC, this does not seems cost efficient even when possible. Once the first QC's are capable and start messing with TX I suspect[1] someone has a hardfork solution in some drawer.

[1] actually I have no idea how realistic this is, but considering that we have at least a decade Im positive.

Like I previously said quantum computers can't even begin to tackle the problem and that the user was pulling nonsense. Now he's just copying information from other people's statements.

[Amph]

no you are reading that in a wrong way, i said that a 128 key for a quantum is like a 64 for a standard pc, in the sense that a standard pc can break 64 and a QC can break 128

well my intention was not say that it could break sha256, but all i want to said, is that it could break 128 key, that's it, there is nothing flawed about my logic

Your writing is bad. That's the issue. I told you, instead of posting a lot of uninformative posts, time would be better spent learning the language itself.
There is no logic and everything is flawed.

I've told you this already. There is no working quantum computer that can even begin trying to break that key. You should focus on reading rather that replying.

Yes, you would have a possible race condition and how well you are connection to the network would be very important. The attack you are talking about here assumes that Eve (attacker) gets the pubkey from Alice (user) before Bob (miner) confirms the transaction. Not only getting the public key, but also calculating the private key from it and creating a competing TX. Thus Eve would have to be in control of all peers Alice is connected to and all nodes Bob is connected to in order to make this a very likely success. If only a single node (of those connected to Alice) is not under Eves control the TX Alice creates will most likely reach Bob before Eve's.

This is a big problem, but it does not mean bitcoin is broken. It makes every single transaction risky until the problem is fixed though.

Depending on the costs to run a QC, this does not seems cost efficient even when possible. Once the first QC's are capable and start messing with TX I suspect[1] someone has a hardfork solution in some drawer.

[1] actually I have no idea how realistic this is, but considering that we have at least a decade Im positive.

Like I previously said quantum computers can't even begin to tackle the problem and that the user was pulling nonsense. Now he's just copying information from other people's statements.

apparently you don't know how to read, it's not that my english is bad, well i don't care much, i have provided to you more then an evidence, and many quotes that say that is possible, if you still believe otherwise, this conversation can be closed now

"Now he's just copying information from other people's statements." everyone here is copying information from the internet this isn't something new...

[amazon4u]

Well, sorry to disrupt the techies at work but anyone got time for a history lesson ?
first personal computer : IBM
Release date    August 12, 1981; 33 years ago
Discontinued    April 2, 1987
Operating system    IBM BASIC / PC DOS 1.0
CP/M-86
UCSD p-System
CPU    Intel 8088      @ 4.77 MHz
Memory               16 kB ~ 256 kB
Sound                1-channel PWM

so 33 years ago we were doing 4.77mhz and a 256kb memory was more than enough for anybody...I think we should expect big things in the near future....quantum computers are definitely coming and standard encryption as we know it will go the dinosaur way.....along with it many other things that we consider untouchable today (Bitcoin included)...


the sad part is that by the time a private company would have quantum computers for sale, the NSA/GCHQ would've had years in advance of scorching the net with qbits...who is to say they aren't doing it already ?
http://www.washingtonpost.com/world/national-security/nsa-seeks-to-build-quantum-computer-that-could-crack-most-types-of-encryption/2014/01/02/8fff297e-7195-11e3-8def-a33011492df2_story.html

History is quite useless if you ask me (look what happens to Windows because it isn't rewritten from scratch) . This isn't even relevant. The development might actually slow down. The current processors are reaching a plateau when it comes to speed per core.

When talking about a quantum computer the numbers are quite different. A quantum computer is quite fast at very low speeds (even under a single MHz). Quantum computing will make an impact on asymmetric encryption, but symmetric algorithms are considered safe with a large enough key size e.g. 256 bits. Essentially we could just upgrade it to a very high number which would render quantum computers useless in beating encryption.

Yes I agree, however the government might have quantum computers for all we know.

I hardly doubt that. The are probably using Windows XP with the built in firewall.  

The current processors are reaching a plateau when it comes to speed per core

that is correct, and silicon is showing its limit .... but who is to say that in 5 years from now Silicon Valley won't be named Graphene Valley  !? Graphene has enormous potential in future of circuitry, the only problem is its price...and we all know that the NSA has endless resources ...I honestly think that we underestimate the power of NSA and their thirst of "knowledge"

you should check this out, I used to think the same ("The are probably using Windows XP with the built in firewall") but not after viewing this :

http://www.imdb.com/title/tt4044364/

[Lauda]

apparently you don't know how to read, it's not that my english is bad, well i don't care much, i have provided to you more then an evidence, and many quotes that say that is possible, if you still believe otherwise, this conversation can be closed now

"Now he's just copying information from other people's statements." everyone here is copying information from the internet this isn't something new...

Quoting random people on forums and expecting correct information, ah.  How about you start reading research papers and getting information from actual scientists or companies that are working on the matter?
There is no working quantum computer that can tackle these problems now. If there was, one could find a link to it.
You claim that there is one, then go and find us one.

The current processors are reaching a plateau when it comes to speed per core

that is correct, and silicon is showing its limit .... but who is to say that in 5 years from now Silicon Valley won't be named Graphene Valley  !? Graphene has enormous potential in future of circuitry, the only problem is its price...and we all know that the NSA has endless resources ...I honestly think that we underestimate the power of NSA and their thirst of "knowledge"

you should check this out, I used to think the same ("The are probably using Windows XP with the built in firewall") but not after viewing this :

http://www.imdb.com/title/tt4044364/

Actually I understand that. I'm looking forward for graphene usage. I think that graphene processors will be here sooner than quantum computing, but we will see.

[Furio]

I don't think that we will be facing a problem 'soon'. If quantum computers break ECDSA (The Elliptic Curve Digital Signature Algorithm) which is used for signing transactions, we might be facing a problem. I'm pretty sure that most members here don't know what happens in this scenario.  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.

It does look simple doesn't it? Well it's not like that. The thing is that your public key isn't really made public, but your Bitcoin address is rather a hash of it. What I'm saying is that while a quantum computer could get the private key from a public key, it can't derive the public key from your Bitcoin address.

on sha256 security bit are only 128, and quantum computer can break this(i can't find the article), if today pc can break 64 quantum computer can break at least the double of that
so bitcoin will need an hard fork in the future to survive

Stop talking nonsense. Quantum computers can't break SHA256 (used for hashing) without brute forcing it unless a flaw in it has been found. There is no article to link. I'm not saying that someone won't find a way to attack it in the future though.

Bitcoin is SHA256, SHA2 hasn't even been broken yet, once 256 will be broken, the bitcoin algo can change to SHA512 for another 40/50 years

This is wrong too. While it looks 'simple' it definitely is not. You do realize that changing the hashing algorithm means that all the current mining equipment would become worthless?
If SHA256 gets broken that would cause huge problems. Changing the signing algorithm is much easier than the hashing one, if you look at the big picture.

Technology are developing, everything is possible in the future, maybe Bitcoin will be obsolete in next 100 year, even before all Bicoin were mined.

This is why a better way of upgrading is needed. Hard forks are complicated and there will always be people who think that they know better than the people who are actually working on the software itself.



Note: Finally a decent topic has been made after a while.

You're logic is flawwed, the hashrate would be lowered by 50%, nothing more, nothing less.... So if the mining HW now gets 1 th/s with sha256, it will be 500 gh/s with sha512...

[Lauda]

You're logic is flawwed, the hashrate would be lowered by 50%, nothing more, nothing less.... So if the mining HW now gets 1 th/s with sha256, it will be 500 gh/s with sha512...

I got caught up replying in too many places and made a honest mistake. I've updated the post.
Although I still don't believe that it will be that simple.

[BlackMachine]

it would really still be sometime before quantum computers become a reality. if this happens, the network could be forked quickly to a new algorithm. The quantum computers can certainly break ecdsa but they are safe as long as no transactions hasn't been broadcasted.

[GenTarkin]

Even if today's cryptography were to be broken by quantum computing a new form of proof of work would arise which worked w/ quantum computers...

[arivar]

+1 to whoever posts that picture explaining about how the laws of thermodynamics would have to be broken to crack SHA256...

The original one was posted here and probably a few dozen other places as well.  I thought the background looked a little dull, so I made my own version.

+2 because I like yours more!

These gifs seem to be wrong. Which thermodynamic principle is that ? By Landauer's principle it would take less than one second to count from 1 to 2^256 on these conditions...

[BitcoinPenny]

technology develops in a very quick fashion. what today can be seen as secure and not possible to crack might be something we laugh at in 2020 or so. it's just a matter of years.

Agreed. But as long as cracking technology improves, anti-cracking technology will continue to improve right along with it. In other words, by the time quantum computers are computing fast enough to create problems with the current bitcoin technology, there will have already been a fix for it.

No big deal, as far as I'm concerned. Of course, I could be wrong. Often am.

Me

[thriftshopping]

You'll know once a quantum hack is underway when all banks lose their account balances, and all military secrets are disclosed. BTC loss will be the least of your problems