Topic: First simple factorization solved by quantum computing (Read 2673 times)

I've only read "The Fabric of Reality" by Deutsch, so I have just a rough understanding, but how does this prove Everett's interpretation?

thumbs up!

With several generations of die-shrunk, parallelized, and optimized ASICS in between.

Even if it can't be used for cracking addresses, is this the next step in mining after ASICs?

+1

I think I've said it before, but I'll say it again: I'll start to worry when there is a quantum computer that can factor 64-bit numbers faster than non-quantum computers. I bet that is at least 20 years away...

I'm in my 30s, and I consider myself an optimist about technology.  And I still don't think that I have to worry about anyone creating a quantum circuit for SHA or ECDSA in my lifetime.

There are generic algorithms (Grover's, for example) that operate on quantum computers that can "solve" arbitrary circuits.  In principle, that means that anything that we can figure out how to build can be solved in roughly the square root of the amount of time it would take in a classical computer.

The catch is, of course, that SHA and ECDSA don't really lend themselves well to circuit design.  We can't really even build a classical circuit that implements SHA-256 without iteration and memory, and we don't even blink about putting billions and billions of transistors on a chip these days.

Meanwhile, state of the art in reversible quantum circuits is currently something like 4 qubits and 5 loops, and to be quite honest, we aren't even 100% sure that these devices are even quantum computation devices (but the early signs are encouraging).

Classical computing has a 50 year head start, but development in quantum computing will likely be faster (we already know how to miniaturize, and we have computer aided design and manufacturing tools).  But not so fast that we won't see problems coming decades in advance and have plenty of chances to switch algorithms.

You can increase the pool of 100 addresses to much larger numbers.

I mainly re-use addresses because I know my backup wallets only have 100 keys in them, and if I use too many addresses it makes it necessary to do backups too frequently.

Dips on the day shift!

ok, ok ..
PS: I did see many "quantum-resistant" algos on arxiv, I looked over a bit, still, I cant swear I am sure they are 100% bulletproof, I never imagined we are so close of this threshold.

There was a greate piece on phys.org recently about a (proposed) experiment where past and future qubits interacted via the vacuum field:

http://phys.org/news/2012-07-qubits-interact-past-future-entanglement.html

I hope the qubitcoiners of the future send us a message on any modifications required to the bitcoin protocol via this technique. We just have to start listening to any entangled particles we coming across really carefully.

See https://gist.github.com/2355445 .  Specifically, the section that starts "Example: re-define OP_NOP1 to be OP_Q_CHECKSIGVERIFY, using a quantum-resistant digital signature algorithm."

Well, an attacker could attack a given bitcoin address just when it is spent.   He would just listen to non yet-validated transactions, and immediately produce a new, competing one for each of them.  Not all of them would be validated (it would be kind of random, my guess is a 50/50 chance), but some will definitely be.

The only way to keep your bitcoins safe would be not to spend them.  Ever.   And what good is a bitcoin you can't spend??

Well, it's time to start planning a graceful transition from bitcoin to qubitcoin. 

Bitcoin has an additional layer of security.   Shor's algorithm requires the public key to be known to solve for the private key (an unknown).   

Bitcoin addresses are hashes (with checksum) of the public key.   For example even with a 256 qubit quantum computer, properly programmed to apply Short's algorithm against ECDSA (using the specific rare curve that Bitcoin uses) you couldn't determine the private key of this address:

14dsL2KKeHhMFYqTkATz8cpQWs5pqqRVFp


To do that you would need the public key and that is unknown until the owner of the private key spends the coins.  At that point the public key becomes part of the blockchain and is trivial to lookup.  The only addresses which would be vulnerable are ones where funds have been received, spent, and then more funds received to the same address.

It is currently recommend to use an address for a single use.   There is no need to re-use addresses but many users do.  If (and we likely are decades and decades away) Quantum computing gets powerful enough to apply shor's algorithm to 256 bit numbers one can be quantum resistant by ensuring they never use addresses more than once.   Wallets could easily be programmed to warn users of actions which would leave funds vulnerable, even auto-sweeping funds received at an address where the private key is known.

It will require some changes in how individuals and companies use the network but it wouldn't fundamentally break the network.  The largest change would be processes where periodic payments result in address re-use.  Some examples which would need be converted to dynamic addresses would be tipping or donation address,  a single payout address for pool mining, vanity addresses,  a debtor making multiple interest payments to a single address.   None of those are particularly difficult.  They could be changed today through the use of APIs or bulk loading addresses.

Wow I actually just watched a documentary that had quantum computers in it a few days ago and the entire time I was thinking of bitcoin lol

Damn it.

Well, the bright side is that bitcoin thus gives an other big incentive to develop quantum computing.

Yep, Shor's Algorithm can be applied to elliptic curve cryptography. I'm not sure if this applies specifically to the variant that Bitcoin uses however.

http://arxiv.org/abs/quant-ph/0301141
http://www.mathcs.richmond.edu/~jad/summerwork/ellipticcurvequantum.pdf

And more...

https://www.google.com/search?q=shor's+algorithm+elliptic+curve

This has been discussed in the past on this forum as well.

https://bitcointalksearch.org/topic/128-bit-quantum-computer-commercially-available-qubitcoin-coming-soon-54542

For interested parties, MWI is the Many Worlds Interpretation of Quantum Mechanics and basically states that all possible events occur in parallel worlds. See http://plato.stanford.edu/entries/qm-manyworlds/.

I have no idea. But thats one good looking processor

Wow, I think this was David Deutsch proposed proof for MWI of QM.