Bitcoin is quantum-computing proof?

[BC Systems]

http://www.reddit.com/r/Bitcoin/comments/zb6qu/first_quantum_chip_announced/c63511q

Nope! Satoshi was a fucking turbo-genius (or more likely, "he" was a team of "normal" geniuses) and built the protocol to be more-or less quantum-proof. Have you ever wondered why the reference client never uses the same address twice? It's because before you send money from an address, it is secured by a one-time merkle signature, which is not vulnerable to a quantum computer.

So, let's say that ECDSA is broken. Here's what you do:

    1. Generate a new bitcoin address.

    2. Send all your bitcoins to that address. This ensures that all your bitcoins belong to a "virgin" address that has never sent money. Only you know the public key, which means that it is quantum-proof.

    3. Wait until the devs update the protocol with some new opcodes to allow non-ECDSA signatures, or until someone figures out a clever way to do merkle sigs with the existing opcodes.

    4. Until then, make sure you never receive any bitcoins at an address that you have sent bitcoins from.

Congratulations! Your bitcoins are quantum-secure. The only way to get them is to generate a RIPE160 collision on your address, which is very, very difficult.

[1714016197]

1714016197

[1714016197]

1714016197

[1714016197]

1714016197

[Come-from-Beyond]

A hacker with a quantum computer could just listen for incoming transactions, that have not been added to the blockchain yet, and attempt his attack. 10 mins should be enough.

>> Have you ever wondered why the reference client never uses the same address twice?

Aye. And I'm 100% sure it's for anonymity. So quantum-computing "proof" is just a side-effect which doesn't really work.

[Etlase2]

RIPEMD160 is not a one-time lamport signature, it is just a hash of a public key. For all we know, Satoshi may have done this to save space in the block chain, though that's somewhat doubtful considering all of the non-considerations that went into how much data is used. And as come from beyond pointed out, ECDSA is not secure at all against quantum computing, and in fact would be broken almost instantly with a quantum computer possessing enough qubits. AKA your money gets stolen.

[Severian]

If quantum computing ever becomes an issue, I suspect the loss of bitcoin's keyspace will be among the least of our worries. It would be a very different world.

[Boussac]

If quantum computing ever becomes an issue, I suspect the loss of bitcoin's keyspace will be among the least of our worries. It would be a very different world.

+1
On top of that, my understanding from a convincing demonstration by Bruce Schneier is that a quantum computer, if it is ever built, would have to break the laws of thermodynamics to break bitcoin. Therefore I would not worry to much about quantum computing.

[Foxpup]

If quantum computing ever becomes an issue, I suspect the loss of bitcoin's keyspace will be among the least of our worries. It would be a very different world.

+1
On top of that, my understanding from a convincing demonstration by Bruce Schneier is that a quantum computer, if it is ever built, would have to break the laws of thermodynamics to break bitcoin. Therefore I would not worry to much about quantum computing.

The demonstration you're referring to relates to the impossibility of brute-forcing large keyspaces. Shor's algorithm is useful specifically because it is not a brute-force solution. (Grover's algorithm isn't a brute-force solution either, but only reduces the effective search space by a square root, so can be countered by simply doubling the key size).

[Ivica]

Why would you target bitcoin wallets with quantum computer.
It would be much more fun to break into actual banks and steal much more real money.

As someone said before, it would be a very different world.

[Etlase2]

banks don't leave public keys lying around that give access to tens or hundreds of thousands of dollars

[Boussac]

If quantum computing ever becomes an issue, I suspect the loss of bitcoin's keyspace will be among the least of our worries. It would be a very different world.

+1
On top of that, my understanding from a convincing demonstration by Bruce Schneier is that a quantum computer, if it is ever built, would have to break the laws of thermodynamics to break bitcoin. Therefore I would not worry to much about quantum computing.

The demonstration you're referring to relates to the impossibility of brute-forcing large keyspaces. Shor's algorithm is useful specifically because it is not a brute-force solution. (Grover's algorithm isn't a brute-force solution either, but only reduces the effective search space by a square root, so can be countered by simply doubling the key size).

You are mistaken in believing that Shor's algorithm is relevant.
ECDSA does NOT rely on the difficulty of prime integer factorisation (for which Shor is effective) but on the difficulty of finding the discrete logarithm (for which Shor is irrelevant)..

[Etlase2]

You are mistaken in believing that Shor's algorithm is relevant.
ECDSA does NOT rely on the difficulty of prime integer factorisation (for which Shor is effective) but on the difficulty of finding the discrete logarithm (for which Shor is irrelevant)..

perhaps you should do some googling before spouting claims: http://arxiv.org/abs/quant-ph/0301141

"It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits."

it's easier than integer factorization

[DeathAndTaxes]

If quantum computing ever becomes an issue, I suspect the loss of bitcoin's keyspace will be among the least of our worries. It would be a very different world.

+1
On top of that, my understanding from a convincing demonstration by Bruce Schneier is that a quantum computer, if it is ever built, would have to break the laws of thermodynamics to break bitcoin. Therefore I would not worry to much about quantum computing.

The demonstration you're referring to relates to the impossibility of brute-forcing large keyspaces. Shor's algorithm is useful specifically because it is not a brute-force solution. (Grover's algorithm isn't a brute-force solution either, but only reduces the effective search space by a square root, so can be countered by simply doubling the key size).

You are mistaken in believing that Shor's algorithm is relevant.
ECDSA does NOT rely on the difficulty of prime integer factorisation (for which Shor is effective) but on the difficulty of finding the discrete logarithm (for which Shor is irrelevant)..

Bruce Schneier estimate on energy required to brute force 256 bit keys (one I have quoted extensively) refers to "classical" computing. Schneier didn't state that quantum computing using Grover or Shor algorithms would violate the laws of thermno-dynamics.  The reason why is that it effectively reduces the effective keyspace by the square of the key size and those smaller keys can (at least in theory) be searched.

I would point out that:
a) 2^128 is still an incredibly large keyspace so it isn't like Quantum computing is an "auto-win" for instantly stealing all the coinz.
b) It is unknown if quantum computers will ever be able COST EFFECTIVELY attack 256 bit keys.
c) It is far cheaper to use larger keys than it is to build larger quantum computers.
d) If the risk of Quantum computing becomes large enough the protocol could be extend to incorporate new address types.

We can say a classical brute force of 256 bit number is impossible (based on our current understanding of physics).  However while quantum computing attack on Bitcoin in the near term is highly unlikely it isn't impossible from a thermodynamic point of view.

[DeathAndTaxes]

A hacker with a quantum computer could just listen for incoming transactions, that have not been added to the blockchain yet, and attempt his attack. 10 mins should be enough.

So how would this attack happen?  We can simulate that you have a perfect quantum computer which can break 256 bit public/private keypairs at negigible cost by me simply giving you the private key.  Say we experimented with a scenario where I submit a tx to the network and 1 second later give you the private key.  While you could attempt a race the fact that my tx has a headstart would mean your chance of inclusion in a block is very unlikely.  If you were delayed by more than a few seconds the chance of inclusion in a block drops to essentially zero.

If "quantum key snooping" became a problem there are plenty of countermeasures.   One option would be to implement new addresses which are quantum resistant but that likely would take some time.  Another option would be larger keysize (i.e. going to 512 bit private keys would make those 256bit quantum computers completely useless). An interim solution could be the use of "security brokers".  I submit an encrypted transaction to a security broker who decrypts it, ensures his fee is included, and re-encrypts it with the public keys of miners who subscribe to this broker's service.  The broker them simultaneously transmits it to all miners. Before someone decries "centralization" there is no real barrier to entry so one could imagine multiple competing security brokers.  Also it is unlikely this would be needed on low value (sum of all outputs including change) transactions.  The opportunity cost of a 256 qubit quantum computer is a little to high to be stealing $20 txs.

Now where quantum computing "could" (and we likely are decades away) be useful is in mining.  However even if quantum computers large enough to be useful in mining could be built it still remains unknown if they would be cost effective.

[Come-from-Beyond]

A hacker with a quantum computer could just listen for incoming transactions, that have not been added to the blockchain yet, and attempt his attack. 10 mins should be enough.

So how would this attack happen?  We can simulate that you have a perfect quantum computer which can break 256 bit public/private keypairs at negigible cost by me simply giving you the private key.  Say we experimented with a scenario where I submit a tx to the network and 1 second later give you the private key.  While you could attempt a race the fact that my tx has a headstart would mean your chance of inclusion in a block is very unlikely.  If you were delayed by more than a few seconds the chance of inclusion in a block drops to essentially zero.

1. Get a private key.
2. Create a transaction to transfer coins to your own wallet.
3. Find a nonce to solve the block (imagine that I'm a pool owner).

Legit transaction can still circulate in the network but I already got the coins.

[DeathAndTaxes]

The above assumes you can out mine the entire rest of the bitcoin network.

How much hashing power you have? 0.1% of the network?  Your chances are 0.1%.  In reality your chances are even less because while Quantum computer can solve problems magnitudes after the time is still not zero.  That time delay counterfeits some of the hashing power.  If the avg solution time is 5 minutes then the odds of success (find private key, create double spend, solve block first) are more like 0.05%.

I don't think using a pool will work for more than a token number of attacks.  The attack is very obvious (much like a 51%) and you would see miners leave in droves.  Even greedy, selfish miners would leave under the fear that you could just as easily steal their funds.

Still you are right, a private miner with a huge amount of hashing power AND a hugely expensive quantum computer with a couple thousand qubits could pull it off.   Of course "security brokers" would defeat all the sunk cost and breaking tx into multiple smaller tx would lower the reward on that cost (at the expense of more blockchain size).

Still my guess (just a guess) is even those kinds of countermeasures probably won't be necessary unless some massive quantum computing breakthrough catches the entire world by surprise.  The bitcoin protocol could be extended to support new address types based on "post-quantum" encryption algorithms.

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

[Etlase2]

D&T for christ's sake man, you are the biggest bitcoin apologizer in the universe.

"Here let me start with some ridiculous best-case scenarios that let me apologize for bitcoin because that's what I do!"

You claim the attack is obvious, but miners aren't even aware (or weren't for the longest time, perhaps pool ops operate slightly more above board now) when their own pool solves a block, what the makes you think that they would know that the pool op is stealing txes with a quantum computer? That's right, nothing but apologism. This also makes for no account of the likely tens of thousands of public keys that are sitting right there in the block chain waiting to be stolen anyway. Coinbase transactions are in the pubkey format if I'm not mistaken. All of those coins that Satoshi "lost" according to apologists could be easily taken.

Will there be counter-measures? Sure. Will some coins get stolen? Most likely. Is it the end of the world? Probably not. But being as dishonest as possible is not the best way to discuss the issue. Additionally, while post-QC algorithms exist, the most data-friendly one, NTRU, requires 3kbit pubkeys and 6kbit signatures for the equivalent 128-bit security that bitcoin currently employs.

[Gavin Andresen]

From "Operator Imprecision and Scaling of Shor's Algorithm" (2008):

In this paper, we show that the polynomial scaling of SA (Shor's algorithm) is destroyed by input errors to the QFT part of the algorithm. We also show that Quantum Error Correcting Codes (QECC) are not capable of suppressing errors due to operator imprecision and that propagation of operator precision errors is sufficient to severely degrade the effectiveness of SA. Additionally we show that operator imprecision in the error correction circuit for the Calderbank-Shor-Steane QECC is mathematically equivalent to decoherence on every physical qubit in a register. We conclude that, because of the effect of operator precision errors, it is likely that physically realizable quantum computers will be capable of factoring integers no more efficiently than classical computers.

I don't see any published rebuttals in a quick Google Scholar search. Maybe there will be a breakthrough (or already has been... any QC wizards listening here?) in handling the fuzziness of quantum calculations as you scale up the number of qbits, but 256-bit ECDSA looks pretty darn secure to me right now.

[HostFat]

http://www.technologyreview.com/news/429429/the-cia-and-jeff-bezos-bet-on-quantum-computing/
They are still betting on it