Bitcoin Forum
December 07, 2016, 08:41:12 AM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: « 1 2 [3]  All
  Print  
Author Topic: 128-bit Quantum Computer Commercially Available - Qubitcoin coming soon?  (Read 7226 times)
Revalin
Hero Member
*****
Offline Offline

Activity: 728


165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g


View Profile
December 15, 2011, 08:25:08 PM
 #41

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.

      War is God's way of teaching Americans geography.  --Ambrose Bierce
Bitcoin is the Devil's way of teaching geeks economics.  --Revalin 165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g
1481100072
Hero Member
*
Offline Offline

Posts: 1481100072

View Profile Personal Message (Offline)

Ignore
1481100072
Reply with quote  #2

1481100072
Report to moderator
1481100072
Hero Member
*
Offline Offline

Posts: 1481100072

View Profile Personal Message (Offline)

Ignore
1481100072
Reply with quote  #2

1481100072
Report to moderator
1481100072
Hero Member
*
Offline Offline

Posts: 1481100072

View Profile Personal Message (Offline)

Ignore
1481100072
Reply with quote  #2

1481100072
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
Steve
Hero Member
*****
Offline Offline

Activity: 868



View Profile WWW
December 15, 2011, 09:33:06 PM
 #42

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.

(gasteve on IRC) Does your website accept cash? https://bitpay.com
Revalin
Hero Member
*****
Offline Offline

Activity: 728


165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g


View Profile
December 15, 2011, 09:46:07 PM
 #43

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

      War is God's way of teaching Americans geography.  --Ambrose Bierce
Bitcoin is the Devil's way of teaching geeks economics.  --Revalin 165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g
MatthewLM
Legendary
*
Offline Offline

Activity: 1092



View Profile WWW
December 15, 2011, 09:46:41 PM
 #44

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

Bitcoin Extra Wallet | Peercoin Android Wallet
BTC: 1D5A1q5d192j5gYuWiP3CSE5fcaaZxe6E9  PPC: PH7fVn1Xs7nkUFmdwCX2ZRYfLPCSwGxAq9
Revalin
Hero Member
*****
Offline Offline

Activity: 728


165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g


View Profile
December 15, 2011, 10:34:54 PM
 #45

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.

      War is God's way of teaching Americans geography.  --Ambrose Bierce
Bitcoin is the Devil's way of teaching geeks economics.  --Revalin 165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g
Steve
Hero Member
*****
Offline Offline

Activity: 868



View Profile WWW
December 15, 2011, 10:58:30 PM
 #46

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.

(gasteve on IRC) Does your website accept cash? https://bitpay.com
Revalin
Hero Member
*****
Offline Offline

Activity: 728


165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g


View Profile
December 15, 2011, 11:13:52 PM
 #47

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

      War is God's way of teaching Americans geography.  --Ambrose Bierce
Bitcoin is the Devil's way of teaching geeks economics.  --Revalin 165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g
Steve
Hero Member
*****
Offline Offline

Activity: 868



View Profile WWW
December 16, 2011, 12:15:17 AM
 #48

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

(gasteve on IRC) Does your website accept cash? https://bitpay.com
Revalin
Hero Member
*****
Offline Offline

Activity: 728


165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g


View Profile
December 16, 2011, 01:41:05 AM
 #49

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.


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


Quote
(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.

      War is God's way of teaching Americans geography.  --Ambrose Bierce
Bitcoin is the Devil's way of teaching geeks economics.  --Revalin 165YUuQUWhBz3d27iXKxRiazQnjEtJNG9g
Pages: « 1 2 [3]  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!