Why is Bitcoin safe against a quantum computer?

[MarlboroMan]

Quantum Computing is a risk to Bitcoin in 20+ years. For now we are fine as even the newest quantum computer arent even close to catching the Bitcoin Network.

[FTWbitcoinFTW]

Quantum Computing is a risk to Bitcoin in 20+ years. For now we are fine as even the newest quantum computer arent even close to catching the Bitcoin Network.

It's not about network , it's about break a private key !

[coinpeculiator]

As we all know elliptic curve cryptography is vulnerable to a quantum computer. For a conventional computer difficulty of breaking 256-bit key equals 256/2=128 bits. For a quantum computer it's just sqrt(256)=16 bits.
Bitcoin address is a hashed public key of 256-bit EC. Hashes are resistant to quantum algos, so while someone keeps his public key unknown it's OK. But when he wants to transfer his money he must reveal the key.
Let's assume that an attacker with a quantum computer monitors all transactions. The attacker can pick any key while a transaction awaits to be included into a block. Now imagine that miners choose transactions with higher fees. The attacker can issue other transaction (when he picks the private key) that transfer coins to his address and set a higher fee. Or he could switch his mining rig on and try to find a block himself. With 0.1% of all hashpower he needs only 5 days to solve a block with 50% chance.

Seems Bitcoin is NOT safe. Or am I wrong?

If this attack were ever to become a potential threat it would be simple to avoid being a victim without altering the protocol but just with client behavious change. So with your theory, after you do a transaction from an address a quantum computer could break the private key from the transaction and use the remainder of bitcoins in that address.

The answer is not to leave any coins on that address... so when you want to make a payment you give it two outputs, one to the person you want to pay, and the other output is your next generated address which has no transactions to crack.

[Come-from-Beyond]

As we all know elliptic curve cryptography is vulnerable to a quantum computer. For a conventional computer difficulty of breaking 256-bit key equals 256/2=128 bits. For a quantum computer it's just sqrt(256)=16 bits.
Bitcoin address is a hashed public key of 256-bit EC. Hashes are resistant to quantum algos, so while someone keeps his public key unknown it's OK. But when he wants to transfer his money he must reveal the key.
Let's assume that an attacker with a quantum computer monitors all transactions. The attacker can pick any key while a transaction awaits to be included into a block. Now imagine that miners choose transactions with higher fees. The attacker can issue other transaction (when he picks the private key) that transfer coins to his address and set a higher fee. Or he could switch his mining rig on and try to find a block himself. With 0.1% of all hashpower he needs only 5 days to solve a block with 50% chance.

Seems Bitcoin is NOT safe. Or am I wrong?

If this attack were ever to become a potential threat it would be simple to avoid being a victim without altering the protocol but just with client behavious change. So with your theory, after you do a transaction from an address a quantum computer could break the private key from the transaction and use the remainder of bitcoins in that address.

The answer is not to leave any coins on that address... so when you want to make a payment you give it two outputs, one to the person you want to pay, and the other output is your next generated address which has no transactions to crack.

No. I meant the key could be picked while a transaction is unconfirmed, so an attacker could double-spend the coins. Two outputs won't help.

[HurtK]

I just read this thread up to this point.  It is almost all nonsense.  The capabilities of quantum computers have been describe well in other forum topics.

Bottom line:  Quantum computers can't do anything, except this: 15 = 3 * 5;

15 = (3 * 5) 48% of time

http://www.youtube.com/watch?v=Yl3o236gdp8

[monkeybars]

Real quantum computing will break most existing widespread forms of cryptographic security. If someone is able to jump the gun and realize a full quantum computer (not just quantum annealing like D-Wave) before it's expected, they will wreak havoc on the Internet. It's far more likely that technology innovators will simply replace security layers with quantum-proof ones before then however. Bitcoin's security layer can easily be swapped out with another -- as Litecoin shows.

[Etlase2]

As we all know elliptic curve cryptography is vulnerable to a quantum computer. For a conventional computer difficulty of breaking 256-bit key equals 256/2=128 bits. For a quantum computer it's just sqrt(256)=16 bits.
Bitcoin address is a hashed public key of 256-bit EC. Hashes are resistant to quantum algos, so while someone keeps his public key unknown it's OK. But when he wants to transfer his money he must reveal the key.

Some things need clarification:

A 256-bit EC key has an effective security level of 128 bits against brute force attacks. EC keys can be broken in minutes regardless of the number of bits, theoretically as long as the QC has enough qubits. Shor's.

A hashing algorithm such as SHA-256 would be reduced to the sqrt of 256-bits which is 128 bits, not 16. Grover's. So any hashing algorithm or public key system that does not rely on factoring is as secure with double the bits.

Banks do not store your money via public/private keypairs that are accessible to everyone. Arguing that banks will be insecure is downright stupid. Yes their websites will be insecure, but the money will be fine. Bitcoin is far, far more vulnerable than the traditional banking system to quantum computing.

[AlexWaters]

Bitcoin is a living, breathing code-base. Most of the attacks that are discussed could be dealt with quickly - if they occur. Yes some merchants could get hurt by it in the short term.

[GigaDice]

The real question is if the feds really wanted to shut down Bitcoin there are much easier methods to do so that don't require the use of quantum computation.

[darkmule]

Even if, in some period of years, it becomes possible to crack Bitcoin (I assume the day will arrive sometime), that is probably not the first thing TPTB would do with it.  In fact, it is more likely they'd sit on the capability and not use it, because it is a capability that is much more useful to have if nobody knows you have it.

I'd assume by the time it becomes possible for the kind of bad guys I'm more worried about to do this, work will be done to transition to some more resistant technology.  I will leave it to those more knowledgeable than I to find these.

[luv2drnkbr]

Because linear key space expansion exponentially increases brute force difficulty.  /Thread

[Etlase2]

Because linear key space expansion exponentially increases brute force difficulty.  /Thread

It's a shame that factorization to prime numbers is not a brute force attack.

[minertt]

Dont worry q-computer can solve algorithms quickly but not crack SHA256 that quickly

[Come-from-Beyond]

Dont worry q-computer can solve algorithms quickly but not crack SHA256 that quickly

The problem is with Elliptic Curve Crypto, not hashing algo.