What does Quantum Computing mean for Bitcoin?

[RodeoX]

I thought about this also. A true Quantum computer could end the current bitcoin system. Even though it is only theoretical now. The speed of development is impressive. A system for sending messages using wave collapse already exists!

[1713587275]

1713587275

[1713587275]

1713587275

[wb3]

I thought about this also. A true Quantum computer could end the current bitcoin system. Even though it is only theoretical now. The speed of development is impressive. A system for sending messages using wave collapse already exists!

Please explain, How?

As I see it, you would need to crack the Key Pair almost instantaneously before it got added to the chain, if another Key pair is then generated before the next transaction, you would have to start over. It would just take a minor change to the source to achieve this.

But then if we are using Quantum Computers, BitCoin could scale the PKC using the Quantum Computer. Just increase the Odds with the capability of the machines.

But if Quantum Computing becomes prevalent so would Quantum Pairing. No one would be able to see the transaction or intercept it between parties. Using a Trekie term: it is sub-space communications faster than the speed of light.

[RodeoX]

I thought about this also. A true Quantum computer could end the current bitcoin system. Even though it is only theoretical now. The speed of development is impressive. A system for sending messages using wave collapse already exists!

"Please explain, How?

As I see it, you would need to crack the Key Pair almost instantaneously before it got added to the chain, if another Key pair is then generated before the next transaction..."

"But if Quantum Computing becomes prevalent so would Quantum Pairing. No one would be able to see the transaction or intercept it between parties."

Wooah. Thats a good way to do it. It won't work every time, but you could break some keys before they are added to the chain, right? And you have a solution! Add quantum entanglement to the system and you could verify a transaction, perhaps before sending it to any nodes.

[gigitrix]

If Quantum Computing is realised the entire industry of two computers ever interchanging information in a secure manner is rewritten. The internet? Hacked. Banks? Hacked, Bitcoin? Flawed. Everything changes from the ground up at that point.

The holders of the first non-trivial quantum computers will be nothing short of mortal gods, with absolute control over the entire digital infrastructure of the world.

EDIT: Interesting Wikipedia Link (albeit usual Wikipedia caveat applies
http://en.wikipedia.org/wiki/Shor%27s_algorithm

[bitcoinBull]

Quantum computation renders certain public key crypto insecure.  Since bitcoin addresses are ECDSA public keys, using a quantum computer to discover the corresponding private key would give someone the ability to recreate any bitcoin address's wallet.dat file, so they could spend them.

So the crypto for transactions in bitcoin is vulnerable to QC (as is SSL which is RSA).

http://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Quantum_computing_attacks

The crypto for mining bitcoins is not affected, except potentially increasing the hash rate above that of classical computers.  So the ghash network rate would grow faster with more quantum miners.  We wouldnt reach 21 million faster, as the difficulty factor would be scaled accordingly.

The ECDSA public key crypto could be changed to one not vulnerable to quantum attacks, like Unbalanced Oil and Vinegar.

http://en.wikipedia.org/wiki/Post-quantum_cryptography

[neotrino]

The ECDSA public key crypto could be changed to one not vulnerable to quantum attacks, like Unbalanced Oil and Vinegar.

http://en.wikipedia.org/wiki/Post-quantum_cryptography

Then I think that we should do this ASAP.

quantum computers are a reality, you can buy a 128qubit one for "only" 10$ million (that's small change for a large company)

http://venturebeat.com/2011/05/27/first-quantum-computer-sold/
http://www.dwavesys.com/en/products-services.html


How difficult would be change the algorithm of the public-key encryption for Bitcoin to one not vulnerable to quantum attacks?
Would we have to start from scratch or we could change the algorithm "on the fly" without losing our coins?

[neotrino]

Is cryptography dead?

Imagine that it’s fifteen years from now and someone announces the successful construction of a large quantum computer. The New York Times runs a frontpage article reporting that all of the public-key algorithms used to protect the Internet have been broken. Users panic. What exactly will happen to cryptography?

Perhaps, after seeing quantum computers destroy RSA and DSA and ECDSA, Internet users will leap to the conclusion that cryptography is dead; that there is no hope of scrambling information to make it incomprehensible to, and unforgeable by, attackers; that securely storing and communicating information means using expensive physical shields to prevent attackers from seeing the information—for example, hiding USB sticks inside a locked brief-case chained to a trusted courier’s wrist.

A closer look reveals, however, that there is no justification for the leap from “quantum computers destroy RSA and DSA and ECDSA” to “quantum computers destroy cryptography.” There are many important classes of cryptographic systems beyond RSA and DSA and ECDSA

• Hash-based cryptography. The classic example is Merkle’s hash-tree public-key signature system (1979), building upon a one-message-signature idea of Lamport and Diffie.
• Code-based cryptography. The classic example is McEliece’s hidden-Goppa-code public-key encryption system (1978).
• Lattice-based cryptography. The example that has perhaps attracted the most interest, not the first example historically, is the Hoffstein–Pipher–Silverman “NTRU” public-key-encryption system (1998).
• Multivariate-quadratic-equations cryptography. One of many interesting examples is Patarin’s “HFEv− ” public-key-signature system (1996), generalizing a proposal by Matsumoto and Imai.
• Secret-key cryptography. The leading example is the Daemen–Rijmen “Rijndael” cipher (1998), subsequently renamed “AES,” the Advanced Encryption Standard.

All of these systems are believed to resist classical computers and quantum computers. Nobody has figured out a way to apply “Shor’s algorithm”—the quantum-computer discrete-logarithm algorithm that breaks RSA and DSA and ECDSA—to any of these systems. Another quantum algorithm, “Grover’s algorithm,” does have some applications to these systems; but Grover’s algorithm is not as shockingly fast as Shor’s algorithm, and cryptographers can easily compensate for it by choosing somewhat larger key sizes.

This text was extracted from the first chapter of the book Post-quantum cryptography ( by Daniel J. Bernstein )



This is scary... I think that we should seriously to look a way of replacing the ECDSA algorithm of Bitcoin with another "post-quantum" algorithm

[bitcoinBull]

The ECDSA public key crypto could be changed to one not vulnerable to quantum attacks, like Unbalanced Oil and Vinegar.

http://en.wikipedia.org/wiki/Post-quantum_cryptography

Then I think that we should do this ASAP.

quantum computers are a reality, you can buy a 128qubit one for "only" 10$ million (that's small change for a large company)

http://venturebeat.com/2011/05/27/first-quantum-computer-sold/
http://www.dwavesys.com/en/products-services.html


How difficult would be change the algorithm of the public-key encryption for Bitcoin to one not vulnerable to quantum attacks?
Would we have to start from scratch or we could change the algorithm "on the fly" without losing our coins?

D-Wave is smoke and mirrors.  It is more like 128 1-bit analog computers, as the qubits are not entangled.  Without entanglement, there is no quantum speedup over classical computation.  Even the 8-bit system they published in Nature is not entangled.

The highest number of qubits which have demonstrated entanglement is 3.

Still, not too soon to examine plans for switching bitcoin from ECDSA to something post-quantum.

Remember, when "true" quantum computers become a reality, far more than bitcoin is defeated.  HTTPS (which uses RSA) is defeated.  So basically all internet traffic (passwords, credit card numbers, etc) will be readable by anyone on the same wifi, by an employee at your ISP, or someone at your ISP's ISP, etc.

[Jaime Frontero]

The ECDSA public key crypto could be changed to one not vulnerable to quantum attacks, like Unbalanced Oil and Vinegar.

http://en.wikipedia.org/wiki/Post-quantum_cryptography

Then I think that we should do this ASAP.

quantum computers are a reality, you can buy a 128qubit one for "only" 10$ million (that's small change for a large company)

http://venturebeat.com/2011/05/27/first-quantum-computer-sold/
http://www.dwavesys.com/en/products-services.html


How difficult would be change the algorithm of the public-key encryption for Bitcoin to one not vulnerable to quantum attacks?
Would we have to start from scratch or we could change the algorithm "on the fly" without losing our coins?

D-Wave is smoke and mirrors.  It is more like 128 1-bit analog computers, as the qubits are not entangled.  Without entanglement, there is no quantum speedup over classical computation.  Even the 8-bit system they published in Nature is not entangled.

The highest number of qubits which have demonstrated entanglement is 3.

Still, not too soon to examine plans for switching bitcoin from ECDSA to something post-quantum.

Remember, when "true" quantum computers become a reality, far more than bitcoin is defeated.  HTTPS (which uses RSA) is defeated.  So basically all internet traffic (passwords, credit card numbers, etc) will be readable by anyone on the same wifi, by an employee at your ISP, or someone at your ISP's ISP, etc.

+1

yes - D-Wave is pretty much vapor-ware.  big business ego-boo: "we have the first quantum computer! (quoth Lockheed)"  and even if delivered, it's only a threat on the order that a cell-phone is.

[neotrino]

Still, not too soon to examine plans for switching bitcoin from ECDSA to something post-quantum.

Remember, when "true" quantum computers become a reality, far more than bitcoin is defeated.  HTTPS (which uses RSA) is defeated.  So basically all internet traffic (passwords, credit card numbers, etc) will be readable by anyone on the same wifi, by an employee at your ISP, or someone at your ISP's ISP, etc.

If I can break ECDSA with a quantum computer I can steal all the money on bitcoin and make all the bitcoins disappear from day to night.
However if i can break RSA, banks and people only have to stop relying on SSL meanwhile they implement a new algorithm. ( Probably they would have to stop using credit cards for a while but they won't loose all their money at all )

So, the first problem is that a quantum computer able to break crypto is a death threat to Bitcoin, meanwhile for a bank that relies on RSA is only a major threat.

The second problem is that the first company who will own a quantum computer able to break crypto will be sure the "US Government". And in the future, when Bitcoin will be much popular than now, I am sure that the US Goverment will have strong incentives to make bitcoin disappear because the bitcoin thing is a major threat to the debt-based economic system of the dollar.

So far.. how much you think will take to the US Gov own such quantum computer and break the ECDSA system of bitcoin? 5 years perhaps?

[vuce]

I think the switch to quantum computer resistant crypto will be done long before the first (serious) one will see the light of day.

[Jaime Frontero]

Still, not too soon to examine plans for switching bitcoin from ECDSA to something post-quantum.

Remember, when "true" quantum computers become a reality, far more than bitcoin is defeated.  HTTPS (which uses RSA) is defeated.  So basically all internet traffic (passwords, credit card numbers, etc) will be readable by anyone on the same wifi, by an employee at your ISP, or someone at your ISP's ISP, etc.

If I can break ECDSA with a quantum computer I can steal all the money on bitcoin and make all the bitcoins disappear from day to night.
However if i can break RSA, banks and people only have to stop relying on SSL meanwhile they implement a new algorithm. ( Probably they would have to stop using credit cards for a while but they won't loose all their money at all )

So, the first problem is that a quantum computer able to break crypto is a death threat to Bitcoin, meanwhile for a bank that relies on RSA is only a major threat.

The second problem is that the first company who will own a quantum computer able to break crypto will be sure the "US Government". And in the future, when Bitcoin will be much popular than now, I am sure that the US Goverment will have strong incentives to make bitcoin disappear because the bitcoin thing is a major threat to the debt-based economic system of the dollar.

So far.. how much you think will take to the US Gov own such quantum computer and break the ECDSA system of bitcoin? 5 years perhaps?

who cares? (although i'd be more likely to bet on 10+ years...)

in five years Bitcoin will either be worth too much to destroy - and all governments will be in the process of changing their tax-base from income-based to consumption-based...

...or Bitcoin will be worth nothing.

[bitcoinBull]

Creighto says here that the ECDSA in bitcoin is modular enough to be swapped out.

I'm guessing the upgrade would be a version which uses post-quantum private keys, but is backwards-compatible with the current ECDSA private keys.

Bitcoins received with the new version would have a post-quantum wallet file.  Any bitcoins not re-sent to a new address with the new version would be vulnerable to theft by a quantum computer.

Therefore, the first entity with access to a quantum computer could steal any coins which have not been re-sent.

This entity would be able to recover all lost bitcoins!

[Jaime Frontero]

This entity would be able to recover all lost bitcoins!

oh my.

now that is interesting.

[LegitBit]

Could the sudden existence of quantum computing mean the sudden uselessness of Bitcoin as a currency?

I don't think practical quantum computing will "suddenly" exist.

[bitcoinBull]

This entity would be able to recover all lost bitcoins!

oh my.

now that is interesting.

Unless the network subsequently upgraded to a post-quantum version without backwards-compatibility, which would render all coins not re-sent by then as obsolete.


I don't know the technicals well enough to say with confidence that this is the only scenario.  But if the upgrade to post-quantum is compatible with the current blockchain, it seems this would be how.

[caston]

would we call this "qubitcoin"?

[Saturn7]

This is the best doc I've read on qc.

http://www.obld.net/qcintro.pdf

[cbeast]

If some qc is created that is so powerful like it would solve all BTC, then likely it will be simply used as a superweapon to create bioweapons that will selectively kill entire races of people. It will also probably be used to solve the problem of fusion so some country can destroy an entire continent without any radioactive fallout. I doubt that we will have to worry about it being used to destroy bitcoin. OTOH there is a very small chance it could be used to help mankind never have any need for money at all and allow us to live in peace.

tl;dr QC > BTC

[Pieter Wuille]

Assuming QC "suddenly" appears, and ECDSA is instantaneously crackable using Shor's algorithm, and SHA256/RIPEMD160 become vulnerable to Grover's algorithm:

• Every unspent coin, sent to an address whose pubkey is not yet revealed, is somewhat safe (80 bit security left, instead of 160 bit)
• The block chain is quite safe (128 bit security left, instead of 256 bit)
• Transactions to new quantum-computing-based addresses with corresponding keys, are safe
• ... only unspent coins sent to reused addresses will be trivially claimable by any attacker (a few bits of security left, instead of 128 bit)