First simple factorization solved by quantum computing

[Dusty]

Physicists demonstrate that 15=3x5 about half of the time

The device in the photomicrograph was used to run the first solid-state demonstration of Shor's algorithm. It is made up of four phase qubits and five superconducting resonators, for a total of nine engineered quantum elements. The quantum processor measures one-quarter inch square


[...]
"Fifteen is a small number, but what's important is we've shown that we can run a version of Peter Shor's prime factoring algorithm on a solid state quantum processor. This is really exciting and has never been done before," said Erik Lucero, the paper's lead author. Now a postdoctoral researcher in experimental quantum computing at IBM, Lucero was a doctoral student in physics at UCSB when the research was conducted and the paper was written. "What is important is that the concepts used in factoring this small number remain the same when factoring much larger numbers," said Andrew Cleland, a professor of physics at UCSB and a collaborator on the experiment. "We just need to scale up the size of this processor to something much larger. This won't be easy, but the path forward is clear."


While this is a far cry to begin to worry for the decryption of our private bitcoin keys, it nonetheless is a notable starting point.

Anyone has in depth information on how and if this kind of technology could evolve to the point to crack all existing encryption schemes?

[grondilu]

Could Shor's algorithm be applied to crack ECDSA?  I'm not sure.

Shor's algo is about factoring large prime integers.  In ECDSA there is an additional difficulty, as the algebra is not about integers but points of an elliptc curve.  Has anyone shown that solving the former permits solving the latter?

[beekeeper]

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

[P4man]

I have no idea. But thats one good looking processor

[garyrowe]

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

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

[kaii]

Could Shor's algorithm be applied to crack ECDSA?  I'm not sure.

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://bitcointalk.org/index.php?topic=54542.0

[grondilu]

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

Damn it.

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

[TYDIRocks]

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

[DeathAndTaxes]

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.

[becoin]

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

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

[grondilu]

Bitcoin has an additional layer of security.

Shor's algorithm requires the public key.   Bitcoin addresses are hashed of the public key.   When you spend coins the public key is included in the tx but until spent the public key remains unknown.  The only addresses which would be vulnerable are ones where funds have been received, spent, and then more funds received to the same address.

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??

[Gavin Andresen]

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

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

[jim618]

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.

[beekeeper]

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

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

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.

[runeks]

It is currently recommend to use an address for a single use.   There is no need to re-use addresses but many users do.

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.

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.

Dips on the day shift!

[Mushoz]

It is currently recommend to use an address for a single use.   There is no need to re-use addresses but many users do.

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.

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.

Dips on the day shift!

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

[kjj]

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.

[Gavin Andresen]

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.

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

[cbeast]

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

[BitBlitz]

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

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