BC Systems
Newbie
Offline
Activity: 28


September 04, 2012, 06:01:30 AM 

http://www.reddit.com/r/Bitcoin/comments/zb6qu/first_quantum_chip_announced/c63511qNope! Satoshi was a fucking turbogenius (or more likely, "he" was a team of "normal" geniuses) and built the protocol to be moreor less quantumproof. 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 onetime 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 quantumproof.
3. Wait until the devs update the protocol with some new opcodes to allow nonECDSA 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 quantumsecure. The only way to get them is to generate a RIPE160 collision on your address, which is very, very difficult.

BC Systems VLLC.






Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.


ComefromBeyond
Legendary
Offline
Activity: 1526
Newbie


September 04, 2012, 06:11:09 AM 

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 quantumcomputing "proof" is just a sideeffect which doesn't really work.




Etlase2


September 04, 2012, 07:45:17 AM 

RIPEMD160 is not a onetime 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 nonconsiderations 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


September 04, 2012, 07:56:41 AM 

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
Legendary
Offline
Activity: 1174
educat.fr


September 04, 2012, 09:46:41 AM 

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
Legendary
Online
Activity: 1806


September 04, 2012, 10:06:29 AM 

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 bruteforcing large keyspaces. Shor's algorithm is useful specifically because it is not a bruteforce solution. (Grover's algorithm isn't a bruteforce solution either, but only reduces the effective search space by a square root, so can be countered by simply doubling the key size).




Ivica


September 04, 2012, 10:11:47 AM 

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


September 04, 2012, 10:56:31 AM 

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




Boussac
Legendary
Offline
Activity: 1174
educat.fr


September 04, 2012, 01:13:35 PM 

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 bruteforcing large keyspaces. Shor's algorithm is useful specifically because it is not a bruteforce solution. (Grover's algorithm isn't a bruteforce 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


September 04, 2012, 01:22:40 PM 

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/quantph/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 securitywise equivalent 1024 bit RSA modulus would require about 2000 qubits." it's easier than integer factorization




DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Gerald Davis


September 04, 2012, 01:33:58 PM 

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 bruteforcing large keyspaces. Shor's algorithm is useful specifically because it is not a bruteforce solution. (Grover's algorithm isn't a bruteforce 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 thermnodynamics. 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 "autowin" 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
Donator
Legendary
Offline
Activity: 1218
Gerald Davis


September 04, 2012, 01:40:57 PM 

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 reencrypts 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.




ComefromBeyond
Legendary
Offline
Activity: 1526
Newbie


September 04, 2012, 04:23:05 PM 

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
Donator
Legendary
Offline
Activity: 1218
Gerald Davis


September 04, 2012, 04:30:03 PM 

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 "postquantum" encryption algorithms. http://en.wikipedia.org/wiki/Postquantum_cryptography




Etlase2


September 04, 2012, 06:38:52 PM 

D&T for christ's sake man, you are the biggest bitcoin apologizer in the universe.
"Here let me start with some ridiculous bestcase 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 countermeasures? 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 postQC algorithms exist, the most datafriendly one, NTRU, requires 3kbit pubkeys and 6kbit signatures for the equivalent 128bit security that bitcoin currently employs.




Gavin Andresen
Legendary
Offline
Activity: 1652
Chief Scientist


September 04, 2012, 07:58:27 PM 

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 CalderbankShorSteane 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 256bit ECDSA looks pretty darn secure to me right now.

How often do you get the chance to work on a potentially worldchanging project?



HostFat
Staff
Legendary
Offline
Activity: 2394
I support freedom of choice


October 04, 2012, 05:56:07 PM 





