Topic: 512-qubit Quantum Computer acquired, is bitcoin doomed? (Read 12209 times)

This is basically a science fiction entertainment for those that have too much free time. No, SHA256 is still safe, and if it cracked, the banking system would collapse as well since everything is running under SHA256 those days, from ATMs to electronic payment systems that each bank has implemented for their internet transactions, Paypal would get hit hard as well.

the problem i could see, if they don't  disclose the release of a possible working machine, and keeps it secret, this could be a real issue

for those who are too busy/lazy to read D&T's statement, my interpretation is:

If QC starts to look like a threat to Bitcoin over the coming decades, a hardfork could be done into a new set of software and blockchain, that is QC proof. Basically a migration.

The only thing is that this migration has to be done early enough to prevent an (QC proof) altcoin from taking over. 

Here is a great exchange from a "mass storage and other technical stuff" related email list that I subscribe to discussing this IBM breakthrough:

First were the questions:


Then the reply to the questions:


Plus a follow on posting:

Nice article.
I think the Skynet robots will keep using Bitoins after they have destroyed the human race, because they will think it's perfect. I don't see any problem for Bitcoin here. Chill.

This just means that the news is useless. They haven't figured out a 'working quantum computer'. How can you say that something is working if it isn't stable for longer than 15 seconds?
I wouldn't worry about QComputers right now at the moment. Maybe in the future we will have to consider changing algorithms.

"There is as yet insufficient data for a meaningful answer."

IBM reports it works well for almost 15 seconds before bursting into a ball of flames. They expect great results as soon as they work out a way to bury it in the core of the ice planet Neptune.

I like how you stopped posting at 666.

But hydrogen cars are already operational in Germany.
They even produce solid hydrogen now.
I think it might catch up in the next decade as some countries like Japan or European countries will want to get away from oil.

Seems like the appropriate thread for this:

http://www.eetimes.com/document.asp?doc_id=1326468&_mc=NL_EET_EDT_EET_daily_20150429&cid=NL_EET_EDT_EET_daily_20150429&elq=a59559bfb7664cde842c7b2bb9e68b8c&elqCampaignId=22769&elqaid=25618&elqat=1&elqTrackId=6252292228f14224804cfbfa4bed4c75

No need to nuke anyone.  Just blow up some nukes in space, and have the beautiful EMP burn all technology alive.  Then, we won't have to worry about any form of hacking for many years to come!

Whow, he makes Iranian nuclear bombs look like the last straw of hope for the human race

No chance.  I don't see the encryption on bitcoin being beaten in our lifetimes, or that of our children's.  Maybe in the very late future.  But if bitcion is doomed, EVERY SINGLE secure process on the internet is too.

To summarize, the OP is wrong. Bitcoin is not doomed because 256 bit keys are beyond brute force using anything that can be manufactured and we could always fork Bitcoin to 512 which is beyond beyond brute force but that will create a blockchain requiring a hard drive the size of Chevy van. lol

That's a bit reassuring !

One thing I have pointed out in the past (and likely will need to continue to point out for a very long time ) is that DWAVE's system implements (or it stated to implement there is some controversy over exact what is happening) quantum annealing algorithm which while it does (or may) have some quantum properties is not the same thing as a general purpose quantum computer.

To attack public encryption requires a general purpose quantum computer (QPQC) capable of implementing Shor's algorithm (or one built to only implement ONLY Shor's algorithm, a quantum "ASIC" if you will).  Even if DWAVE's computer was a quadrillion qubits it would be absolutely useless for attacking public encryption.  

The global recognition for successfully factoring larger numbers using a GPQC and Shor's algorithm is a pretty big deal.  To date nobody publicly has shown the ability to factor numbers larger than 143 (an 8 bit number).  Even factoring 32 bit numbers at commercially viable speeds would probably mean we are decades away from being able to break 256 bit ECC keys but we aren't even close to that.  While QC is powerful in theory, practical progress has also been agonizingly slow:

2001
First successful demonstration of Shor's algorithm.
Computer size:  7 qubits
Number factored: 15 (into the factors 5 & 3)
Equivelent RSA keysize: 4 bit

2011
First successful factorization of a three digit number (143)
Computer size:  8 qubits (actually 4 bits using an iterative process)
Number factored: 143 (into the factors 11 & 13)
Equivelent RSA keysize: 8 bit

So the bit strength of "encryption" (I use this term loosely because one could crack 8 bit "encryption" with paper and pencil) that can be broken using QC has gone from 4 bit to 8 bit after a decade of research.  Even if this can scale, at the current growth rate breaking Bitcoin would be more than a lifetime away.  ECDSA is a little different than RSA in that it doesn't involve factoring large numbers and instead uses the properties of elliptical curves but both can be broken using Shor's algorithm.  In general ECC requires smaller keys than RSA for an equivelent level of security.  To achieve 128 bit key strength (which is considered beyond brute force for classical computing) using ECDSA requires 256 bits, but using RSA requires 3,072 bits. Bitcoin could use RSA and be just as secure however transactions would be up 12x as large.  

Still both RSA and ECC in theory can be broken faster than what is possible with classical computing by using a large enough (and fast enough) quantum computer implementing Shor's algorithm. I have only found one paper to date which compares the qubit cost of implementing Shor's algorithm against both RSA & ECC.

http://arxiv.org/pdf/quantph/0301141.pdf  I emphasis of relevant portions is by me.  

So we are looking at a general purpose quantum computer which needs at least 1,800 logical qubits.  Nobody (AFAIK) has even done research on the amount of error correction required for a commercial general purpose quantum computer (because none exists) but lets take the authors estimate of "dozens of physical qubits per logical qubit" and use 24x as a low end.   This would mean (1,800 * 24) a system with 43,200 or more physical qubits.  To put that into perspective the largest (AFAIK please correct me if you find a larger example) general purpose quantum computer capable of implementing Shor's algorithm is ... 7 qubits so we aren't eve in striking range yet.

Still QC "may" may break 256 bit ECDSA within our lifetime, so should be looking to future solutions.  There are a couple things which can be done to improve the quantum security of the Bitcoin network.  The simplest change would be to implement a new address type which uses a larger ECC curve.  While larger ECDSA keys can sitll be broken they do increase the qubit requirements, moving to 512 bit keys doubles the required qubits and 1,024 will quadruple them.  If GPQC proves viable this would buy the network some time for a longer term solution.  I don't even know if 1,024 bit ECC is supported by major libraries, outside of quantum computing there is little need for 1,024 bit ECC because even 256 bit ECC is considered beyond brute force. 

A longer term and more complex solution would be moving to an address scheme based on a post-quantum algorithms (http://en.wikipedia.org/wiki/Post-quantum_cryptography).  These systems generally have no wide spread deployment so there may be unknown security issues so I am not advocating a change anytime soon just pointing out there are algorithms which can be used to protect the network even if large GPQC become available.   The largest obstacle to these post quantum systems is generally they involve much much larger public keys.  The bandwidth and storage requirements of Bitcoin are highly correlated to the size of the public key and we are talking about public keys in the tens of kilobytes (notice the plural) so transactions and blocks would be easily a hundred times larger.   Now it is entirely possible that Moore's law will mitigate this somewhat,  and stat using a 50,000 byte key in 2048 will be no more of a challenge then using a 256 bit key today.

For those who are interested in post quantum cryptography one implementation (which has open source implementation) is NTRU.  It is likely far too early to consider any such implementation in a production system but implementing a patched version of bitcoin on testnet which incorporates NTRU would be an interesting project.

I'd like to see papers about that

I will bring my linked blog into play here on my Theory of Everything.

Quantum superposition is due to the emergent derivation that matter is relative to itself.

When we measure something, i.e. form coherence, it is only valid in our local coherent delusion because it is always aliasing error on the universal scale.

Traditional CMOS electronics constrain quantum effects to local measurement components, i.e. transistors so the potential increased global degrees-of-freedom due to entanglement across the entire circuit are destroyed, i.e. made coherent by quantizing each logic gate locally within the circuit. In other words, pre-mature coherence.

A black hole is superpositioned matter. If we could superposition ourselves, we wouldn't be perceivable (not coherent) in a local reality.

Entanglement doesn't mean two quantum particles are joined across great distance, rather that can be an aliasing error effect that we perceive in the local 3D context. It means that quantum particles (actually waves) can interact on universal global scale (i.e. distance is irrelevant). You see in the superpositioned universe, there are infinite dimensions thus 3D is just a local delusion. When I use the terms local and global I am not referring to distance in 3D, rather to limited versus unlimited perspectives (aka samples or measurements). In superpositioned matter there are infinite perspectives thus no one single coherent realization and thus the black hole-- maximally disordered ether. Now you know what anti-matter is.

This isn't hand waving. This is the only description of the universe that can be logically globally coherent. I discussed these concepts in another thread and another one.

So the challenge of quantum computing is to build a circuit that allows computation to proceed in the maximally disordered ether, while quantizing only the result of the computation.

The arguable criticism of the D-Wave system is it may not be enabling entanglement between the qubits, i.e. they are just akin to supercooled transistors which locally have two (finite) superpositioned states each.

Edit: many details omitted for brevity.

That's a bit scary ! :/