128-bit Quantum Computer Commercially Available - Qubitcoin coming soon?

[Gavin Andresen]

I spent some time today looking again at the state of quantum computing: I'm still not worried.

The D-Wave system is not a general-purpose quantum computer; it is pretty specialized for solving certain problems (I'm reasonably certain cracking ECDSA encryption is not one of the problems it would be good at, but I am definitely NOT a quantum crypto expert).

Skimming the research, it looks like you'd need a specially-constructed quantum computer with 515 qbits and over 100million quantum gates, running more than 16 million quantum operations to crack Bitcoin's 256-bit ECDSA private keys using Shor's algorithm.

There's was a good reality-check article in the New York Times just last week:
   http://www.nytimes.com/2011/12/06/science/scott-aaronson-quantum-computing-promises-new-insights.html

Unfortunately, while small quantum computations have already been demonstrated in the lab, they typically fall apart after only a few dozen operations. That’s why one of the most-celebrated quantum computations to date has been to factor 15 into 3 times 5 — with high statistical confidence! The problem is decoherence: basically, stray interactions that intrude prematurely on the computer’s fragile quantum state, “collapsing” it like a soufflé. In theory, it ought to be possible to reduce decoherence to a level where error-correction techniques could render its remaining effects insignificant. But experimentalists seem nowhere near that critical level yet.

I've said it before:  I'll start to worry when quantum computers can factor 64-bit numbers.

[ShadowOfHarbringer]

Hmm, dwave again...
They tricked us last time, i highly doubt this is the real deal..

Actually last time they themselves didn't know if it was quantum (!!) or not, are they sure this time ?

Or did they also invent Quantum Trolling Technology™ ?

[BTCurious]

Hmm, dwave again...
They tricked us last time, i highly doubt this is the real deal..

Actually last time they themselves didn't know if it was quantum (!!) or not, are they sure this time ?

Or did they also invent Quantum Trolling Technology™ ?

They can't be sure, until their brain-particles interact with the troll-quantum-bits, splitting our subjective view into one of the multiworlds, yet losing the quantum-troll-decoherence in the process.

[Andrew Vorobyov]

ROFL!

Lol
soundcard mining

[finway]

I spent some time today looking again at the state of quantum computing: I'm still not worried.

The D-Wave system is not a general-purpose quantum computer; it is pretty specialized for solving certain problems (I'm reasonably certain cracking ECDSA encryption is not one of the problems it would be good at, but I am definitely NOT a quantum crypto expert).

Skimming the research, it looks like you'd need a specially-constructed quantum computer with 515 qbits and over 100million quantum gates, running more than 16 million quantum operations to crack Bitcoin's 256-bit ECDSA private keys using Shor's algorithm.

There's was a good reality-check article in the New York Times just last week:
   http://www.nytimes.com/2011/12/06/science/scott-aaronson-quantum-computing-promises-new-insights.html

Unfortunately, while small quantum computations have already been demonstrated in the lab, they typically fall apart after only a few dozen operations. That’s why one of the most-celebrated quantum computations to date has been to factor 15 into 3 times 5 — with high statistical confidence! The problem is decoherence: basically, stray interactions that intrude prematurely on the computer’s fragile quantum state, “collapsing” it like a soufflé. In theory, it ought to be possible to reduce decoherence to a level where error-correction techniques could render its remaining effects insignificant. But experimentalists seem nowhere near that critical level yet.

I've said it before:  I'll start to worry when quantum computers can factor 64-bit numbers.

Glad to hear that.

[Matthew N. Wright]

I spent some time today looking again at the state of quantum computing: I'm still not worried.

The D-Wave system is not a general-purpose quantum computer; it is pretty specialized for solving certain problems (I'm reasonably certain cracking ECDSA encryption is not one of the problems it would be good at, but I am definitely NOT a quantum crypto expert).

Skimming the research, it looks like you'd need a specially-constructed quantum computer with 515 qbits and over 100million quantum gates, running more than 16 million quantum operations to crack Bitcoin's 256-bit ECDSA private keys using Shor's algorithm.

There's was a good reality-check article in the New York Times just last week:
   http://www.nytimes.com/2011/12/06/science/scott-aaronson-quantum-computing-promises-new-insights.html

Unfortunately, while small quantum computations have already been demonstrated in the lab, they typically fall apart after only a few dozen operations. That’s why one of the most-celebrated quantum computations to date has been to factor 15 into 3 times 5 — with high statistical confidence! The problem is decoherence: basically, stray interactions that intrude prematurely on the computer’s fragile quantum state, “collapsing” it like a soufflé. In theory, it ought to be possible to reduce decoherence to a level where error-correction techniques could render its remaining effects insignificant. But experimentalists seem nowhere near that critical level yet.

I've said it before:  I'll start to worry when quantum computers can factor 64-bit numbers.

Exactly.

The Future of Quantum Computing - Michiu Kaku
http://www.youtube.com/watch?v=YgFVzOksm4o

"Our most advanced robots have the collective intelligence and wisdom of a mentally challenged lobotomized cockroach. They take about 6 hours to walk across the room."

How to Program a Quantum Computer - Michiu Kaku
http://www.youtube.com/watch?v=rUWfod_8JsM

"Moore's law may begin to expire in the next 10 or so years."

[Steve]

I don't think shor's algorithm helps because the address is a hash of the public key not the actual public key.  Either Satoshi got reallly luck or he was some super genius who saw the threat of quantum computing.  Since the public key is an unknown to the attacker they have no input for shor's algorithm.

Interesting!  From what I've read, I think you're correct.  Shor's algorithm is effective against asymmetric ciphers, not secure hash functions or symmetric ciphers (though Grover's algorithm promises somewhat improved performance in computing hashes and ciphers, but this isn't likely to result in any dramatic, overnight jumps in block computation).  It would be a bit of an inconvenience though…you would always want to spend all bitcoins out of an address exactly once (because you do have to reveal the public key when you spend coins) and then never use that address again.  After spending, since the public key has been revealed, any remaining coins at that address would be at risk (assuming a quantum computer could derive the private key in a timely fashion).

I'm guessing Satoshi was well aware of quantum based algorithms (Shor's has been known for a long time).  Reading up on the application of these algorithms, it doesn't take much to realize that the strategic application of a secure hash function may be effective in mitigating the risk that quantum computing would pose.  Using a hash of the public key has a practical benefit (shorter addresses), but I imagine Shor's was in the back of his mind as well.

[finway]

I don't think shor's algorithm helps because the address is a hash of the public key not the actual public key.  Either Satoshi got reallly luck or he was some super genius who saw the threat of quantum computing.  Since the public key is an unknown to the attacker they have no input for shor's algorithm.

Interesting!  From what I've read, I think you're correct.  Shor's algorithm is effective against asymmetric ciphers, not secure hash functions or symmetric ciphers (though Grover's algorithm promises somewhat improved performance in computing hashes and ciphers, but this isn't likely to result in any dramatic, overnight jumps in block computation).  It would be a bit of an inconvenience though…you would always want to spend all bitcoins out of an address exactly once (because you do have to reveal the public key when you spend coins) and then never use that address again.  After spending, since the public key has been revealed, any remaining coins at that address would be at risk (assuming a quantum computer could derive the private key in a timely fashion).

I'm guessing Satoshi was well aware of quantum based algorithms (Shor's has been known for a long time).  Reading up on the application of these algorithms, it doesn't take much to realize that the strategic application of a secure hash function may be effective in mitigating the risk that quantum computing would pose.  Using a hash of the public key has a practical benefit (shorter addresses), but I imagine Shor's was in the back of his mind as well.

I dont' get it , If the sender don't know the receiver's public key, how can he send money?

[PatrickHarnett]

Also interesting from this corner.  DWave ran a distributed computing project for a long time called Aqua.  It was suspended earlier this year because they had the results they needed in progressing commercialisation of what they were looking at.  I'll wait and see if it really has advantages over conventional linear or parallel computing.

[DeathAndTaxes]

I don't think shor's algorithm helps because the address is a hash of the public key not the actual public key.  Either Satoshi got reallly luck or he was some super genius who saw the threat of quantum computing.  Since the public key is an unknown to the attacker they have no input for shor's algorithm.

Interesting!  From what I've read, I think you're correct.  Shor's algorithm is effective against asymmetric ciphers, not secure hash functions or symmetric ciphers (though Grover's algorithm promises somewhat improved performance in computing hashes and ciphers, but this isn't likely to result in any dramatic, overnight jumps in block computation).  It would be a bit of an inconvenience though…you would always want to spend all bitcoins out of an address exactly once (because you do have to reveal the public key when you spend coins) and then never use that address again.  After spending, since the public key has been revealed, any remaining coins at that address would be at risk (assuming a quantum computer could derive the private key in a timely fashion).

I'm guessing Satoshi was well aware of quantum based algorithms (Shor's has been known for a long time).  Reading up on the application of these algorithms, it doesn't take much to realize that the strategic application of a secure hash function may be effective in mitigating the risk that quantum computing would pose.  Using a hash of the public key has a practical benefit (shorter addresses), but I imagine Shor's was in the back of his mind as well.

It wouldn't be that much of a pain.  Anytime you spend coins you spend all of them and by default the client uses a new address for change.  So by default the "spending" address is empty after a spend. The only limitation would be the inability to re-use an address.  Well more technically re-using an address would leave those funds potentially vulnerable (in a someday when quantum computers are powerful enough hypothetical way) to attack/seizure.

However if that risk evolved we likely would see evolution of the client software to mitigate it.  For example say you have address 123 given to a mining pool and they periodically pay you.  To avoid leaving funds at risk the client could mark that address as vulnerable and auto-sweep funds into a newly generated address thus the amount in the vulnerable address is always small and the the window of vulnerability is equally small.

Even more secure would be to pre-generate addresses and provide them to a periodic payer.  For example you could generate 365 unique payment addresses and send them to your mining pool.  Each day the mining pool uses the next one on the list. 

Before anyone flips out I am not saying such protections are necessary but that the problems isn't "insolvable" even in a future when quantum cryptography is a threat to EC cryptogrpahy.

[DeathAndTaxes]

I don't think shor's algorithm helps because the address is a hash of the public key not the actual public key.  Either Satoshi got reallly luck or he was some super genius who saw the threat of quantum computing.  Since the public key is an unknown to the attacker they have no input for shor's algorithm.

Interesting!  From what I've read, I think you're correct.  Shor's algorithm is effective against asymmetric ciphers, not secure hash functions or symmetric ciphers (though Grover's algorithm promises somewhat improved performance in computing hashes and ciphers, but this isn't likely to result in any dramatic, overnight jumps in block computation).  It would be a bit of an inconvenience though…you would always want to spend all bitcoins out of an address exactly once (because you do have to reveal the public key when you spend coins) and then never use that address again.  After spending, since the public key has been revealed, any remaining coins at that address would be at risk (assuming a quantum computer could derive the private key in a timely fashion).

I'm guessing Satoshi was well aware of quantum based algorithms (Shor's has been known for a long time).  Reading up on the application of these algorithms, it doesn't take much to realize that the strategic application of a secure hash function may be effective in mitigating the risk that quantum computing would pose.  Using a hash of the public key has a practical benefit (shorter addresses), but I imagine Shor's was in the back of his mind as well.

I dont' get it , If the sender don't know the receiver's public key, how can he send money?

You don't send money to the receiver's public key you send it to the receiver's address which is an irreversible hash of the public key (w/ some other alterations like adding a "1" prefix, and including a 32bit checksum).

[Steve]

It wouldn't be that much of a pain.  Anytime you spend coins you spend all of them and by default the client uses a new address for change.  So by default the "spending" address is empty after a spend.

For the sake of clarity (I think you know this, but others might not), when spending, you spend all of the coins in the input transaction, but the address may have other coins sent to it in other transactions.  You could still reuse addresses (i.e. your example of pool payouts), but once you spend out of that address the first time, to be completely safe you would want to spend all of the transactions to that address and then never send any coins to that address again.

[DeathAndTaxes]

It wouldn't be that much of a pain.  Anytime you spend coins you spend all of them and by default the client uses a new address for change.  So by default the "spending" address is empty after a spend.

For the sake of clarity (I think you know this, but others might not), when spending, you spend all of the coins in the input transaction, but the address may have other coins sent to it in other transactions.  You could still reuse addresses (i.e. your example of pool payouts), but once you spend out of that address the first time, to be completely safe you would want to spend all of the transactions to that address and then never send any coins to that address again.

Good point.  I hadn't thought of that. It would require some client modification (and potentially higher fees) but the client could be programmed that when it uses coins from Address A it includes all the input transactions in Address A thus always emptying an address on any spend. 

Might look kinda stupid in the block explorer to see a transaction involving 12 inputs and total of 800 BTC to pay someone 2 BTC and get 798 BTC back as change. 

The better "solution" would be to avoid re-using addresses in the first place.  Take donation address in signature.  You could have smart signatures that each time you receive a donation (or maybe just sizable donations) the signature updates to a new address. 

[Steve]

The more I think about it, the more I believe it must have been a deliberate design goal of Satoshi's to allow the public key to remain private until it's actually used to spend bitcoins.  Even with shortened addresses, it's not hard to imagine inferior designs that might have required the revelation of public keys prior to spending.  Not revealing public keys prior to spending would seem to be the best defense against an attack based on Shor's algorithm.

[Matthew N. Wright]

The more I think about it, the more I believe it must have been a deliberate design goal of Satoshi's to allow the public key to remain private until it's actually used to spend bitcoins.  Even with shortened addresses, it's not hard to imagine inferior designs that might have required the revelation of public keys prior to spending.  Not revealing public keys prior to spending would seem to be the best defense against an attack based on Shor's algorithm.

I was just arguing the other day that we should change the code to allow for registering of addresses at time of creation for some kind of validation to keep from allowing coins to be sent to 'black holes', but I guess I'll stop arguing that now.

[finway]

The more I think about it, the more I believe it must have been a deliberate design goal of Satoshi's to allow the public key to remain private until it's actually used to spend bitcoins.  Even with shortened addresses, it's not hard to imagine inferior designs that might have required the revelation of public keys prior to spending.  Not revealing public keys prior to spending would seem to be the best defense against an attack based on Shor's algorithm.

So using a new address to store bitcoins, is more secure than and old spent one , even if quantum computers born ?

[LightRider]

Also interesting from this corner.  DWave ran a distributed computing project for a long time called Aqua.  It was suspended earlier this year because they had the results they needed in progressing commercialisation of what they were looking at.  I'll wait and see if it really has advantages over conventional linear or parallel computing.

A significant portion of that work was done by members of the Zeitgeist Movement team.

[Steve]

The more I think about it, the more I believe it must have been a deliberate design goal of Satoshi's to allow the public key to remain private until it's actually used to spend bitcoins.  Even with shortened addresses, it's not hard to imagine inferior designs that might have required the revelation of public keys prior to spending.  Not revealing public keys prior to spending would seem to be the best defense against an attack based on Shor's algorithm.

So using a new address to store bitcoins, is more secure than and old spent one , even if quantum computers born ?

Well, first, no one should be concerned about reusing addresses…maybe 20 years from now, but by then, bitcoin would probably also have support for Shor's resistant algorithms for signatures.  But, it is more secure in the sense that to recover a private key to enable spending coins at a given address, one would first have to find the public key corresponding to the bitcoin address (reversing the hash function).  After that, you would then need to derive the private key from that public key.  If you've spent coins out of an address, you've revealed the public key, thereby eliminating the first step.  So, yes, it's technically more secure if you only spend coins out of an address once and never reuse it, but it's hardly something to be concerned about (now or in the foreseeable future).

[kjj]

My (incomplete) understanding of quantum cryptography is that in general quantum attacks have the potential to halve the bit strength of any system, but no more.  As in, a fully capable quantum computer could defeat a 160 bit system in the same time that an equivalent classical computer could break an 80 bit system.

As in, using a classical computer, we expect to be able to beat a 160 bit system in about 2^160 operations.  Attacking the same problem with a quantum computer would only require 2^80 operation.  Note that 2^80 is still insanely huge.

Quantum computing isn't really new, and cryptographers took notice like 20 years ago, so everything we use today (including everything in bitcoin) is still secure in a fully quantum world (which doesn't exist yet, and probably still won't for another 10 to 30 years).

[PatrickHarnett]

Also interesting from this corner.  DWave ran a distributed computing project for a long time called Aqua.  It was suspended earlier this year because they had the results they needed in progressing commercialisation of what they were looking at.  I'll wait and see if it really has advantages over conventional linear or parallel computing.

A significant portion of that work was done by members of the Zeitgeist Movement team.

Yes, 1.4B credits

I contributed 1M credits to the #3 team there before it shut down.  I liked the screensaver, but it slowed the computations down a lot.