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

[Revalin]

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.

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.

[1714118773]

1714118773

[1714118773]

1714118773

[Steve]

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.

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.

[Revalin]

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. 

[MatthewLM]

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

[Revalin]

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.

[Steve]

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.

[Revalin]

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

[Steve]

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

[Revalin]

The signature algorithm only affects the security of the addresses that use it.

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.

as opposed to waiting until it's an urgent situation and a new algorithm is needed asap

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.

(haste makes waste)

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.