Topic: 128-bit Quantum Computer Commercially Available - Qubitcoin coming soon? (Read 7960 times)

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.

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.

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

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.

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.

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

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. 

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.

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.

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.

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

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

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

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

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.

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.

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. 

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.

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

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.