Bitcoin Forum

http://www.dwavesys.com/en/products-services.html

Recently, D-Wave Systems unveiled their latest commercial quantum computer with 128 qubit capability. Given the rate at which their expanding the number of qubits available in such systems, how long until we have to worry about private key mining becoming more profitable than hash mining?

Haha using http://en.wikipedia.org/wiki/Shor%27s_algorithm, one can find prime factors in linear time.

Thanks for the link!

The already have a 512 qubit chip:

http://nextbigfuture.com/2011/12/dwave-systems-shows-off-512-qubit.html

But there are still doubts if their computers really are quantum.

That would be fun if it was a scam ;)

Quickly! instal the bitcoin client and start mining!

mine all the coins in 1 day!


could this 10 square foot Black Box really punch a hole in bitcoin?

even if it could bitcoin would just use different encryption.

Change ECDSA to Q_ECDSA.

Looks like a scam, but I may be wrong.  :o

I don't think they have an quantum algorithm to do reverse ECDSA yet. But I could be wrong.

shor's algorithm can be modified to work on elliptic curves.

So how do you program a quantum computer? Using qBASIC?

With quantum operators :)

Lol

"128 qbit capability"!?  The soundcard mining was more believable.

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.

IIRC shor's alogrithm is simply a "speed booster" which when given a public key K can find the private key k magnitudes faster than conventional brute force.  With Bitcoin only the owner of the private key knows the public key.


The other nice thing about Bitcoin is it is unlikely there is any economic value in attacking the network.  If you could out solve the entire rest of the network you likely would make more just being a masive hashing farm than trying to attack it.  The threat of 51% comes from a non-economic attack.  An entity who seeks to double spend not for profit but to destroy Bitcoin.  While a quantum computer might someday help an attacker if it is public available it would also help defenders too.

Finally, a computer capable of running Crysis.

http://financialriskanalytics.weebly.com/1/post/2011/11/is-quantum-computing-a-threat-to-bitcoin.html

 ::) ;D

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

From what I have read.....

A 1024 Qbit computer would take about 1000 years to break a key.  This is much better then the millions of years all of the computers on the planet combined would take so it is revolutionary.  It just does not threaten bitcoin yet.  With the rate of growth in quantum computing, bitcoin will need to be upgraded, and it should be done before five years.  After five years, quantum key breaking may start to enter the relm of possibility for large institutions. 

I don't know if this is true, but would like to note that the public key is known for addresses that have been spent from.

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 (http://arxiv.org/abs/quant-ph/0205095), 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


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

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.

ROFL!

Glad to hear that.

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

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?

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.

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.

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

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. 

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.

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

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

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

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

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.

This is only true for symmetric crypto.  AES-256 will degrade to a 128-bit level of protection, which is plenty for virtually any purpose.

For asymmetric (public key, signing) ciphers the story is grim: it will be possible to break it in about the same number of operations it takes to use it - IE, they will be completely broken.  This is true for RSA, DH and ECC.  Hopefully new algorithms will be discovered in time.

The very best quantum computers are only recently factoring 4-bit numbers, and they're enormous, slow, and very expensive.  The greatest entanglement we've achieved is 14 qbits.

Current technologies aren't scalable, and even with revolutionary technologies this is still a much harder problem than scaling silicon transistors.  I'm not convinced that it's possible.

That said, it's been doubling about every 6 years.  Extrapolating, that means we have 20-30 years to get our act together.

There are already asymmetric algorithms that are believed to be quantum resistant:
http://en.wikipedia.org/wiki/NTRU

My guess is that because such algorithms are relatively new and it does not appear there is an imminent threat to the existing, proven algorithms, they haven't yet seen more widespread adoption.

Correct.  They're doing a lot of things different, and it'll be a while before they're mature enough to be widely trusted.  NIST is saying good things about it, though, so perhaps there's hope.  :)

Question is, how easy would a transition in software be, when new software is needed for security?

When it looks like a break is plausible within ten years, we pick the best available algorithm at that time and release a new a new client that uses it for all new transactions.

When you run the new client for the first time it'll pop up a message that says "you need to forward your coins to a secure address, here's why, [yes | no]".  Publicize it so people with offline wallets get the message.

Then we wait 5-20 years to find out how many people with a high value wallet (the break probably wouldn't be worthwhile for small wallets) live under a rock.  It will be a small but lulzy number.  Since the break will likely be slow there may be time for a few people to rescue their wallets after the first one hits the news.

Then the miners start competing to build overclocked quantum computers to mine the pool of abandoned coins.  After a period of slightly increased inflation, all the lost coins end up back in circulation and life goes on.

Actually, it would probably be a good idea to go ahead and add support for one of these algorithms soon.  There's no reason the network couldn't recognize multiple algorithms concurrently.  The new algorithm would be disabled by default for creating new addresses, but people could enable it and experiment with the alternative algorithm.  This would lay the groundwork necessary to adopt an algorithm in the future once it was widely accepted to be resistant to quantum computing.

"10 years out" isn't really when we choose to do it.  In reality it's just a tradeoff between quantum's speculated future and the maturity of quantum-resistant algorithms.

Now isn't the time: the quantum break is a very long ways out, and the algorithms aren't mature.  Any code we add we have to support forever, and any algorithm with an exploit will end up harming users who freak out about some snakeoil (like the joke that launched this thread) and thought the new signatures were "better".

I do agree that we should do it whenever there's a good, mature algorithm, even if it looks like a quantum break is still past the horizon.  NIST did a good job with AES, they're doing it again with hashes, and I'd expect DSA will be next on the list.  Barring an imminent threat, I'd much rather wait until the available algorithms are put through some serious public scrutiny.  Bad things happen when you move too fast with crypto.

The signature algorithm only affects the security of the addresses that use it.  I guess what I'm saying is: I'd rather see the structure put in place to support multiple signature algorithms sooner rather than later such that it can be well tested with no time pressure…as opposed to waiting until it's an urgent situation and a new algorithm is needed asap (haste makes waste).  Also, there's the consideration that it will take significant time for the network to be upgraded to recognize alternative algorithms.

It affects the people you send coins TO.  It also increases the code complexity of all Bitcoin clients, which will ALL need to support the new code, in perpetuity.  Optimistically, 50, 100, 200 years...  Adding alternatives has to be done very carefully.  We don't want this to turn into PGP.



Quantum computers capable of breaking ECDSA are a long, long way out.  This isn't going to sneak up on us.  We won't know if it's even possible to build such a machine for ten years.

Now IS the time to start working on the problem, but the work needs to be done in the wider crypto community to develop and test the techniques for quantum-resistance.  Good crypto algorithms take a long time to bake.

The actual technical work to implement it is very easy once we settle on the signature algorithm.  We can do it in a couple days and have it tested in a week or two.



That axiom leads me to the opposite conclusion:  It's very easy for us to make the change to the code, but the blockchain is forever.  We should not make format changes lightly.  A proof of concept on the testnet would be fine just to check for unforseen problems, but fooling with the production net now would be seriously premature.

The real work is in creating better algorithms, and it's not being ignored.

As for Bitcoin's security, there are any of a dozen things that are much more urgent to work on.  Just off the top of my head: key handling; cold storage; trust management; code auditing; refactoring.